大M变换法

2022-09-21 本文已影响0人 alue

在调用整数规划求解器时，约束条件必须是线性的，这时候怎么表达 $x \neq y$ 呢 ?
在整数规划中： $x \neq y$ 就意味着 $x \le y-1$ 或者 $x \ge y+1$ . 但最优化工具不允许有这种“或”的操作啊。它只能处理线性的目标函数和约束条件。

这就是工程问题跟科学问题之间的区别。我们想要利用已有的工具，就要想方设法去满足它的应用条件。

这里给出 Big-M 转换技巧。

在整数规划中：
$x \neq y$
等价于以下以下两个不线性不等式约束
$x \le y-1+bM$
$x \ge y+1-(1-b)M$

其中 M 是一个非常大的常数，可以根据问题的实际来设置。 $b$ 是引入的布尔变量。

如何理解呢？
当 $b=0$ 时，上面的不等式等价于
$x \le y-1$
$x \ge y+1-M$

由于M很大，第二个不等式肯定会满足，所以相当于没有。同理，当 $b=1$ 时，上面的不等式等价于 $x \ge y+1$

而 $b$ 要不就等于1，要不就等于0，这就等同于 $x \le y-1$ 或者 $x \ge y+1$ 。

在工程问题中，通过引入大数M和布尔变量b，就实现了约束条件线性化。