混合整数规划问题中变量乘积的线性化

最近在做毕设时需要解决一个混合整数规划问题，于是学习了一些凸优化相关的知识，下面记录一些实用的线性化方法。

混合整数规划(MIP, Mixed Integer Programming)问题，是运筹优化中常见的一类问题，它的目标函数和约束条件中既包含整数变量，又包含连续变量。相较于连续优化，MIP问题因为整数变量的引入使得解空间变得离散，从而使得求解过程变得更加复杂，求解难度更大。

在求解MIP问题时，首先考虑能否将问题线性化。因为非线性项的存在往往导致问题非凸，从而使问题不易求解，即使能够求解，也容易陷入局部最优。两自变量的乘积是很常见的非线性项，下面分别记录三种不同情况下自变量乘积项的线性化方法。

实数型变量与二进制变量相乘的线性化

现在有实数型变量，二进制变量，其中的取值为0或1。在MIP问题的表达式中，含非线性项。引入新变量替代乘积项即令，然后通过对变量添加线性约束使问题线性化。首先我们需要知道连续变量的上下边界，假设有:

其中和分别为的下界和上界。对进行如下约束:


当时，，当时，。以上两个约束均为线性约束，因此可以将乘积项线性化。

实数型变量与实数型变量相乘的线性化

考虑变量, 均为实数型变量的情况。首先引入两个新变量和，令:


则有:

如果直接用替代乘积项，问题仍然是一个二次规划问题。继续对和的平方项进行分段近似线性化，可以将问题转化为近似的线性规划问题。

二进制变量与二进制变量相乘的线性化

最后考虑二进制变量和相乘的情况。引入新变量替代乘积项，则应受到如下约束:




当或时，，当时，。以上约束均为线性约束，因此可以将乘积项线性化。