整数规划建模技巧

By Z.H. Fu
切问录 www.fuzihao.org

整数约束变为连续约束

\(y(y-1)=0\) (这是非线性的)

或约束

希望两个约束选一个,让目标最优。例如\(3x_1+2x_2\le18;x_1+4x_2\le 16\),利用大M,添加一个0-1变量y,得:\(3x_1+2x_2\le18+My;x_1+4x_2\le 16+M(1-y)\)

If-Then约束

以转化为或约束。例如If \(2x_1+x_2< 5\) then \(2x_3-x_4\ge 2\)。等价于\(2x_1+x_2\ge 5\) or \(2x_3-x_4\ge 2\)

保留N个约束中的K个

N个约束:\(f_i(x_1,x_2,\cdots,x_n)\le d_i,i=1,\cdots,N\). 同样利用大M和0-1变量得:\(f_i(x_1,x_2,\cdots,x_n)\le d_i+My_i,i=1,\cdots,N\);\(\sum_{i=1}^N y_i=N-K\)

函数有N个可能取值

\(f(x_1,x_2,\cdots,x_n)=d_1~or~d_2~\cdots~or~d_N\). 写作\(f(x_1,x_2,\cdots,x_n)=\sum_{i=1}^N d_iy_i;\sum_{i=1}^N y_i=1\);\(y_i\) are binary.

固定支出问题

只要\(x_j>0\),便要收一个起步价\(k_j\),\(\min Z=\sum_{j=1}^n(c_jx_j+k_jy_j)\) s.t. \(x_j-My_j\le 0\); \(y_i\) are binary.

一般整数变量的二值表示

\(2x_1+3x_2\le 30\),利用二进制及自变量值域,令\(x_1=y_0+2y_1+4y_2\);\(x_2=y_3+2y_4+4y_5+8y_6\),替换后得\(2y_0+4y_1+8y_2+3y_3+6y_4+12y_5+24y_6\le30\)