数理最適化（MILP）× ローカルAI 解説記事

『大学時間割編成 AI Copilot』の裏側：
4次元0-1整数計画問題（UCTP）と複数枚連動パズルの定式化

対象読者：混合整数線形計画（MILP）およびAIエージェントによる構造化入力に関心のある方。
なぜ大学の時間割は「1枚の表」ではなく学年別（4枚）・教員別（10名）・教室別（7室）の複数枚が裏で同時に絡み合うNP困難問題になるのか、そしてGemini Nano（構造化抽出）× WaSHI / HiGHS（厳密求解・矛盾診断）がどのように連携しているのかを解説します。

1. なぜ「大学の時間割」は複数枚が裏で連動して解けなくなるのか？

オペレーションズ・リサーチ（OR）において、大学時間割編成問題（University Course Timetabling Problem; UCTP）はナース・スケジューリング問題（NSP）と並び、国際コンペティション（ITC-2007等）が開催され続ける代表的な実務組合せ最適化問題です。

小学校のクラス時間割なら「1クラス＝1枚の表」の中で完結しますが、大学の学部時間割では「1年〜4年の学生カリキュラム（4枚の時間割）」「専任・非常勤10名の教員スケジュール」「定員・PC設備の異なる7つの講義室・演習室」がすべて共通の曜日・時限（週25枠）を奪い合います。ある学年の1コマを動かした瞬間、同じ先生が担当する他学年のゼミや、同じ大講義室を使う別科目が玉突きで衝突します。

アプリ上の要素 実務の大学時間割（UCTP）での意味 数理モデル上の表現
開講科目 c ∈ C（全25科目・計30コマ） 週1コマまたは週2コマ開講される講義・PC演習・ゼミ 週間必要コマ数 S_c ∈ {1, 2}、履修者数 Enr_c
曜日 d ∈ D・時限 p ∈ P・教室 r ∈ R 月〜金（5日）× 1〜5限（計25枠）× 7室の講義室/PC室 4次元0-1決定変数 x_{c,d,p,r} ∈ {0, 1}（計4,375個）
学年別4枚の時間割（1年〜4年） 各学年の必修・選択必修カリキュラム（Curriculum） 学年 k のコア科目集合 Core_k の同時開講禁止
非常勤講師の出講可能曜日・教授会NG枠 「小林先生は火・木のみ」「水曜5限は教授会」等の個別制約 該当枠の決定変数和を 0 に固定するハード制約
PC演習室必須・大講義室定員制約 プログラミング演習はPC端末必須、130名講義は大講義室のみ 不適合教室 r ∉ R_c への割当を禁止（x_{c,d,p,r} = 0）
学生の「空きコマ（中空き）」の最小化 1限と3限に必修があり2限が空く「中空き」の解消 補助連続変数 gap_{k,d,p} >= 0 によるソフト制約ペナルティ
解なし（Infeasible）時の衝突ルール診断 条件の詰め込みすぎで時間割が組めない原因の特定 二段階スラック緩和（Elastic Relaxation）による極小衝突集合の抽出

2. 4次元二値決定変数と基本ハード制約の定式化

科目集合を C（25科目）、曜日集合を D = {Mon, Tue, Wed, Thu, Fri}、時限集合を P = {1, 2, 3, 4, 5}、教室集合を R（7室）とします。科目 c を曜日 d・時限 p・教室 r に割り当てるとき 1、そうでないとき 0 をとる二値決定変数 x_{c,d,p,r} ∈ {0, 1} を定義します。

また表記を簡潔にするため、科目 c が枠 (d, p) のいずれかの教室で開講されるかを表す射影式を u_{c,d,p} = Σ_{r ∈ R} x_{c,d,p,r} と置きます。

大学時間割編成問題（UCTP）の基本ハード制約群 (1) 週間必要コマ数:         Σ_{d ∈ D} Σ_{p ∈ P} Σ_{r ∈ R} x_{c,d,p,r} == S_c      (∀c ∈ C)
(2) 1枠につき高々1教室:     u_{c,d,p} = Σ_{r ∈ R} x_{c,d,p,r} <= 1              (∀c, d, p)
(3) 教室定員・設備適合:     Σ_{d ∈ D} Σ_{p ∈ P} Σ_{r ∉ R_c} x_{c,d,p,r} <= 0     (∀c ∈ C)
(4) 教室の同時使用禁止:     Σ_{c ∈ C} x_{c,d,p,r} <= 1                           (∀r ∈ R, d ∈ D, p ∈ P)
(5) 教員の同時担当禁止:     Σ_{c ∈ C_{prof}} u_{c,d,p} <= 1                      (∀prof, d ∈ D, p ∈ P)
(6) 学年カリキュラム重複禁止: Σ_{c ∈ Core_k} u_{c,d,p} <= 1                       (∀k ∈ {Y1..Y4}, d, p)
(7) 非常勤・教員NG枠禁止:   Σ_{c ∈ C_{prof}} u_{c,d,p} <= 0                      (∀(prof, d, p) ∈ Unavail)
💡 なぜ「学年別」「教員別」「教室別」の3つのビューが同じ解から同時に描けるのか 決定変数 x_{c,d,p,r} を学年 k でスライスすれば「学年別の4枚の時間割」になり、教員 prof でスライスすれば「教員別×25コマ一覧表」（式(5)により各マス高々1科目）、教室 r でスライスすれば「教室別×25コマ一覧表」（式(4)により各マス高々1科目）になります。つまり3種類の時間割ビューはすべて同じ4次元テンソル x_{c,d,p,r} の異なる断面（射影）です。

3. 現場特有のカリキュラム条件の線形化

(A) 週2コマ科目の「同日・連続時限開講」（course_consecutive）

通常、週2コマの講義（例：『線形代数学I』『アルゴリズム』）は学習効果のため別々の曜日に分散させます（Σ_{p ∈ P} u_{c,d,p} <= 1）。しかし『ソフトウェア設計演習（C12）』のようなプログラミング演習では、「同じ曜日の連続する2時限（例：火曜2〜3限）にまとめて実施したい」という要望が頻繁に出ます。

これをMILPで表現するため、「曜日 d の時限 p と p+1 の両方で開講されたとき 1 になる補助二値変数 z_{d,p} ∈ {0, 1}（p ∈ {1, 2, 3, 4}）」を導入し、以下の線形不等式で連続開講を強制します：

同日連続2コマ開講の線形化（p ∈ {1, 2, 3, 4}） (a) z_{d,p} - u_{c,d,p} <= 0      (∀d ∈ D, p ∈ {1..4}) : p限に開講されないなら z_{d,p} = 0
(b) z_{d,p} - u_{c,d,p+1} <= 0    (∀d ∈ D, p ∈ {1..4}) : (p+1)限に開講されないなら z_{d,p} = 0
(c) Σ_{d ∈ D} Σ_{p=1}^{4} z_{d,p} >= 1                  : いずれかの曜日・隣接時限ペアで必ず連続開講する

(B) 学生の「空きコマ（中空き）」最小化の線形化

学生にとって「1限と3限に必修授業があり、2限が1コマだけ空いてしまう（中空き）」時間割は不評です。各学年 k・曜日 d・中間時限 p ∈ {2, 3, 4} について、前後の時限 p-1 と p+1 の両方にコア科目があるのに p 限が空いているときだけ 1 以上になる連続スラック変数 gap_{k,d,p} >= 0 を導入します：

中空き（Hollow Gap）検出不等式と目的関数ペナルティ Σ_{c ∈ Core_k} u_{c,d,p-1} + Σ_{c ∈ Core_k} u_{c,d,p+1} - Σ_{c ∈ Core_k} u_{c,d,p} - gap_{k,d,p} <= 1
目的関数項:   minimize   Σ_{k,d,p} W_{gap} * gap_{k,d,p}

(C) 微調整モード（Minimal Perturbation：既存時間割の維持）

運用中の時間割に対して「佐藤先生の金曜午後をNGにして」と1つ条件を追加したとき、関係ない科目の曜日まで全面シャッフルされてしまうと教務現場は大混乱します。微調整モードがONのときは、直前の時間割解で割り当てられていた枠 (c, d^*, p^*, r^*) に対して負の目的関数報酬（-6 * u_{c,d^*,p^*} - 2 * x_{c,d^*,p^*,r^*}）を与えることで、変更が必要な最小限のコマだけを移動させます。

4. Gemini Nano（構造化抽出）× WaSHI（二段階スラック緩和による矛盾診断）

このデモでは、LLMに「時間割そのもの」を作らせることは一切していません。4,400変数の組合せ制約をLLMの推論だけで解かせると、教室の定員オーバーや非常勤講師のダブルブッキングが必ず発生するからです。代わりに役割を明確に分離しています：

  1. Chrome Built-in AI（Gemini Nano / LanguageModel API）：自然言語の要望（「非常勤の小林先生は火・木の午後しか来られないようにして」等）を、responseConstraint（JSON Schema強制）によって型安全な操作コマンド（set_professor_unavailability 等）へ変換します。
  2. WaSHI + HiGHS（WebAssembly MILPソルバー）：抽出された操作を数理モデルに反映し、約250ミリ秒で厳密最適解を求め、model.validateSolution() で全1,601本の制約違反が 0 であることを検算します。
  3. 解なし（Infeasible）時の自動矛盾診断（Elastic Relaxation）：もし「火・木のみ出講可の小林先生の科目を月曜3限に固定」のような矛盾した要望が来た場合、すべてのハード制約に非負スラック変数 s_i >= 0 を入れた緩和モデルを2通りの重み（Pass 1: 追加ルール優先緩和、Pass 2: 基本ルール優先緩和）で解き、どのルールとどのルールが正面衝突しているかを数理的に特定して提示します。 
// WaSHI による 4次元時間割モデル (UCTP) と 二段階スラック緩和診断の骨格
const m = new Model("UniversityCourseTimetabling_UCTP", { solver: "highs" });

// 1. 4次元0-1決定変数 x[course][day][period][room]
for (const c of courses) {
  for (const d of ["Mon", "Tue", "Wed", "Thu", "Fri"]) {
    for (const p of [1, 2, 3, 4, 5]) {
      for (const r of rooms) {
        x[c.id][d][p][r.id] = m.binary(`x_${c.id}_${d}_P${p}_${r.id}`);
      }
    }
  }
}

// 2. 教室重複禁止・教員同時担当禁止・学年カリキュラム重複禁止・個別ルールを追加
m.constraint(expr`${sum(roomSlotVars)} <= 1`, `room_excl_${r.id}_${d}_P${p}`);

// 3. 求解と検算 (Infeasible 時は Elastic Relaxation で衝突ルールを特定)
const status = await m.solve({ timeLimit: 4.0, relGap: 0.001 });
const report = m.validateSolution();
🎓 『大学時間割編成 AI Copilot』を体験する ▶ 🏥 『ナーススケジューリング AI Copilot』を開く → ✨ ショーケース一覧へ →