如何在混合整数规划(MIP)中实现含OR的至少两变量选择约束

要实现你需求的OR逻辑约束，需要引入辅助二进制变量来将逻辑关系转化为线性约束，具体步骤如下：

• 引入辅助二进制变量
  定义三个二进制变量 y1, y2, y3，分别对应三个原约束条件：

  • y1=1 代表 x1+x2+x3+x4 >=2 成立
  • y2=1 代表 x5+x6+x7+x8+x9 >=2 成立
  • y3=1 代表 x10+x11+x12 >=2 成立

• 核心OR逻辑约束
  添加以下约束，保证三个条件中至少有一个成立：

  y1 + y2 + y3 >= 1
  

• 关联辅助变量与原变量
  针对每个变量组，添加一对线性约束，确保辅助变量的取值与原变量的和严格对应：

  1. 第一组（x1~x4）：

     x1 + x2 + x3 + x4 >= 2 - 4*(1 - y1)
     x1 + x2 + x3 + x4 <= 1 + 4*y1
     

     • 当y1=1时，第一个约束强制该组和≥2，第二个约束因上限为5（远大于该组最大可能和4）自动满足，等价于要求第一组至少选2个。
     • 当y1=0时，第一个约束下限为-2（自动满足），第二个约束强制该组和≤1，即第一组最多选1个。

  2. 第二组（x5~x9）：

     x5 + x6 + x7 + x8 + x9 >= 2 - 5*(1 - y2)
     x5 + x6 + x7 + x8 + x9 <= 1 + 5*y2
     

     • y2=1时强制该组至少选2个；y2=0时强制该组最多选1个。

  3. 第三组（x10~x12）：

     x10 + x11 + x12 >= 2 - 3*(1 - y3)
     x10 + x11 + x12 <= 1 + 3*y3
     

     • y3=1时强制该组至少选2个；y3=0时强制该组最多选1个。

• 变量类型说明
  确保所有变量x1~x12和y1~y3均声明为二进制变量（取值仅为0或1）。

内容的提问来源于stack exchange，提问作者Sungsy