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

Question

我已经研究同一段代码很长一段时间了，但尚未找到解决方案。

我使用 python PuLP 来解决任务交换优化作为 LP 问题。

我想在我的代码中引入一个变量来限制多点值班交换的步骤数。

每个人都会始终履行一项职责。如果你把责任交给别人，你总是需要收回责任。

当前代码。

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

我想引入一个变量 X，如果将其设置为 1 将导致

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

如果变量 X 设置为 2 将导致

# 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

如果变量 X 设置为 3 将导致

# 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

在 Reinderien 提出问题后添加更多信息。

• 代码最大化交换次数（lpMaximize）
• 限制如下
  • 每位参与者只能放弃一次职责
  • 每位参与者只能领取一次任务
  • 对于每个参与者，放弃的职责数量等于收到的职责数量（0 或 1）
• 一对一互换是职责 A 转到 B，职责 B 转到 A 的互换。三点互换是职责 A 转到 B，B 转到 C，C 转到 A。

我的目标是能够限制步数。这将减少交换的总数。在给定的最大步骤下，我试图最大化交换次数。

我添加了一个 NX 图来显示参与者之间可能的交换

这段代码最终适用于数百种可能的交换。 希望我的问题很清楚。非常感谢您的帮助！

Answer 1

要正确理解这一点，您需要更改可视化，并调整一些术语。

用这张图：

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()

我们更清楚地看到有向图是高度循环的。

您的问题是一个图重写问题，您需要生成具有以下属性的子图。

X

是一个不好的变量名，而且也偏离了现实。您对

X=1

的描述实际上意味着“输出子图的最大周期 order 必须为 2”； X=2 意味着最大循环阶数为 3，依此类推。

否则，输出子图的属性：

• 还是定向的
• 保留输入图中的所有顶点
• 从输入图中删除一些边
• 它可能有循环，每个未交换职责的参与者都有一个循环
• 每个顶点的度数必须为 2
• 每个顶点必须在一个循环中

希望这可以引导您在 LP 构建时朝着正确的方向前进。如果我有更多时间我可以写一个演示。