基于PuLP的无容量设施选址覆盖问题求解结果异常的排查与修正问询

Hey there! Let's walk through each of your three attempts, spot the mistakes, and fix them so you get the optimal solution you're expecting (only selecting location B in most cases).

First Attempt: Incorrect Constraint Logic #

What Went Wrong #

Your constraint setup was backwards. Instead of ensuring each demand point is covered by at least one selected facility, you added constraints that forced any facility capable of covering any demand point to be selected. For example, since location A can cover demands 1 and 5, your code added J["A"] >= 1—that's why both A and B were selected.

Fixed Code #

from pulp import *

# Set of locations J
Locations = ["A", "B","C"]
# Set of demands I
Demands = ["1", "2", "3", "4", "5"]
# Distance matrix
dt = [
    [2, 23, 30, 54, 1], # A
    [3, 1, 2, 2, 3], # B (covers all demands within distance 5)
    [50,65,80,90,100] # C (covers none)
]
# Max distance to be considered covered
s = 5

# Generate coverage matrix correctly (1 if distance <= s, else 0)
covered = []
for row in dt:
    covered_row = [1 if d <= s else 0 for d in row]
    covered.append(covered_row)

# Create problem
prob = LpProblem("Set covering", LpMinimize)

# Decision variables: 1 if location is selected, 0 otherwise
J = LpVariable.dicts("location", Locations, cat='Binary')

# Objective: Minimize number of selected locations
prob += lpSum(J.values()), "Total Locations Selected"

# Correct constraints: Each demand point must be covered by at least one selected location
for demand_idx, demand in enumerate(Demands):
    prob += lpSum([J[loc] * covered[loc_idx][demand_idx] for loc_idx, loc in enumerate(Locations)]) >= 1, f"Cover Demand {demand}"

# Solve and print results
prob.writeLP("SetCovering.lp")
prob.solve()

print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Total Locations = ", value(prob.objective))

Expected Output #

Status: Optimal
location_A = 0.0
location_B = 1.0
location_C = 0.0
Total Locations = 1.0

Second Attempt: Missing Link Between Service and Facility Variables #

What Went Wrong #

You didn't add constraints that connect the ser_customer (service assignment) variables to the use_facility (facility selection) variables. The solver could assign customers to Fac-2 without enabling it because there was no rule saying "you can't use a facility unless it's selected." Also, your objective mixed facility count and distance costs—if your goal is just to minimize facility count, you can drop the distance term.

Fixed Code #

from pulp import *

Customer = [1,2,3,4,5]
Facility = ['Fac-1', 'Fac-2', 'Fac-3']

# Distance dictionary
distance = {
    'Fac-1' : {1 : 54, 2 : 76, 3 : 5, 4 : 76, 5 : 76},
    'Fac-2' : {1 : 1, 2 : 3, 3 : 1, 4 : 8, 5 : 1},
    'Fac-3' : {1 : 45, 2 : 23, 3 : 54, 4 : 87, 5 : 88}
}
# Max distance for coverage
dist_limit = 8

# Create problem
prob = LpProblem("pb", LpMinimize)

# Decision variables
use_facility = LpVariable.dicts("Use Facility", Facility, 0, 1, LpBinary)
# Service variable: 1 if customer i is served by facility j, 0 otherwise
ser_customer = LpVariable.dicts("Service", [(i,j) for i in Customer for j in Facility], 0, 1, LpBinary)

# Objective: Minimize number of facilities selected
prob += lpSum(use_facility.values()), "Total Facilities Selected"

# Constraints
# 1. Each customer must be served by at least one facility that can reach them
for i in Customer:
    prob += lpSum([ser_customer[(i,j)] for j in Facility if distance[j][i] <= dist_limit]) >= 1, f"Cover Customer {i}"

# 2. A customer can only be served by a facility that's been selected
for i in Customer:
    for j in Facility:
        prob += ser_customer[(i,j)] <= use_facility[j], f"Service {i} from {j} Requires Facility"

# Solve and print results
prob.solve()

print("Status:", LpStatus[prob.status])
for v in prob.variables():
    if v.varValue > 0.0001:
        print(v.name, "=", v.varValue)

print("\nEstablished Facilities:")
for j in Facility:
    if use_facility[j].varValue > 0.0001:
        print(f"- {j}")

Expected Output #

Status: Optimal
Service_(1,_'Fac_2') = 1.0
Service_(2,_'Fac_2') = 1.0
Service_(3,_'Fac_2') = 1.0
Service_(4,_'Fac_2') = 1.0
Service_(5,_'Fac_2') = 1.0
Use_Facility_Fac_2 = 1.0

Established Facilities:
- Fac-2

Third Attempt: Missing Facility Selection Variables #

What Went Wrong #

You didn't define binary variables for facility selection—instead, you tried to minimize the covered variables, which don't represent whether a facility is active. This completely misses the core of the facility location problem.

Fixed Code #

from pulp import *

prob = LpProblem('source minimizer', LpMinimize)
dist_limit = 5

sources = ['A', 'B','C']
destinations = list(range(5)) # 0-4

# Distance dictionary
dist = {
    'A': [2, 23, 30, 54, 1],
    'B': [3, 1, 2, 2, 3], # Covers all destinations within dist_limit
    'C':[24,54,12,56,76]
}

# Decision variables: 1 if source is selected, 0 otherwise
select_source = LpVariable.dicts("Select Source", sources, cat='Binary')

# Objective: Minimize number of selected sources
prob += lpSum(select_source.values()), "Total Sources Selected"

# Constraints: Each destination must be covered by at least one selected source that can reach it
for dest in destinations:
    prob += lpSum([select_source[src] for src in sources if dist[src][dest] <= dist_limit]) >= 1, f"Cover Destination {dest}"

# Solve and print results
prob.solve()

print("Status:", LpStatus[prob.status])
for v in prob.variables():
    print(v.name, "=", v.varValue)
print("Total Locations Selected = ", value(prob.objective))

Expected Output #

Status: Optimal
Select_Source_A = 0.0
Select_Source_B = 1.0
Select_Source_C = 0.0
Total Locations Selected = 1.0

Key Takeaways for Facility Location Problems #

• Always define binary variables for facility selection (whether a site is active or not).
• Constraints must ensure every demand point is covered by at least one active facility that can reach it.
• If using service assignment variables, add constraints to link them to facility selection (you can't use a facility that's not active).

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