高度な LP の解決

LP 技術は成熟度を増していますが、一部のユースケースでは、より高度な手法が必要になります。たとえば、LP のアルゴリズムと実装にはさまざまなものがありますが、それぞれに長所と短所があります。さらに、数値が不安定な場合、解法が遅くなったり、特定のモデルの解決に失敗したりすることがあります。

このガイドでは、LP ソルバーのパフォーマンスと信頼性を最大化するためのコンセプトを紹介し、例を示します。

概念

このセクションでは、LP ソルバーの高度な使用方法に関する主なコンセプトについて説明します。ここでは、LP における二重という概念に精通していることを前提としています。

LP アルゴリズムのファミリー

LP の次のクラスのアルゴリズムには、OR-Tools を介してアクセスできます。

  1. Simplex アルゴリズムは、最初の実用的な LP アルゴリズムであり、現在でも最も人気があります。アルゴリズムは実行可能領域の頂点（角点）に沿って歩き、最適な解に到達するまで目的関数の値を繰り返し改善します。シンプレックス アルゴリズムには、次の 2 種類があります。

    1. 基本シンプレックスは、基本実行可能領域の頂点に沿ってステップを実行します。このバリアントは、さまざまな目的関数を持つ、つまり主要な実行可能領域が固定されている一連の LP 問題を解く場合に特に効果的です。
    2. デュアル シンプレックスは、デュアル実行可能領域の頂点に沿ってステップを実行します。このバリアントは、変数の境界のみが変更された場合など、二重実行可能領域が固定されている一連の LP 問題を解決する際に特に効果的です。このため、デュアル シンプレックスは MIP ソルバーで広く使用されています。

  2. バリアまたは内部点手法は、LP の 2 番目の実用的なアルゴリズム ファミリーでした。バリア手法では、効率的な（多項式時間）収束の理論的な保証と、実際の信頼性の高いパフォーマンスを組み合わせます。シンプレックス アルゴリズムのパフォーマンスが低い場合は、シンプレックス アルゴリズムを補完します。たとえば、シンプレックスとバリアの両方を並列に実行し、最初に完了したアルゴリズムから解を求めるソルバーがあります。

  3. 1 次メソッドは、勾配情報（1 階導関数）のみを使用して反復処理をガイドするアルゴリズム ファミリーです。よく知られた例として 勾配降下法があります。これらの方法は、非線形最適化と ML でよく利用されています。LP の場合、1 次メソッドはシンプレックスやバリアよりも大きな問題にスケーリングでき、メモリ要件もはるかに小さい場合があります。それ以外の場合は数値の問題に敏感で、高精度の解を得るのが困難である可能性があります。

以下の表は、OR-Tools で利用可能な LP ソルバーと、3 つのアルゴリズム ファミリーのいずれが各ソルバーに実装されるかを示しています。

ソルバー シンプレックス Barrier 1 回目の注文
Clp X X
CPLEXL X X
GlopG X
GLPK X X
グロービルL X X
PDLPG X
XpressL X X

G は、ソルバーが Google によって開発されたことを示します。L は、ソルバーにそれぞれのサードパーティ デベロッパーから発行されたライセンスが必要であることを示します。

使用するソルバーとアルゴリズムに関する提案については、推奨事項をご覧ください。

「解決」とは、実際には何を意味するのでしょうか？

LP 解法を最大限に活用するには、LP 問題の解法を解明したと主張する解法が意味するものを理解することが重要です。このセクションでは、特に数値の不正確さとソリューションの一意性の欠如を考慮して、この質問に回答するために必要な基本事項について説明します。

許容差

LP 解法ではほとんどの場合、浮動小数点演算を使用するため、解が数値の不精度になる可能性があります。これを考慮し、すでに十分に良いソリューションに取り組むことを避けてパフォーマンスを改善するために、ソリューションは、ソリューションが特定の許容範囲までの条件を満たす場合に、ソリューションを受け入れ、問題を解いたと主張します。

線形計画問題を考える

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

対応する二重問題を

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

この一対の問題には、$ x_1 = 1、x_2 = 0 $、二重解 $ y = -2 $ という唯一最適な原理解があります。解法では、どの解が最適として受け入れられるでしょうか。これに答えるために、次の数量を定義します。

  • 二重性ギャップは、基本目標値と二重目標値の差です。この場合は、$ |(-2x_1 - x_2) - y| $ となります。
  • 主な実行不能は、基本制約に違反することです。この場合、$ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\}-x_2, 0\}) $です。
  • 二重制約とは、二重制約に違反することを指します。この場合は、$ (\max\{ 2 + y, 0 \}, \max\} 1 + y, 0 \}, \max\} y, 0 \}) $ となります。

ソルバーは、二重性ギャップ、主要な非実現性、二重実現性が所定の許容値より小さい場合、解を最適と宣言します1。

特に、許容値の適用は、ソルバーとアルゴリズムの自然な理由と固有の理由の両方で異なります。たとえば、シンプレックス アルゴリズムの二重性ギャップは数値の不精度によってのみ発生しますが、基本と二重の非実現可能性は正確な計算でも存在します。 あるメソッドでは、$ x_1 \ge 0, x_2 \ge 0, $ および $ y \le 0 $ という境界制約を直接適用するメソッドもあれば、$x_1 + x_2 \le 1$ のような線形制約の違反に対する $ \ ibual の違反を異なる方法で処理します。また、問題によっては $ \ ibual が等価性と相対的に等しくない、すなわち、E が最適となるパラメータもあります。

許容差の影響の例として、$ \epsilon = \frac{1}{2} $ という絶対許容度を上記の基本二重ペアに適用した場合を考えてみます。解 $ x_1 = 1.5、x_2 = 0、y = -3 $ にはゼロの二重性ギャップがあり、実行不能性はすべて $ \epsilon $ 以下であるため、解法はこの解を「最適」と宣言することがあります。しかし、その目標値（-3）は、真の最適な目標値である -2 と 1 だけ異なります。$ \epsilon $ の一般的なデフォルト値は $10^{-6}$ から $10^{-8}$ であり、このような極端な例はまれですが、不可能ではありません。

ソリューションの種類

LP の問題には複数の最適な解が存在する場合がありますが、許容差を考慮する場合は特にそうです。上記の LP アルゴリズムの 3 つの異なるファミリーが返すソリューションの特性について簡単に説明します。

シンプレックス アルゴリズムは常に実行可能領域の頂点または隅の点を返します。これらのソリューションはスパースになる傾向があるため、状況によっては推奨されます。

バリア メソッドと 1 次メソッドは通常、頂点を返しません。（このガイドでは説明しませんが、その他の特徴も説明しています）。

歴史的な理由と頂点ソリューションには魅力的な特性があるため、ソルバーはデフォルトでクロスオーバー手順を適用して、バリア アルゴリズムによって見つかった解から最適な頂点に移動します。現在、一次的な方法で見つかったソリューションではクロスオーバーは提供されていません。

推奨事項

LP ソルバーの高度な使用方法について、次の推奨事項があります。

問題データのスケーリング

数値の問題により、モデルの収束が遅くなったり、エラーになったりすることがあります。このような問題が生じる理由はさまざまです。ここでは一例を挙げます。

LP モデルでは、数値定数が非常に小さい、または大きいことが一般的です。上記の例を拡張し、 \(x_1\) \(x_2\) が「プロバイダ 1」または「プロバイダ 2」に割り当てられた顧客の割合を表す場合、これらの顧客にサービスを提供するメリットを最大化するには、次の目的関数を記述します。

$$ \min -c_1x_1 - c_2x_2 $$

ここで

  • $ c_1 $ は、顧客をプロバイダ 1 に割り当てることによるメリット
  • $ c_2 $ は、顧客をプロバイダ 2 に割り当てることによるメリット

次の制約を満たす Duals は、絶対許容差 $ \epsilon $ で実行可能とみなされます。

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $。

$ c_1 $ と $ c_2 $ の利点単位が $ \epsilon $ と同じスケールになる小さな小数値である場合、二重実現可能性条件がかなり弱くなるため、非常に最適でない原理が最適であると宣言される可能性があります。

一方、給付単位が「マイクロドル」（1,000,000 マイクロドル = 1 ドル）である場合、結果として得られる絶対値が非常に大きいため、解の精度が非常に高くなり、浮動小数点数の制限を考えると、不当に高くなる可能性があります。この方法で問題を定式化した場合、解法が収束に失敗する可能性があります。高度なモデル化担当者は、適切に設定された問題を構造化する際に、解法の許容範囲に沿うように問題データがスケーリングされるかどうかを検討する必要があります。

数値エラーを回避するだけでなく、パフォーマンス向上のために許容範囲を調整することもできます。シンプレックスとバリアのメソッドは許容度にそれほど敏感にはなりませんが、解法の終盤で進行が停滞することが確認された場合は、許容差を大きくしたほうが良い場合があります。一方、通常、1 次メソッドは機密性が非常に高くなります。1 次メソッドのユーザーには、コンテキストが許す限り許容範囲を緩和することで、迅速なソリューションからメリットがあります。

Glop の許容値については、GlopParameters の primal_feasibility_tolerance、dual_feasibility_tolerance、solution_feasibility_tolerance をご覧ください。primal_feasibility_tolerance と dual_feasibility_tolerance はアルゴリズム内で使用され、solution_feasibility_tolerance は数値上の問題を報告するために解決後にチェックされます。PDLP については、eps_optimal_absolute と eps_optimal_relative をご覧ください。

この種の問題の詳細については、Gurobi の 数値問題に関するガイドラインをご覧ください。このガイドラインは Gurobi のユーザー向けに作成されていますが、原則の多くは一般的に適用されます。

解法とアルゴリズムの選択

まず、解法とアルゴリズムの選択による影響がどの程度大きいかを示す例から始めて、LP 解法を選択するためのガイドを提示します。

実際のばらつき

LP アルゴリズムとソルバーのパフォーマンスのばらつきを、Hans Mittelmann が LP ソルバーのベンチマークに使用したいくつかのインスタンスの解決時間を比較することで示しています。インスタンスは、相対的なパフォーマンスの極値を示すために明示的に選択されており、必ずしも一般的な動作を表すわけではありません。

Glop の基本およびデュアル シンプレックス方法を、Gurobi のバリア法（クロスオーバーの有無で頂点解法を見つける）や一次法である PDLP と高精度および低精度を比較します。下の表は、解決時間を秒単位で報告します。上限は 20 分（1, 200 秒）です。

インスタンス Glop
基本シンプレックス		 Glop
デュアル シンプレックス		 グロービ バリア
（クロスオーバー付き）		 グロービバリア
（クロスオーバーなし）		 PDLP
高精度		 PDLP
低精度
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3rd >1200 252.8 1,446 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 46.4 32.4
wide15 >1200 2,080 万台 >1200 >1200 9,164 万台 56.3
建物エネルギー 178.4 267.5 12.8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
ソルバーのバージョン OR-Tools 9.3 OR-Tools 9.3 Gurobi 9.0 Gurobi 9.0 OR-Tools 9.3 OR-Tools 9.3
solver_specific_parameters （デフォルト） use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

これらの結果から、以下の結論を導き出します。

  • アルゴリズムとソルバーの相対的なパフォーマンスは、単一のインスタンスでは桁違いに変化します。
  • 単一のアルゴリズムや解法が他のアルゴリズムや解法より均一に優れていることはありません。
  • クロスオーバー（デフォルトで有効）により、解決時間が長くなり、場合によっては大幅に長くなります。
  • PDLP では、高精度の 10 倍の速さで低精度を解決できます。

LP ソルバーを選択するための簡単なガイド

単一の LP アルゴリズムや解法で最善のものは存在しないため、次の手順でユースケースに最適なものを見つけることをおすすめします。最初のステップから開始し、パフォーマンスが十分でない場合は次のステップに進みます。

  1. Glop をお試しください。理由: Glop は、基本とデュアル シンプレックス メソッドを Google が社内で実装したものです。Glop はオープンソースであり、Google の本番環境ワークロードで信頼されています。
    • デフォルトの構成（基本シンプレックス）がうまく機能しない場合は、use_dual_simplex: true を使用してデュアル シンプレックスに切り替えてみてください。
  2. ライセンスが利用可能な場合は、商用ソルバー（CPLEX、Gurobi、Xpress）を試します。シンプレックス手法やバリア手法を試してみましょう。理由: これらのソルバーは業界標準であり、高度に最適化されています。また、バリア方式は Glop が提供するシンプレックス アルゴリズムを補完します。
    • バリアを使用する場合、頂点ソリューションが不要な場合は「クロスオーバー」を無効にします。
  3. PDLP をお試しください。アプリケーションに合わせて収束の許容値を調整します。理由: PDLP は、シンプレックス手法とバリア手法がメモリ上限に達したり、速度が遅すぎるなどの大きな問題用に設計されています。PDLP は、厳密には時間のかかるソリューションよりも、概算で迅速なソリューションのほうが効果を発揮します。
  4. ここまで来たら、あなたは上級 LP ユーザーです。詳しくは、OR-Tools のサポート オプションをご覧ください。

  1. 多くの場合、これよりも複雑です。ソルバーは通常、事前解決問題と呼ばれる問題を変換または簡素化したバージョンで、これらの条件をチェックします。場合によっては、事前に解決された問題の解が、入力の問題に対する解決策とはかけ離れていることがあります。これにより、CPLEX の OptimalInfeas や Glop の IMPRECISE などの異常なステータスが発生する可能性があります。↩