2011 年 6 月 1 日

Gurobi Optimizer version 4.5 ベンチマーク総合評価
Gurobi Optimizer 4.5 は、優位を維持
Gurobi Optimizer 4.5 が他のソルバに対する優位性を維持していることが、重要な実用ベンチマークで示されました。Gurobi はコア数 1、4、12 いずれの場合でも、最適化のモデルを CPLEX や XPRESS より一貫して高速に解きました。あるベンチマーク問題グループでは、Gurobi の平均パフォーマンスは、他の 8 倍を超えています。さらに、計算時間に制限が課せられている時には、他のソルバが解を得られない場合でも Gurobi は頻繁に解を得ています。計算が速いことと確実に解が得られることは、最適化ソルバにとって重要なことであり、役に立つ解と生産性の向上をユーザにもたらします。
アリゾナ州立大学のミッテルマン教授は、多くの最適化ソルバと広範な種類の最適化問題について、ベンチマーク結果を公表しています。ベンチマーク問題は８つの種類に分かれ、実数と混合整数の LP について、3 つの代表的な商用最適化ソルバの性能を比較しています。
ベンチマーク全体を見ると、Gurobi Optimizer 4.5 は、CPLEX 12.2.0.2 と XPRESS 7.2 より一貫して優れていることが明らかになります。このベンチマークの詳細は、ミッテルマン教授のウェブサイ
トBenchmarks for Optimization Softwareに示されています。
以下では、そのベンチマーク結果を、項目別に説明します。
混合整数計画(MIP)ベンチマークでの Gurobi の優位•

Feasibility: MIP問題で、実行可能解をひとつ見つけるまでの時間を測定しています。Gurobiの速度は平均で、CPLEXの 3 倍、XPRESSの 8 倍を超えています。

•Infeasibility: MIPモデルに実行可能解がないことを証明することは、モデル開発において重要な意味を持ちます。GurobiはCPLEXより 20%、XPRESSより 80%速く、実行不可能性を証明しました。

•Pathological: 極端に例外的な問題についてのベンチマークです。ここでGurobiは勝っていませんが、ミッテルマン教授は「このベンチマーク項目は、ソルバ間の代表的な相対比較ではない」と断っており、最高のMIPソルバにも例外的に不得意な問題があることを示しています。テスト
モデルが頻繁に入れ替えられているために、この項目での勝者は、頻繁に入れ替わっています。

•MIQP: 目的関数が 2 次のMIPモデルについての性能測定です。Gurobiの平均の速さは、CPLEX、XPRESSの 2 倍を超えています。解けない問題が少ない点でも、Gurobiは優れています。

•MIPLIB 2010: MIP最適解を得る時間の比較です。この表を作成する時、Gurobi 4.5 はbetaバージョンしか公開されていなかったため、Gurobi 4.5 betaが他のソルバの正式リリースバージョンと比較されています。この比較表にはまだ載っていませんが、Gurobi Optimizer 4.5 正式リリース版は、CPUコア数が 1 でも 12 でも、CPLEX 、XPRESSより良い結果が得られています。

他のソルバと Gurobi の計算時間比 Gurobi を 1.0 とする
Benchmark

CPLEX

XPRESS

P=1

P=4

P=12P=1

P=4

P=12Feasibility

3.57x

-

-

8.16x

-

-

Infeasibility

-

1.20x

-

-

1.80x

-

Pathological*

-

0.83x

-

-

0.98x

-

MIQP

-

2.43x

-

-

2.22x

-

MIPLIB 2010 - beta**

1.17x

-

0.98x

0.85x

-

0.94x

MIPLIB 2010**

1.40x

-

1.16x

1.02x

-

1.11x

表中の '-' は、データがないこと示しています。
* この項目の値はウェブページFrom Prof. Mittelmannのデータを使用しましたが、サイトの所有者
ミッテルマン教授は、「このベンチマーク項目は、ソルバ間の代表的な相対比較ではない」と断っています。
ここで示したのは、Gurobi 社独自の見解です。
** MIPLIB 2010 関してはふたつの値が載っています。上段は Gurobi Optimizer 4.5 ベータ版によるもので、公式にはこの値が採用されています。下段は Gurobi Optimizer 4.5 正式リリース版の値で、公式にはまだ発表されていません。表中の値から分かるように、正式リリース版は明らかに改善されています。正式リリース版の結果は、近いうちに公式に発表されるでしょう。

次の表は、異なる観点から MIP に対する Gurobi の性能を示しています。テスト問題ごとに異なる値を設定した制限時間内に、各ソルバが解けなかったモデル数を示しており、値が小さいほど、制限時間内に多くの問題が解けたことを示しています。例えば MIPLIB 2010、コア数 12 で、Gurobi は全 87 問の解を得ています。一方 XPRESS は 87 問中の 7 問で解が得られませんでした。全体として Gurobi
Optimizer 4.5 は、CPLEX や XPRESS より、制限時間内に解が得られなかった問題数がかなり少ないです。

問 解けなかった問題数
Benchmark

題Gurobi

数

P=1P=4P=12P=1P=4P=12P=1P=4P=12Feasibility

342-

-

5-

-

7-

-

Infeasibility

12-

0-

-0-

-

1-

Pathological

16-

4-

-

3*-

-

7*-

MIQP

24-

0-

-

2--

2-

13-

3*

14-

7MIPLIB

2010

beta**87

MIPLIB 2010**

1212CPLEX

3-0XPRESS

表中の '-' は、データがないこと示しています。
* CPLEX と XPRESS が解けなかった原因のうちのいくつかは、クラッシュまたはメモリオーバーによるものです。
** MIPLIB 2010 関して Gurobi Optimizer 4.5 だけふたつの値が載っている理由は、前の表と同じです。

線形(LP)のベンチマークでの Gurobi の優位•

Dual Simplex と Barrier with Crossover: デュアル・シンプレックスとバリア・アルゴリズム
は、LP問題の解法として広く使われています。この比較表を見れば、コア数が 1 でも 4 でも、Gurobiが速いことが分かります。

•Barrier without Crossover: この表は、バリアでクロスオーバーを使わないという、一般的でない解き方で比較しています。この解き方が必要なことはまれであるため、テスト問題は少ししか用意されていません。Gurobiは大規模で解きにくい問題で良い結果を出しており、実用アプリケーションで優れていることを示しています。
他のソルバと Gurobi の計算時間比 Gurobi を 1.0 とする

Benchmark

CPLEX

XPRESS
P=1

P=4

P=1

P=41.36x-1.16x-

LP Barrier with Crossover

-

1.50x

-

1.16x

LP Barrier without Crossover

-

2.04x

-

0.76x

LP Dual Simplex

表中の '-' は、データがないこと示しています。

Gurobi Optimization の提供する最適化ソルバは、広範な産業分野で使われています。
性 能 、 個 別 の 最 適 化 問 題 を ど う 解 く か な ど 、 Gurobi Optimizer 4.5 に 関 す る よ り 詳 し い 情 報
は、info@octobersky.jpにお問い合わせください。
以上