0

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!

1 Answer 1

0

Just limit the total swap?

import pulp


weights = {'Alice': 1, 'Bob': 3, 'Charlie': 2, 'David': 1}
participants = weights.keys()

# 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(name='Swap', indices=allowed_swaps, cat='Binary')

model = pulp.LpProblem('DutySwap', pulp.LpMaximize)
model.objective = pulp.lpDot(
    swaps.values(),
    (
        (1000 + weights[p1] + weights[p2])
        for (p1, p2) in allowed_swaps
    ),
)

for p in participants:
    source_sum = pulp.lpSum(
        swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p1 == p)
    dest_sum = pulp.lpSum(
        swaps[(p1, p2)] for (p1, p2) in allowed_swaps if p2 == p)
    model.addConstraint(source_sum <= 1)
    model.addConstraint(dest_sum <= 1)
    model.addConstraint(source_sum == dest_sum)

model.addConstraint(pulp.lpSum(swaps.values()) <= 3)

print(model)
model.solve()
assert model.status == pulp.LpStatusOptimal

for p1, p2 in allowed_swaps:
    if pulp.value(swaps[(p1, p2)]) > 0.5:
        print(f"{p1:>7s}'s duty goes to {p2}")
  Alice's duty goes to Bob
    Bob's duty goes to Charlie
Charlie's duty goes to Alice
2
  • Thank you for your answer! That would work in this case but I'm trying to use this with 50+ allowed swaps :)
    – Oehoe
    Sep 27 at 5:54
  • If it doesn't work for 4, please add an example to your question
    – Reinderien
    Sep 27 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.