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

概要

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

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

例

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

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

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

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

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

その他の資料

• Gurobi がMIPを解くのにかかる時間を推定する方法はあるか？
• 多くのスレッドを利用することでGurobiは高速化するか？
• GurobiのAPIの言語によってパフォーマンスに違いはあるか？
• Gurobiの動作はなぜ異なるマシン上で変化するのか？