Combinatorial optimization solves the "problem of assigning class members" based on the student's wishes. This is the Python version of A story about optimizing junior high school committeeing at the minimum cost flow.
--Create a pandas.DataFrame with one record of the student committee's wishes. --The first choice cost is 10 and the second choice cost is 30. --Create a mathematical optimization model (cost minimization) using DataFrame. -Solve Mathematical Optimization Model with a solver to get the assignment.
--Variable: Created as a DataFrame column (1 row, 1 variable). --Objective function: Minimize the total desired cost --Constraints --Up to one committee member can be a student --The committee members meet the fixed number
Create a DataFrame.
import pandas as pd
from pulp import lpDot, lpSum
from ortoolpy import model_min, addbinvars, addvals
lst = [['Taprice', 'Disciplinary committee', 10], ['Aoba', 'Class representative', 10], ['Kaguya', 'Disciplinary committee', 10],
['Chino', 'Class representative', 10], ['mirror', 'Disciplinary committee', 10],
['Taprice', 'Class representative', 30], ['Aoba', 'library Commission', 30], ['Kaguya', 'library Commission', 30],
['Chino', 'Disciplinary committee', 30], ['mirror', 'Class representative', 30]]
need = {"Class representative": 1, "library Commission": 2, "Disciplinary committee": 2}
df = pd.DataFrame(lst, columns=['Name', 'Committee', 'Cost'])
addbinvars(df)
print(df)
Name | Committee | Cost | Var | |
---|---|---|---|---|
0 | Taprice | Disciplinary committee | 10 | v000001 |
1 | Aoba | Class representative | 10 | v000002 |
2 | Kaguya | Disciplinary committee | 10 | v000003 |
3 | Chino | Class representative | 10 | v000004 |
4 | mirror | Disciplinary committee | 10 | v000005 |
5 | Taprice | Class representative | 30 | v000006 |
6 | Aoba | library Commission | 30 | v000007 |
7 | Kaguya | library Commission | 30 | v000008 |
8 | Chino | Disciplinary committee | 30 | v000009 |
9 | mirror | Class representative | 30 | v000010 |
Var column is variable (1: assign, 0: do not assign)
m = model_min()
m += lpDot(df.Cost, df.Var) #Sum of desired costs
for _, gr in df.groupby('Name'):
m += lpSum(gr.Var) <= 1 #Up to one committee member can be a student
for k, gr in df.groupby('Committee'):
m += lpSum(gr.Var) == need[k] #Committee members meet a fixed number
m.solve()
addvals(df)
print(df[df.Val > 0])
Name | Committee | Cost | Var | Val | |
---|---|---|---|---|---|
0 | Taprice | Disciplinary committee | 10 | v000001 | 1 |
3 | Chino | Class representative | 10 | v000004 | 1 |
4 | mirror | Disciplinary committee | 10 | v000005 | 1 |
6 | Aoba | library Commission | 30 | v000007 | 1 |
7 | Kaguya | library Commission | 30 | v000008 | 1 |
In the original article, it is the minimum cost flow problem. In that case, you can use min_cost_flow
from NetworkX.
However, if you want to modify the model, the mathematical optimization model like this article will be easier to handle. The calculation time for mathematical optimization is also fast enough.
Recommended Posts