With python and pulp I'm trying to solve a problem using linear programming.
I have this working code below which creates a multipoint swap solution based on allowed swaps. The problem is, I want to be able to limit the maximum number of participants in a multi-way swap. For example I would like to be able to limit the swaps to three-way swaps.
import pulp
# Sample data: List of requests
participants = ['Alice', 'Bob', 'Charlie', 'David']
weights = {'Alice': 1, 'Bob': 3, 'Charlie': 2, 'David': 1}
# Sample data: Define which swaps are allowed based on your constraints. e.g. Alice to Bob
allowed_swaps = [('Alice', 'Bob'), ('Bob', 'Alice'), ('Bob', 'Charlie'), ('Charlie', 'David'),
('Charlie', 'Alice'), ('Charlie', 'Bob'), ('David', 'Alice')]
swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')
model = pulp.LpProblem("DutySwap", pulp.LpMaximize)
model += pulp.lpSum((1000 + weights[p1] + weights[p2]) * swaps[(p1, p2)] for (p1, p2) in allowed_swaps)
for p in participants:
model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p) <= 1
model += pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p) <= 1
model += (pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p)
== pulp.lpSum(swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p))
print(model)
status = model.solve()
for (p1, p2) in allowed_swaps:
if pulp.value(swaps[(p1, p2)]) == 1:
print(f"{p1}'s duty goes to {p2}")
# This will output
# Alice's duty goes to Bob
# Bob's duty goes to Charlie
# Charlie's duty goes to David
# David's duty goes to Alice
With the allowed swaps entered I would like to be able to limit the multi-way swap to (for example) a three-way swap which in this case would result in.
# Alice's duty goes to Bob
# Bob's duty goes to Charlie
# Charlie's duty goes to Alice
I can't think of a way to enter constraints which make this possible. Do you have an idea for a solution? Thank you!