混合整数规划的易处理形式推导问询

阿华AIGC实验室

2026-4-20

混合整数规划的易处理形式推导问询

嘿，我来帮你捋捋这个混合整数规划问题的可处理化思路～先把你的问题明确下来，方便后续拆解：

给定常数矩阵 $A_1\in\mathbb{R}^{1\times l}$ 和 $A_2\in\mathbb{R}^{1\times l}$，以及常数 $b_i$（$i=1,\dots,n$），我们的决策变量是二进制变量 $c_i\in{0,1}$ 和矩阵 $X=[x_1,\dots,x_n]\in\mathbb{R}^{l\times n}$（其中每个 $x_i\in\mathbb{R}^{l}$）。

原问题的MIP形式如下：
目标函数：$\min \sum_{i=1}^{n} |c_iA_1x_i|$
约束条件：

$A_2x_i \le c_ib_i$，$\forall i=1,\dots,n$
$\sum_{i=1}^n c_i \ge 1$
$c_i\in{0,1}$，$\forall i=1,\dots,n$

你说得没错，原问题难处理的核心就是目标里的 $c_i$ 和 $x_i$ 乘积项，这让问题变成了非凸的非线性规划，常规求解器很难直接搞定。不过咱们可以通过引入辅助变量+线性化技巧，把它转成线性混合整数规划（LMIP），这样就能用标准MIP求解器轻松处理了。

下面是具体的转换步骤：

第一步：处理绝对值项

对于每个 $i$，我们引入一个非负辅助变量 $y_i$，用来代替 $|c_iA_1x_i|$。绝对值的线性化约束很经典：
$$y_i \ge c_iA_1x_i \quad \text{和} \quad y_i \ge -c_iA_1x_i$$
这两个约束能保证 $y_i$ 始终不小于 $|c_iA_1x_i|$，而因为我们的目标是最小化 $\sum y_i$，求解器会自动让 $y_i$ 等于 $|c_iA_1x_i|$（只要后续约束不限制它）。

第二步：线性化乘积项的逻辑

接下来要解决的是 $c_i$（二进制）和 $A_1x_i$（连续）的乘积问题。关键观察是：

当 $c_i=0$ 时，$c_iA_1x_i=0$，所以对应的 $y_i$ 必须等于0；
当 $c_i=1$ 时，$c_iA_1x_i=A_1x_i$，此时 $y_i$ 要等于 $|A_1x_i|$。

我们可以用大M法来把这个逻辑转换成线性约束：
首先为每个 $i$ 确定一个足够大的常数 $M_i$，这个 $M_i$ 需要大于当 $c_i=1$ 时 $|A_1x_i|$ 的最大可能值（可以从约束 $A_2x_i \le b_i$ 推导 $x_i$ 的可行范围，进而算出 $A_1x_i$ 的上下界，取绝对值较大的那个作为 $M_i$）。

然后添加约束：
$$y_i \le M_i c_i$$

这个约束的作用是：

当 $c_i=0$ 时，$y_i \le 0$，结合 $y_i \ge 0$（绝对值非负，也可以显式加约束 $y_i \ge 0$），直接锁定 $y_i=0$，完美对应原目标的项为0；
当 $c_i=1$ 时，$y_i \le M_i$，而 $M_i$ 是 $|A_1x_i|$ 的上界，所以不会影响 $y_i$ 取到 $|A_1x_i|$ 的值。