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

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

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.

Recommended Posts

Junior high school committee
Junior high school committee (NetworkX version)
SIR model that even junior high school students can understand
Let's create an automatic factorization device / Junior High School Mathematics Vol.1
[High school mathematics + python] Logarithmic problem
Script of "Programming book starting from elementary and junior high school students"
Introduction to Python Mathematical Optimization Solving junior high school math problems with pulp
[Python] A junior high school student implemented Perceptron and tried to classify irises.
I tried to refactor the code of Python beginner (junior high school student)