cuopt-multi-objective-exploration

多目的探索

cuOpt は、1 回の求解につき 1 つの目的を最適化します。現実の多くの問題には、コストとサービスレベル、利益とリスク、メイクスパンと残業、距離と車両台数など、互いに相反する複数の目的があります。1 回の求解でわかるのは「特定の重み付けにおける最適解」ですが、ユーザーが知る必要のあるトレードオフは見えなくなります。

このスキルでは、単一目的の cuOpt 求解を連続して実行し、パレートフロンティア（ある目的を改善するには、別の目的を犠牲にしなければならない解の集合）を導き出し、その読み解き方を説明します。ソルバーの機能は追加せず、定式化スキルと API スキルで扱った LP／MILP／QP の求解を組み合わせます。

この方法が適用される場合

合意された重み付けのない 2 つ以上の目的がある場合に、このワークフローを使います。次のような表現が目印になります。

• 「X と Y のバランスを取る」「トレードオフ」「サービスを損なわずに、できるだけ安く」
• 「コストを最小化し、かつカバレッジを最大化する」「1 つの答えではなく、選択肢がほしい」
• 別の目的と引き換えに緩和してもよいとユーザーが考える目的全般

明確な目的が 1 つだけで、その他すべてが厳格な制約である場合、このスキルは適用されません。1 回だけ定式化して求解してください。

基本的な考え方 — 1 回の求解は曲線上の 1 点

単一の最適解には、目的に対する暗黙の重み付けが 1 つ反映されています。重み付けを変えると、最適解も変わります。フロンティアとは、支配されない最適解すべてが描く曲線です。

解 A が解 B を支配するのは、A がすべての目的で B 以上に優れており、少なくとも 1 つの目的で厳密に優れている場合です。支配された解を選ぶ価値はありません。パレートフロンティアは支配されない解の集合そのものであり、フロンティア上の点を選ぶのはユーザーの役割です。あなたの役割は、トレードオフが最も急になる場所とともに、曲線全体を示すことです。

多目的問題を単一の加重値にまとめ、その最適解を「答え」として提示してはいけません。それでは、ユーザーに代わってトレードオフを決めてしまいます。フロンティアを追跡し、ユーザーが選べるようにしてください。

目的と制約は入れ替えられます。現在は固定条件として扱われている要件（カバレッジの下限、公平性の上限、予算など）は、潜在的な目的であることがよくあります。その水準は与えられたものではなく、仮定されたものだからです。このような制約をパラメーター付きの ε 制約に昇格させて値を変化させると、そうしなければ見えなかったトレードオフが明らかになります。そのため、単一目的モデルの厳格な制約は単なる上限・下限ではなく、候補となる目的として捉えてください。ただし、その水準が仮定に基づく場合に限ります。真に固定された譲れない制限（厳格な予算上限、規制上の最低基準など）は制約のままにしてください。実際には存在しないトレードオフを作り出してはいけません。昇格させる量は、ε 制約として使えるように線形式で表します（cuopt-numerical-optimization-formulation を参照）。

ステップ 1 — 目的を定義する

有益なフロンティアを得るには、実際に相反する目的が必要です。互いに相反しない場合、トレードオフのない単一の点に収束します。また、定式化の形式、向き、スケールが間違っているとトレードオフがゆがみ、転換点の位置も変わるため、それぞれの目的を正しく定式化する必要があります。値を変化させる前に、cuopt-numerical-optimization-formulation を使って各目的を定式化してください。

ステップ 2 — ペイオフテーブルを作成する（各目的を基準化する）

まず、各目的を単独で最適化します。目的が k 個なら、求解も k 回です。それぞれの最適解における全目的の値を記録します。

              f1        f2        f3
min f1   →   f1*       f2(at f1*) f3(at f1*)
min f2   →   ...       f2*        ...
min f3   →   ...       ...        f3*

対角要素（f1*、f2*、…）は各目的で達成可能な最良値を示します。非対角要素は、他の目的の最適解において各目的が取りうる範囲を示します。このテーブルには次の 2 つの役割があります。

• ε 制約法の値の範囲（制約対象の各目的が取りうる実行可能範囲）を設定します。
• 正規化に必要なスケールを与えます。ドル、パーセント、時間で表された目的は、それぞれの値を範囲で割るまで、意味のある重み付けができません。

単一目的の求解のいずれかが実行不可能な場合は、値を変化させる前に作業を止め、モデルを修正してください。フロンティアはまだ存在しません。

ステップ 3 — スカラー化手法を選ぶ

重み付き和

目的関数を1つにまとめ、重みを変えながら探索します。

minimize  w1·f1(x) + w2·f2(x) + ... ,   for a grid of weight vectors w

どのソルバーでも安価かつ簡単に実行できます。ただし、次の2点に注意が必要です。

• フロンティアの凸包上にある点しか見つかりません。 フロンティアの凹領域（非凸領域）は、重みをどう選んでも到達できません。また、MILP では到達可能な点がまばらになり、大きな間隔が生じることがあります。フロンティアが不自然なほど直線的に見えたり、点が少数のクラスターにしか集まっていなかったりする場合は、その兆候です。
• 目的関数を正規化しない限り、重みは優先順位を表しません。 まず各 f_k をペイオフテーブルの範囲で割ります。そうしないと、意図にかかわらず、絶対値が最大の目的関数が支配的になります。

ε制約法（完全なフロンティアを得る場合に推奨）

1つの目的関数を残し、ほかの目的関数は制約に移して、右辺を変えながら探索します。

minimize  f1(x)
subject to  f2(x) ≤ ε2
            f3(x) ≤ ε3
            (original constraints)

各 ε_k をペイオフテーブルの範囲にわたって変化させます。各 (ε2, ε3, …) の組み合わせは、cuOpt の標準的なソルバー実行1回に相当します。重み付き和では到達できない凹領域も含め、フロンティア全体を得られるため、完全性が重要な場合のデフォルトの方法です。その代わり、ソルバー実行回数が増え（制約対象の目的関数に対するグリッド探索）、ε値の管理も必要になります。

線形の目的関数は、直接 ε制約にします。2次目的関数（たとえばリスク xᵀΣx）は、線形の目的関数を ε制約にしながら、目的関数 f1 として残すのが最も簡単です。凸2次目的関数を直接 ε制約にすることもできます。その場合、2次制約 xᵀQx ≤ ε として追加します。cuOpt はこれをサポートしています。非凸の2次制約と等式の2次制約はサポートされておらず、MILP の経路では線形制約のみが使えます。

既存のコードでは、目標値や予算値（リターン目標、コスト上限など）を手書きのループで変化させている場合、すでに ε制約法を使っています。この方法の名前を明示し、支配される点を除外したうえで、探索対象の制約の双対値を確認してください（LP/QP のみ）。

双対値は局所的な交換レートとして読み取ります。 フロンティアが滑らかな箇所では、探索対象の ε制約の双対値がその傾きを示します。これは、すでに実行したソルバー処理以外のコストをかけずに、上限を単位量動かしたときに、残した目的関数 f1 がどれだけ変化するかを表します。折れ曲がりの箇所では、一方向のレートしか得られません。双対値がゼロの場合、通常は上限に余裕があることを意味し、探索がフロンティアの端を越えています（上限に余裕がある場合は常に双対値がゼロになりますが、縮退があると、上限に達していてもゼロになることがあります）。この読み方が使えるのは LP/QP と、線形の ε制約の場合です（MILP の最適解と2次制約を含む問題では双対値は返されません）。双対値が使えない場合は、隣接するフロンティア上の点どうしの差を計算してください。

方法の選び方： 凸形状の概略をすばやく把握したい場合や、フロンティアが凸だとわかっている場合（純粋な LP/QP のトレードオフなど）は重み付き和を使います。問題が MILP の場合、フロンティアが非凸の可能性がある場合、またはユーザーが正確で完全な曲線を必要としている場合は、ε制約法を使います。

ステップ 4 — 探索、収集、フィルタリング

frontier = []
for each weight vector (or ε vector) in the grid:
    set the combined objective (or ε right-hand sides)
    solve with cuOpt              # reuse the prior solution as a warm start
    if status is Optimal/Feasible:
        record (objective values, solution)
discard dominated and duplicate points
sort the survivors to form the frontier

実践上の注意：

• LP 探索ではウォームスタートを使います。 LP フロンティアを探索する場合、次の求解に直前の求解の PDLP ウォームスタートデータを引き継ぐと、求解時間を短縮できます。cuOpt では LP のみが対象です。MILP の求解では PDLP ウォームスタートを使用できません（代わりに、必要に応じて MIP スタートを設定できます）。呼び出し方法については cuopt-numerical-optimization-api を参照してください。
• 各 MILP 求解に上限を設定します。 MILP の探索では、求解ごとに時間制限を設定してください（cuopt-numerical-optimization-api を参照）。探索では多数の求解を行います。また、分枝限定法はごく小さなギャップを超えて最適性を証明しようとして、時間を使いすぎることがあります。一方、cuOpt はデフォルトで制限を設けず、警告も出しません。結果の点は、証明済みの最適解ではなく、設定したギャップに対して最適なものとして報告してください。
• 劣解に支配された点を除外します。 正しい探索でも、劣解に支配された点が出力されることがあります（特に、凸包付近の加重和法や MILP で発生します）。これらはフロンティアの一部ではないため、取り除いてください。
• 解像度は予算です。 曲線の忠実度と求解回数はトレードオフの関係にあります。まず粗い設定で形状を把握し、その後、曲線が曲がる箇所だけグリッドを細かくしてください。
• 傾きが変化する箇所に予算をかけます（LP/QP）。 ε 制約法の双対値はフロンティアの局所的な傾きを表すため、求解済みの点どうしで比較します。変化がごく小さい箇所では曲線はほぼ直線なので、求解を追加する代わりに補間します。差が求解許容誤差を超えて大きい箇所では、その点どうしの間でフロンティアが曲がっているため、そこで細かくします（それより小さな差は曲率ではなく、ソルバーのノイズです）。こうすることで、一様なグリッドに求解を分散させるのではなく、実際に曲線が曲がる箇所に集中できます。MILP では、代わりに主目的関数値の間のギャップを見て、細かくする箇所を判断します。
• 思い込みではなく、検証します。 ある手法が別の手法より優れていると主張する場合は、それを測定してください。たとえば、加重和法では見つからず、ε 制約法で得られた効率的な点の数を数えます。主張するだけではいけません。また、Optimal ではなく実行可能解を返した求解にはフラグを付け、証明されていない点が正確な値として扱われないようにしてください。

ステップ 5 — フロンティアを完成させる：測定し、探索で見落とした部分を補う

加重和法の探索で得られるのは 支持点 のみです（ステップ 3 の凸包による制約）。MILP のフロンティアでは、非支持点、つまり加重和法でどのような重みを設定しても得られない点が、非劣解集合の大部分を占めることがよくあります。粗い ε 制約グリッドでも同様にギャップが残ります。有限回の探索では、どのような場合でも領域を見落とす可能性があります。探索で得られたフロンティアを提示する前に、見落としの可能性を測定し、補完するかどうかを判断してください。

見落としを測定する

探索で得られた点を目的関数の一方でソートします。隣接する各点の間に、目的空間で矩形（一般には直方体）を作ります。中央値よりかなり大きい矩形（目安として 3 倍）や、フロンティアが占める面積の大部分をカバーする矩形にフラグを付けます。得られた点がほんの数個しかない探索では、すべての箇所にギャップがあるため、中央値と比べても目立つ矩形はありません。大きな矩形が生じる原因は 2 つあります。非支持領域（加重和法では到達できず、固定費構造でよく見られるもの）と、重みの集中（ほぼ凸なフロンティアでも、有限のグリッドでは同じ角を何度も見つけてしまうこと）です。補完の手順では、どちらの原因にも同じ方法で対処します。

すべての矩形が小さく、均等であれば、探索はおそらく十分です。その旨を伝えて、終了してください。

最大のギャップから先に埋める

フラグが付いた各ボックスについて、その内部を対象とする ε 制約部分問題を 1 つ解きます。片方の目的を最適化し、もう片方はボックスの中点で制約します（目的が 2 つの場合。目的がそれ以上ある場合は、各目的ごとに順番にソートし、再帰処理の代わりに、フラグが付いた各ボックスに目標値を 1 つ設定します）。ここで確定や方針決定の根拠にできるのは、認証済みの Optimal 結果だけです。時間制限に達した時点の暫定解は点として保持します（下記のタグを付けます）が、ギャップについては何も証明しません。Step 4 の優越性フィルターを通過した新たな認証済みの点は、ギャップが実際に存在したことを意味します（ε ソルバーは弱最適点を返す場合があります）。ボックスを二分割し、できた 2 つのサブボックス内に目標値を追加します。認証済みの端点が返された場合、境界の調査した側だけがクリアになります。ボックス全体が真の不連続であると認証するには、既知の目的関数のステップサイズ（整数変数に対する目的関数係数がすべて整数なら得られます）も必要です。このステップサイズを使って、遠い側の端点のすぐ内側に境界を設定し、その認証済み最適値と一致することを確認します。ステップサイズが分からない場合は、そのボックスを不連続の証明済み箇所ではなく、ギャップ候補として報告します。解の予算に達するか、残りのボックスがフラグのしきい値を下回ったら終了します。

各解でウォームスタートする（手軽な備え）

連続する埋め合わせ解では制約が 1 つだけ異なるため、それぞれの解に隣接する解を MIP 開始点として設定します（Step 4 のウォームスタートに関する注記）。1 行で済み、最適解が変わることもありません。解時間は変わらないと見込んでください。難しい部分問題に備えるための措置です。

段階的にフォールバックし、決して黙って処理しない

部分問題が時間制限に達し、実行可能な暫定解（FeasibleFound）が得られた場合、その点を保持します。実行可能であり、解で報告されたギャップがその劣解の程度を上から抑えます。ただし、近似として記録します。時間制限付きの解は、暫定解と境界値の両方を返すため、第一のフォールバックとして使います。ヒューリスティックのみのモード（mip_heuristics_only）では証明処理が省かれ、ギャップ境界のない実行可能点が返されます。実行可能点だけが必要な場合に使い、返されたすべての点に近似のタグを付けてください。

出典情報を添えて報告する

提示する各点には、次の 2 種類のタグのいずれかを付けます。

• exact — 設定したギャップに対して Optimal、つまりそのギャップの範囲で最適です（Step 4）。
• approximate — 時間制限に達した時点の暫定解（報告されたギャップを記載）またはヒューリスティックのみの結果（境界値は存在しないことを明記します）。

フロンティアの点数と内訳を記載します（「14 点、exact が 11 点、低コスト側付近に approximate が 3 点、最大ギャップは 2.4%」）。混在するフロンティアを、すべて一様に最適であるかのように提示しないでください。

ステップ 6 — パレートフロンティアを解釈する

• 単一の数値ではなく、トレードオフを報告します。 フロンティア上の点は、それだけでは意味をなしません。交換比率を「この領域では、カバレッジを 1% 追加するごとに約 4,000 ドルのコスト増」のように示し、その移動に価値があるかユーザーが判断できるようにします。LP/QP のフロンティアでは、この交換比率はその点における掃引対象の制約の双対値、つまりフロンティアの局所的な傾きであり、求解の最適性許容誤差の範囲で正確です（双対値を信頼する前に、許容誤差を厳しくしてください）。MILP では、隣接するフロンティア上の点との間隔から推定します。
• 膝点にはフラグを付けます。自動で選ばないでください。 「膝点」とは、曲線が最も急に曲がる位置であり、そこを超えると、わずかな改善に大きなコストがかかります。バランスの取れた妥協点として最適なことが多く、注目する価値はありますが、最終的な選択はルールではなく、ユーザーの好みに委ねます。膝点では傾きが左右で異なります。すぐ手前の双対値とすぐ先の双対値は異なるため、交換比率は単一の数値ではなく範囲で示します。
• 支配された出力や点の欠けた出力は、診断の手がかりとして扱います。 フィルタリング後に支配された点が残る場合や、フロンティアが不自然に疎、または完全に線形である場合は、掃引方法かモデルに問題がないか確認します。多くの場合、加重和法で凹領域が隠れている（ステップ 5 に戻って、その間の点を補う）か、正規化に誤りがあります。
• 使用した重み付け／εを明記します。 報告する各点は、そのスカラー化を前提としています。単一の求解結果が「唯一の」最適解と誤解されないよう、そのことを明示してください。LP/QP では、ε 制約の双対値はその点における暗黙の重みです。これは、解が各制約付き目的に付ける実効価格であり、加重和法の求解で同じトレードオフを再現するために必要な重みでもあります。これらを報告すると、採用したトレードオフ比が明確になります。

インターフェース

このスキルは、ソルバーやインターフェースに依存しません。目的関数の構築、ε 制約の追加、ウォームスタートの指定、ステータスの読み取りといった求解ごとの処理は、API スキルに記載されています。

• cuopt-numerical-optimization-api — LP、MILP、QP の求解（Python、C、CLI）。
• cuopt-routing-api-python — 同じフロンティアのワークフローを、ルーティングのトレードオフ（距離と車両数と時間）にも適用できます。