原文链接： https://www.codewoody.com/posts/34803/
本文翻译自 How to linearize max, min, and abs functions。这篇文章将介绍我们在构建线性规划模型（也包括混合整型线性规划模型）时，如何将 max, min, abs(绝对值)等形式约束转化成线性约束，从而能够使用 SCIP 等线性求解器进行高效求解。
这些约束的数学形式可以写成：
X≤max(A,B)(1)
X≥min(A,B)(2)
X≥|A|(3)
这里我们选择的比较难处理的几个不等关系，其相反形式的转化是非常简单的。例如，对于 X≥max(A,B) 不等式，我们可以很简单地将其转化成
X≥AX≥B(4)
首先我们来看开始的三个不等式中比较简单的一个 X≥|A| 这个不等式可以等价于
X≥AX≥−A(5)
接下来来我们来处理的 X≥min(A,B)，这个式子可以等价为
X≥max(A,B)−|A−B|(6)
然后可以带入 (4) 转化为
X≥A−|A−B|X≥B−|A−B|(7)
引入两个新变量 S+,S−，要求
S+≥B−AS−≥A−BS+,S−≥0(8)
我们将 S+ 和 S− 纳入优化目标，且让其最小化，那么最终 S+,S− 中的一个将会逼近 |A−B|，另一个逼近 0。则 S++S− 会逼近 |A−B|，因此 (7) 可以转化为：
X≥A−S−−S+X≥B−S−−S+S+≥B−AS−≥A−BS+,S−≥0(9)
max 不等式的操作是类似的，我们就不给出分析过程了，给出结论如下：
X≤max(A,B)(10)
等价于
X≤A+S−+S+X≤B+S−+S+S+≥B−AS−≥A−BS+,S−≥0(11)
本文转自： https://www.codewoody.com/posts/34803/
本站仅做收录，版权归原作者所有。