ILP中如何编写“X不在区间[Y,Y+10]内”的约束？是否可行？

这个需求完全具备可行性，整数线性规划（ILP）中可以通过引入0-1辅助变量结合大M法来实现这类逻辑约束。

核心思路 #

原需求“X不在区间[Y, Y+10]内”等价于两个线性条件的逻辑或：

• X ≤ Y - 1
• X ≥ Y + 11

我们需要用ILP能识别的线性约束来表达这种“二选一”的逻辑，具体步骤如下：

具体约束写法 #

1. 引入一个0-1变量Z（Z ∈ {0, 1}），用来控制两个分支的激活状态：

   • 当Z=0时，强制满足X ≤ Y - 1
   • 当Z=1时，强制满足X ≥ Y + 11

2. 选择一个足够大的常数M（即“大M”）：
   M的取值需要覆盖X的最大可能偏差，比如如果X的取值范围是[X_min, X_max]，那么M至少要取max(X_max - (Y-1), (Y+11) - X_min)，确保当约束不生效时，右边的项不会限制X的合理取值。

3. 写出最终的线性约束：

   • X ≤ Y - 1 + M * Z：当Z=0时，约束为X ≤ Y-1；当Z=1时，M*Z足够大，约束自动失效
   • X ≥ Y + 11 - M * (1 - Z)：当Z=1时，约束为X ≥ Y+11；当Z=0时，-M*(1-Z)足够小，约束自动失效
   • Z ∈ {0, 1}：明确变量的整数属性

注意事项 #

• 大M的取值不能过大，否则会导致ILP求解器的数值稳定性问题；也不能过小，否则会错误限制X的取值范围。建议根据问题中X、Y的实际上下界来确定。
• 如果Y是常数，约束逻辑不变；如果Y是变量，上述方法同样适用。

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