多路占空比交换的线性规划问题

Question

使用Python和Pulp，我试图使用线性编程来解决问题。

我有下面的工作代码，它根据允许的交换创建多点交换解决方案。问题是，我希望能够限制多路交换的最大参与者数量。例如，我希望能够将交换限制为三向交换。

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

输入允许的交换后，我希望能够将多路交换限制为（例如）三路交换，在这种情况下会导致。

# Alice's duty goes to Bob
# Bob's duty goes to Charlie
# Charlie's duty goes to Alice

我想不出一种方法来输入使这成为可能的约束。您有解决方案吗？谢谢！

Answer 1

只是限制总交换量？

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