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

约束

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

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

现在,让我们假设您的任务如下所示: ((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

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