基于L1距离的多2D点：中心距离最小化与内部距离最大化优化求助

现有代码的核心问题 #

1. 点到中心距离的变量复用错误：原代码使用全局的d1、d2变量绑定所有点与中心的偏移，导致所有点的坐标被迫完全相同，必然重叠。每个点需要独立的变量计算L1距离。
2. 内部距离的约束逻辑矛盾：原代码对d1_internal、d2_internal的约束完全错误（例如-d1_internal >= min_internal_distance等价于d1_internal <= -2，同时又限制d1_internal <= 2，形成矛盾约束），导致无解；移除约束后又未正确关联内部距离的计算逻辑，无法影响结果。
3. 目标函数依赖错误的约束/变量：虽然“最小化总到中心距离 - 总内部距离”的思路可行，但变量和约束的错误导致目标无法生效。

修正后的完整实现 #

from ortools.linear_solver import pywraplp

# 配置参数
center = (8, 9)
num_points = 2
min_internal_l1 = 2  # 点间最小L1距离，避免重叠

# 初始化求解器
solver = pywraplp.Solver.CreateSolver('GLOP')
if not solver:
    exit()

# 定义所有点的坐标变量
points = []
for i in range(num_points):
    x = solver.NumVar(0, 1000, f'x_{i}')
    y = solver.NumVar(0, 1000, f'y_{i}')
    points.append((x, y))

# 计算每个点到中心的L1距离（线性化绝对值）
dist_to_center = []
for i in range(num_points):
    x_i, y_i = points[i]
    c_x, c_y = center
    
    # 线性化|x_i - c_x|
    dx = solver.NumVar(0, 1000, f'dx_{i}')
    solver.Add(dx >= x_i - c_x)
    solver.Add(dx >= c_x - x_i)
    
    # 线性化|y_i - c_y|
    dy = solver.NumVar(0, 1000, f'dy_{i}')
    solver.Add(dy >= y_i - c_y)
    solver.Add(dy >= c_y - y_i)
    
    # 该点到中心的L1距离
    dist = solver.NumVar(0, 2000, f'dist_to_center_{i}')
    solver.Add(dist == dx + dy)
    dist_to_center.append(dist)

# 计算点间内部L1距离并添加最小距离约束
internal_dists = []
for i in range(num_points):
    for j in range(i + 1, num_points):
        x_i, y_i = points[i]
        x_j, y_j = points[j]
        
        # 线性化|x_i - x_j|
        dx_ij = solver.NumVar(0, 1000, f'dx_{i}_{j}')
        solver.Add(dx_ij >= x_i - x_j)
        solver.Add(dx_ij >= x_j - x_i)
        
        # 线性化|y_i - y_j|
        dy_ij = solver.NumVar(0, 1000, f'dy_{i}_{j}')
        solver.Add(dy_ij >= y_i - y_j)
        solver.Add(dy_ij >= y_j - y_i)
        
        # 点对(i,j)的L1距离
        dist_ij = solver.NumVar(0, 2000, f'internal_dist_{i}_{j}')
        solver.Add(dist_ij == dx_ij + dy_ij)
        internal_dists.append(dist_ij)
        
        # 强制点间距离不小于最小值，避免重叠
        solver.Add(dist_ij >= min_internal_l1)

# 设置目标函数：最小化总到中心距离，同时最大化总内部距离
total_dist_center = solver.Sum(dist_to_center)
total_internal_dist = solver.Sum(internal_dists)
# 通过线性组合实现多目标优化，可调整权重（如*0.5）改变优先级
solver.Minimize(total_dist_center - total_internal_dist)

# 求解并输出结果
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print("最优解：")
    for i in range(num_points):
        x, y = points[i]
        print(f"点{i}坐标：({x.solution_value():.2f}, {y.solution_value():.2f})")
        print(f"到中心的L1距离：{dist_to_center[i].solution_value():.2f}")
    for idx, dist in enumerate(internal_dists):
        print(f"点对{idx}的L1距离：{dist.solution_value():.2f}")
elif status == pywraplp.Solver.FEASIBLE:
    print("找到可行解，但非最优")
else:
    print("无解")

关键修正说明 #

1. 独立计算每个点的到中心距离：为每个点创建独立的dx_i、dy_i变量，通过线性约束实现绝对值的等价转换，避免所有点坐标绑定。
2. 正确线性化点间L1距离：对每对点的x、y差值分别做绝对值约束，再求和得到L1距离，同时添加最小距离约束确保点不重叠。
3. 多目标优化的合理实现：通过总到中心距离 - 总内部距离的线性组合，在最小化到中心距离的同时最大化点间距离；若需调整优先级，可给内部距离添加权重（如total_dist_center - 0.5 * total_internal_dist）。

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