Insight Edgeのデータサイエンティストのki_ieです。 数理最適化の専門家として、これまでさまざまな課題を数理最適化問題としてモデリングしてきました。 モデリングはアルゴリズム設計と比べて注目を集めることが少ないようですが、 実際には技術的な知見・調査を要求する骨の折れるタスクです。
このタスクを簡単にしたいとは日々思っていたところですが、最近 OpenAI o1 というモデルの論理的推論能力が高いらしいという聞きました。この賢いLLMがモデリングのお手伝いをしてくれたら嬉しいですね！ 今日は数理最適化問題(混合整数計画問題)のモデリングをどれだけLLMに任せられるのか、簡単な実験結果をご紹介します。
数理最適化問題とは
数理最適化問題と混合整数計画問題の基礎知識がある方はこの節はスキップしましょう(面白いことは一つも書いてありません)！
数理最適化問題とその実行可能解・最適解
数理最適化問題とは「変数・制約・目的関数」が与えられたときに、 「制約を守るなかで最も目的関数を小さく(または大きく)する決定変数を選ぶ」 という問題です。
数理最適化問題は、一般に以下の形で表現できます:
数理最適化問題
- 変数 : $x \in D \ \ (\subseteq \mathbb{R}^n)$
- 変数 $x$ は $D$ の中から選べる
- 制約 : $g_i(x) \leq b_i \ \ (i \in I)$
- $x$ は $g_i(x) ≤ b_i$ がすべての $i \in I$ について成り立つように選ぶ
- 目的関数(最小化) : $\min f(x)$
- 上記ルールを守ったうえで $f(x)$ を最小化したい。
上手に $D$, $g_i$, $f$ を設計してやることで、配送計画から証券ポートフォリオの最適化まで幅広い問題が 数理最適化問題として表現できることが知られています。 たとえばコンビニの店長の立場でおにぎりの仕入れ量を適正化する問題を単純化すれば、以下のような最適化問題としてモデル化できます:
例: おにぎりの仕入れ量の適正化
- 変数: おにぎりに仕入れ量 $x \in \mathbb{Z}_+$
- 制約: おにぎりが店から溢れない $x \leq 100$
- 目的関数: $\max f(x)$
- $f(x)$ : おにぎり $x$ を仕入れたときの期待利益
$D$ の要素で制約をすべて守るものはその問題の実行可能解と呼ばれます。 実行可能解のうち目的関数を最小にするものは数理最適化問題の最適解(または解)と呼ばれます。 数理最適化問題で課題をモデリングする目的は、最適解を得ることにあります。 たとえばおにぎりの仕入れ量の適正化の文脈では最も利益があがる仕入れ量が $70$ であれば、$x=70$ が最適解です。 これが計算で求められれば、このコンビニでは利益を最大化する仕入れの意思決定ができるようなってハッピーです。
一方、問題によっては最適解を求めることが極めて難しいことがあります。 おにぎりの仕入れ量の適正化問題は$x=0, 1, 2 \cdots 100$ を全探索すれば簡単に最適解が求まりますが、 もっと複雑な問題ではそうはいかないこともしばしばあるのです。 そのような場合は「目的関数値の良い」実行可能解が求まったらそれでよしとすることが実務上は一般的です。 おにぎりの仕入れ量の問題で言えば、$x=68, 71$ といった解が見つかって、$x=70$ が見つけられなかったら、 $x=68, 71$ をとりあえずの答えとして採用するというイメージです。 この場合でも、あてずっぽうで仕入れ量を決定するコンビニよりは利益を大きくできるわけです。
混合整数計画問題
数理最適化問題の中でも特別に重要な問題クラスとして、混合整数計画(MIP; Mixed Integer Programming)問題があります。 これは実行可能領域 $D$ を$\mathbb{R}^n \times \mathbb{Z}^m$ として、制約・目的関数を線形なものに限定したものです。
混合整数計画問題
- 変数 : $x \in \mathbb{R}^n \times \mathbb{Z}^m$
- 制約 : $a_i^\top x \leq b_i \ \ (i \in I)$
- $a_i^\top$ を行ベクトルとして集めた行列を$A$, $b_i$ を集めたベクトルを $b$ としたら、まとめて $Ax ≤ b$ と書ける。
- 目的関数(最小化) : $\min c^ \top x$
変数に別途上下限を許す場合も、等号制約を許す場合もある。いずれもここで示した形に容易に変形できる
この問題クラスの重要性を説明するために、まず数理最適化を利用した課題解決の一般的な流れを説明します。 さまざまなタイプの数理最適化問題に対して、最適解または最適解ではないにせよ目的関数値の良い実行可能解を求めてくれるプログラムが作られています。これらのプログラムはよく「ソルバー」とよばれます。数理最適化の考え方とソルバーを利用して現実の課題を解くときの流れは以下のようになります。
- 課題の整理
- 課題を数理最適化問題としてモデル化
- 数理最適化問題をソルバーで求解する
- 得られた最適解(または目的関数値の良い実行可能解)を現実世界で採用する
課題を数理最適化問題に落とし込むことにも技術的な難しさがありますが、 その数理最適化問題を解くソルバーを設計・実装することもまた大変に難しいことです。 そのため、できれば既存のソルバーを用いて求解できるような範囲でモデル化をしたいというのが数理最適化エンジニアの本音です。
MIPによるモデリングはこの観点で大変すぐれています。MIPは多様な問題を表現でき、さらに優れたソルバーが存在するからです。 MIPは制約・目的関数が線形に限定されているため一見すると限られた表現力しかないように見えますが、0, 1の値しかとらないバイナリ変数を巧みに使うことで複雑な論理関係を表現でき、幅広い問題を表現可能です。表現できる問題の幅広さゆえ、学術的にも深く研究され、ソルバーの研究が積み重ねられてきました。その結果、優れた商用・OSSのソルバーが存在するのです。
このような背景から、MIPによるモデリングは数理最適化の実務においてなくてはならない基本技術となっています。
LLMに混合整数計画問題をモデリングさせたいモチベーション
課題のMIPモデリングというのはなかなか骨の折れる作業です。 論理的に正しいというだけではなくソルバーにとって解きやすいモデルを作ることが求められるため、 難しい課題の場合は最適化モデルの試行錯誤・調査の1サイクルだけで数日かかってしまう、ということも稀ではありません。
この作業、なるべくサボりたいですね。性能向上の著しいLLMに手伝ってもらえれば、 まるごと作業代替とはならなくとも効率化できるのではないか？というのが、本記事で検証したいポイントです。
数理最適化エンジニアとして確認したい具体的なポイントは以下の3つです。
- 有名問題をモデル化できるか / 有名定石を利用できるか？
- 有名問題に簡単な要件を追加してもモデル化がうまくいくか？
- 複雑な要件を上手にモデル化できるか？
LLM に 1. ができたら、数理最適化初心者/学習者にはLLMによる補助が有用だと考えられるでしょう。 数理最適化問題のモデリングにはさまざまな「定石」が登場します。 例えば、0/1変数 $x, y \in \{0, 1 \}$ の論理積をMIPの枠組みで考えたいときには、補助変数 $z \in \{0, 1 \}$ を導入して 制約 $z ≤ x, z ≤ y, x+y-1≤z$ を加えれば $z$ は $x, y$ の論理積(AND)となる、というテクニックがあります。 知っていれば簡単に使えるテクニックですが、自分で思いつくのは難しいです。 初心者がこれをLLMに教えてもらえるなら、学習効率は上がりそうですね。 ある程度経験のある数理最適化エンジニアにとっても、モデル化方法の検討がつかないときのサーベイの代替として LLMに聞くというのが有用になるかもしれません。
2.ができたら、実務的なモデリングの補助としても使えそうです。 実際の問題は有名定石単体で解けないケースのほうが多く、 そのような場合定石を組み合わせたり、自分でテクニックを作ってモデル化する必要があります。 ここまでLLMがやってくれるなら、実務的なモデリングの補助として十分有用でしょう。
3.は、ここまでできたらモデリングの初手はLLMとの対話になりそうですね。 これで毎回完璧な答えが出てきたら私達は冷や飯を食わされることになりそうですが…どこまでできるか見てみましょう。
LLM に数理最適化問題をモデリングさせる
現在利用可能な o1 モデルの o1-mini モデルを利用して実験を行います。 確認したいポイントに対応させて、3つのレベルに分けて実験を進めましょう。
1. 有名問題をモデル化できるか/有名定石は使えるか？
まずは有名問題・有名定石のモデリングをさせてみましょう。毛色の違う2つの有名問題を解かせてみます。
巡回セールスマン問題
o1-mini へ次の質問を投げました:
次の課題を混合整数計画問題としてモデル化してください。
「10個の都市をすべて回って出発地点に返ってくる必要がある。移動時間を最短化したい。」
結果は「パラメタ」「決定変数」「制約」「目的関数」の4セクションに分けてください。
これは巡回セールスマン問題という有名問題で、特殊なモデリングの技法が使われていますが「知っていれば書ける」タイプの問題です。 o1-mini の出力を見てみましょう。見出しのレベルだけ編集で本文に合うように揃えている点以外、出力そのままです。
パラメタ
- $ N = \{1, 2, \dots, 10\} $: 10個の都市の集合。
- $ t_{ij} $: 都市 $ i $ から都市 $ j $ への移動時間（$ i, j \in N $, $ i \neq j $）。
決定変数
- $ x_{ij} \in \{0,1\} $: 都市 $ i $ から都市 $ j $ へ移動する場合に1、そうでない場合に0。
- $ u_i $ （連続変数）: 都市 $ i $ の訪問順序を表す補助変数（サブツアー除去のため）。ここでは都市1を出発地点とし、$ u_1 = 1 $ とする。
制約
- 各都市からちょうど1つの都市へ出発する
$$\sum_{\substack{j \in N \\ j \neq i}} x_{ij} = 1 \quad \forall i \in N$$- 各都市へちょうど1つの都市から到着する
$$\sum_{\substack{i \in N \\ i \neq j}} x_{ij} = 1 \quad \forall j \in N$$- サブツアーを防止するための順序変数に関する制約（ミラー・タミルゾーラックの制約）
$$u_i - u_j + 10 \cdot x_{ij} \leq 9 \quad \forall i, j \in N, \, i \neq j$$- 順序変数の範囲制約
$$2 \leq u_i \leq 10 \quad \forall i \in N \setminus \{1\}$$目的関数
総移動時間を最小化する：
$$\min \sum_{i \in N} \sum_{\substack{j \in N \\ j \neq i}} t_{ij} \cdot x_{ij}$$
このモデルは、10個の都市を全て一度ずつ訪問し、出発地点に戻る巡回経路（ツアー）を見つけるための混合整数計画問題として定式化されています。制約条件により、各都市の出発と到着が一度ずつ行われることを保証し、順序変数を用いることでサブツアーの発生を防いでいます。目的関数は、全体の移動時間を最小化することを目指しています。
正しく巡回セールスマン問題がモデリングできているようですね！ 人名だけ間違っているようです。 制約 3., 4. は Miller-Tucker-Zemlin (MTZ) 定式化などと呼ばれます(正確には制約3., 4.を含むこのモデル全体を指す言葉だと思います)。 o1-mini の出力では「ミラー・タミルゾーラック」という知らない人の名前が出てきましたが、これはMTZの人名が日本語で書かれることが稀であるから起きる間違いかもしれませんね。 ちょっと怪しい言葉が登場してしまいましたが、o1-mini は巡回セールスマン問題を「知っている」ということがわかりました。
クラス分け問題
別の有名問題、クラス分け問題を定式化をしてみましょう。 o1-mini へ次の質問を投げました。
次の課題を混合整数計画問題としてモデル化してください。
「120人の学生を3つのクラスに分けたい。3つのクラスの人数は等しくしたうえで、クラス間の成績のばらつきを最小に抑えたい。」
結果は「パラメタ」「決定変数」「制約」「目的関数」の4セクションに分けてください。
次の結果が返ってきました:
以下に、指定された課題を混合整数計画問題としてモデル化します。
パラメータ
$ N = 120 $
学生の総数。$ C = 3 $
クラスの数。$ s_i $
学生 $ i $（$ i = 1, 2, \dots, 120 $）の成績。$ M $
大きな定数（必要に応じて使用）。決定変数
$ x_{i,c} $
バイナリ変数。
$$ x_{i,c} = \begin{cases} 1 & \text{学生 } i \text{ がクラス } c \text{ に割り当てられる場合} \\ 0 & \text{それ以外の場合} \end{cases} $$ ここで、$ c = 1, 2, 3 $。$ \mu_c $
クラス $ c $ の平均成績（連続変数）。$ \delta $
クラス間の成績のばらつきを表す変数（連続変数）。最小化対象。制約
各学生はちょうど1つのクラスに割り当てられる。 $$ \sum_{c=1}^{3} x_{i,c} = 1 \quad \forall i = 1, 2, \dots, 120 $$
各クラスの学生数は40人である。 $$ \sum_{i=1}^{120} x_{i,c} = 40 \quad \forall c = 1, 2, 3 $$
クラスの平均成績を定義する。 $$ \mu_c = \frac{1}{40} \sum_{i=1}^{120} s_i x_{i,c} \quad \forall c = 1, 2, 3 $$
クラス間のばらつきを定義する（例として最大の平均成績差を用いる）。
クラス間の平均成績差を表すために、以下の制約を導入します。 $$ \mu_c - \mu_{c'} \leq \delta \quad \forall c, c' = 1, 2, 3 \text{ かつ } c < c' $$ $$ \mu_{c'} - \mu_c \leq \delta \quad \forall c, c' = 1, 2, 3 \text{ かつ } c < c' $$
目的関数
クラス間の成績のばらつきを最小化する。ここでは、最大の平均成績差 $ \delta $ を最小化します。
$$\text{Minimize } \delta$$
モデルの概要
- 目的: クラス間の平均成績差を最小化することで、成績のばらつきを抑える。
- 制約: 各学生が1つのクラスに割り当てられ、各クラスに40人の学生が配置される。
- 決定変数: 学生のクラス割り当てを表すバイナリ変数と、各クラスの平均成績およびばらつきを表す連続変数。
- パラメータ: 学生数、クラス数、および各学生の成績。
このモデルにより、120人の学生を3つのクラスに均等に分けつつ、クラス間の成績のばらつきを最小化する最適な割り当てを求めることができます。
おおむね問題のないモデリングですね！ 「クラス間の成績のばらつきを最小に」というあいまいな言葉を「最大の平均成績差 $ \delta $ を最小化」と解釈してMIPモデルを作っているのは、よくあるテクニックですが素晴らしいです。 なぜか $M$ という謎のパラメタが導入されていますが無視してあげましょう。 平均成績を変数+制約で定義するのは正しいですが少し無駄のあるモデルにも思えます。これは4セクションに分けてくださいという指示があるため仕方ないかもしれません。
2. 有名問題に簡単な要件を追加してもモデル化がうまくいくか？
有名な問題は知っている/モデリングできるということがわかったので、先程の2問題に少し要件を加えてみましょう。
巡回セールスマン問題 + α
巡回セールスマン問題に要件を加えた問題を投げてみます。下線部 が追加要素です。
次の課題を混合整数計画問題としてモデル化してください。
「10個の都市をすべて回って出発地点に返ってくる必要がある。移動時間を最短化したい。 ただし、特定の3都市を先に訪問し、残りの7都市を後に訪問したい。 」
結果は「パラメタ」「決定変数」「制約」「目的関数」の4セクションに分けてください。
結果は次の通りです(数式の開始終了記号が一部変だったので見やすいよう手作業で修正しています):
以下に、課題を混合整数計画問題としてモデル化しました。
パラメタ（Parameters）
- $N$: 都市の集合、$ N = \{1, 2, \ldots, 10\} $。
- $S$: 先に訪問すべき特定の3都市の集合、$ S \subseteq N $（例：$ S = \{1, 2, 3\} $）。
- $t_{ij}$: 都市 $ i $ から都市 $ j $ への移動時間（$ i, j \in N $, $ i \neq j $）。
決定変数（Decision Variables）
- $x_{ij}$: バイナリ変数。都市 $ i $ から都市 $ j $ への移動が選択された場合に 1、そうでない場合に 0（$ x_{ij} \in \{0,1\} $）。
- $u_i$: 順序変数。都市 $ i $ が訪問される順序を表す連続変数（$ u_i $ は 1 から 10 の整数）。
制約（Constraints）
- 出発点からの移動:
- 出発地点（例えば都市 1）から出る経路は1つ。$$ \sum_{j \in N, j \neq 1} x_{1j} = 1$$
- 各都市の出入り:
- 各都市から出る移動はちょうど1つ。$$ \sum_{j \in N, j \neq i} x_{ij} = 1 \quad \forall i \in N$$
- 各都市に入る移動はちょうど1つ。$$ \sum_{j \in N, j \neq i} x_{ji} = 1 \quad \forall i \in N$$
- 巡回路の排除（サブツアー排除）:
- ミラー・タム・ゾメラック（MTZ）制約を適用。$$ u_i - u_j + 10 x_{ij} \leq 9 \quad \forall i, j \in N, i \neq j$$
- 訪問順序の制約:
- 特定の3都市 $ S $ は、出発点から最初の3つの訪問都市でなければならない。$$ u_i \leq 4 \quad \forall i \in S$$
- 残りの7都市は、訪問順序4より後でなければならない。$$ u_i \geq 5 \quad \forall i \in N \setminus S$$
- 出発点の順序固定:
- 出発地点（例えば都市 1）の順序を1に固定。$$ u_1 = 1$$
目的関数（Objective Function）
- 移動時間の最小化:$$ \min \sum_{i \in N} \sum_{j \in N, j \neq i} t_{ij} x_{ij}$$
以上のモデルにより、10都市をすべて回って出発地点に戻る際に、特定の3都市を先に訪問しつつ、総移動時間を最短化する経路を求めることができます。
これもほぼ正しそうですね！ 良い点も気になるところもあるのでコメントしておきます:
- 先に訪問すべき都市を$N$の部分集合 $S$ として定義しているのは、見通しがよく素晴らしい。
制約 1, 2 を分けているのが不思議。
- 2 で統一したらよさそう。
- 1 での「入る移動」を省略をしているのは、数学的には間違いとはいえない(残りの 1, 2 の制約から導かれる) が、それで意味のある高速化がおきるのかは不明。普通は 2 で統一する気がします。
$ u_i $ が連続変数なのか整数変数なのかよくわらかない書き方になっている。技術的には「$[1, 10]$ の連続変数として定義したら結果的に整数変数になってくれる」というタイプの変数なので、連続変数と書くのが適切。
- 制約4の $≤4, \: ≥5$ は、正しくは $≤3, \: ≥4$ であるべき。
- 定数ミスは慣れてる人でもしてしまう軽微な問題。
- しかし $≤|S|, \:\: ≥ |S|+1$ みたいな書き方だったらミスが発生しないのだから、せっかくならそう書いてほしい。
人力の確認と修正が入る前提であれば、それなりに有用な出力を出せていると思います。
クラス分け問題 + α
クラス分け問題の発展編も解かせてみましょう。 o1-mini へ次の質問を投げます。LLM に喧嘩を防いでもらいましょう。
次の課題を混合整数計画問題としてモデル化してください。
「120人の学生を3つのクラスに分けたい。3つのクラスの人数は等しくしたうえで、クラス間の成績のばらつきを最小に抑えたい。 ただし、何対かの喧嘩をしてしまう生徒ペアがあるため、それらのペアの生徒は必ず別のクラスにしてほしい。 」
結果は「パラメタ」「決定変数」「制約」「目的関数」の4セクションに分けてください。
次の結果が返ってきました:
パラメタ
- $ S $: 学生の集合、$|S| = 120$。
- $ C $: クラスの集合、$ C = \{1, 2, 3\} $。
- $ P_i $: 学生 $ i $ の成績。
- $ K $: 喧嘩をしている学生ペアの集合、$ K \subseteq S \times S $。
決定変数
- $ x_{i,c} $: バイナリ変数。学生 $ i $ がクラス $ c $ に割り当てられる場合は1、そうでなければ0。$$ x_{i,c} \in \{0, 1\}, \quad \forall i \in S, \forall c \in C$$
- $ F_c $: クラス $ c $ の総成績。$$ F_c = \sum_{i \in S} P_i x_{i,c}, \quad \forall c \in C$$
- $ M $: 最大クラス成績。$$ M \geq F_c, \quad \forall c \in C$$
$ m $: 最小クラス成績。$$ m \leq F_c, \quad \forall c \in C$$
制約
各学生はちょうど一つのクラスに割り当てられる：$$ \sum_{c \in C} x_{i,c} = 1, \quad \forall i \in S$$
- 各クラスの人数が40人である：$$ \sum_{i \in S} x_{i,c} = 40, \quad \forall c \in C$$
- 喧嘩をしている学生ペアは同じクラスに割り当てられない：$$ x_{i,c} + x_{j,c} \leq 1, \quad \forall (i,j) \in K, \forall c \in C$$
- クラス成績の定義：$$ F_c = \sum_{i \in S} P_i x_{i,c}, \quad \forall c \in C$$
- 最大および最小クラス成績の定義：$$ F_c \leq M, \quad \forall c \in C$$ $$ F_c \geq m, \quad \forall c \in C$$
目的関数
クラス間の成績のばらつきを最小に抑えるため、最大クラス成績と最小クラス成績の差を最小化する。$$\text{Minimize } Z = M - m$$
このモデルにより、120人の学生を3つのクラスに均等に分けつつ、クラス間の成績のばらつきを最小限に抑え、喧嘩をしている学生ペアが同じクラスに割り当てられないようにすることができます。
すごい、完璧ですね。$F_c, M, m$ の定義がなぜか繰り返されていますが軽微な問題です。 そもそも補助変数が登場する問題はこちらが指定した4セクションに分けた記述になじまないので、出題者側の問題もありそうです。ごめん。
3. 複雑な要件を上手にモデル化できるか？
ここまで、有名問題に毛が生えた程度の問題であれば o1-mini はそれなりに正しくモデル化してくれることがわかりました。 最後にしっかりと複雑な要件を与えて、モデル化できるか見てみます。
o1-mini へ次の質問を投げます。
次の課題を混合整数計画問題としてモデル化してください。
「拠点にある一台の車を使ってすべての店舗を回って拠点に戻る計画を立てたい。拠点と各店舗にはそれぞれタイムウィンドウが設定されている。各店舗のタイムウィンドウは最大3つであり、作業開始時間がいずれかのタイムウィンドウに入っていれば許されるものとする。拠点のタイムウィンドウは1つであるが、出発時刻・帰還時刻のいずれもここに収まる必要がある。巡回中のいずれかのタイミングで1度だけ拠点への報告業務を行うため、ここで一定の時間を使う必要がある。報告業務はいずれかの地点での作業終了直後に行うものとする。報告業務を行うことができるタイムウィンドウは1つ指定されているものとする。各店舗での作業時間・地点間の移動時間・報告業務の時間はパラメタで与えられる。」
結果は「パラメタ」「決定変数」「制約」「目的関数」の4セクションに分けてください。
結果は次の通りです:
パラメータ
- $ N $: 拠点および店舗の集合。拠点を0、店舗を1,…, $ n $ とする。
- $ TW_0 = [a_0, b_0] $: 拠点のタイムウィンドウ。
- $ TW_i = \{ [a_{i1}, b_{i1}], [a_{i2}, b_{i2}], [a_{i3}, b_{i3}] \} $（最大3つ）: 店舗 $ i $ の各タイムウィンドウ。
- $ TW_R = [a_R, b_R] $: 報告業務を行うタイムウィンドウ。
- $ t_{ij} $: 地点 $ i $ から地点 $ j $ への移動時間。
- $ s_i $: 店舗 $ i $ での作業時間。
- $ t_R $: 報告業務に要する時間。
- $ M $: 十分に大きな定数（ビッグM）。
決定変数
- $ x_{ij} \in \{0,1\} $: 車が地点 $ i $ から地点 $ j $ へ移動する場合に1、そうでない場合に0。
- $ t_i \geq 0 $: 地点 $ i $ に到着する時刻。
- $ y_i \in \{0,1\} $: 地点 $ i $ で報告業務を行う場合に1、そうでない場合に0。
- $ w_{ik} \in \{0,1\} $: 店舗 $ i $ がタイムウィンドウ $ k $ （$ k = 1,2,3 $）を使用する場合に1、そうでない場合に0。
制約
- 各店舗の訪問
- 各店舗は一度だけ訪問される：$$ \sum_{j \in N} x_{ij} = 1 \quad \forall i \in N \setminus \{0\}$$
- 拠点から出発する経路：$$ \sum_{j \in N} x_{0j} = 1$$
- 拠点に帰着する経路：$$ \sum_{i \in N} x_{i0} = 1$$
- タイムウィンドウの選択と遵守
- 各店舗はいずれかのタイムウィンドウを選択する：$$ \sum_{k} w_{ik} = 1 \quad \forall i \in N \setminus \{0\}$$
- 到着時刻が選択されたタイムウィンドウ内にある：$$ a_{ik} \leq t_i \leq b_{ik} + M(1 - w_{ik}) \quad \forall i \in N \setminus \{0\}, \forall k$$
- 報告業務の実施
- 報告業務は一箇所で行われる：$$ \sum_{i \in N} y_i = 1$$
- 報告業務を行う時刻が指定のタイムウィンドウ内：$$ a_R \leq t_i + s_i \leq b_R + M(1 - y_i) \quad \forall i \in N$$
- 報告業務の開始時刻が作業終了直後である：$$ t_R = t_i + s_i \quad \text{if } y_i = 1$$ これを線形化するために以下の制約を追加：$$ t_R \geq t_i + s_i - M(1 - y_i) \quad \forall i \in N$$ $$ t_R \leq t_i + s_i + M(1 - y_i) \quad \forall i \in N$$
- 時間の整合性
- 時間の流れを維持する：$$ t_j \geq t_i + s_i + t_{ij} - M(1 - x_{ij}) \quad \forall i,j \in N, i \neq j$$
拠点のタイムウィンドウ遵守
- 出発時刻が拠点のタイムウィンドウ内にある：$$ a_0 \leq t_0 \leq b_0$$
- 帰還時刻が拠点のタイムウィンドウ内にある：$$ a_0 \leq t_{end} \leq b_0$$ ここで、$ t_{end} $ は拠点への最終帰還時刻とする。
サブツアーの排除
- 順序変数 $ u_i $ を用いたMTZ制約：$$ u_i - u_j + n x_{ij} \leq n - 1 \quad \forall i,j \in N \setminus \{0\}, i \neq j$$ ここで、$ u_i $ は地点 $ i $ の訪問順序を示す連続変数であり、$ 1 \leq u_i \leq n $。
目的関数
- 総移動時間の最小化：$$ \min \sum_{i \in N} \sum_{j \in N} t_{ij} x_{ij} + \sum_{i \in N} s_i + t_R$$ ※ 他の目的（例：総移動距離の最小化）を設定することも可能。以上のモデルにより、10都市をすべて回って出発地点に戻る際に、特定の3都市を先に訪問しつつ、総移動時間を最短化する経路を求めることができます。
なんとなくそれっぽくてすごい！のですがよく見ると変なところが目立ちますね。見ていきましょう。
タイムウィンドウ関係の制約は正しく書けていません。「2. タイムウィンドウの選択と遵守」の「到着時刻が選択されたタイムウィンドウ内にある」という制約で「$a_{ik} \leq t_i \leq b_{ik} + M(1 - w_{ik}) \quad \forall i \in N \setminus \{0\}, \forall k$ 」とあります。このままでは左辺の値が常に有効になってしまって、最も遅いタイムウィンドウのみが使われるようになってしまいます。正しくは左辺を $a_{ik} - M(1- w_{ik})$ などとするべきでしょう。「報告業務を行う時刻が指定のタイムウィンドウ内」でも同様のミスがみられます。
「3. 報告業務の実施」の「報告業務の開始時刻が作業終了直後である」という制約は意味不明なものになっています。他の制約にも報告業務による時間経過を妥当な形でモデリングしている箇所はないので、本モデルでは報告業務は無視されていると考えていいでしょう。
$t_{end}$ に関しても変数定義などの準備が足りていないのはいただけませんし、「時間の整合性」を与えている以上「MTZ制約」は不要です。また不要な「MTZ制約」中でも係数が$n$地点の場合のものが書かれているところと (実際には地点数は$n+1$)、拠点の$u_0=0$が関与しない書き方になっているところも良くないですね。
これくらいしっかりと間違えていると、 LLM が答えてくれたモデルを修正して正しいモデルを作るというのが効率の良い作業なのか疑問になってきます。
まとめ
実験結果のまとめです:
- 有名問題をモデル化できるか / 有名定石を利用できるか？ ▶ できる
- 有名問題に簡単な要件を追加してもモデル化がうまくいくか？ ▶ ちょっとできる
- 複雑な要件を上手にモデル化できるか？ ▶ できない
o1-mini は有名問題の知識をもっており、これに簡単な改変を加える程度の思考であればある程度やってくれそうです。 一方で、見たことがないような複雑な要件を与えると、意味不明なモデリングを行ってしまうようです。
現時点では以下の2つの使い方ができそうです:
- 数理最適化初心者が簡単なモデルを作りたいとき・学習したいとき
- 簡単なモデルは作ってくれる
- ただし正誤判断は自分でできる必要があるため、 教科書で基本的な勉強をしたうえで利用する
- 中級者~上級者レベルの人のモデリング補助
- LLMの知識の幅は圧倒的。調査・検討をしたいときに「ダメもとで聞いてみる」のには意味がありそう
- たとえば、定石をしらない問題がでてきたときに(枝葉の要件を削って)モデル化させてみて、良さそうなもの使う and/or 出典を調べて調査する、など
LLMを使って面白いモデルを書いていきましょう！
