线性规划中如何线性化 max, min 以及 abs 等形式的约束

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

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

$$\begin{array}{}X\le max(A,B)& \text{(1)}\end{array}$$

$$\begin{array}{}X\ge min(A,B)& \text{(2)}\end{array}$$

$$\begin{array}{}X\ge |A|& \text{(3)}\end{array}$$

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

$$\begin{array}{}\begin{array}{cc}X& \ge A\\ X& \ge B\end{array}& \text{(4)}\end{array}$$

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

$$\begin{array}{}\begin{array}{cc}X& \ge A\\ X& \ge -A\end{array}& \text{(5)}\end{array}$$

接下来来我们来处理的 $X\ge min(A,B)$，这个式子可以等价为

$$\begin{array}{}X\ge max(A,B)-|A-B|& \text{(6)}\end{array}$$

然后可以带入 $\text{(4)}$ 转化为

$$\begin{array}{}\begin{array}{cc}X& \ge A-|A-B|\\ X& \ge B-|A-B|\end{array}& \text{(7)}\end{array}$$

引入两个新变量 $S^{+},S^{-}$，要求

$$\begin{array}{}\begin{array}{cc}{S}^{+}& \ge B-A\\ S^{-}& \ge A-B\\ S^{+},S^{-}& \ge 0\end{array}& \text{(8)}\end{array}$$

我们将 $S^{+}$ 和 $S^{-}$ 纳入优化目标，且让其最小化，那么最终 $S^{+},S^{-}$ 中的一个将会逼近 $|A-B|$，另一个逼近 0。则 $S^{+}+S^{-}$ 会逼近 $|A-B|$，因此 $\text{(7)}$ 可以转化为：

$$\begin{array}{}\begin{array}{cc}X& \ge A-S^{-}-S^{+}\\ X& \ge B-S^{-}-S^{+}\\ S^{+}& \ge B-A\\ S^{-}& \ge A-B\\ S^{+},S^{-}& \ge 0\end{array}& \text{(9)}\end{array}$$

$max$ 不等式的操作是类似的，我们就不给出分析过程了，给出结论如下：

$$\begin{array}{}X\le max(A,B)& \text{(11)}\end{array}$$

等价于

$$\begin{array}{}\begin{array}{cc}X& \le A+S^{-}+S^{+}\\ X& \le B+S^{-}+S^{+}\\ S^{+}& \ge B-A\\ S^{-}& \ge A-B\\ S^{+},S^{-}& \ge 0\end{array}& \text{(12)}\end{array}$$

Update: 距离写这个篇文章已经过去了几个月，实际应用检验下来，这套方法存在很大的问题，这是因为我们需要将 $S^{+}$ 和 $S^{-}$ 也纳入优化目标中，这意味着我们需要优化 $|A-B|$，而 $A$ 和 $B$ 作为优化目标可能对我们的已有目标的权重分配产生影响。