[PYTHON] Coordinator and integer linear programming

From the submitted adjustment, I formulated and solved the optimal combination of lunch parties as an integer linear programming.

I solved it with a python optimization package called PuLP.

This article is very easy to understand how to use PuLP. http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

Requirements

First, let's get the adjustment.

** ・ Be sure to participate in some schedule per person ** ** ・ Equalize the number of people for each schedule as much as possible **

Let's do our best to formulate this.

First, $ P $ = (set of members) $ D $ = (set of dates) will do.

For $ p \ in P, d \ in D $

\mathrm{hope}[p][d] = \left\{
\begin{array}{ll}
1 & (p becomes d ○) \\
0 & (p becomes d ×)
\end{array}
\right.

And decide the constant from the result of Mr. Adjustment.

Then set the variables.

$ \ mathrm {attend} [p] [d] = (1or0) $ is a variable that indicates whether $ p $ actually participates in $ d $. $ M $ is the maximum number of participants for each schedule. By aiming to minimize this, it is possible to allocate a uniform number of people to each schedule.

When formulated, it looks like this.

\begin{align}
\mathrm{min} &\ M \\
\mathrm{s.t} \ &\forall d\in D\ \Sigma_{p \in P}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] \leq M \\
&\forall p\in P\ \Sigma_{d \in D}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] = 1

\end{align}

The first constraint is that the number of participants is M or less on each day. The second expression of the constraint is that each person must participate only once.

Let's do this hard.

code

chousei.py

import pulp

date = ["3/8", "3/9", "3/11", "3/15"]
people = #Put a list of member names here

_table = [
[1,1,1,1], 
[0,1,0,0],
[1,1,0,0],
[0,1,1,0],
[1,0,0,0],
[1,1,0,1],
[1,0,0,0],
[0,1,0,1],
[0,1,1,0],
[1,1,1,1],
[1,1,1,1],
[1,1,0,0],
[1,0,0,1],
[0,1,1,1],
[0,1,0,0],
[1,1,1,1]] #Write the result of Mr. Adjustment


table = {}
for i,p in enumerate(people):
    table[p] = {}
    for j,d in enumerate(date):
        table[p][d] = _table[i][j]
#Convert to dictionary type

problem = pulp.LpProblem('chousei', pulp.LpMinimize)
attend = pulp.LpVariable.dicts('attend', (people, date), 0, 1, 'Binary')
M = pulp.LpVariable('M', 0, 1000, 'Integer')
problem += M

for p in people:
    each_people = 0
    for d in date:
        each_people += table[p][d]*attend[p][d]
    problem += each_people == 1

for d in date:
    each_date = 0
    for p in people:
        each_date += table[p][d]*attend[p][d]
    problem += each_date <= M

problem.solve()

for d in date:
    each_date = ''
    for p in people:
        if(table[p][d] == 1　and attend[p][d].value() > 0):
            each_date += p
    print "{}: {}".format(d, each_date)

Improvement

At this rate, there is a possibility that only the elders will have a set schedule, so I think it's a good idea to give weight to each member and minimize the upper limit of the sum of the weights for each schedule. .. I will explain it when I feel like it.