本記事では，一般割り当て問題として，実験テーマの割り振り問題をPythonで解いてみたいと思います．
以下の記事を参考にさせて頂きました．
問題設定
大学の実験授業で、学生をいくつかの実験テーマに割り当てるとき、各学生に1～3希望のアンケートを取ったうえで、できるだけ希望が通るように割り当てることを考えます。
具体的には、今回は以下のような状況を考えます。
条件
- 学生は50名
- 実験テーマは15個
- 学生は15個のテーマに対して、1～3希望を付ける。
- 制約条件１：学生は3つの必ずテーマをするように割り当てる。
- 制約条件２：各テーマには10人∼11人にするようにする（しかし、この場合すべてのテーマに10人ずつしかありえない。(コード中の数字を変えるだけで8~12人のようにすることも可能）。
Pulpのインストール
このような問題をPythonで解くときは，Pythonのライブラリ『PuLP』を用いると簡単です．PuLPは以下でインストールできます．
pip install pulp
解法とコードの解説
今回は、行ラベルにテーマ、列ラベルに学生をとったExcelのデータ（つまり、15（行）×50（列）の表）を用意し、このプラグラムを実行すると割り当て表が出力されるようにしました。この準備するExcelの表には、縦方向に1,2,3のいずれかの数字が各1つずつどこかのテーマに入力されており、割り当てるときにこの値を最大化するので、1は第3希望、2は第2希望、3は第1希望ということになります。例えば、学生が出した希望調査票の第1希望のテーマのところに3と入力することになります。
例えば，以下のようなExcelファイルです．
割当最適化のコードは以下の通りです。このプログラムを実行するには、theme_user.xlsxというExcelデータを正しいディレクトリ（何も書き換えないならば、このPythonデータと同じところ）に用意しておく必要があります。
#excelから読み込み割り当てる。
#第一希望を3,第二希望を2,第三希望を1とし、最大化する。
#reference:https://qiita.com/cheerfularge/items/d1474c4f3ad65a34941c
import pulp
import random
import numpy as np
import xlrd
import xlwt
import pprint
def main():
#excelからデータを持ってくる。縦軸にテーマ(i)、横軸に人（j)
book = xlrd.open_workbook('theme_user.xlsx')
sheet = book.sheet_by_name('Sheet1')
def get_list(sheet):
return [sheet.row_values(row) for row in range(sheet.nrows)]
W = get_list(sheet)
W = np.array(W) #リストをnumpyに変換
n = sheet.ncols #人の数
theme = sheet.nrows #テーマの数
print('人数',n)
print('テーマの数',theme)
#GPAを配慮
for j in range(n):
k = random.uniform(2.0,4.0)
for i in range(theme):
W[i,j] = k*W[i,j]
# 各行を割合に変換
# sumbox = W.sum(axis=0, dtype='float')
# W /= sumbox
# 問題の宣言
problem = pulp.LpProblem(name='allocation theme', sense=pulp.LpMaximize)
# 変数の宣言
x = {(i,j):pulp.LpVariable(name='x_{}_{}'.format(i, j), cat='Binary') for i in range(theme) for j in range(n)}
# 目的関数
problem += pulp.lpSum([W[i,j]*x[i,j] for i in range(theme) for j in range(n)])
#一つのテーマには10～11人
for i in range(theme):
problem.addConstraint((pulp.lpSum([x[i,j] for j in range(n)]) >= 10),"seat_limitation_{}".format(i))
problem.addConstraint((pulp.lpSum([x[i,j] for j in range(n)]) <= 11),"seat_limitation2_{}".format(i))
#ユーザーは3つのテーマを行う
for j in range(n):
problem.addConstraint((pulp.lpSum([x[i,j] for i in range(theme)]) == 3),"user_gets_onlyoneseat_{}".format(j))
status = problem.solve()
print(pulp.LpStatus[status])
print("目的関数値 = {}".format(pulp.value(problem.objective)))
for j in range(n):
for i in range(theme):
if pulp.value(x[i,j]) > 0:
print(f'user {j} theme {i} : {pulp.value(x[i,j])}')
#Wを表示
print('割当完了！！！')
#1人り当たりのテーマ数を確認
for j in range(n):
a = 0 #選んだテーマの数
for i in range(theme):
if W[i,j] > 0:
a += 1
print(f'user {j} : {a}' )
#テーマごとの人数を確認
for i in range(theme):
b = 0
for j in range(n):
if pulp.value(x[i,j]) > 0:
b += 1
print(f'theme {i} : {b}')
#結果をexcelに書き込み
output = xlwt.Workbook()
sheet = output.add_sheet('Sheet2')
c = np.zeros([theme,n])
for i in range(theme):
for j in range(n):
if pulp.value(x[i,j]) > 0:
c[i,j] = 1
for i in range(theme):
for j in range(n):
sheet.write(i, j, c[i,j])
output.save('output.xls')
if __name__ == '__main__':
main()
実行したとき、「テーマの数」の下に「Optimal」と出ていれば成功ですが，
しかし，新しいxlrdを使っていると
raise XLRDError(FILE_FORMAT_DESCRIPTIONS[file_format]+'; not supported') xlrd.biffh.XLRDError: Excel xlsx file; not supported
というエラーが出るので，
pip install xlrd==1.2.0
で古いバージョンに戻すか，新しいxlrdのバージョンに合わせてプログラムを書く必要があります．
そして、「割当完了！！！」の下に、確認として学生（user）ごとのテーマを選んだ数と（入力Excelデータtheme_user.xlsxが正しければすべて3になっているはず）、テーマごとの人数が出てきます（10人ずつになってると思います）。
「割当完了！！！」の上は、その学生がどのテーマに割り当てられたかを意味します。
同じディレクトリに、以下のようなoutput.xlsというファイルが出力されていると思います。これが割り当て表です。
リストからnumpyにわざわざ変換しなければならないようにした理由は特にありません。参考にしたプログラムがnumpyだったので、Excelと対応付けるためにリストに変換しました。多分、リストのままでもできるのではないかと思います（PuLP次第ですが、分かりません）。
今回は15（テーマ数）×50（学生数）で行いましたが、コードの制約条件の数字を変えるだけであらゆる状況に応用できます（そもそも解がない問題は無理）。
また、今回は希望順位のみで判断しましたが、Excelデータに学生ごとにGPA数などの補正項をかけることで学生に成績による有利不利を付けることができます（コード内に打ち込んでももちろん可能）。コードには、コメントアウトしてありますが学生のGPAをランダムに決めて優劣をつけることができる部分あるので、疑似的に試したい場合はコメントアウトを外してください。
※この記事は筆者の別ブログから移行したものです．
コメント