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

Question

我正在尝试在 MIP 中模拟以下约束:

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

想法是引入一个变量 z，如果 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=1然后是第二个约束 x_1 +x_2 + ... +x_n <= d-1必须持有并且第一个约束 x_1+x_2 + ... +x_n >= L满足 L 的定义.

(请检查错别字。)

---

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

---

有关更多技巧，请在谷歌上搜索“整数编程技巧”。特别是，参见 AIMMS Modeling Guide - Integer Programming Tricks对于这个大 M 方法技巧。