混合整数线性规划到和/或约束条件

问题描述：

我正在寻求满足使用PuLP的一组约束条件，我并不完全确定如何设置变量来做到这一点。混合整数线性规划到和/或约束条件

例如，我将如何设置为以下约束变量：

((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更少或更大。

任何帮助，将不胜感激。谢谢！

你到目前为止尝试过什么？请发布您的代码（请参阅[如何创建最小，完整和可验证示例]（https://stackoverflow.com/help/mcve）），包括错误消息。 – MrT

答

约束

((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}

在我能够理解这个简单的答案之前，我必须先通读并实施其他答案。这是干净的，并有很大帮助。谢谢！即使LP通常不处理不等式，我猜这可能是正确的一些小的常数值c？例如： x1 + c = c + x2 - （1-delta）M; x1> = c + x3 - （1-delta）M; {0,1}中的 delta – wu2g

答

首先一句话：没有<运营商线性规划。只有<=。这意味着：如果你想要严格的不平等，你需要添加一些小的常量epsilon！

现在让我们假设你的任务是这样的：((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)（看在“简化”上面的链接真值表），你可以遵循一个非常活跃的＃1 -user here来线性化xor：
  - 介绍另一个二进制变量z3
  - 添加线性常量raints
    - 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

（上面可能有一些错误，但概念应该没问题。随着在手的代码，你应该能够使它工作）

这太棒了！所以我们知道z3 =！（z1 XOR z2）。有什么区别（1）引入z3和额外的约束来线性化异或，（2）只添加约束z1 = z2？ – wu2g

混合整数线性规划到和/或约束条件

相关推荐