import csv
import re
import time
import pulp
import pandas as pd

rd = lambda p: [r for r in csv.reader(open(p, encoding='utf-8-sig'))][1:]

# データ整形課題で作成した定数
a = [(int(s), int(t)) for s, t, _ in rd('a.csv')]
h = [(int(s), int(r)) for s, r, _ in rd('h.csv')]
d = {int(s): int(v) for s, v in rd('d.csv')}
m = {int(s): int(v) for s, v in rd('m.csv')}

# あらかじめ与えられる定数
b = {int(s): (int(g), int(dp), int(v)) for s, g, dp, v in rd('b.csv')}
e = {(int(s), int(g), int(dp), int(p), int(w)) for s, g, dp, p, w, v in rd('e.csv') if int(v) == 1}
l0 = {(int(g), int(dp), int(p), int(w)) for g, dp, p, w, v in rd('g.csv') if int(v) == 0}
txt = open('sub1_sub2.txt').read()
S1 = set(map(int, re.search(r'Subject1 = ([^;]+)', txt).group(1).split(',')))
S2 = set(map(int, re.search(r'Subject2 = ([^;]+)', txt).group(1).split(',')))

W = range(1, 6)   # 曜日
Pr = range(1, 5)  # 時限
subs = list(b)
GD = sorted({(g, dp) for g, dp, _ in b.values()})

# 科目ごとの担当可能教員と利用可能教室
Ts = {}; Rs = {}
for s, t in a: Ts.setdefault(s, []).append(t)
for s, r in h: Rs.setdefault(s, []).append(r)
sub_by_t = {}; sub_by_r = {}
for s, t in a: sub_by_t.setdefault(t, []).append(s)
for s, r in h: sub_by_r.setdefault(r, []).append(s)

print(f'科目 {len(subs)}, 教員 {len(sub_by_t)}, 教室 {len(sub_by_r)}, クラス {len(GD)}')
print(f'連続科目 {len(S1)}, 固定科目 {len(S2)}')

科目 270, 教員 100, 教室 60, クラス 20
連続科目 20, 固定科目 26

def build_model(cr9=False, cr10=False, cr11=False, cr12=False):
    prob = pulp.LpProblem('timetable', pulp.LpMinimize)
    y = {(s, w, p): pulp.LpVariable(f'y_{s}_{w}_{p}', cat='Binary') for s in subs for w in W for p in Pr}
    x = {(s, t, w, p): pulp.LpVariable(f'x_{s}_{t}_{w}_{p}', cat='Binary') for s in subs for t in Ts[s] for w in W for p in Pr}
    z = {(s, r, w, p): pulp.LpVariable(f'z_{s}_{r}_{w}_{p}', cat='Binary') for s in subs for r in Rs[s] for w in W for p in Pr}
    k = {(g, dp, w, p): pulp.LpVariable(f'k_{g}_{dp}_{w}_{p}', cat='Binary') for g, dp in GD for w in W for p in Pr}
    prob += 0  # 目的関数なし(制約充足問題)

    # CR1: 教員の重複禁止
    for t in sub_by_t:
        for w in W:
            for p in Pr:
                prob += pulp.lpSum(x[(s, t, w, p)] for s in sub_by_t[t]) <= 1
    # CR2: 教室の重複禁止
    for r in sub_by_r:
        for w in W:
            for p in Pr:
                prob += pulp.lpSum(z[(s, r, w, p)] for s in sub_by_r[r]) <= 1
    # CR3, CR5, CR6
    for s in subs:
        g, dp, bs = b[s]
        prob += pulp.lpSum(y[(s, w, p)] for w in W for p in Pr) == bs
        for w in W:
            for p in Pr:
                prob += pulp.lpSum(x[(s, t, w, p)] for t in Ts[s]) == d[s] * y[(s, w, p)]
                prob += pulp.lpSum(z[(s, r, w, p)] for r in Rs[s]) == m[s] * y[(s, w, p)]
    # CR4: クラスの時間帯には高々1科目(授業をするならちょうど1科目)
    for (g, dp) in GD:
        ss = [s for s in subs if b[s][0] == g and b[s][1] == dp]
        for w in W:
            for p in Pr:
                prob += pulp.lpSum(y[(s, w, p)] for s in ss) == k[(g, dp, w, p)]
    # CR7: 固定科目
    for s in S2:
        g, dp, _ = b[s]
        for w in W:
            for p in Pr:
                prob += y[(s, w, p)] == (1 if (s, g, dp, p, w) in e else 0)
    # CR8: 授業不可の時間帯
    for (g, dp, p, w) in l0:
        if (g, dp) in GD:
            prob += k[(g, dp, w, p)] == 0
    # CR9: 連続科目は2時限連続
    if cr9:
        for s in S1:
            for w in W:
                prob += y[(s, w, 1)] == y[(s, w, 2)]
                prob += y[(s, w, 3)] == y[(s, w, 4)]
    # CR10: 2、3時限目に空きを作らない(固定科目や授業不可の時間帯を除く)
    if cr10:
        R3gd = {(g, dp, p, w) for s, g, dp, p, w in e}
        for (g, dp) in GD:
            for w in W:
                for p in (2, 3):
                    if (g, dp, p, w) not in R3gd and (g, dp, p, w) not in l0:
                        prob += k[(g, dp, w, p)] == 1
    # CR11: 一般科目は1日1回まで
    if cr11:
        for s in subs:
            if s not in S1 and s not in S2:
                for w in W:
                    prob += pulp.lpSum(y[(s, w, p)] for p in Pr) <= 1
    # CR12: 連続科目は午後のみ
    if cr12:
        for s in S1:
            for w in W:
                prob += y[(s, w, 1)] == 0
                prob += y[(s, w, 2)] == 0
    return prob, y

prob, y = build_model()
n_vars = len(prob.variables())
print(f'変数 {n_vars}, 制約 {len(prob.constraints)} (CR1-CR8 のみの場合)')

変数 22220, 制約 15228 (CR1-CR8 のみの場合)

cases = [
    ('CR1-CR8', {}),
    ('+CR9(連続)', {'cr9': True}),
    ('+CR9+CR11(1日1回)', {'cr9': True, 'cr11': True}),
    ('+CR9+CR10(空き禁止)+CR11', {'cr9': True, 'cr10': True, 'cr11': True}),
    ('+CR9+CR10+CR11+CR12(午後限定)', {'cr9': True, 'cr10': True, 'cr11': True, 'cr12': True}),
]
results = {}
for name, kw in cases:
    prob, y = build_model(**kw)
    t0 = time.time()
    prob.solve(pulp.PULP_CBC_CMD(msg=0, timeLimit=600))
    status = pulp.LpStatus[prob.status]
    print(f'{name}: {status} ({time.time() - t0:.1f}秒)')
    results[name] = (status, prob, y)

CR1-CR8: Optimal (2.2秒)

+CR9(連続): Optimal (3.0秒)

+CR9+CR11(1日1回): Optimal (3.1秒)

+CR9+CR10(空き禁止)+CR11: Optimal (3.8秒)

+CR9+CR10+CR11+CR12(午後限定): Infeasible (5.0秒)

status, prob, y = results['+CR9+CR10(空き禁止)+CR11']
smap = {int(r[0]): r[1] for r in rd('subject_map.csv')}

def class_table(g, dp):
    ss = [s for s in subs if b[s][0] == g and b[s][1] == dp]
    days = ['月', '火', '水', '木', '金']
    tbl = pd.DataFrame('', index=[f'{p}限' for p in Pr], columns=days)
    for s in ss:
        for w in W:
            for p in Pr:
                if y[(s, w, p)].value() == 1:
                    tbl.iloc[p - 1, w - 1] = smap[s]
    return tbl

print('1年1学科の時間割:')
class_table(1, 1)

1年1学科の時間割:

print('4年1学科の時間割:')
class_table(4, 1)

4年1学科の時間割:

定数	意味	ファイル
$a_{st}$	教員 $t$ が科目 $s$ を担当できるなら1	a.csv(課題で作成)
$h_{sr}$	教室 $r$ で科目 $s$ を行えるなら1	h.csv(課題で作成)
$d_s$	科目 $s$ に必要な教員数	d.csv(課題で作成)
$m_s$	科目 $s$ に必要な教室数	m.csv(課題で作成)
$b_{sgd}$	科目 $s$(学年 $g$ 学科 $d$)の週に必要な単位数	b.csv
$e_{sgdwp}$	固定科目 $s$ を曜日 $w$ 時限 $p$ に行うなら1	e.csv
$l_{gdwp}$	学年 $g$ 学科 $d$ が曜日 $w$ 時限 $p$ に授業をしてよいなら1	g.csv
$\mathrm{Sub}_1, \mathrm{Sub}_2$	連続科目、固定科目の集合	sub1_sub2.txt

	月	火	水	木	金
1限	LHR(1年1学科)	平面基礎デザイン演習Ⅲ(1年1学科)	保健／体育実技(1年1学科)	化学(1年1学科)	基礎数学Ⅰ(1年1学科)
2限	平面基礎デザイン演習Ⅰ(1年1学科)	情報倫理(1年1学科)	基礎数学Ⅰ(1年1学科)	基礎数学Ⅱ(1年1学科)	国語(1年1学科)
3限	現代社会(1年1学科)	英語(1年1学科)	英語(1年1学科)	英語(1年1学科)
4限	基礎数学Ⅱ(1年1学科)	平面基礎デザイン演習Ⅳ(1年1学科)	表現(1年1学科)	平面基礎デザイン演習Ⅱ(1年1学科)

	月	火	水	木	金
1限		デザイン実習Ⅱ(4年1学科)			英語演習(4年1学科)
2限	デザイン概論(4年1学科)	選択英語(4年1学科)		デザイン実習Ⅱ(4年1学科)	自然科学概論(4年1学科)
3限	造形学(4年1学科)	応用デザイン実習Ⅰ(4年1学科)	デザイン方法論(4年1学科)	コンピュータグラフィックスⅡ(4年1学科)	デザイン心理(4年1学科)
4限	国語(4年1学科)	応用デザイン実習Ⅰ(4年1学科)	プレゼンテーション(4年1学科)	体育実技(4年1学科)	デザイン実習Ⅱ(4年1学科)

時間割編成問題: モデルの定式化と求解¶

1. はじめに¶

2. 問題設定¶

3. 定式化¶

3.1 定数¶

3.2 決定変数¶

3.3 制約条件¶

4. 実装¶

4.1 データの読み込み¶

4.2 モデル構築¶

4.3 制約を段階的に課して解く¶

4.4 時間割表への復元¶

5. 課題¶

6. 注意事項¶

7. 卒業研究概要への手引き¶

1章はじめに(文章量の比率: 15%)¶

2章時間割編成問題(文章量の比率: 30%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶

参考文献¶

時間割編成問題: モデルの定式化と求解¶

1. はじめに¶

2. 問題設定¶

3. 定式化¶

3.1 定数¶

3.2 決定変数¶

3.3 制約条件¶

4. 実装¶

4.1 データの読み込み¶

4.2 モデル構築¶

4.3 制約を段階的に課して解く¶

4.4 時間割表への復元¶

5. 課題¶

6. 注意事項¶

7. 卒業研究概要への手引き¶

1章 はじめに(文章量の比率: 15%)¶

2章 時間割編成問題(文章量の比率: 30%)¶

3章 実験(文章量の比率: 40%)¶

3.1節 概要¶

3.2節 結果と考察¶

4章 おわりに(文章量の比率: 15%)¶

参考文献¶

1章はじめに(文章量の比率: 15%)¶

2章時間割編成問題(文章量の比率: 30%)¶

3章実験(文章量の比率: 40%)¶

3.1節概要¶

3.2節結果と考察¶

4章おわりに(文章量の比率: 15%)¶