はじめに

今回の学生の配属問題において、効率的で公平な配属を目指してアルゴリズムを開発しました。この問題を解く際に、量的功利主義の考え方を参考にしました。量的功利主義とは、最大多数の最大幸福を追求する倫理理論であり、リソースや利益を最大化しながら全体の幸福度を高めることを目指します。
この投稿では、Pythonと線形計画法を使って学部配属問題を解決する方法を紹介します。Pulpライブラリを使い、各学生の希望順位に基づいて配属する問題を解きます。また、配属先の定員やNGリストも考慮します。

数学的背景: ナップサック問題と線形計画法

このプログラムは、学生を効率的に割り当てるために、線形計画法を用いています。特に、この問題はナップサック問題に類似しています。

ナップサック問題とは？

ナップサック問題は、限られた容量の中に、最大の利益をもたらすアイテムを選択する最適化問題です。学生の割り当て問題も、似たような制約条件を持っています。

容量制約: 実習先ごとに受け入れ可能な学生数（定員）という「容量」が設定されています。
利益（コスト）: 学生の希望順位に基づいて実習先への割り当てを行う際、低い希望順位に割り当てられるほどコスト（不満度）が大きくなります。この不満度を最小化することが目標です。

このプログラムでの最適化

この問題では、学生が希望する実習先とその希望順位を考慮しながら、実習先ごとの定員制約内で学生を実習先に割り当てます。プログラムでは、以下の目的関数と制約を考慮しています。

目的関数
学生の希望順位に応じた割り当てコストの総和を最小化します。具体的には、学生が各実習先に割り当てられる際に、その実習先への希望順位（数値が小さいほど好ましい）に基づいた重み付けを行い、全体のコストを最小化します。

$$ \text{minimize} \quad \sum_{i=1}^{n} \sum_{j=1}^{m} P_{ij} \cdot x_{ij} $$

ここで、$P_{ij}$ は学生 $i$ の実習先　$j$ への希望順位、$x_{ij}$ は学生 $i$ が実習先 $j$ に割り当てられる場合に1、そうでない場合は0です。
制約条件
- 各学生は1つの実習先にのみ割り当てられる（各学生は1つの選択肢しか持たない）。
  
  $$ \sum_{j=1}^{m} x_{ij} = 1 \quad \forall i $$
- 各実習先には定員があり、それを超えることはできない。
  
  $$ \sum_{i=1}^{n} x_{ij} \leq C_j \quad \forall j $$
  
  ここで $C_j$ は実習先 $j$ の定員です。
- NGリストの制約も含まれており、特定の学生同士が同じ実習先に配属されないようにします。
  
  $$ x_{ij} + x_{kj} \leq 1 \quad \text{(NGリストで指定された学生 $i$ と $k$)} $$

解法: 線形計画法（Linear Programming, LP）

このプログラムは、Pythonのpulpライブラリを使って、上記の目的関数と制約条件を満たす最適な割り当てを探索します。線形計画法は、与えられた線形な制約と目的関数のもとで最適な解を見つける手法であり、大規模な最適化問題を効率的に解決できる方法です。

必要なライブラリ

まず、必要なライブラリをインストール・インポートしましょう。

pip install pulp pandas

import pandas as pd
import pulp

クラスの定義

DepartmentalMatchingProblemクラスは、学生データ、NGリスト、実習先データをロードし、配属問題を解決します。

class DepartmentalMatchingProblem:
    def __init__(self, data_file):
        self.data_file = data_file
        self.df_students, self.df_ng, self.df_departments, self.department_caps = self.load_data()

    def load_data(self):
        # Excelファイルからデータを読み込む
        df_students = pd.read_excel(self.data_file, sheet_name='Sheet1')
        df_ng = pd.read_excel(self.data_file, sheet_name='Sheet2', index_col=0)
        df_departments = pd.read_excel(self.data_file, sheet_name='Sheet3')
        department_caps = dict(zip(df_departments['配属先名'], df_departments['定員']))
        return df_students, df_ng, df_departments, department_caps

`load_data()` メソッド

df_students: 学生のデータが入ったDataFrame。
df_ng: 学生が配属を希望しない学部のリスト。
df_departments: 学部名と定員が入ったDataFrame。
department_caps: 実習先の定員を辞書形式に変換。
Here’s how you can describe the structure of the DataFrames (df_students, df_ng, and df_departments) in your Qiita post:

データの構成

このプログラムでは、3つのExcelシートを読み込み、対応するDataFrameを以下のように構成しています。

df_students（Sheet1）
- 各行が学生を表し、列には以下の情報が含まれます:
  - 学籍番号: 学生のID
  - 名前: 学生の名前
  - 第1希望から第n希望までの実習先への希望順位
例:

学籍番号名前消化器外科内分泌内科 ... ...

12345 田中太郎 1 2 3 ...

67890 山田花子 2 1 3 ...
df_ng（Sheet2）
- 各行が学生を表し、特定の学生と一緒に同じ実習先に配属されるべきでない学生のリストを示します。
  - 学籍番号: 学生のID
  - NGリストに含まれる他の学生のID
例:

学籍番号 NG

12345 67890,83425

67890 12345,52353,63262,63
df_departments（Sheet3）
- 各行が実習先を表し、列には以下の情報が含まれます:
  - 配属先名: 実習先名
  - 定員: 各実習先の定員数
例:

配属先名定員

消化器外科 3

内分泌内科 2

配属問題の解法

    def solve(self):
        num_students = len(self.df_students)
        num_departments = len(self.df_departments)

        # 学生と実習先の割り当てを表す変数を作成
        assign = pulp.LpVariable.dicts('assign', ((i, j) for i in range(num_students) for j in range(num_departments)), cat='Binary')

        # 線形計画問題の定義
        problem = pulp.LpProblem('DepartmentalMatchingProblem', pulp.LpMinimize)

        # 目的関数（学生の希望順位を最小化）
        problem += pulp.lpSum([self.df_students.iloc[i, j+2] * assign[(i, j)] for i in range(num_students) for j in range(num_departments)])

        # 各学生は1つの実習先にのみ割り当て
        for i in range(num_students):
            problem += pulp.lpSum([assign[(i, j)] for j in range(num_departments)]) == 1

        # 実習先の定員制約
        for j in range(num_departments):
            problem += pulp.lpSum([assign[(i, j)] for i in range(num_students)]) <= self.department_caps[self.df_departments.iloc[j, 0]]

        # NGリスト制約
        for i in range(num_students):
            for j in range(num_departments):
                if self.df_ng.iloc[i, :].isin([self.df_students.iloc[k, 0] for k in range(num_students)]).any():
                    ng_list = list(self.df_ng.iloc[i, :].dropna())
                    for ng in ng_list:
                        if self.df_students.iloc[i, 0] != ng:
                            problem += assign[(i, j)] + assign[(self.df_students[self.df_students['学籍番号'] == ng].index[0], j)] <= 1

        # 問題を解く
        result = problem.solve(pulp.PULP_CBC_CMD(msg=1, threads=4, timeLimit=100))
        return result, assign

制約条件

各学生は1つの実習先にしか配属されません。
実習先には定員があり、その人数を超えません。
NGリストに記載された学生同士は同じ実習先に配属されません。

配属結果の表示

    def print_results(self, assign):
        num_students = len(self.df_students)
        num_departments = len(self.df_departments)

        # 学生ごとの配属結果を表示
        for i in range(num_students):
            for j in range(num_departments):
                if assign[(i, j)].value() == 1:
                    print(f"{self.df_students.iloc[i, 0]}: {self.df_students.iloc[i, 1]} -> {self.df_departments.iloc[j, 0]}")

        # 学部ごとの配属学生リストを表示
        assignments = {}
        for i in range(num_students):
            for j in range(num_departments):
                if assign[(i, j)].value() == 1:
                    if self.df_departments.iloc[j, 0] not in assignments:
                        assignments[self.df_departments.iloc[j, 0]] = []
                    assignments[self.df_departments.iloc[j, 0]].append(self.df_students.iloc[i, 1])
        for department in assignments:
            print(f"{department}:")
            for student in assignments[department]:
                print(f"  {student}")

結果の解釈

学生ごとの配属先を表示。
各実習先に配属された学生リストを実習先別に表示。

配属結果をDataFrameに変換

    def create_assignment_df(self, assign):
        num_students = len(self.df_students)
        num_departments = len(self.df_departments)
        assign_df = pd.DataFrame(index=self.df_students['学籍番号'], columns=self.df_departments['配属先名'])

        for i in range(num_students):
            for j in range(num_departments):
                if assign[(i, j)].value() == 1:
                    assign_df.loc[self.df_students.iloc[i, 0], self.df_departments.iloc[j, 0]] = 1
                else:
                    assign_df.loc[self.df_students.iloc[i, 0], self.df_departments.iloc[j, 0]] = 0
        return assign_df

まとめ

学生の希望順位、NGリスト、実習先定員を考慮して最適な実習先配属を決定しました。これにより大規模なデータに関しても迅速に配属先を決定することが可能です。

pandasのindex使用することでexcelのカラムの名前に依存しないで実装することも可能です。また、シンプルなコードであるので三次元に拡張することにより、応用性もある気がします。