带绝对值的极大极小问题（曼哈顿距离）线性规划建模错误排查

问题背景 #

我尝试用线性规划解决带绝对值的极大极小曼哈顿距离问题：给定n维点集L和搜索空间S，目标是在S中找到一点x，使得x到L中所有点的曼哈顿距离的最小值最大化。我将其建模为线性规划问题，但用PuLP库实现时无法得到正确的最优解，恳请排查绝对值和约束改写中的错误。

现有实现代码 #

import pulp as plp

# Define the dimensionality of the problem
n = len(model) #dimension of the space 
m = len(L) #number of points in L


# Create the LP problem
prob = plp.LpProblem("Maximize minimal manhattan distance", plp.LpMaximize)

# Define the decision variables
x = plp.LpVariable.dicts("x", range(n), cat = 'Continuous')

#Define the variable to maximize
z = plp.LpVariable("z", lowBound=0, cat = 'Continuous')

print(x, z)

# Define the constraints for x, i.e. the search space constraints
for i in range(n):
   if i == 0:
       prob += x[i] >= model[i][0]
       prob += x[i] <= model[i][1]
   else:
       prob += x[i] >= model[i][0] + x[i-1]
       prob += x[i] <= model[i][1] + x[i-1]
       
# Define the constraints for the absolute value of the difference between x and each point in L
for j in range(m): #for every sigma in L
   
   #prob += z <= plp.lpSum([abs(x[i] - L[j][i]) for i in range(n)])  #this is how it could be if abs() was acceptable

   diff = plp.LpVariable.dicts("diff_" + str(j), range(n), cat = 'Continuous')
   diff_plus = plp.LpVariable.dicts("diff_plus" + str(j), range(n), cat = 'Continuous')
   
   for i in range(n):
       #print(x[i])
       prob += diff[i] == L[j][i] - x[i]
       prob += -diff_plus[i] <= diff[i]  <= diff_plus[i]
   
   prob += z == plp.lpSum([diff_plus[i] for i in range(n)])

# Define the objective function
prob += z

# Solve the problem
prob.solve()

示例数据 #

L = [(0,0,0),(2, 3, 4), (3,6, 7),(4,5, 8), (4,6, 9), (4,7, 10),  (7, 12, 15)]
model = [(0,7),(0,5),(0,3)]

部分可行解示例 #

• [5.0, 10.0, 12.5]
• [5.5, 9.5, 12.5]
• [5.5, 10.0, 12.0]
• [5.5, 10.5, 11.5]
• [6.0, 9.5, 12.0]
• [6.0, 10.0, 11.5]
• [6.0, 10.5, 11.0]
• [6.5, 9.0, 12.0]
• [6.5, 9.5, 11.5]
• [6.5, 10.0, 11.0]
• [6.5, 10.5, 10.5]
• [7.0, 9.0, 11.5]
• [7.0, 9.5, 11.0]
• [7.0, 10.0, 10.5]

错误分析与修正方案 #

核心错误 #

1. 约束逻辑完全偏离问题需求：
   原问题要求z是x到所有L中点的曼哈顿距离的最小值，即对每个j必须满足 z ≤ sum(|x_i - L[j][i]|)。但当前代码中对每个j都强制 z == sum(diff_plus[i])，这意味着只有当x到所有L中点的曼哈顿距离完全相等时才有解，完全不符合极大极小问题的定义，直接导致模型无解或得到错误解。

2. 冗余变量引入：
   引入diff变量完全没必要，直接针对x[i] - L[j][i]的绝对值定义辅助变量即可，简化模型的同时减少计算量。

修正后的代码 #

import pulp as plp

# 示例数据
L = [(0,0,0),(2, 3, 4), (3,6, 7),(4,5, 8), (4,6, 9), (4,7, 10),  (7, 12, 15)]
model = [(0,7),(0,5),(0,3)]

n = len(model)
m = len(L)

# 创建LP问题
prob = plp.LpProblem("Maximize minimal manhattan distance", plp.LpMaximize)

# 决策变量
x = plp.LpVariable.dicts("x", range(n), cat='Continuous')
z = plp.LpVariable("z", lowBound=0, cat='Continuous')

# 搜索空间约束（保留原逻辑，若搜索空间定义不同可自行调整）
for i in range(n):
    if i == 0:
        prob += x[i] >= model[i][0]
        prob += x[i] <= model[i][1]
    else:
        prob += x[i] >= model[i][0] + x[i-1]
        prob += x[i] <= model[i][1] + x[i-1]

# 曼哈顿距离最小值约束：z ≤ 每个点的曼哈顿距离
for j in range(m):
    # 为每个维度的绝对值定义辅助变量
    abs_vars = plp.LpVariable.dicts(f"abs_j{j}_dim", range(n), lowBound=0, cat='Continuous')
    for i in range(n):
        # 绝对值约束：abs_vars[i] ≥ |x[i] - L[j][i]|
        prob += abs_vars[i] >= x[i] - L[j][i]
        prob += abs_vars[i] >= L[j][i] - x[i]
    # z 不超过当前点的曼哈顿距离
    prob += z <= plp.lpSum(abs_vars[i] for i in range(n))

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

# 求解并输出结果
prob.solve()

print("最优解x：")
for i in range(n):
    print(f"x[{i}] = {plp.value(x[i])}")
print(f"最大最小曼哈顿距离z = {plp.value(z)}")

修正说明 #

• 将每个点的约束从z == sum(...)改为z <= sum(...)，确保z是所有曼哈顿距离的最小值
• 简化绝对值约束的实现：直接用abs_vars[i] >= x[i]-L[j][i]和abs_vars[i] >= L[j][i]-x[i]来表示abs_vars[i] = |x[i]-L[j][i]|，无需额外的diff变量
• 保留原搜索空间约束逻辑，若你的搜索空间S定义不同（比如是各维度独立的区间），可自行调整这部分代码

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