实施最小成本流算法或有条件的组分配
Implementing Minimum Cost Flows algorithm or group allocation with conditions
我正在尝试根据参与者的偏好将参与者分配到组 Tn 和子组 TnSm。我正在使用 Python 中 Google 中的 OR 工具来使用最小成本流方法。考虑以下 table 首选项：
T1S1 T1S2 T1S3 T2S1 T2S2 T2S3
name1 1 0 3 2 2 3
name2 2 1 1 1 0 1
name3 0 2 1 2 2 3
name4 3 2 3 3 0 0
name5 1 0 2 3 1 2
...
两组 Tn 共有 6 个点，由 3 个子组 TnSm 组成，每个子组有 2 个点。我有以下几个条件：
- 总人数参与者的人数小于或等于所有小组人数的总和 (=12)
- 每个参与者可以属于 1 - 3 个子组，但前提是这些子组属于同一组
- 这 12 个小组名额中的每个名额都需要分配一名参与者
我可以通过在源端为每个参与者创建一个容量为 3 的节点，在汇点为每个子组创建一个容量为 2 的节点来将参与者分配到多个子组：
capacities = [3,3,3,3,...] + [1,1,1,1...] + [2,2,2,2,2,2]
但是，如果某个特定的子组属于组 Tn，我现在如何才能确保该参与者仅被分配到第二或第三个子组？
if min_cost_flow_2.SolveMaxFlowWithMinCost() == min_cost_flow_2.OPTIMAL:
print('Minimum cost:', min_cost_flow_2.OptimalCost(), min_cost_flow_2.MaximumFlow())
for arc in range(min_cost_flow_2.NumArcs()):
if min_cost_flow_2.Tail(arc) != source and min_cost_flow_2.Head(arc) != sink:
if min_cost_flow_2.Flow(arc) > 0:
print(" ")
print("***worker %d assigned to team %d at cost: %d" % (min_cost_flow_2.Tail(arc),min_cost_flow_2.Head(arc),min_cost_flow_2.UnitCost(arc)))
这是我的草草提议。
注意：我添加了约束
- 参与者不能同时使用子组的两个位置。
#!/usr/bin/env python3
from ortools.sat.python import cp_model
def main():
participants = [
"name1",
"name2",
"name3",
"name4",
"name5",
"name6",
"name7",
"name8",
#"name9",
#"name10",
#"name11",
#"name12",
]
preferences = [
#T0 T0 T0 T0 T0 T0 T1 T1 T1 T1 T1 T1
#S0 S0 S1 S1 S2 S2 S0 S0 S1 S1 S2 S2
# a b a b a b a b a b a b
[1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3], # 1
[2, 2, 3, 3, 1, 1, 1, 1, 0, 0, 1, 1], # 2
[0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3], # 3
[3, 3, 2, 2, 3, 3, 3, 3, 0, 0, 0, 0], # 4
[1, 1, 0, 0, 2, 2, 3, 3, 1, 1, 2, 2], # 5
[1, 1, 0, 0, 3, 3, 2, 2, 3, 3, 2, 2], # 6
[2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1], # 7
[0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3], # 8
[3, 3, 1, 1, 0, 0, 3, 3, 0, 0, 2, 2], # 9
[1, 1, 0, 0, 2, 2, 3, 3, 0, 0, 2, 2], # 10
[1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3], # 11
[2, 2, 1, 1, 0, 0, 3, 3, 2, 2, 1, 1], # 12
]
num_participants = len(participants)
all_participants = range(num_participants)
num_groups = 2
all_groups = range(num_groups)
num_sub_groups = 3
all_sub_groups = range(num_sub_groups)
num_sub_groups_spots = 2
all_sub_groups_spots = range(num_sub_groups_spots)
# 2 spots per TxSy
# Create Model
model = cp_model.CpModel()
# Variables
# True if the participant is assigned to this spot
x = {}
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
x[(p, tn, sg, sg_s)] = model.NewBoolVar(
f"x[{participants[p]},{tn},{sg},{sg_s}]")
# True is the participant is assigned to this group
y = {}
for p in all_participants:
for tn in all_groups:
y[(p, tn)] = model.NewBoolVar(f"y[{participants[p]},{tn}]")
# Constraints
# Each spots is assigned to exactly one participant.
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
model.Add(
sum(x[(n, tn, sg, sg_s)] for n in all_participants) == 1)
# Each participant can't use both spots of any sub groups of any groups.
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
model.Add(
sum(x[(p, tn, sg, n)] for n in all_sub_groups_spots) <= 1)
# Each participant is assigned to exactly one group.
for p in all_participants:
model.Add(sum(y[(p, n)] for n in all_groups) == 1)
# A participant work in a group if it is assigned to at least one spots in the group
for p in all_participants:
for tn in all_groups:
# implement y[(p, tn)] == (sum(x[(p, tn, *, *)]) >= 1)
model.Add(
sum(x[(p, tn, n, m)] for n in all_sub_groups
for m in all_sub_groups_spots) >= 1).OnlyEnforceIf(
y[(p, tn)])
# implement not y[(p, tn)] == (sum(x[(p, tn, *, *)]) == 0)
model.Add(
sum(x[(p, tn, n, m)] for n in all_sub_groups
for m in all_sub_groups_spots) == 0).OnlyEnforceIf(
y[(p, tn)].Not())
#model.Minimize(
model.Maximize(
sum([
x[(p, tn, sg, sg_s)] * preferences[p][tn * sg * sg_s + sg * sg_s + sg_s]
for p in all_participants
for tn in all_groups
for sg in all_sub_groups
for sg_s in all_sub_groups_spots
]))
# Creates the solver and solve.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print('Maximum cost = %i' % solver.ObjectiveValue())
print()
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
if solver.Value(x[(p, tn, sg, sg_s)]) == 1:
print(
f'Participant: {participants[p]}, assigned to T{tn}S{sg}:{sg_s}, Preference({preferences[p][tn*sg*sg_s+sg*sg_s+sg_s]})'
)
# Statistics.
print()
print('Statistics')
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())
if __name__ == '__main__':
main()
解决方案：
./assignment.py
Maximum cost = 27
Participant: name1, assigned to T0S0:1, Preference(1)
Participant: name2, assigned to T0S1:1, Preference(3)
Participant: name3, assigned to T1S1:1, Preference(2)
Participant: name4, assigned to T1S0:0, Preference(3)
Participant: name4, assigned to T1S1:0, Preference(3)
Participant: name4, assigned to T1S2:0, Preference(3)
Participant: name5, assigned to T1S0:1, Preference(1)
Participant: name6, assigned to T1S2:1, Preference(3)
Participant: name7, assigned to T0S0:0, Preference(2)
Participant: name7, assigned to T0S1:0, Preference(2)
Participant: name7, assigned to T0S2:0, Preference(2)
Participant: name8, assigned to T0S2:1, Preference(2)
Statistics
- conflicts : 508560
- branches : 544413
- wall time : 42.424461 s
我正在尝试根据参与者的偏好将参与者分配到组 Tn 和子组 TnSm。我正在使用 Python 中 Google 中的 OR 工具来使用最小成本流方法。考虑以下 table 首选项：
T1S1 T1S2 T1S3 T2S1 T2S2 T2S3
name1 1 0 3 2 2 3
name2 2 1 1 1 0 1
name3 0 2 1 2 2 3
name4 3 2 3 3 0 0
name5 1 0 2 3 1 2
...
两组 Tn 共有 6 个点，由 3 个子组 TnSm 组成，每个子组有 2 个点。我有以下几个条件：
- 总人数参与者的人数小于或等于所有小组人数的总和 (=12)
- 每个参与者可以属于 1 - 3 个子组，但前提是这些子组属于同一组
- 这 12 个小组名额中的每个名额都需要分配一名参与者
我可以通过在源端为每个参与者创建一个容量为 3 的节点，在汇点为每个子组创建一个容量为 2 的节点来将参与者分配到多个子组：
capacities = [3,3,3,3,...] + [1,1,1,1...] + [2,2,2,2,2,2]
但是，如果某个特定的子组属于组 Tn，我现在如何才能确保该参与者仅被分配到第二或第三个子组？
if min_cost_flow_2.SolveMaxFlowWithMinCost() == min_cost_flow_2.OPTIMAL:
print('Minimum cost:', min_cost_flow_2.OptimalCost(), min_cost_flow_2.MaximumFlow())
for arc in range(min_cost_flow_2.NumArcs()):
if min_cost_flow_2.Tail(arc) != source and min_cost_flow_2.Head(arc) != sink:
if min_cost_flow_2.Flow(arc) > 0:
print(" ")
print("***worker %d assigned to team %d at cost: %d" % (min_cost_flow_2.Tail(arc),min_cost_flow_2.Head(arc),min_cost_flow_2.UnitCost(arc)))
这是我的草草提议。
注意：我添加了约束
- 参与者不能同时使用子组的两个位置。
#!/usr/bin/env python3
from ortools.sat.python import cp_model
def main():
participants = [
"name1",
"name2",
"name3",
"name4",
"name5",
"name6",
"name7",
"name8",
#"name9",
#"name10",
#"name11",
#"name12",
]
preferences = [
#T0 T0 T0 T0 T0 T0 T1 T1 T1 T1 T1 T1
#S0 S0 S1 S1 S2 S2 S0 S0 S1 S1 S2 S2
# a b a b a b a b a b a b
[1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3], # 1
[2, 2, 3, 3, 1, 1, 1, 1, 0, 0, 1, 1], # 2
[0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3], # 3
[3, 3, 2, 2, 3, 3, 3, 3, 0, 0, 0, 0], # 4
[1, 1, 0, 0, 2, 2, 3, 3, 1, 1, 2, 2], # 5
[1, 1, 0, 0, 3, 3, 2, 2, 3, 3, 2, 2], # 6
[2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1], # 7
[0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3], # 8
[3, 3, 1, 1, 0, 0, 3, 3, 0, 0, 2, 2], # 9
[1, 1, 0, 0, 2, 2, 3, 3, 0, 0, 2, 2], # 10
[1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3], # 11
[2, 2, 1, 1, 0, 0, 3, 3, 2, 2, 1, 1], # 12
]
num_participants = len(participants)
all_participants = range(num_participants)
num_groups = 2
all_groups = range(num_groups)
num_sub_groups = 3
all_sub_groups = range(num_sub_groups)
num_sub_groups_spots = 2
all_sub_groups_spots = range(num_sub_groups_spots)
# 2 spots per TxSy
# Create Model
model = cp_model.CpModel()
# Variables
# True if the participant is assigned to this spot
x = {}
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
x[(p, tn, sg, sg_s)] = model.NewBoolVar(
f"x[{participants[p]},{tn},{sg},{sg_s}]")
# True is the participant is assigned to this group
y = {}
for p in all_participants:
for tn in all_groups:
y[(p, tn)] = model.NewBoolVar(f"y[{participants[p]},{tn}]")
# Constraints
# Each spots is assigned to exactly one participant.
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
model.Add(
sum(x[(n, tn, sg, sg_s)] for n in all_participants) == 1)
# Each participant can't use both spots of any sub groups of any groups.
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
model.Add(
sum(x[(p, tn, sg, n)] for n in all_sub_groups_spots) <= 1)
# Each participant is assigned to exactly one group.
for p in all_participants:
model.Add(sum(y[(p, n)] for n in all_groups) == 1)
# A participant work in a group if it is assigned to at least one spots in the group
for p in all_participants:
for tn in all_groups:
# implement y[(p, tn)] == (sum(x[(p, tn, *, *)]) >= 1)
model.Add(
sum(x[(p, tn, n, m)] for n in all_sub_groups
for m in all_sub_groups_spots) >= 1).OnlyEnforceIf(
y[(p, tn)])
# implement not y[(p, tn)] == (sum(x[(p, tn, *, *)]) == 0)
model.Add(
sum(x[(p, tn, n, m)] for n in all_sub_groups
for m in all_sub_groups_spots) == 0).OnlyEnforceIf(
y[(p, tn)].Not())
#model.Minimize(
model.Maximize(
sum([
x[(p, tn, sg, sg_s)] * preferences[p][tn * sg * sg_s + sg * sg_s + sg_s]
for p in all_participants
for tn in all_groups
for sg in all_sub_groups
for sg_s in all_sub_groups_spots
]))
# Creates the solver and solve.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print('Maximum cost = %i' % solver.ObjectiveValue())
print()
for p in all_participants:
for tn in all_groups:
for sg in all_sub_groups:
for sg_s in all_sub_groups_spots:
if solver.Value(x[(p, tn, sg, sg_s)]) == 1:
print(
f'Participant: {participants[p]}, assigned to T{tn}S{sg}:{sg_s}, Preference({preferences[p][tn*sg*sg_s+sg*sg_s+sg_s]})'
)
# Statistics.
print()
print('Statistics')
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())
if __name__ == '__main__':
main()
解决方案：
./assignment.py
Maximum cost = 27
Participant: name1, assigned to T0S0:1, Preference(1)
Participant: name2, assigned to T0S1:1, Preference(3)
Participant: name3, assigned to T1S1:1, Preference(2)
Participant: name4, assigned to T1S0:0, Preference(3)
Participant: name4, assigned to T1S1:0, Preference(3)
Participant: name4, assigned to T1S2:0, Preference(3)
Participant: name5, assigned to T1S0:1, Preference(1)
Participant: name6, assigned to T1S2:1, Preference(3)
Participant: name7, assigned to T0S0:0, Preference(2)
Participant: name7, assigned to T0S1:0, Preference(2)
Participant: name7, assigned to T0S2:0, Preference(2)
Participant: name8, assigned to T0S2:1, Preference(2)
Statistics
- conflicts : 508560
- branches : 544413
- wall time : 42.424461 s