Gurobi Optimizer：ソルバー
ユーザは、Gurobiの分散最適化を使用することで複数マシンを活用でき、求解時間を短縮できます。いくつかの数理最適化モデルでは、32台のマシンの利用で15倍もの求解時間の高速化が実現され、8台のマシンでは平均で2～3倍も高速化しています。
Gurobiでは、下記の3つの最適化アルゴリズムを利用できます。
- 分散MIP : 複数マシンを活用し、一つのMIPモデルを求解
- 分散並列最適化： 複数マシンを活用し、異なるアルゴリズムを用いて競争をさせてLPまたはMIPモデルを解く
- 分散チューニング：複数マシンで試行的求解を行い、パフォーマンス改善を実現するパラメータセットを見つけ出す
上記に挙げた3つの分散アルゴリズムを使うのは簡単です。分散ワーカとして使用したい複数マシンに Gurobi リモートサービスをインストールし、あとは 1 台のマシンで最適化を実行したり、チューニングを実行したりするのとまったく同じようにGurobi Optimizerのコマンドを入力するだけで使用できます。Gurobi Optimizer のパラメータで、分散アルゴリズムを走らせることができるワーカとなるマシンの名前を指定し、別のパラメータでワーカ上に起動すべきジョブの数を指定すれば、Gurobi Optimizer が複数マシンにまたがり計算を分割する全ての仕事を処理します。
分散最適化により速度改善がどの程度実現できるかは、モデルに依存します。
Gurobi Optimizer での分散最適化
Gurobi Optimizerは、ユーザの目的に合わせて複数種類のアルゴリズムが利用できます。
分散 MIP（一つのMIPモデルを解くため複数マシンを活用）
| 手法および効果 | 1 つのMIPモデルを解く作業を、複数マシンの間で分割します。マネージャとなるマシンは、MIP探索ツリーの異なる部分をそれぞれのワーカとなるマシンに送信して解かせ、定期的にすべてのワーカが望ましい負荷状態になるよう探索ツリーを再調節します。 MIPLIB2010ベンチマークセットを使用したパフォーマンステストが、分散MIPの利点を示しています。例えば、求解に100秒以上かかるMIPLIB2010ベンチマークセットで8台のマシンを使って分散MIPを実施した場合、2.87倍も速度が改善しました。分散MIPは、MIPLIB2010ベンチマークセットのいくつかの最も難しいモデルに対しては、劇的に求解時間を短縮しています。例えば、MIPLIB2010の集合被覆問題のインスタンスであるseymourでは、1台のマシンで求解に9,627秒もの時間がかかっていましたが、32台のマシンを使って分散MIPで解いた場合は、633秒まで求解時間を短縮できました。これは、14.6倍もの速度改善です。 |
| 効果的なモデル | 大きな探索ツリーを持つような難度の高いモデルに効果があります。これらのモデルを分散MIPで解くためには、すべての分散ワーカが常に動作していることが必要です。なお、より簡単なモデルでは、余分な分散ワーカは必要ありません。 |
分散並列最適化（LPまたはMIPモデルを解くために、異なるアルゴリズムを用いて競争させるため複数マシンを活用）
| 手法および効果 | 分散並列最適化は、複数マシン活用のためシンプルな手法を採用しています。複数のマシンを使い、マシン毎にそれぞれ異なったアルゴリズムを用いて解を求めます。そして、どのアルゴリズムを使ったマシンが一番早く解けるのかを競い合います。求解は、最初のマシンがゴールラインを通過した時点で終了します。異なったアルゴリズムを同時に試すことで、分散並列最適化は、たった一つのアルゴリズムを選択して解を求めるより高速に解を見つけ出すことがあります。Gurobiが実施したテストでは、難しい広範囲にわたるLPモデルのセットで2台のマシンを使った場合に1.1倍の速度を改善し、難しい広範囲にわたるMIPモデルのセットで5台のマシンを使った場合では、1.7倍も速度を改善しました。 |
| 効果的なモデル | モデルを定義するために使われたデータ、または、求解するために利用されたアルゴリズムによって求解時間が大きく変化するようなモデルに効果があります。異なるアルゴリズムを異なるマシンで試すことで、システムの堅牢さが増し、求解時間のバリエーションを平準化することができます。 |
分散チューニング（パフォーマンス改善のためのパラメータセットを見つけ出すために、試行的求解をするため複数マシンを活用）
| 手法および効果 | 一つのモデルまたは複数モデルのセットに対して、最適化パフォーマンス改善を実現するパラメータセットを自動的に探索します。このチューニングツールは、とても効果的でかつユーザがとても支持していることが証明されています。一つの否定的な側面は、時間がかかるということです。自動チューニングは、対象モデルに対して異なるパラメータセットを使用しながら、多くの試行的求解を行います。通常、改善されたパラメータセットの探索に、モデルを単純に求解するのにかかる時間のおよそ10倍程度の時間を要するとみていいでしょう。（大抵は、チューニングツールをより長時間稼働させれば、より良い結果を得ることができます。）分散チューニングツールは、複数の独立したマシンをチューニング作業に用いますので、同じ時間内でより多くのパラメータセットの候補を探索することが可能になります。Gurobiの社内ベンチマークテストでは、デフォルトのパラメータセットと比較した場合、分散チューニングで発見されたパラメータセットを使うと2倍を超えるパフォーマンス改善ができたことが示されました。 |
| 効果的なモデル | 1台のマシンでの求解時間を、最大限に速度改善ができるパラメータセットを見つける必要がある場合に効果があります。 |
動作環境（必要なマシン）
分散最適化アルゴリズムは、分散ワーカとして稼働する複数台のマシンが必要です。これらの分散ワーカ用のマシンは、すべてのマシンが同じマシンスペックであることが一番望ましいですが、マシンスペックがわずかに異なる場合でも問題ありません。分散最適化を利用するのに一番良いマシン台数は、8～32台です。ただし、分散並列最適化の場合は2～16台が最も効果的です。分散ワーカ用のマシンに異なるライセンスは必要なく、Gurobi リモートサービスをインストールだけです。
ご購入の前に
分散最適化オプションご購入の前に、分散最適化を試してみたい、自身のモデルの速度改善がどれくらいできるかを知りたい方は、下記の方法で試すことができます。
- 対象のモデルを弊社に送付。弊社とGurobiがお送りいただいたモデルでどれくらいの速度改善が可能かを試して、その結果をご連絡します。
- すでに分散最適化オプションが使えるライセンス（ネームドユーザ・ライセンス、無制限使用・無制限ユーザ・ライセンス、計算サーバ･ライセンス）をお持ちであれば、分散最適化オプションの期間限定の評価ライセンスをご提供します。
