基于PuLP求解n维空间最小曼哈顿距离最大化线性规划问题

问题定义 #

我们需要求解n维空间中的极大极小优化问题：在指定搜索空间内找到点$x$，最大化$x$到有限点集$L$中所有点的最小曼哈顿距离。数学形式如下：

曼哈顿距离定义：
$$d(x, L) = \min_{\sigma \in L} d(x, \sigma) = \min_{\sigma \in L} \sum_{i = 1}^n |x_i - \sigma_i|$$

最终优化目标：
$$\max_{x \in \text{SearchSpace}} \min_{\sigma \in L} \sum_{i=1}^n |x_i - \sigma_i|$$

原代码问题分析 #

你提供的代码在绝对值转化和极大极小约束逻辑上存在问题：

• diff[i] == L[j][i] - x[i]的符号错误，曼哈顿距离是$|x_i - \sigma_i|$，应基于$x_i - L[j][i]$进行绝对值转化
• 变量定义存在冗余（如diff变量），且未为每个点单独隔离diff_plus/diff_minus变量，可能导致约束冲突
• 核心逻辑未正确关联$z$与所有曼哈顿距离的最小值关系

修正后的完整代码 #

import pulp as plp

# 示例参数：可根据实际需求修改
n = 2  # 空间维度
L = [[0, 0], [2, 2]]  # 给定的点集
search_space = [(0, 3), (0, 3)]  # 每个维度的搜索上下界（下界，上界）
m = len(L)

# 初始化最大化问题
prob = plp.LpProblem("MaxMin_Manhattan_Distance", plp.LpMaximize)

# 定义变量：x是n维决策点，z是要最大化的最小距离
x = plp.LpVariable.dicts(
    "x", 
    range(n), 
    lowBound=search_space[i][0], 
    upBound=search_space[i][1], 
    cat="Continuous"
)
z = plp.LpVariable("z", lowBound=0, cat="Continuous")

# 为每个点σ∈L添加约束：z ≤ 该点到x的曼哈顿距离
for j in range(m):
    # 为当前点的每个维度定义非负变量，用于线性表示绝对值
    diff_plus = plp.LpVariable.dicts(f"diff_plus_{j}", range(n), lowBound=0, cat="Continuous")
    diff_minus = plp.LpVariable.dicts(f"diff_minus_{j}", range(n), lowBound=0, cat="Continuous")
    
    for i in range(n):
        # 绝对值的线性转化：x_i - L[j][i] = diff_plus[i] - diff_minus[i]
        prob += x[i] - L[j][i] == diff_plus[i] - diff_minus[i]
    
    # 约束z ≤ 当前点到x的曼哈顿距离（曼哈顿距离为各维度绝对值之和）
    prob += z <= plp.lpSum([diff_plus[i] + diff_minus[i] for i in range(n)])

# 设置目标函数：最大化z
prob += z

# 求解（关闭日志输出，如需查看过程可删除msg=False）
prob.solve(plp.PULP_CBC_CMD(msg=False))

# 输出结果
print("最优决策点x：")
for i in range(n):
    print(f"x_{i+1} = {round(plp.value(x[i]), 4)}")
print(f"最大最小曼哈顿距离：{round(plp.value(z), 4)}")

关键修正说明 #

• 绝对值线性转化：通过两个非负变量diff_plus和diff_minus，将$|x_i - \sigma_i|$转化为$diff_plus[i] + diff_minus[i]$，满足$x_i - \sigma_i = diff_plus[i] - diff_minus[i]$
• 变量隔离：为每个点$j$单独定义diff_plus_j和diff_minus_j，避免不同点的变量冲突
• 极大极小逻辑：将$z$约束为小于等于每个点到$x$的曼哈顿距离，再最大化$z$，确保$z$的最优值就是所有曼哈顿距离中的最小值的最大值
• 搜索空间约束：正确为$x$的每个维度设置上下界，符合问题要求

内容的提问来源于stack exchange，提问作者UStBB