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

Question

我正在寻求满足使用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更少或更大。

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

Answer 1

约束

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

Answer 2

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

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