あなたは Mr. 〇〇 の YouTube 動画『1週間映画館生活！ 成功すれば賞金1万ドル！』に出演することになりました．ここには，食料もトイレもあります．もちろん映画という娯楽もあります．1週間映画館に居続けることができれば，賞金1万ドルを獲得することができます！
👨⚕️👩⚕️「これはとても過酷な挑戦だ．重篤な影響が出るかもしれない」
さあ，この困難なミッションを乗り越え，賞金1万ドルを持って帰りましょう！
自己紹介
株式会社Sapeet にてアルゴリズム・エンジニアをしております，西田と申します．新卒で入社し現在一年目になります．数理最適化など数学を用いる業務を中心に取り組んでおり，本記事でも数理最適化の簡単なデモンストレーションをご紹介します．
本記事で作るもの
数理最適化を用いて，このミッションを乗り越えるための最適な映画鑑賞スケジュールを作成します．
最初は，できるだけ満足度が高くなるような鑑賞スケジュールを検討します．実験を行う中で新たな条件を取り入れることで，解の変化を観察します．また，チケット代の合計費用をできるだけ安くするような鑑賞スケジュールも検討します．本記事では，合計 5 つの実験を行い，最終的に下図の最適スケジュールを得ます．
定式化の変化による解の変化をみることで，数理最適化の柔軟性と強力さについても観察します．
また，本記事で作成した Python コード（notebook）は GitHub にて公開しております．
ルール
- 映画館から1歩でも足を踏み出したらチャレンジ失敗．賞金を受け取れません
- 満足ゲージが0 を下回ってしまうと，あなたは映画館から出ていく決断をしてしまいます
- 上映中の映画はどれでも鑑賞できます．ただし，料金は通常通り支払います
- 映画が上映されるのは営業時間の9〜22時
満足ゲージ
映画の営業時間（9〜22時）中に少しずつ減少していきます．0 を下回ってしまうと，チャレンジ失敗になります．映画を観ることで，その映画の満足度に応じて満足ゲージを回復させることができます．映画鑑賞中は満足度の減少は止まります．
作戦会議
あなたは映画館のHP にアクセスし，映画の上映スケジュールを確認します．この映画館にはシアター1〜10 までが存在し，今週は20作品を毎日同じスケジュールで上映しています．
上映作品リスト
※ 一部，著作権の切れた古典作品・クラシック音楽を除き，実在する作品とは一切関係ありません．
| タイトル | 上映時間/分 | 満足度 | 料金/円 |
|---|---|---|---|
| 旧世紀ドグマリオン | 120 | 5 | 2,000 |
| 映画 魔法少女リオン！F | 85 | 5 | 1,900 |
| 転生しなくても人間だった件 | 105 | 5 | 2,000 |
| 復刻版 高速船ウィイー | 32 | 5 | 1,300 |
| ご芳名は。 | 107 | 5 | 2,000 |
| 劇場版 名探偵ラナ 裏切りの特異点 | 110 | 5 | 2,000 |
| 劇場版 PRINCE☆STAGE―輝きのステージへ― | 95 | 4 | 2,000 |
| 俺たちがゲートボーラーだ!! 2 | 115 | 4 | 2,000 |
| アンノーン・エリア〜隠された政府の陰謀〜 | 130 | 4 | 2,000 |
| スイーティー♡ガールズ! | 110 | 4 | 1,800 |
| 俺の義理の妹の友人の兄の彼女の母のいとこのお嬢さん | 120 | 3 | 2,000 |
| マリス・ナイト・アポカリプス―解放されし厄災― | 134 | 3 | 2,000 |
| 宇治拾遺物語 | 85 | 3 | 1,400 |
| 警視庁ゴミ拾い係 | 105 | 3 | 2,000 |
| ウワサのイケメンがアタシにだけ優しい！？ | 90 | 2 | 1,800 |
| イッキ見! ワーグナー《ニュルンベルクのマイスタージンガー》 | 320 | 2 | 16,000 |
| ザ・グレート・スカイ・ウォー 4 | 125 | 2 | 2,000 |
| オレが握ったおにぎりを食えないっていうのかよぉ | 125 | 1 | 1,800 |
| ヒト vs. オニ | 77 | 1 | 1,800 |
| ザ・サメ・パニック | 82 | 1 | 1,400 |
詳細な上映スケジュール
HP には，上映スケジュールの他にも，作品を鑑賞したときの満足度が書かれています．
あなたはぼんやりと，次のような作戦を立てます：
- 満足度の高い映画を鑑賞した方が良さそう
- 同じ映画は2回観たくないな
- 映画を観ていないとき，満足度は少しずつ下がっていく．なので 0 にならないように気をつけてスケジュールを組む必要がある
- チケット代が安くて満足度の高い映画はコスパが良さそう
この茫洋とした作戦をもとに，1週間を生き抜く鑑賞スケジュールを立てるにはどのようにすれば良いでしょうか？ 複雑な上映スケジュールを組み合わせて戦略的なスケジュールを作るのは難しそうです．特に， 複数の条件を満たしながら取り得るすべての組み合わせを比較検討して計画を立てるのは難しい問題 です．
数理最適化
数理最適化は，制約条件（前提条件）を満たしつつ，何かを最適化する変数の組み合わせを発見するのに適した手法です．例えば，以下のような問題を解くことができます．
- 利益最大化問題: 生産キャパシティ（制約条件）を満たしつつ，工場の利益を最大化する（最適化する 目的関数 は工場の利益）ような，原材料ごとの仕入れと製品の生産量（決定変数）を決定する
- 最小経路問題: 通行可能な道だけを通って（制約条件），ある地点から別の地点への経路長を最小化する（最適化する 目的関数 は経路長）ようなルート（決定変数）を決定する
数理最適化においては，
- 決定変数: 何を決定するか
- 制約条件: 何が守らなければならない前提条件であるか
- 目的関数: 何を最適化するか
を数式，次いでコードに落とし込みます．そして汎用的に数理最適化の問題を解くことができる ソルバー というソフトウェアで 最適解（最適な変数の組み合わせ）を求めることができます．
映画館1週間生活では
今回の問題を数理最適化の問題として考えてみましょう．まずは数式を使わずに言葉で整理します．制約条件や目的関数は5つの実験の中で追加や見直しを行いますが，まずは以下の問題（実験1）に取り組むことにしましょう！
- 決定変数: どの映画をいつ鑑賞するか
-
制約条件:
- 同じ時間に異なる映画を鑑賞することはできない
- 鑑賞後は一定時間の休憩時間を挟む
- 満足ゲージは徐々に減少する
- 映画を鑑賞すると，映画の満足度に応じてゲージが回復する
- 映画鑑賞中は満足ゲージが減少しない
- 満足ゲージは常に 0 以上となるようにする
- 目的関数: 満足度を最大にする
細かい部分を明らかにして数式に落とし込むと，以下のような数理最適化問題となります（トグル内）
実験1: 満足度を最大にする
集合・添字
- $m \in M$：作品
- $r \in R$：シアタールーム
- $d \in D = {0, 1, \dots, |D|-1}$：日にち
- $t \in T$：時刻スロット（15分刻み, 9:00–21:45）
- $P = {(m, r, d, t) \mid \text{映画 } m \text{ が } r \text{ にて } d \text{ の } t \text{ に上映開始}}$
- $P_d = {(m, r, t) \mid (m, r, d, t) \in P}$（補助的な集合）
パラメータ
- $l_m \in \mathbb{Z}_{>0}$：作品 $m$ の上映時間
- $s_m \in \mathbb{Z}$：作品 $m$ の満足度（1–5）
- $\mathrm{time_{rest}} \in \mathbb{Z}_{\ge 0}$：鑑賞後の休憩スロット数
- $\mathrm{satis_{init}} \in \mathbb{R}$：初期満足ゲージ
- $\mathrm{satis_{min}} \in \mathbb{R}$：満足ゲージの下限
- $\mathrm{satis_{factor}} \in \mathbb{R}_{>0}$：映画を鑑賞していないスロットの満足度減少係数
各 $d, t$ に対しての被覆集合
$$
\mathrm{cov}(d, t) = {(m, r, t_0) \in P_d \mid t_0 \le t \le t_0 + l_m - 1}
\quad \text{($t$ に上映中の回)}
$$
$$
\mathrm{cov^+}(d, t) = {(m, r, t_0) \in P_d \mid t_0 \le t \le t_0 + l_m + \mathrm{time_{rest}} - 1}
\quad \text{(上映中＋休憩中の回)}
$$
被覆集合 $\mathrm{cov}(d, t)$ は，日にち $d$ の時刻 $t$ に，上映中の映画の $(m, r, t_0)$ の集合を表します．上映中かどうかは，時刻$t$ が上映開始時刻と上映終了時刻の間であるかで判定できます: $t_0 \le t \le t_0 + l_m - 1$．$\mathrm{cov^+}(d, t)$ は，上映中またはその映画を鑑賞した場合に休憩しなければならない時間中である映画の集合です．判定する時間の範囲を変えて同じように考えることができます．
決定変数
$d$ の $t$ に $r$ で上映開始する映画 $m$ を鑑賞するかどうかを表す二値変数 $x_{m,r,d,t}$:
$$
x_{m,r,d,t} \in {0, 1} \quad \forall (m, r, d, t) \in P
$$
$d$ の $t$ における満足ゲージを表す実数変数 $y_{d,t}$:
$$
y_{d,t} \in \mathbb{R} \quad \forall d \in D,\ t \in T
$$
（$(m, r, d, t) \notin P$ では常に $x_{m,r,d,t} = 0$ とみなす）
目的関数：総獲得満足度の最大化
$$
\max \quad \sum_{(m,r,d,t) \in P} s_m, x_{m,r,d,t}
$$
制約条件
(1) 同一時刻に鑑賞できる映画は1つ & 映画鑑賞後には休憩時間を入れる
$$
\sum_{(m,r,t_0) \in \mathrm{cov^+}(d,t)} x_{m,r,d,t_0} \le 1
\qquad \forall d \in D,\ t \in T
$$
(2) 満足ゲージの推移
$$
y_{d,t} = y_{d,t-1} + \mathrm{satis_{factor}}\left( \sum_{(m,r,t_0) \in \mathrm{cov}(d,t)} x_{m,r,d,t_0} - 1 \right) + \sum_{m \in M,, r \in R}, s_m, x_{m,r,d,t} \qquad \forall d \in D,\ t \in T
$$
(3) ゲージの境界条件
$$
y_{0,-1} = \mathrm{satis_{init}}
$$
$$
y_{d,-1} = y_{d-1,,\max(T)} \qquad \forall d \in D \setminus {0}
$$
(4) 満足ゲージの下限（下限=0 を下回るとチャレンジ失敗なので，そうならないようにする）
$$
y_{d,t} \ge \mathrm{satis_{min}} \qquad \forall d \in D,\ t \in T
$$
（トグルここまで）
この問題は，決定変数が整数（$x_{m,r,d,t}$ は 0 or 1）または実数（$y_{d,t}$）となります．このような数理最適化の問題は 混合整数計画問題（MIP; mixed integer programming） と呼ばれます．
数理最適化の問題を Python で解く場合，様々なライブラリが提供されています．今回は，以下を用いました．
これらは，pip や uv を用いて簡単にインストールすることができます:
pip install pyomo highspy
# or
uv add pyomo highspy
実験（制約条件や目的関数も変えてみる）
それでは，映画館生活の最適化を行います．本記事では，得られる解を観察して制約条件や目的関数を順次見直し，解がどのように変化するかを観察します．
実験1: 満足度を最大にする
先に述べた実験1 の問題の制約条件と目的関数をおさらいすると，
-
制約条件:
- 同じ時間に異なる映画を鑑賞することはできない
- 鑑賞後は一定時間の休憩時間を挟む
- 満足ゲージは徐々に減少する
- 映画を鑑賞すると，映画の満足度に応じてゲージが回復する
- 映画鑑賞中は満足ゲージが減少しない
- 満足ゲージは常に 0 以上となるようにする
- 目的関数: 満足度を最大にする
としたのでした．これを Pyomo や HiGHS を用いて実装・求解して得られたスケジュールが以下になります．なお，Python コード（notebook）は GitHub に掲載しております．
満足度の推移をプロットしたものが下図になります．
満足度を下げる要因がほとんどないため，上がり続けています．
実験1は， 満足度☆5 の2映画ばかりを観る結果 となりました．これは数理最適化のライブラリ（ソルバ）のバグではなく，問題設定において同じ映画を何度も観ないという制約条件を入れなかったため です．そのため，上映回数が多く短い時間で高い満足度を得られる映画を繰り返し鑑賞するような鑑賞プランになってしまったのでした．
そこで，次の実験では，同じ映画は2回と観ないことを制約として入れてみます．
実験2: 同じ映画は2回観ない
-
制約条件:
- 同じ時間に異なる映画を鑑賞することはできない
- 鑑賞後は一定時間の休憩時間を挟む
- 満足ゲージは徐々に減少する
- 映画を鑑賞すると，映画の満足度に応じてゲージが回復する
- 映画鑑賞中は満足ゲージが減少しない
- 満足ゲージは常に 0 以上となるようにする
- どの映画も，鑑賞回数は 1 以下（NEW）
- 目的関数: 満足度を最大にする
追加する制約条件
$P_m = {(r, d, t) \mid (m, r, d, t) \in P}$ として
$$
\sum_{(r,d,t) \in P_m} x_{m,r,d,t} \le 1 \qquad \forall m \in M
$$
この制約を追加して再度解いた結果が下図になります．
20すべての作品を1週間のうちで必ず1回ずつ鑑賞するスケジュールが得られました．同一の映画であれば，どの上映回も得られる満足度・上映時間は同じであるため，実は 20作品すべてを鑑賞するスケジュールであればどれも最適解になります（ただし，満足度が 0 未満にならないものに限る）．そのため，実は実験2に関しては，数理最適化を使わずとも直感的に最適解が想像できます．
これは面白みが少ないため，さらに制約条件を足してみます．
【余談】
今回のように，目的関数値が等しい最適解が複数存在する（最適解が非一意である）ことがあります．さらに，20作品が互いに交換可能であるといった対称性が問題にあると，ソルバは複数の最適解を探索してしまい，計算時間が伸びることがあります．今回はソルバが瞬時に解き終えるので問題ありませんが，こうした場合には「映画タイトルに番号を振り，小さい順に鑑賞する」といった 対称性を破る制約条件（symmetry breaking） を加える技法が有効です．
実験3: 予算制限
実験2において，映画鑑賞費用（チケット代）の総額は 51,200円 になります．これはちょっと高すぎるので，予算制限を掛けてみましょう．賞金1万ドルならば，数万円くらい気にしなくてもと思われるかも知れませんが...
-
制約条件:
- 同じ時間に異なる映画を鑑賞することはできない
- 鑑賞後は一定時間の休憩時間を挟む
- 満足ゲージは徐々に減少する
- 映画を鑑賞すると，映画の満足度に応じてゲージが回復する
- 映画鑑賞中は満足ゲージが減少しない
- 満足ゲージは常に 0 以上となるようにする
- どの映画も，鑑賞回数は 1 以下
- チケット代の総額は予算以下（NEW）
- 目的関数: 満足度を最大にする
追加する制約条件
パラメータとして，作品 $m$ の料金 $p_m \in \mathbb{Z}_{\ge 0}$ を追加．
$\mathrm{budget} \in \mathbb{Z}_{\ge 0}$ を予算として
$$
\sum_{(m,r,d,t) \in P} p_m, x_{m,r,d,t} \le \mathrm{budget}
$$
予算額を30,000円に設定して解いた結果が下図になります．
『イッキ見! ワーグナー《ニュルンベルクのマイスタージンガー》』のように，チケット代が異様に高い（16,000円！）作品や，『ヒト vs. オニ』のように，チケット代が安くない（1800円）わりに満足度の低い（☆1）作品が除外されました．
満足ゲージにはまだ余裕があり，チャレンジ終了時点ではゲージが比較的高い状態です．
実験4: 合計チケット代を目的関数とし，費用最小化問題を解く
実験1–3 においては，満足度の最大化を行いました．実験4 では，チケット代の合計金額を最小化する問題を解きます．制約条件に入っていたチケット代予算を目的関数に移します．
-
制約条件:
- 同じ時間に異なる映画を鑑賞することはできない
- 鑑賞後は一定時間の休憩時間を挟む
- 満足ゲージは徐々に減少する
- 映画を鑑賞すると，映画の満足度に応じてゲージが回復する
- 映画鑑賞中は満足ゲージが減少しない
- 満足ゲージは常に 0 以上となるようにする
- どの映画も，鑑賞回数は 1 以下
- 目的関数: チケット代の合計を最小にする（NEW）
実験4の定式化
目的関数は
$$\min \quad \sum_{(m,r,d,t) \in P} p_m, x_{m,r,d,t}.$$
予算制限を除去する以外，制約条件はそのまま．
新しい目的関数で計算した結果が下図になります．
チケット代合計は 16,400円となり，過去の実験よりもずっと安い費用で1週間を乗り切れることがわかりました．スケジュールを見ると，コスパの良い（チケット代に対して満足度の高い）映画を鑑賞する結果であることがわかります．また，満足度は低水準で推移し，一日何も鑑賞しない日が出現しました．
実験5: 3日目は割引デー
その後，HP を見ていたあなたは，3日目が割引デーであることに気づきました．どの映画も300円チケットが安くなります！ いま，得られた最適解では3日目に映画を一つも観ていません．これは明らかに損です！ そこで，割引を考慮に入れて費用最小化を行いましょう 1．
割引を考慮した目的関数
各日の割引額を $\mathrm{disc}_d$（ [0, 0, 300, 0, 0, 0, 0] ）として
$$\min \quad \sum_{(m,r,d,t) \in P} (p_m - \mathrm{disc}_d), x_{m,r,d,t}.$$
これにより，3日目に鑑賞する映画のチケット代のみが 300円引きになります．
割引を考慮して得られる解が下図になります．
予想できる通り，3日目に鑑賞が集中することになりました．チケット代は 16,400円 → 14,900円と 1,500円の節約に成功しています．鑑賞する映画のセット自体は実験4から変化がなく，鑑賞する日時が変化しています．3日目に5映画を鑑賞することで， $300\text{円} \times 5 = 1500\text{円}$ 合計費用が安くなったとわかります．
まとめ
こうして最適な鑑賞スケジュールを得られたあなたは，無事1週間の映画館生活を乗り切り，賞金1万ドルを手にすることができました！
数理最適化は，現実の様々な事物や条件を数式に落とし込み（モデリング），意思決定を支援するための最適解を提案する強力な手法です．また，アルゴリズムを駆使して解を求める手法では制約条件や目的関数が変わるごとに計算方法が大きく変化しがちですが，数理最適化においてはこれらを入れ替えて再計算することで比較的簡単に実験を行うことができます（そうでない場合も多々ありますが）．
本記事では，満足度の最大化やコスト最小化を行いました．実務においても数理最適化は，コスト最小化，利益最大化，効率最大化，顧客満足度最大化などの経営やマーケティングの問題を解くために使われています．
一方で，数理最適化はモノを設計する際にも使われる応用の広い手法です．例えば，Sapeet においては，オーダーメイド製品の設計を支援する，数理最適化を用いたソリューションを提供しています．詳細は，9月11日開催の OpenSapeet にて私・西田よりお話しさせていただく予定 です！ ぜひ下記リンクよりチェックしていただけますと幸いです！
OpenSapeet（2026年9月11日開催予定）: https://connpass.com/event/398374/
-
ちなみに，むかし私がある映画を観に行ったとき，割引デーを狙って映画館に行きました．しかし，その作品は特別上映だったために割引が効かない作品でした．私は悲しい気持ちになりながら，定価通りのチケット代を払いました． ↩