指示约束条件 (indicator constraint) 与大M (big M) 条件

admin管理员组

文章数量:1550528

数学规划软件 cplex 或 gurobi 都有专门的指示约束条件：约束一个变量与另外一些变量的关系，例如对于一个 0-1 变量 z z z，它与 x x x 有以下关系：

x > 0 ⇒ z = 1 x = 0 ⇒ z = 0 \begin{aligned} x>0 \Rightarrow z=1\\ x=0\Rightarrow z=0 \end{aligned} x>0⇒z=1x=0⇒z=0​

一般情况下可以使用大 M 构造成线性规划模型：
x ≤ M z x ≥ 0 \begin{aligned} x &\leq Mz\\ x&\geq 0 \end{aligned} xx​≤Mz≥0​

什么时候用 indicator constraint 与 big M 似乎没有明确的标准，gurobi 的官方说明有点模糊：

https://www.gurobi/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints

它只说明了用 indicator constraint 的好处，没有说可能的缺点。 cplex的官方说明比较清楚些：

https://www.ibm/support/pages/difference-between-using-indicator-constraints-and-big-m-formulation

基本是以下标准：

• 当大 M 值没有比模型中的其他系数大很多时，使用大M约束
• 当大 M 值比模型中的其他系数大很多时，使用 indicator constraint

我实际测试 gurobi 时，indicator constraint 的确比大 M 约束的预处理时间长。

本文标签： 条件指示indicatorconstraintBig