7

私はLPを初めて使用PuLPし、Pythonで簡単に使用しただけです。

  1. SCIP 3.2.1 - CPLEX 12.63と の間に速度差があるのはなぜCPLEX 12.6.3ですか? SCIP はまだ解決に CPLEX を使用していませんか?

  2. CPLEX を直接使用する代わりに、CPLEX ソルバーで SCIP を使用するのはなぜですか?

ここに画像の説明を入力

4

1 に答える 1

13

この違いは何ですか

このプロットは LP ベンチマークではなく、混合整数計画ベンチマークを示しています。

混合整数計画法ソルバーは、通常、(ヒューリスティックスなどを含む)分岐カットベースのアルゴリズムを使用します。このアルゴリズムでは、多くの緩和が解決されます (順番に; バイナリ/整数変数を連続として扱い、LP 問題が発生します)。 ）。

その場合の 1 つの決定は、これらの緩和された副問題をどのように解決するかを選択することです。最も単純な決定 (他にも多数あります。たとえば、シンプレックス アルゴリズムのパラメーターを調整します。非線形円錐目的の問題を解く場合はさらに複雑になります) は、LP ソルバーを選択することです。

SoPlexは、SCIP チームによる LP ソルバーの実装です。意味：

  • SCIP - SoPlex は、内部 LP サブ問題のソルバーとして SoPlex を使用して、MIP (分岐、カット生成などの処理) に SCIP のアルゴリズムを使用します。
  • SCIP - CPLEX は、CPLEX を内部 LP サブ問題のソルバーとして使用する MIP に SCIP のアルゴリズムを使用します。

(純粋な CPLEX アプローチを使用する代わりに) CPLEX で SCIP を使用する理由

その理由を説明するのはそれほど簡単ではありません。

  • すべての MIP ソルバーはヒューリスティックに基づいており、問題によっては SCIP が CPLEX よりも高速になることに注意してください(基礎となる LP ソルバーが選択されているにもかかわらず)。

    いくつかの理論のキーワード: (MIP の) NP 困難性とNo free lunch 定理

    • より速いということは、基礎となる LP ソルバーの速度ではなく、MIP ベースの戦略によってより速くなるため、部分問題で CPLEX を使用して全体的な速度を向上させることさえできるということです!

  • 2 つのソルバー (MIP ソルバー) は、(内部アルゴリズム コンポーネントの) パラメータとアクセシビリティに関しても、おそらく大きく異なります。CPLEX よりもはるかに一般的な方法で SCIP を調整できることは明らかです (オープン ソースであるため)。

  • コメントでmattmiltenが述べたように：SCIPとCPLEXは、解決できる問題クラスのサポートに関しても異なります。この 1 つの例は、いくつかの特別な非線形制約(結果として MINLP が発生する)の可能性です。この種の問題に SCIP を使用しても、CPLEX の LP ソルバーを内部的に使用できます (上記と同じ議論)。

于 2016-10-07T19:22:04.747 に答える