cuopt-numerical-optimization-formulation

数理最適化の定式化

問題の説明から、LP、MILP、QPにわたって明確な定式化を行うための概念とワークフローです。ここではAPIコードを扱いません。

LP / MILP / QPとは

• LP：線形目的関数、線形制約、連続変数です。
• MILP：LPと同じですが、一部の変数が整数またはバイナリです（例：スケジューリング、施設配置、選択）。
• QP：二次目的関数（例：x²、x·y の項 — ポートフォリオ分散、最小二乗法）と線形制約です。cuOptでのQPサポートは現在ベータ版です。

問題の種類の特定

特性	LP	MILP	QP
目的関数	線形	線形	二次（xᵀQx + cᵀx）
制約	線形	線形	線形（二次制約なし）
変数	連続	混合：連続 + 整数/バイナリ	連続
方向	最小化または最大化	最小化または最大化	最小化のみ（最大化の場合は符号を反転）

目的関数が純粋に線形の場合は、LP/MILPを優先してください。二次項を人為的に導入しないでください。変数のいずれかが整数またはバイナリの場合、ほかの条件にかかわらず問題はMILPです。

定式化に必要な質問

まだ明確でない場合は、以下を確認してください。

1. 決定変数 — どのような変数ですか？上下限はありますか？
2. 目的関数 — 最小化ですか、最大化ですか？線形ですか、二次ですか？QPの場合、二乗項または交差項（x²、x·y）はありますか？二次関数を最大化する場合、ユーザーは符号を反転して最小化する必要があります。
3. 制約 — 線形不等式制約または等式制約ですか？（二次制約はサポートされていません。）
4. 変数の型 — すべて連続（LP / QP）ですか、それとも整数/バイナリ変数が含まれますか（MILP）？
5. 凸性（QPのみ） — 適切に定義された問題にするには、最小化の場合、二次形式（行列Q）が半正定値である必要があります。

典型的なモデリング要素

• 連続変数 — 生産量、フロー、割り当て、ポートフォリオのウェイト。
• バイナリ変数 — 開く/閉じる、はい/いいえ（例：施設を開く、項目を選択する）。
• 連結制約 — 例：施設が開いている場合にのみ生産する（Big-Mまたはインジケーター）。
• リソース制約 — 使用量の線形上限（材料、時間、容量）。
• 二次目的関数の項 — 分散（xᵀQx）、二乗誤差（‖Ax − b‖²）、相互作用項。

典型的なQPのユースケース

• ポートフォリオ最適化 — リターンと予算の制約のもとで分散を最小化します。
• 最小二乗法 — 線形制約のもとで‖Ax − b‖²を最小化します。
• 線形制約を伴うその他の二次目的関数。

---

問題文の解析

ユーザーが問題文を提示したら、定式化する前に各文を分類し、その後に要約してください。以下の解析フレームワークは、LP / MILP / QPのいずれにも適用されます。

各文を パラメーター/所与の条件、制約、決定事項、または目的関数として分類してください。暗黙の制約（例：確定事項と任意事項を示す表現）や暗黙の目的関数（例：「計画を決定する」+ コスト → 総コストを最小化）に注意してください。

曖昧さ： まだ曖昧な点がある場合は、ユーザーに質問するか、考えられるすべての解釈について解いて結果をすべて報告してください。単一の解釈を仮定しないでください。

🔒 必須：不確かな場合は質問する

• 制約または値を含めるべきかどうかに少しでも疑問がある場合は、ユーザーに質問し、考えられる解釈を伝えてください。

🔒 必須：完全な経路での実行 — すべてのバリエーションを試す

• ユーザーが完全な経路の実行（例：エンドツーエンド、フルパイプライン）を求めた場合は、考えられるすべてのバリエーションを実行し、結果をすべて報告して、ユーザーが選べるようにしてください。単一の解釈を仮定しないでください。

3 つのラベル

ラベル	意味	例（文の種類）
パラメーター／与件	固定データ、入力、事実です。モデルが選択するものではありません。	「需要は 100 単位です。」「工場は 3 つあります。」「コストは 1 単位あたり 5 ドルです。」
制約	満たさなければならない条件です。明示されている場合もあれば、表現から暗黙的に読み取れる場合もあります。	「生産能力は 200 です。」「すべての需要を満たす必要があります。」「少なくとも 2 交代制で人員を配置する必要があります。」
決定	選択または最適化するものです。	「生産量をどれだけにするか。」「どの施設を開設するか。」「何人雇用するか。」
目的	最小化または最大化するものです。明示的（「コストを最小化する」）な場合も、暗黙的（コストが与えられたうえで「計画を決定する」）な場合もあります。	「総コストを最小化する。」「生産計画を決定する」（コストが与えられている）→総コストを最小化する。

暗黙の制約：確定事項としての表現と任意事項としての表現

確定・固定を示す表現 → パラメーターまたは暗黙の制約として扱います（言及されていることはすべて与件であるか、実施しなければなりません）。決定ではありません。

表現	解釈	理由
「X 個の製品を生産する計画です」	制約：X 個すべてを生産する必要があります。	確定事項であり、生産量は固定されています。
「工場を 3 つ操業しています」	パラメーター：3 つすべてが稼働しています。立地選択の問題ではありません。	現状は固定されています。
「N 人の従業員を雇用しています」	パラメーター：N 人全員が雇用されています。採用の決定ではありません。	従業員数は与件です。
「生産能力は C です」	パラメーター（C）＋制約：使用量 ≤ C です。	生産能力は固定されています。
「すべての需要を満たさなければなりません」	制約：需要を充足する必要があります。	明示的な要件です。

任意・決定を示す表現 → 決定として扱います。

表現	解釈	理由
「最大で…まで生産できます」	決定：生産量をどれだけにするか。	水準は任意です。
「（工場や拠点を）開設する選択ができます」	決定：どれを開設するか。	選択を決定します。
「採用を検討しています」	決定：何人採用するか。	採用を検討中です。
「注文量を決定します」	決定：注文量です。	明示的な決定です。
「…を最小化／最大化したいと考えています」	目的（決定を導くもの）。	目標であり、決定はそのための手段です。

暗黙の目的 — 見落とさないこと

問題が「計画を決定する」（または同様の表現）よう求めていて、「最小化」や「最大化」が明示されていない場合、目的が暗黙的に示されていることがよくあります。 定式化の前に、必ず目的を特定して明示してください。目的のないモデルを作成してはいけません。

表現／文脈	考えられる暗黙の目的	理由
「生産計画を決定する」＋コストが提示されている（単位あたり、時間あたりなど）	総コストを最小化する（生産＋検査／販売＋残業など）	計画を選択し、コストが示されているため、総コストの最小化が自然な目標です。
「計画を決定する」＋コストと収益が提示されている	利益を最大化する（収益 − コスト）	収支の両方が示されているため、利益を最適化します。
「月間生産計画を決定してみる」＋工場の時間あたりコスト、検査／販売コスト	総コストを最小化する	すべてのコスト項目が示されており、最大化する収益がないため、総コストを最小化します。

ルール： 問題でコスト（またはコストと収益）のデータが与えられ、「計画を決定する」「計画を見つける」「計画を立てる」よう求められた場合、必ず目的を明示してください（例：「コストのみが示されているため、目的は総コストの最小化とします。」）。コストと収益の両方がある場合は、「コストを最小化する」のか「利益を最大化する」のかを明示してください。不明な場合はユーザーに確認してください。

解析ワークフロー

1. 分割：問題文を文または論理的な節に分けます。
2. 分類：それぞれを次のいずれかに分類します：パラメーター／既知の値 | 制約 | 意思決定 | 目的（記載されている場合）。
3. 目的を特定する（明示的または暗黙的）：「X を最小化／最大化する」と問題文にある場合、それが目的です。「計画を決定する」（または「見つける」「確立する」といった表現）としか書かれていなくても、コスト（および場合によっては収益）が示されている場合、目的は暗黙的です。これを明示します（例：総コストの最小化、または利益の最大化）。曖昧な場合はユーザーに確認します。
4. 暗黙的な制約に印を付ける：各文について、「これは固定された事実または要件（→パラメーター／制約）を示しているか、それともこちらで選ぶ内容（→意思決定）か」と確認します。
5. 動詞と助動詞を確認して曖昧さを解消する：
   • 「である」「持つ」「運営している」「雇用している」「計画している」（固定／確定済み）→パラメーターまたは暗黙的な制約。
   • 「してもよい」「選択できる」「検討している」「決定する」「したい」（任意）→意思決定または目的。
6. 🔒 必須 — まだ曖昧な点がある場合（例：値や制約に複数の解釈があり得る場合）は、どの解釈が正しいかをユーザーに尋ねるか、考えられるすべての解釈について解き、結果をすべて報告します。単一の解釈を勝手に採用してはいけません。
7. ユーザー向けに要約する：数式を定式化する前に、パラメーター、制約（明示的および印を付けた暗黙的なもの）、意思決定、**目的（明示的または推定）**を列挙します。

解析チェックリスト

• すべての文に分類が付いている（パラメーター | 制約 | 意思決定 | 記載されている場合は目的）。
• 目的を特定している：明示的（「最小化／最大化」）または暗黙的（「計画を決定する」＋コスト → 総コストを最小化、収益あり → 利益を最大化）。目的を明示せずに定式化してはいけません。
• 確定を示す表現（「計画している」「運営している」「雇用している」）→意思決定ではありません。
• 任意を示す表現（「してもよい」「選択できる」「検討している」）→意思決定です。
• 確定を示す表現から生じる暗黙的な制約を明記している（例：「すべての X を生産する必要がある」）。
• 🔒 必須 — 曖昧さ：二通りに解釈できる表現があれば、ユーザーに尋ねるか、考えられるすべての解釈を解いて結果をすべて報告します（解釈を黙って一つに決めてはいけません）。
• 定式化の前に要約を作成している（パラメーター、制約、意思決定、目的）。

例

テキスト：「会社は 3 つの工場を運営しており、500 個を生産する計画です。追加費用をかけて残業を利用してもかまいません。総コストを最小化してください。」

文／句	分類	備考
「3 つの工場を運営している」	パラメーター	3 つすべてが稼働中であり、工場を選択する問題ではありません。
「500 個を生産する計画です」	制約（暗黙的）	500 個すべてを生産する必要があります。
「追加費用をかけて残業を利用してもかまいません」	意思決定	残業の量は意思決定です。
「総コストを最小化してください」	目的	意思決定を導きます。

結果：パラメーター = 3 つの工場、生産目標 500 個。制約 = 500 個を正確に生産する（「生産する計画です」からの暗黙的な制約）。意思決定 = 工場間の生産配分、残業の量。目的 = コストの最小化。

暗黙的な目的の例：「生産計画を決定する」（または同様の表現）よう求められ、コスト項目（例：作業場、検査、販売）が示されていても、「最小化」または「最大化」と明記されていない問題 → 目的は暗黙的です：総コストの最小化。常に「目的は総コストを最小化することです」と明示してください。

---

QP のルール：最小化のみ

QP の目的は最小化でなければなりません。二次式を最大化するには、その符号を反転して最小化し、最適値の符号も反転します。

最小化問題が適切に定義されるには、二次形式 Q が半正定値である必要があります。Q が不定値の場合、問題は非凸であり、有限の最適値が存在しないことがあります。

---

よくあるパターン

以降のセクションでは、LP／MILP の具体的なモデリングパターンを扱います。それぞれは独立しているため、問題に合ったものを読んでください。

整数生産を伴う区分線形目的関数

凹型の区分線形利益関数やコスト関数（例：まとめ売りで限界利益が逓減する場合）をモデル化する標準的な方法では、各セグメントの幅を上限とする連続変数を使います。凹型利益関数を最大化する場合、ソルバーは利益の高いセグメントから自然に割り当てます。

注意点：生産する数量が離散的（個、単位、品目など）である場合、セグメント変数は連続のままでも、総生産量変数は整数にする必要があります。そうしないと、LP 緩和によって、真の整数最適解とは異なる目的関数値（より高い、または低い値）を生む小数の総生産量が得られる場合があります。

パターン

x_total  — INTEGER (total production of a product)
s1, s2, … — CONTINUOUS (amount sold in each price segment, bounded by segment width)

Link: x_total = s1 + s2 + …
Resource constraints use x_total.
Objective uses segment variables × segment profit rates.

素材切断・端材問題

素材切断問題では、廃材面積には端材（各切断パターンで使われない幅）と過剰生産（需要を超えて生産された余分な帯材）の両方が含まれます。端材だけ（パターンごとの廃材幅 × 長さ）を最小化すると、過剰生産が考慮されず、目的関数が不正確になります。

正しい目的関数

必要な有効面積の合計は定数なので、廃材の最小化は、消費する材料面積の合計の最小化と同じです。

minimize  sum_j (roll_width_j × x_j)

ここで、x_j はパターン j を使って切断する長さです。このとき、廃材面積は次のようになります。

waste = total_material_area − required_useful_area

ここで、required_useful_area = sum_i (order_width_i × order_length_i) です。

注意点

目的関数に sum_j (waste_width_j × x_j) を使うと、端材、つまり各パターンで使われない帯材しか考慮されません。注文分を超えて生産した分はペナルティの対象になりません。ソルバーはパターンを効率よく使うために幅の狭い注文品を過剰生産しますが、その余分な材料も廃材です。目的関数には必ず材料面積の合計を使ってください。

目標計画法（優先順位付き／辞書式）

目標計画法では、複数の目的を優先順位に従って最適化します。優先順位ごとに 1 回ずつ逐次的に求解して実装します。

定式化パターン

1. ハード制約 — 容量制限、非負条件など。すべてのフェーズで成立します。
2. 目標制約 — 各目標について、偏差変数（未達を表す d⁻、超過達成を表す d⁺）を導入し、等式 expression + d⁻ − d⁺ = target を記述します。
3. 優先順位に従って逐次的に求解します。
   • フェーズ 1：最優先の目標に関係する偏差を最小化（または最大化）します。
   • フェーズ k：より優先順位の高いすべての偏差を最適値に固定してから、優先順位 k の偏差を最適化します。

目標計画法での変数の型

偏差変数（d⁻、d⁺）とスラック変数／アイドル時間変数は、常に連続です。ただし、意思決定変数は、離散的／計数可能な数量（生産単位、車両、作業員など）を表す場合、引き続き整数でなければなりません。連続偏差変数があるからといって、すべての変数を連続にしないでください。意思決定変数の整数性は、実行可能性と目的関数値に直接影響します。

複数期間の在庫・購入モデル

複数の期間にわたって購入、販売、倉庫容量を扱う問題では、問題のタイミングに関する前提に基づいて、含める容量制約を決めてください。

パターン

在庫バランス stock[t] = stock[t-1] + buy[t] - sell[t] が成り立つ各期間 t について：

• 期間末の容量（変数の上限）：stock[t] <= capacity — 常に必要です。
• 購入後の容量（明示的な制約）：stock[t-1] + buy[t] <= capacity — 期間内に販売が行われる前に、倉庫の収容能力を超えて購入することを防ぎます。

購入後の制約を含めるタイミング

• 含める場合： 問題文で、期間内に販売より先に購入品を受け取ること（逐次的な操作）が明示または示唆されている場合、または倉庫がどの時点でも物理的に容量を超えられない場合です。
• 省略する場合： 期間内に購入と販売が同時に行われ（教科書的な取引・在庫問題で一般的です）、容量制約が期間末の在庫にのみ適用される場合です。古典的な問題の多くでは、期間末の在庫だけが制約されます。

販売制約との重要な相互作用： モデルにすでに sell[t] <= stock[t-1] がある場合（今期に購入した穀物は今期中に販売できません）、購入後の制約がなくてもモデルは有界です。販売制約によって、購入と販売を繰り返して量を無制限に増やすことを防げます。この場合、購入後の制約は数学的に必要な制約ではなく、追加の物理的制約となります。

デフォルト： 期間内のタイミングが問題文で指定されていない場合は、期間末の容量制約（stock[t] <= capacity）のみを使用してください。購入後の制約を追加するのは、問題文で明示的に求められている場合に限ります。

混合工程または中間処理を共有するブレンド

ブレンド問題によっては、複数の原材料を製品ごとに振り分ける前に、まずまとめて混合する必要があります（例：混合タンクでの混合）。その結果得られる中間材は均一な組成になります。つまり、異なる原材料を製品ごとに独立して割り当てることはできません。

標準的なブレンド LP が適切でない理由

標準的なブレンド LP では変数 x[i][j]（製品 j に含まれる原材料 i の量）を使い、各原材料を各製品に自由に割り当てます。原材料を共有の混合工程に通す場合、その原材料を受け取るすべての製品で、それらの原材料の比率を同一にする必要があります。この比例制約は双線形（x[A,1]*x[B,2] = x[B,1]*x[A,2]）であり、LP で直接表現することはできません。

線形化の方法

1. 単一製品への割り当て： 分析の結果、中間材が利益を生む製品が1つだけである場合は、中間材をすべてその製品に割り当てます（ほかの製品への中間材の割り当てをゼロにします）。これにより、比例制約は自明に満たされます。これは最も一般的なケースです。一般的な分割を試みる前に、各製品で中間材を使った場合の収益性を確認してください。

2. 中間材の濃度をパラメーター化： 中間材の硫黄濃度または品質濃度をパラメーター σ として固定します。σ を固定するごとに、問題は標準的な LP になります（中間材は特性が既知の仮想原材料になります）。複数の σ の値を並べて解くか、問題の構造を利用して最適値を解析的に求めます。

3. シナリオの列挙： 製品が2～3種類しかない場合は、中間材を受け取る製品の組み合わせを列挙します（すべて A、すべて B、分割）。受け取り先が1つだけの各シナリオでは、LP は標準的なものになります。分割するシナリオでは、方法2を使います。

収益性の確認

定式化する前に、各製品で中間材を使用した場合に利益が出るか確認してください。

• 実現可能な原材料の組み合わせのうち最も安価なものを使って、中間材のトン当たり最小コストを各製品の販売価格と比較します。
• ある製品 j で cost_intermediate > sell_price[j] となる場合、中間材を製品 j に割り当てるべきではありません。原材料 C（またはほかの直接投入物）だけでも、cost_C > sell_price[j] なら利益が出ない可能性があります。
• この分析により、双線形の分割をまったく行わずに済むこともよくあります。