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）
制約	線形	線形	二次錐を介した線形制約 + 凸二次制約（不等式のみ）
変数	連続	混合：連続 + 整数／バイナリ	連続
最適化の方向	min または max	min または max	最小化のみ（max の場合は符号を反転）
双対値／感度	双対値 + 縮約費用	なし（整数最適解）	双対値 + 縮約費用

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

求解後の感度分析（LP / QP のみ）。 連続 LP および QP の解では、双対値（拘束制約を 1 単位緩和したときの限界目的関数変化：結果を改善するためにどこへ投資すべきか）と、縮約費用（最適化器によってゼロのままになった変数が解に入るには、どれだけ改善する必要があるか：惜しくも採用されなかった候補）を取得できます。MILP の解には双対値がありません — 整数最適解は連続ではないため、返却できる双対値がありません。モデルに二次制約が含まれる場合も、双対値は利用できません — 二次錐の経路では主変数値のみが返されます。求解後の取得方法については、言語別の API スキルを参照してください。

定式化に必要な質問

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

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を最小化／最大化する」）または暗黙的（「計画を決定する」＋費用 → 総費用を最小化、＋収益 → 利益を最大化）。目的を明記せずに定式化してはいけません。
• 確約を示す表現（「〜する予定である」「運用している」「雇用している」）は、意思決定として扱っていない。
• 任意を示す表現（「〜してもよい」「選択できる」「検討する」）は、意思決定として扱っている。
• 確約を示す表現から導かれる暗黙の制約を明記している（例：「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] であれば採算が取れない可能性があります。
• この分析により、双線形な分割を完全に省けることもよくあります。