基于Pulp的离散优化求助：带距离约束的选点问题求解

Looks like you're stuck on translating that nonlinear distance constraint into something PuLP can handle — totally understandable, since PuLP only works with linear constraints. Let's break down how to fix this.

First, Clarify the Constraint Logic #

Your original code tried to use np.multiply(x,D).max() < max_dis and np.multiply(x,D).min() > min_dis, but that's not the right way to model "all selected points have pairwise distances within (min_dis, max_dis)". What we actually need to enforce is:

For any two distinct points i and j, if both are selected (x[i] = 1 and x[j] = 1), then their distance D[i][j] must be strictly greater than min_dis and strictly less than max_dis.

Linearize the Constraint #

Since PuLP can't handle max/min or nonlinear checks, we can rephrase this constraint into linear inequalities:

• For every pair of points (i, j) where i < j:
  1. If D[i][j] ≤ min_dis: These two points can't be selected together → add x[i] + x[j] ≤ 1
  2. If D[i][j] ≥ max_dis: These two points can't be selected together → add x[i] + x[j] ≤ 1

This works because we're explicitly forbidding any pair of points that violate the distance range from being in our selected set. All allowed pairs (those with distances in the valid range) can be selected together, which is exactly what we want.

Full Working Code #

Here's how to integrate this into your existing PuLP model. I'll add a sample distance matrix D for demonstration (replace this with your actual matrix):

A = [300, 436, 234, 11, 23, 897, 439, 56, 123, 432]
# Sample N=10 distance matrix (replace with your real D)
D = np.array([
    [0, 200, 150, 50, 80, 300, 250, 100, 180, 220],
    [200, 0, 100, 250, 220, 400, 350, 150, 80, 120],
    [150, 100, 0, 200, 180, 350, 300, 100, 50, 80],
    [50, 250, 200, 0, 30, 350, 300, 150, 230, 270],
    [80, 220, 180, 30, 0, 320, 270, 120, 200, 240],
    [300, 400, 350, 350, 320, 0, 50, 250, 320, 280],
    [250, 350, 300, 300, 270, 50, 0, 200, 270, 230],
    [100, 150, 100, 150, 120, 250, 200, 0, 80, 120],
    [180, 80, 50, 230, 200, 320, 270, 80, 0, 40],
    [220, 120, 80, 270, 240, 280, 230, 120, 40, 0]
])

import pulp
import numpy as np

N = 10
K = 3
min_dis = 100
max_dis = 300

inds = range(N)
# Create 0-1 variables for each point
x = pulp.LpVariable.dicts('x', inds, lowBound=0, upBound=1, cat=pulp.LpInteger)

my_lp_problem = pulp.LpProblem("Maximize_Attribute_Sum_With_Distance_Constraints", pulp.LpMaximize)

# Objective: Maximize sum of selected attributes
my_lp_problem += sum([A[point] * x[point] for point in inds])

# Constraint: Select exactly K points
my_lp_problem += sum([x[store] for store in inds]) == K

# Add distance constraints: forbid pairs with distances outside (min_dis, max_dis)
for i in range(N):
    for j in range(i + 1, N):
        dist = D[i][j]
        if dist <= min_dis or dist >= max_dis:
            # Can't select both i and j
            my_lp_problem += x[i] + x[j] <= 1, f"Forbid_Pair_{i}_{j}"

# Solve the problem
my_lp_problem.solve()

# Print results
print("Status:", pulp.LpStatus[my_lp_problem.status])
selected_points = [i for i in inds if pulp.value(x[i]) == 1]
print(f"Selected points: {selected_points}")
print(f"Total attribute sum: {sum([A[i] for i in selected_points])}")
# Verify pairwise distances
print("Pairwise distances of selected points:")
for i in range(len(selected_points)):
    for j in range(i + 1, len(selected_points)):
        p1 = selected_points[i]
        p2 = selected_points[j]
        print(f"Distance between {p1} and {p2}: {D[p1][p2]}")

Key Notes #

• Strict Inequalities: PuLP handles strict inequalities (like dist > min_dis) by using non-strict ones in practice, since we're dealing with integer variables and discrete distances. If your distances are continuous, you might need to adjust min_dis/max_dis slightly (e.g., use min_dis + 1e-6 if working with floats) to avoid edge cases.
• Feasibility: Make sure there actually exists a set of K points where all pairwise distances fall within your range. If not, the solver will return "Infeasible".
• Efficiency: For larger N (e.g., N > 50), this approach might get slow because we're adding O(N²) constraints. In that case, you could look into more advanced techniques or specialized solvers, but for N=10 it's totally fine.

Why didn't scipy.optimize work? Because scipy's optimizers are primarily designed for continuous variables, and handling 0-1 integer constraints requires specialized integer programming solvers like the ones PuLP interfaces with (CBC, GLPK, etc.).

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