Kal*_*lle 2 mathematical-optimization integer-programming
我试图在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
在整数程序中.
我假设所有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方法.它可能导致不良的放松,也可能导致病态问题.
对于进一步的技巧,谷歌"整数编程技巧".特别是,请参阅AIMMS建模指南 -这个大M方法技巧的整数编程技巧.