整数规划建模技巧

By Z.H. Fu https://fuzihaofzh.github.io/blog/

在数学优化中，我们经常遇到需要使用特殊技巧或方法来处理的约束。本篇博客将详细介绍如何将一些常见的复杂约束转化为更易处理的形式，包括整数约束、或约束、If-Then约束、保留N个约束中的K个、函数有N个可能取值、固定支出问题，以及一般整数变量的二值表示等。这些转化技巧可以帮助我们更好地理解和解决实际问题中的优化问题，下面让我们一起逐一研究。

整数约束变为连续约束

$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$