Search code examples
pythonlinear-programmingpulp

Linear Programming problem with variable multi-way duty swap

I have been working on the same bit of code for quite some time but have not yet found a solution.

I used python PuLP to solve a duty swapping optimization as an LP problem.

I want to introduce a variable in my code that limits the number of steps of a multipoint duty swap.

Everyone will always keep one duty. If you give your duty to someone else, you always need to get a duty back.

Current code.

import pulp

# Sample data: List of requests
participants = ['Amy', 'Blake', 'Claire', 'Drew', 'Emma', 'Flynn', 'Gabi', 'Hana', 'Izzy', 'Jill']

# Sample data: Define which swaps are allowed based on your constraints. e.g. Alice to Bob
allowed_swaps = [('Amy', 'Blake'), ('Blake', 'Claire'), ('Claire', 'Drew'), ('Drew', 'Emma'),
                 ('Emma', 'Flynn'), ('Flynn', 'Gabi'), ('Gabi', 'Hana'), ('Hana', 'Izzy'),
                 ('Izzy', 'Jill'), ('Jill', 'Amy'),
                 # one on one
                 ('Blake', 'Amy'), ('Emma', 'Drew'),
                 # three point
                 ('Gabi', 'Emma'),
                 # four point
                 ('Flynn', 'Claire'), ('Jill', 'Gabi')]


swaps = pulp.LpVariable.dicts('Swap', allowed_swaps, cat='Binary')


model = pulp.LpProblem("DutySwap", pulp.LpMaximize)

model += pulp.lpSum(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
# Amy's duty goes to Blake
# Blake's duty goes to Claire
# Claire's duty goes to Drew
# Drew's duty goes to Emma
# Emma's duty goes to Flynn
# Flynn's duty goes to Gabi
# Gabi's duty goes to Hana
# Hana's duty goes to Izzy
# Izzy's duty goes to Jill
# Jill's duty goes to Amy

I would like to introduce a variable X which if set to 1 would result in

# Amy's duty goes to Blake
# Blake's duty goes to Amy
# Drew's duty goes to Emma
# Emma's duty goes to Drew

If variable X is set to 2 would result in

# Amy's duty goes to Blake
# Blake's duty goes to Amy

# Emma's duty goes to Flynn
# Flynn's duty goes to Gabi
# Gabi's duty goes to Emma

If variable X is set to 3 would result in

# Amy's duty goes to Blake
# Blake's duty goes to Amy

# Claire's duty goes to Drew
# Drew's duty goes to Emma
# Emma's duty goes to Flynn
# Flynn's duty goes to Claire

# Gabi's duty goes to Hana
# Hana's duty goes to Izzy
# Izzy's duty goes to Jill
# Jill's duty goes to Gabby

To add some more information after questions from Reinderien.

  • The code maximizes the number of swaps (lpMaximize)
  • The constraints are as follows
    • Every participant can only give his duty away once
    • Every participant can only receive a duty once
    • For every participant the number of duties given away is equal to the number of duties received (0 or 1)
  • A one-on-one swap is a swap where duty A goes to B and duty B to A. A three point swap would be Duty A goes to B, B to C and C to A.

My goal is to be able to limit the number of steps. This will reduce the total number of swaps as a result. With a given maximum of steps I'm trying to maximize the number of swaps.

I added a NX graph to show the possible swaps between participants Allowed swaps between participants

This code would eventually work for hundreds of possible swaps. Hope my question is clear. Thank you very much for your help!

Solution

  • To understand this properly you need to change the visualisation, and adjust some of your terminology.

    With this graph:

    import matplotlib.pyplot as plt
import networkx


edges = [
    ('Amy', 'Blake'), ('Blake', 'Claire'), ('Claire', 'Drew'), ('Drew', 'Emma'),
    ('Emma', 'Flynn'), ('Flynn', 'Gabi'), ('Gabi', 'Hana'), ('Hana', 'Izzy'),
    ('Izzy', 'Jill'), ('Jill', 'Amy'),
    # one on one
    ('Blake', 'Amy'), ('Emma', 'Drew'),
    # three point
    ('Gabi', 'Emma'),
    # four point
    ('Flynn', 'Claire'), ('Jill', 'Gabi'),
]
edges += [
    (vertex, vertex)
    for vertex in {
        edge[0] for edge in edges
    }
]

graph = networkx.DiGraph(edges)
networkx.draw_spring(
    graph,
    with_labels=True, font_color='white',
    connectionstyle='arc3, rad=0.3',
    node_size=1500,
)
plt.show()

    digraph

    we more clearly see the digraph as being highly cyclic.

    Your problem is a graph rewriting problem where you need to produce a subgraph with the following properties.

    X is a bad variable name and is also offset from reality. Your description for X=1 actually means "the output subgraph must have a maximum cycle order of 2"; X=2 implies maximum cycle order of 3, and so on.

    Otherwise, properties of the output subgraph:

    • It is still directed
    • All vertices are preserved from the input graph
    • Some edges are removed from the input graph
    • It may have loops, one per participant that has not swapped duties
    • Every vertex must have degree 2
    • Every vertex must be in a cycle

    The loop effect can be implemented by an exclusion constraint where the number of binary selectors for any vertex is at most one:

    import networkx
import pulp

edges = [
    ('Amy', 'Blake'), ('Blake', 'Claire'), ('Claire', 'Drew'), ('Drew', 'Emma'),
    ('Emma', 'Flynn'), ('Flynn', 'Gabi'), ('Gabi', 'Hana'), ('Hana', 'Izzy'),
    ('Izzy', 'Jill'), ('Jill', 'Amy'),
    # one on one
    ('Blake', 'Amy'), ('Emma', 'Drew'),
    # three point
    ('Gabi', 'Emma'),
    # four point
    ('Flynn', 'Claire'), ('Jill', 'Gabi'),
]

graph = networkx.DiGraph(edges)
X = 2
max_cycle_order = X + 1
cycles = tuple(networkx.simple_cycles(graph, length_bound=max_cycle_order))
cycle_names = ['_'.join(c) for c in cycles]
cycle_orders = [len(c) for c in cycles]
selectors = pulp.LpVariable.matrix(
    name='cycle', indices=cycle_names, cat=pulp.LpBinary,
)

prob = pulp.LpProblem(name='swaps', sense=pulp.LpMaximize)
prob.setObjective(pulp.lpDot(selectors, cycle_orders))

for vertex in graph.nodes:
    group = [
        selector
        for selector, cycle in zip(selectors, cycles)
        if vertex in cycle
    ]
    prob.addConstraint(
        name=f'excl_{vertex}',
        constraint=pulp.lpSum(group) <= 1,
    )

prob.solve()
assert prob.status == pulp.LpStatusOptimal

print('Selected cycles:')
for cycle, selector in zip(cycles, selectors):
    if selector.value() > 0.5:
        print(', '.join(cycle))

    Selected cycles:
Flynn, Gabi, Emma
Blake, Amy