代码之家 › 专栏 › 技术社区 › wu2g

和/或约束的混合整数线性规划

mixed-integer-programming pulp linear-programming mathematical-optimization python

1

wu2g · 技术社区 · 8 年前

我希望使用纸浆来满足一组约束,但我不确定如何设置变量来实现这一点。

例如,如何为以下约束设置变量:

((x_1 < x_2) AND (x_1 < x_3)) OR ((x_1 > x_2) AND (x_1 > x_3))

变量x_1小于或大于x_2和x_3。

任何帮助都将不胜感激。谢谢

2 回复 | 直到 8 年前

1

4

Erwin Kalvelagen 8 年前

约束

 ((x1 <= x2) AND (x1 <= x3)) OR ((x1 >= x2) AND (x1 >= x3))

只需一个额外的二进制变量即可公式化:

 x1 <= x2 + delta*M
 x1 <= x3 + delta*M
 x1 >= x2 - (1-delta)*M
 x1 >= x3 - (1-delta)*M
 delta in {0,1}

大多数高级解算器都有指标约束,允许我们在没有大M的情况下编写:

 delta = 0 -> x1 <= x2
 delta = 0 -> x1 <= x3
 delta = 1 -> x1 >= x2
 delta = 1 -> x1 >= x3
 delta in {0,1}

2

sascha 8 年前

首先一句话:没有 < 线性规划中的算子。只有 <= . 这意味着:如果你想要严格不等式,你需要添加一些小常数 ε !

现在,让我们假设您的任务如下所示: ((x1<=x2) && (x1<=x3)) || ((x1>x2) && (x1>x3)) ( > 是的逻辑否定 <= 尽管如此,这将使这项工作得以开展)。

我们打电话吧 (x1>x2) = z1 和 (x1>x3) = z2 . 那么这可能是 simplified 收件人: (!z1 || z2) && (z1 || !z2) (我在链接中使用了名称A和B)。

引入两个新的二进制变量 z1, z2
使用基于bigM的公式 like this page 4 要为您的关系创建指标:
- x1 <= x2 + M * z1 其中M是一个大常数; (z1=0) -> x1 <= x2
- x1 <= x3 + M * z2 其中M是另一个大常数; (z2=0) -> x1 <= x3
现在我们需要上述内容: (!z1 | | z2)&&(z1 | |!z2)
- 这基本上是一个 !(z1 xor z2) 在这里 1-(z1 xor z2) (查看上面“简化”链接中的真值表),您可以关注一个非常活跃的Stackoverflow用户 here 线性化 xor
  - 引入另一个二进制变量 z3
  - 添加线性约束
    - z3 <= (1-z1) + (1-z2)
    - z3 >= (1-z1) - (1-z2)
    - z3 >= (1-z2) - (1-z1)
    - z3 <= 2 - (1-z1) - (1-z2)
- z3 现在是 z1 xor z2
- 添加约束: z3 == 0

(上面可能有一些错误,但概念应该没问题。有了手头的代码,你应该能够让它工作)