I am trying to assign participants to groups Tn and subgroups TnSm based on their preferences. I am using the Minimum Cost Flow method by utilizing OR tools from Google in Python. Consider the following table of preferences:
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
...
Both groups Tn have a total of 6 spots and consist of 3 subgroups TnSm with 2 spots each. I have a few conditions as listed below:
I can allocate participants to several subgroups by creating a node for each participant with capacity=3 at the source and a node for each subgroup with the capacity=2 at the sink:
capacities = [3,3,3,3,...] + [1,1,1,1...] + [2,2,2,2,2,2]
But how can I now make sure that a participant is only allocated to 2nd or 3rd subgroup if that particular subgroup is part of the group 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)))
Here my quick and dirty proposal.
note: I added the constraint
#!/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()
solution:
./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