公司新闻

优化模型线性化方法总结

模型线性化的技巧在优化问题建模和求解中扮演这非常重要的地位，而关于这方面技巧的介绍往往分散在教科书的各个部分，在我们真正面对实际问题的时候往往不知道从何处开始下手或者该从哪里查阅资料。我这里总结了一些常用的优化模型线性化的方法，除了方便在使用的时候查阅以外，尽量在介绍的过程中告诉大家来龙去脉。授人以鱼不如授人以渔，掌握这些基本的思想对我们的建模水平会起到很大的帮助。

原始约束： $z=\\max \\left( x,y \\right)$

线性化后转化为：

$x\\le z, \\;\\;\\;\\;(1.1)\\\\ y\\le z, \\;\\;\\;\\;(1.2)\\\\ z\\le y+\\left( 1-u \\right) M, \\;\\;\\;\\;(1.3)\\\\ z\\le x+uM, \\;\\;\\;\\;(1.4) \\\\ u\\in\\{0,1\\}, \\;\\;\\;\\;(1.5)$

约束（1.1）（1.2）是自然成立的。当 $u=1$ 时约束（1.3）变为 $z\\leq y$ ，而约束（1.4）由于大M的存在变得不起作用。当 $u=0$ 是约束（1.4）变为 $z\\leq x$ ，而约束（1.3）由于大M的存在变得不起作用了。

原始约束： $y=\\max \\left( x_1,x_2,x_3 \\right)$

线性化后转化为：

$x_1\\le y, \\;\\;\\;\\;(1.6)\\\\ x_2\\le y, \\;\\;\\;\\;(1.7)\\\\ x_3\\le y, \\;\\;\\;\\;(1.8)\\\\ y\\le x_1+\\left( 1-u_1 \\right) M, \\;\\;\\;\\;(1.9)\\\\ y\\le x_2+\\left( 1-u_2 \\right) M, \\;\\;\\;\\;(1.10) \\\\ y\\le x_3+\\left( 1-u_3 \\right) M, \\;\\;\\;\\;(1.11) \\\\ u_1+u_2+u_3\\geq 1\\;\\;\\;\\;(1.12) \\\\ u_1,u_2,u_3\\in\\{0,1\\}, \\;\\;\\;\\;(1.13)$

结合约束（1.9）-（1.10）可以看出约束（1.12）的意义是：

$y\\leq x_1,y\\leq x_2,y\\leq x_3$ 至少有一个是成立的。

总结分析：通过上面的方法确实可以将模型线性化，但是同时也会带来一些负面作用。所以同学们在做线性化的时候一定要综合考虑优缺点，主要的负面作用有：

1 导致决策变量数量增加：从上面两个例子中我们不难观察出要线性化一个含有N个元素的Max/Min约束，我们需要引入N个新决策变量。对应上面的例子就是我们要引入 $u_i$

2 导致约束数量增加：同理约束数量也增加了不少，线性化一个含有N个元素的Max/Min约束，我们需要至少添加2N个约束。

3 引入了大M约束：大M约束确实给我们在建模上提供了相当多的遍历，但是在实际求解的过程中大M约束会对求解产生很多的影响，过大的大M值会导致求解过程中出现数值病态的问题，而过小的大M值又不能严格保证约束的成立。

原始约束： $\\left| x \\right|$

稍微思考一下就知道绝对值本质上可以看做是 Max 的特殊情况，即 $\\left| x \\right|=max\\left( x,-x \\right)$

那么我们可以直接套用上一节中处理Max约束的方法来等价处理绝对值，将式（1.1）-（1.5）中的 $y$ 替换为 $-x$ 即可。

方法1 线性化后转化为：

$x\\le z, \\;\\;\\;\\;(2.1)\\\\ -x\\le z, \\;\\;\\;\\;(2.2)\\\\ z\\le x+\\left( 1-u \\right) M, \\;\\;\\;\\;(2.3)\\\\ z\\le -x+uM, \\;\\;\\;\\;(2.4) \\\\ u\\in\\{0,1\\}, \\;\\;\\;\\;(2.5)$

上面方法1（2.1）-（2.5）是针对一般问题而言的，同样也引入了大M约束（2.3）和（2.4），对于一些稍微特殊的情况我们可以去掉约束（2.3）和（2.4），我们将在方法2中进行介绍。

方法2 考虑如下含绝对值的优化问题：

$\緻set{x}{\\min}\\sum_{i=1}^n{c_i\\left| x_i \\right| }\\;\\;\\;\\;(2.6)\\\\ s.t.\\ \\;\\;Ax\\le b \\;\\;\\;\\;(2.7)$

其中 $c_i\\ge 0,\\ \\forall i=1,2,...,n$ ，

线性化转化为如下优化问题：

$\緻set{z}{\\min}\\sum_{i=1}^n{c_i z_i }\\;\\;\\;\\; (2.8)\\\\ s.t.\\ \\;\\;Ax\\le b \\;\\;\\;\\; (2.9)\\\\ x_i\\leq z_i, \\;\\;\\;\\;i=1,2...,n\\;\\;\\;\\; (2.10)\\\\ -x_i\\leq z_i, \\;\\;\\;\\;i=1,2...,n\\;\\;\\;\\; (2.11)$

这样我们就可以将约束（2.3）（2.4）那样很丑的大M约束去掉了。切记之所以上面这种转化是等价的原因在于系数 $c_i$ 是非负的才成立（如何证明这一点留作思考题各位同学可以想一下）。如果系数 $c_i$ 存在负数项的话，那还是需要老老实实按照方法1去转化。

方法3 依然是考虑优化问题（2.6）-（2.7），令 $x_i=u_i-v_i$ , $\\left| x_i \\right|=u_i+v_i$ 由此可得： $u_i=\\frac{\\left| x_i \\right|+x_i}{2}$ , $v_i=\\frac{\\left| x_i \\right|-x_i}{2}$ ，将 $u,v$ 带入（2.6）（2.7）有

$\緻set{x}{\\min}\\sum_{i=1}^n{c_i (u_i +v_i)}\\;\\;\\;\\;(2.12)\\\\ s.t.\\ \\;\\; A(u_i-v_i)\\le b \\;\\;\\;\\;(2.13)\\\\ u_i,v_i\\geq0,i=1,2,...n\\;\\;\\;\\;(2.14)$

同样的方法3也需要 $c_i\\ge 0,\\ \\forall i=1,2,...,n$ 的条件才能成立。若系数 $c_i$ 存在负数项的话事实上我们是无法保证 $u_i$ 和 $v_i$ 至少有一个为0的隐含约束条件。

考虑如下优化问题：

$\緻set{x}{\\min}\緻set{i=1,..,m}{\\max}\\left( c_{i}^{T}x+d_i \\right)\\;\\;\\;\\; (3.1) \\\\ s.t. \\;\\;Ax\\leq b\\;\\;\\;\\; (3.2)$

线性化转化为如下优化问题：

$\緻set{(x,z)}\\min z \\\\ s.t. \\;\\;z\\geq c^T_ix+d_i, \\;\\;\\;\\; i=1,...,m \\;\\;\\;\\;(3.3) \\\\ Ax \\leq b \\;\\;\\;\\;(3.4)$

这一结论从上镜图可以比较直观的看到：

$z$ 变量表示的是所有线性函数 $c^T_ix+d_i, \\;\\;\\;\\; i=1,...,m$ 构成的图的上方（或者说是上界），那么极小化 $z$ 和原问题(3.1) (3.2)很容易看出是等价的。

推论：约束 $\緻set{i=1,...m}{\\max}c_{i}^{T}x+d_i\\le h$ 等价于约束 $c_{i}^{T}x+d_i\\le h,\\;\\;\\forall i=1,...,m$ ，这一条件在实际应用中也是会被经常用到的。

Maxmin和Minmax类似我们这里就不再赘述了。

考虑如下优化问题：

$\緻set{x}{\\max}\緻set{i=1,...m}{\\max}c_{i}^{T}x+d_i \\;\\;\\;\\;（4.1）\\\\$

令 $z=\緻set{i=1,...m}{\\max}c_{i}^{T}x+d_i$ ，带入上式中可得：

$\緻set{(x,z)}{\\max}z \\;\\;\\;\\; \\\\ s.t. \\;\\; z=\緻set{i=1,...m}{\\max}c_{i}^{T}x+d_i \\;\\;\\;\\;（4.2）$

接下来我们发现约束（4.2）在第一节 Max/Min 中我们已经介绍了线性化的方法，那么就套用前面的方法直接对约束（4.2）进行线性化即可。

$\緻set{(x,z)}{\\max}z \\;\\;\\;\\;（4.3）\\\\ s.t. \\;\\;z \\geq c_{i}^{T}x+d_i, \\;\\;\\;\\;i=1,...,m\\;\\;\\;\\;（4.4）\\\\ z \\leq c_{i}^{T}x+d_i + (1-u_i)M, \\;\\;\\;\\;i=1,...,m \\;\\;\\;\\;(4.5)\\\\ \\sum_{i=1}^{m}{u_i}\\geq1\\;\\;\\;\\;(4.6)\\\\ u_i\\in\\{0,1\\},\\;\\;\\;\\;i=1,...,m\\;\\;\\;\\;(4.7)$

由于目标函数是 $maxz$ ，同时考虑约束（4.5）我们知道约束（4.4）必然会被自动满足，因此去掉约束（4.4）也不会影响上述优化问题的最优解，因此最终可得：

$\緻set{(x,z)}{\\max}z \\;\\;\\;\\;（4.8）\\\\ s.t. \\;\\;z \\leq c_{i}^{T}x+d_i + (1-u_i)M, \\;\\;\\;\\;i=1,...,m \\;\\;\\;\\;(4.9)\\\\ \\sum_{i=1}^{m}{u_i}\\geq1\\;\\;\\;\\;(4.10)\\\\ u_i\\in\\{0,1\\},\\;\\;\\;\\;i=1,...,m\\;\\;\\;\\;(4.11)$

Minmin的线性化方式和Maxmax基本一样，这里就不再赘述了。

考虑如下优化问题：

$\緻set{x}{\\min}\\frac{c^Tx+d}{e^Tx+f}\\;\\;\\;\\;(5.1)\\\\ s.t.\\;\\; Ax\\leq b \\;\\;\\;\\;(5.2)\\\\ e^Tx+f>0\\;\\;\\;\\;(5.3)\\\\$

令 $y=\\frac{1}{e^Tx+f}>0$ 带入上面可得：

$\緻set{(x,y)}{\\min}{(c^Tx+d)}y\\;\\;\\;\\;(5.4)\\\\ s.t. \\;\\;Ax\\leq b \\;\\;\\;\\;(5.5)\\\\ ({e^Tx+f})y=1 \\;\\;\\;\\;(5.6)\\\\ y>0\\;\\;\\;\\;(5.7)\\\\$

再令 $z=xy$ 带入上面进一步可得：

$\緻set{(y,z)}{\\min}{(c^Tz+dy)}\\;\\;\\;\\;(5.8)\\\\ s.t. \\;\\;Az\\leq by \\;\\;\\;\\;(5.9)\\\\ ({e^Tz+fy})=1 \\;\\;\\;\\;(5.10)\\\\ y>0,z\\geq0\\;\\;\\;\\;(5.11)\\\\$

通过做两次变量的替换可以将分式目标函数线性化，(5.8)-(5.11) 中优化决策变量为 $\\left( y,z \\right)$ ，不难得到与原优化问题决策变量 $x$ 的关系为：

$y=\\frac{1}{e^Tx+f},\\ z=\\frac{x}{e^Tx+f}\\\\$

考虑如下约束：

$x=0$ 或者 $a\\leq x \\leq b$

线性化转化为：

$au\\leq x\\leq b u, u\\in\\{0,1\\}$

该变量常用于带有fixed cost形式的目标函数或者约束上。

7.1 两个约束至少有一个成立

$\\sum_i{a_ix}\\le b$ 或 $\\sum_i{g_ix}\\le h$ 两个约束至少有一个成立

线性化转化为：

$\\sum_i{a_ix}\\le b+\\left( 1-y_1 \\right)M \\;\\;\\;\\;(7.1)\\\\ \\sum_i{g_ix}\\le h+\\left( 1-y_2 \\right)M \\;\\;\\;\\;(7.2) \\\\ y_1+y_2\\geq1 \\;\\;\\;\\;(7.3) \\\\ y_1,y_2\\in\\left\\{ 0,1 \\right\\}\\;\\;\\;\\;(7.4)$

7.2 两个约束只一个成立

$\\sum_i{a_ix}\\le b$ 或 $\\sum_i{g_ix}\\le h$ 两个约束只一个成立

线性化转化为：

$\\sum_i{a_ix}\\le b+\\left( 1-y_1 \\right)M \\;\\;\\;\\;(7.5)\\\\ \\sum_i{g_ix}\\le h+\\left( 1-y_2 \\right)M \\;\\;\\;\\;(7.6) \\\\ y_1+y_2=1 \\;\\;\\;\\;(7.7) \\\\ y_1,y_2\\in\\left\\{ 0,1 \\right\\}\\;\\;\\;\\;(7.8)$

将约束（7.7）带入约束（7.6）中进一步得到更简洁的形式：

$\\sum_i{a_ix}\\le b+\\left( 1-y_1 \\right)M \\;\\;\\;\\;(7.9)\\\\ \\sum_i{g_ix}\\le h+y_1M \\;\\;\\;\\;(7.10) \\\\ y_1\\in\\left\\{ 0,1 \\right\\}\\;\\;\\;\\;(7.11)$

7.3 If-then

若约束 $\\sum_i{a_ix}\\le b$ 成立，则约束 $\\sum_i{g_ix}\\le h$ 也成立

线性化转化为：

$\\sum_i{a_ix}\\le b+\\left( 1-y_1 \\right)M \\;\\;\\;\\;(7.12)\\\\ \\sum_i{g_ix}\\le h+\\left( 1-y_2\\right)M \\;\\;\\;\\;(7.13)\\\\ y_2\\geq y_1 \\;\\;\\;\\;(7.14)\\\\ y_1,y_2\\in\\left\\{ 0,1 \\right\\}\\;\\;\\;\\;(7.15)$