盒约束下绝对值和最大化问题的简洁可处理重构方法咨询
嘿，我来聊聊你遇到的这个问题——你现在处理的是带盒约束的两个线性组合绝对值之和的最大化问题，目前用二进制变量的思路虽然可行，但确实太繁琐了。咱们可以换个更简洁优雅的方式来重构这个问题，核心是利用绝对值和的本质性质来简化。
首先先明确你的原问题：
$$
\begin{array}{cl}
\max & |a_{11} x_1 + a_{12} x_2| + |a_{21} x_1 + a_{22} x_2| \
\mathrm{s.t.} & 0 \leq x_1 \leq b_1 \
& 0 \leq x_2 \leq b_2.
\end{array}
$$
最快捷的解法：直接枚举符号组合计算最优值
对于表达式$|u| + |v|$，它等价于以下四个线性函数在$(u,v)$处的最大值：
- $u + v$
- $u - v$
- $-u + v$
- $-u - v$
所以原问题可以拆解为4个带盒约束的线性最大化子问题，只需要计算每个子问题的最优值，再取其中最大的那个就是原问题的解。
每个子问题都是形如$\max_{0 \leq x_1 \leq b_1, 0 \leq x_2 \leq b_2} c_1x_1 + c_2x_2$的线性规划，这种问题完全不需要调用求解器，直接代数计算就能得到最优值：
- 如果系数$c_i > 0$，取$x_i = b_i$（最大化正系数的贡献）；
- 如果系数$c_i < 0$，取$x_i = 0$（避免负系数的损失）；
- 如果$c_i = 0$，$x_i$的取值不影响目标值。
比如第一个子问题的最优值就是$(a_{11}+a_{21})^+b_1 + (a_{12}+a_{22})+b_2$，其中$c+ = \max(c,0)$，剩下三个子问题同理计算，最后取四个值里的最大值即可。
适合嵌入大模型的MIP重构（简洁版）
如果你需要把这个问题嵌入到更大的混合整数规划模型里，也可以用更简洁的二进制变量方式重构，避免你原来的冗余约束：
引入4个二进制变量$y_1, y_2, y_3, y_4$，满足$y_1 + y_2 + y_3 + y_4 = 1$（表示选择哪一种符号组合），重构后的问题如下：
$$
\begin{array}{cl}
\max & t \
\mathrm{s.t.} & t \leq (a_{11}+a_{21})x_1 + (a_{12}+a_{22})x_2 + M(1 - y_1) \
& t \leq (a_{11}-a_{21})x_1 + (a_{12}-a_{22})x_2 + M(1 - y_2) \
& t \leq (-a_{11}+a_{21})x_1 + (-a_{12}+a_{22})x_2 + M(1 - y_3) \
& t \leq (-a_{11}-a_{21})x_1 + (-a_{12}-a_{22})x_2 + M(1 - y_4) \
& 0 \leq x_1 \leq b_1 \
& 0 \leq x_2 \leq b_2 \
& y_1 + y_2 + y_3 + y_4 = 1 \
& y_1, y_2, y_3, y_4 \in {0,1} \
& t \in \mathbb{R}
\end{array}
$$
这里的$M$取一个足够大的常数即可，比如$\sum_{i,j}|a_{ij}|b_j$就完全能满足要求。
对比你原来的方法，这个重构只需要4个二进制变量和4个核心约束，简洁性提升非常明显，核心思路就是抓住绝对值和的本质——它是四个线性函数的最大值，避免了给每个绝对值单独拆分带来的冗余约束。
备注：内容来源于stack exchange，提问作者Eason Mao
