[PYTHON] Junior high school committee

what is this

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.

policy

--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.

Mathematical optimization model

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

input

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)

Var column is variable (1: assign, 0: do not assign)

Modeling and solving

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)

result

print(df[df.Val > 0])

Supplement

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.