本文详解如何将非线性的 maximin 优化问题（目标为最大化点到离散点集的最小曼哈顿距离）转化为标准线性规划模型，并在 pulp 中正确建模与求解，核心在于绝对值的线性化处理及 max-min 结构的重构。
在运筹学与设施选址、鲁棒设计等场景中，常需在给定搜索空间内寻找一个点 $ x $，使其到一组已知障碍点（或服务点）集合 $ L $ 的最小曼哈顿距离尽可能大。该问题形式化为：
$$ \max{x \in \mathcal{X}} \min{\sigma \in L} \sum_{i=1}^n |x_i - \sigma_i| $$
其中 $ \mathcal{X} $ 是由变量边界与线性约束定义的可行域（如超矩形、链式不等式等）。该目标函数含嵌套极值（max-min）和非光滑项（绝对值），无法直接送入线性规划求解器。但借助辅助变量法与大M法（Big-M），可将其精确转化为纯线性规划（LP）问题。
关键建模技巧
- 引入松弛变量 $ z $：令 $ z $ 表示所求的最小距离，则原目标变为最大化 $ z $；
-
强制 $ z $ 不超过每个点对的距离：对每个 $ \sigma^{(j)} \in L $，添加约束
$$ z \leq \sum_{i=1}^n |x_i - \sigma^{(j)}_i| $$
这确保 $ z \leq \min_j \sum_i |x_i - \sigma^{(j)}_i| $，而最大化 $ z $ 将自然“拉高”至该最小值； - 线性化绝对值：对每个 $ |x_i - \sigma^{(j)}i| $，引入辅助变量 $ a{ji} \geq 0 $ 及二元变量 $ b{ji} \in {0,1} $，并添加以下四组线性约束（大M法）： $$ \begin{aligned} a{ji} &\geq x_i - \sigma^{(j)}i \ a{ji} &\geq \sigma^{(j)}_i - xi \ a{ji} &\leq x_i - \sigma^{(j)}i + M(1 - b{ji}) \ a_{ji} &\leq \sigma^{(j)}_i - xi + M b{ji} \end{aligned} $$ 其中 $ M $ 是足够大的常数（如取搜索空间直径上界），保证逻辑等价性。
✅ 注意：PuLP 默认不支持原生绝对值函数（abs()），且 LpVariable 不能直接参与 abs() 运算。必须通过上述约束显式建模。
完整可运行代码实现
以下封装了健壮的 add_abs() 工具函数，并集成到主优化流程中：
import pulp as plp
def add_abs(prob, var, big_m=1e5, abs_var_name=None):
"""安全地为 PuLP 表达式添加绝对值变量及其约束"""
# 自动生成唯一变量名
def unique_name(base):
name = base
i = 1
while name in prob.variablesDict():
name = f"{base}_{i}"
i += 1
return name
if abs_var_name is None:
abs_var_name = f"abs({var.getName() or 'expr'})"
abs_var_name = unique_name(abs_var_name)
abs_var = plp.LpVariable(abs_var_name, lowBound=0)
bin_var = plp.LpVariable(unique_name(f"bin_{abs_var_name}"), cat=plp.LpBinary)
# 绝对值定义约束（大M法）
prob += abs_var >= var
prob += abs_var >= -var
prob += abs_var <= var + big_m * (1 - bin_var)
prob += abs_var <= -var + big_m * bin_var
return abs_var
# 示例参数（2D 空间）
model = [(0, 10), (0, 10)] # x₀∈[0,10], x₁∈[0,10]
L = [(1, 2), (3, 4), (5, 6)] # 3 个参考点
n, m = len(model), len(L)
prob = plp.LpProblem("MaxMinManhattan", plp.LpMaximize)
# 决策变量：待优化点 x
x = plp.LpVariable.dicts("x", range(n), lowBound=0, cat="Continuous")
# 目标变量：最小距离下界 z
z = plp.LpVariable("z", lowBound=0)
# 搜索空间约束（此处为简单箱型约束；可按需替换为链式等更复杂结构）
for i in range(n):
prob += x[i] >= model[i][0]
prob += x[i] <= model[i][1]
# 对每个 σ ∈ L，约束 z ≤ d₁(x, σ)
for j, sigma in enumerate(L):
manhattan_sum = 0
for i in range(n):
diff = sigma[i] - x[i]
abs_diff = add_abs(prob, diff, big_m=1e5, abs_var_name=f"abs_{j}_{i}")
manhattan_sum += abs_diff
prob += z <= manhattan_sum
# 设置目标
prob.setObjective(z)
# 求解
solver = plp.PULP_CBC_CMD(msg=False) # 或使用其他求解器如 COIN_CMD, GUROBI
prob.solve(solver)
print("Status:", plp.LpStatus[prob.status])
print("Optimal z:", plp.value(z))
print("Optimal x:", [plp.value(x[i]) for i in range(n)])注意事项与调优建议
- big_m 的选取至关重要：过大会导致数值不稳定或弱松弛；过小则约束失效。推荐设为搜索空间各维度最大可能偏移量之和（如本例中 $ M = 2 \times 10 = 20 $ 即足够，但保守起见设为 1e5 更安全）；
- 避免重复变量名：add_abs() 内置唯一命名逻辑，防止 PuLP 报错 Duplicate name；
- 搜索空间建模灵活性：当前示例使用独立箱型约束，若实际为链式约束（如 x[i] ≥ x[i−1]），只需修改对应 prob += ... 行，不影响绝对值部分；
- 扩展性：该框架天然支持任意维度 $ n $ 和点集大小 $ m $，仅需调整输入数据结构；
- 验证结果：最优解应位于搜索空间“中心偏外”的区域（远离所有 $ L $ 中点），可通过人工计算验证 $ z $ 值是否确实等于某点对的曼哈顿距离。
通过以上方法，你已将一个看似非线性的 maximin 问题，完全转化为 PuLP 可高效求解的标准线性规划问题——这是运筹建模中“转化思维”的典型范例。
