巨大インスタンスは、LP Solverが問題

 Instance20-23でのClp時間を見てみます。NEOS　Serverに乗っかるぎりぎりのサイズ(16MB程度）で、MPSファイルを生成しています。

NEOS上のLPSolverは、COPTを除いて自動的にBarrier　Solverを選択してくれるようです。CLPは、UbuntuPC上にあるそれでSimplexです。

この結果から分かる通り、NSP巨大インスタンスでは、LP　Solverの性能がボトルネックです。現状CLPでは、最初の整数解が出て来るまでに一週間から一ヶ月程度計算機を廻さないといけません。

この問題に対してStrandmarkさんは、FirstOrder　Solverを用いることを提案しています。

https://www.strandmark.net/papers/first-order-scheduling.pdf

しかし私の厳密解に拘るアプローチでは、FirstOrderは、精度の問題があり使えません。Simplexの良い点は、WarmStartできる点にあります。そこで、First Order　Solverや、Barrier　Solverの結果をSimplex形式に変換するCrossoverという手法があります。

2102.09420.pdf (arxiv.org)

Initial Basis Selection for LP Crossover (cerfacs.fr)

どのように巨大インスタンスに立ち向かうべきか思案中です。