本文翻译自 How to linearize max, min, and abs functions。这篇文章将介绍我们在构建线性规划模型(也包括混合整型线性规划模型)时,如何将 max, min, abs(绝对值)等形式约束转化成线性约束,从而能够使用 SCIP 等线性求解器进行高效求解。

这些约束的数学形式可以写成:

这里我们选择的比较难处理的几个不等关系,其相反形式的转化是非常简单的。例如,对于 不等式,我们可以很简单地将其转化成

首先我们来看开始的三个不等式中比较简单的一个 这个不等式可以等价于

接下来来我们来处理的 ,这个式子可以等价为

然后可以带入 转化为

引入两个新变量 ,要求

我们将 纳入优化目标,且让其最小化,那么最终 中的一个将会逼近 ,另一个逼近 0。则 会逼近 ,因此 可以转化为:

不等式的操作是类似的,我们就不给出分析过程了,给出结论如下:

等价于