mathematical-optimization - 整数规划不等式约束

Question

我正在尝试在 MIP 中对以下约束进行建模：

x_1 +x_2 + ... +x_n != d

这个想法是引入一个变量 z 是 1，如果 x_1 +x_2 + ... +x_n = d 并添加约束

z <= 0.

但我不知道如何为约束建模

(x_1 +x_2 + ... +x_n = d) ==> z=1 

在整数程序中。

Answer 1

我假设所有x_i都是整数。让L和U是常数，使得

L <= x_1+x_2 + ... +x_n <= U

和y一个二进制变量。这些约束表达了您正在寻找的内容：

x_1+x_2 + ... +x_n >= d+1 + (L-d-1)y

x_1+x_2 + ... +x_n <= d-1 + (U-d+1)(1-y)

如果y=0那么第一个约束x_1 +x_2 + ... +x_n >= d+1必须成立，并且第二个约束x_1+x_2 + ... +x_n <= U满足 的定义U。

如果y=1then 则第二个约束x_1 +x_2 + ... +x_n <= d-1必须成立，并且第一个约束x_1+x_2 + ... +x_n >= L由 的定义满足L。

（请检查错别字。）

---

这就是整数规划中臭名昭著的大 M 方法。它可能导致放松不良，也可能导致病态问题。

---

更多技巧，谷歌“整数编程技巧”。特别是，请参阅AIMMS 建模指南 - 整数编程技巧，了解这个大 M 方法技巧。