HIGHS1.11LPソルバの評価

 HIGHSの1.11、PDLP版をテストしてみました。

＜PDLP版のコンパイル＞

### Build HiGHS with GPU support

HiGHS must be built, from the root directory, with 

cmake -S. -Bbuild -DCUPDLP_GPU=ON

cmake --build build --parallel

＜PDLP版のオプション指定＞

精度/crossoverの有無等は、コマンドラインから指定できないので、例えば次のようにオプションファイルを指定して、オプションファイルの中で指定します。

highs --options_file highs.opt instance21.mps

solver = pdlp

kkt_tolerance = 1e-7

run_crossover = on

＜結果＞

下表がその結果になります。GPUは、4060TISuperです。

PDLP-Cとの比較

COPT版PDLP-Cとの比較では、1e-4でみると、COPT版の方が速いですが、実用的な精度である1e-7でみると、COPT版では、収束しませんでした。従い、速度的には遅いもののHIGHS版の方が、安定的と見ます。MIPソルバでは、1e-7位の精度がないと使い物にならないという事情があると思いますので、恐らくは、HIGHSチームの意図的な設計によるものと見ます。

HIGHS　IPM版のとの比較

内点法ソルバが更新された模様で、以前のものより速くなっています。内点法ソルバは、WarmStartが出来ないものの、Analytic Centreを使えば、安定度はSimplexよりも良い、との報告もあります。一方、PDLP版では、インスタンス規模とSpeedとの関係が不明確で、必ずしも規模と速度の相関がありません。（規模の小さいinstance19が最も遅くなっている）

これに対して、Highs IPM版では、規模と速度の相関が安定的であるとも言えます。精度に対するSensibityも殆どなく、PDLPと比較すると、遥かに安定していると言えます。

Highs　IPM版は、未だSPARSE行列演算のマルチスレッド化が出来るところもやっていないので、未だ速度向上の余地はあります。何よりGPUを必要としないので、ライブラリの切り替えの手間等がなく実装が楽です。速度もそれなりに期待できるので、未解決残り2問題用のソルバ実装検討には、HIGHS　IPM版で行うことにしました。