运筹系列86：MIP问题的建模tips

1. Either-or constraint

添加辅助变量y。
比如
Either $3x_1+2x_2\le 18$
or $x_1+4x_2\le 16$

可以用

$3x_1+2x_2\le 18+My$
$x_1+4x_2\le 16+M(1-y)$
来代替。

2. k out of N constraints must hold

类似上面，添加辅助变量$y_1$～$y_N$
从
$f_1(...)\le d_1$
…
$f_N(...)\le d_N$

变为

$f_1(...)\le d_1+M{y}_1$
…
$f_N(...)\le d_N+M{y}_N$
${\Sigma }_1^N{y}_i=N-k,y_i$ binary.

3. functions with N possible values

$f(x)\in (d_1,...,d_N)$

添加辅助变量$y_1$～$y_N$
$f(x)=\Sigma d_i{y}_i$
$\Sigma y_i=1$ (mutally exclusive alternatives)

4. fixed-charge problem

f ( x ) = { k + c x , x > 0 0 , x = 0 f(x)=\begin {equation}

\end {equation} f(x)={k+cx,x>00,x=0​​​
可以变为
$f(x)=cx+ky$
$x\le My$
$y$ binary.

5. 综合例子

如果没有题目中的两个restriction，那么模型为：

接下来我们看约束1，要求$x_1,x_2,x_3$最多只能有2个，因此添加$y_1+y_2+y_3\le 2$的约束。
然后是约束2，要求两座工厂二选一，因此添加Either-or变量$y_4$，最终模型为：