最適化問題のサイズと求解時間に関係はあるか？

オリジナルURL：What is the correlation between problem size and solution time?

概要

一般に、問題のサイズとGurobiによる求解時間の間に明確な相関性はありません。最適解を発見し、その最適性を証明するために必要な時間は、お手元の問題に対してGurobiのアルゴリズムがどの程度有効に働くかに依存します。

ただし、特定のモデルのファミリー、すなわち例えば同じ代数的な表現を持ち異なったデータから生成されたようなモデルの集合に対してであればこのような関係を定義可能な場合はしばしばあります。

例

Gurobiのインストーラで提供されている例では、glass4とmisc07というほぼ同じサイズの2つのモデルがあります。これらのモデルをデフォルト設定のGurobi 10.0で解くと、求解時間は25倍も異なります。

• glass4.mps with 396 rows, 322 columns, 1815 nonzeros: ~50 seconds
• misc07.mps with 212 rows, 260 columns, 8619 nonzeros: ~2 seconds

(*rows=制約の数, columns=変数の数)

例外: ファイルから最適化問題を読み込む場合

最適化問題がファイル（例えば MPS ファイル）から読み込まれる場合、すべてのデータをメモリ上のGurobiデータ構造にロードする必要があるため、この読み込み時間は問題のサイズに応じてある程度スケーリングされます。

その他の資料

• Is there a way to predict how long it will take Gurobi to solve a MIP?
• Does using more threads make Gurobi faster?
• Are there performance differences amongst the different Gurobi APIs?
• Why does Gurobi perform differently on different machines?