Highs Hypo

 A factorisation-based regularised interior point method using the augmented system

Highsの新しいIPMソルバの実装論文が出ました。

インスタンスによっては、10倍程度の向上もあったようですが、平均的には、期待したほどではありません。Leading SolverのCOPTとかの比較が論ぜられていないので、性能の相対位置が分からないのですが、トップとは未だ相当の性能差があると思います。監修者のJacek Gondzio氏は、IPM業界の重鎮でありIPMに関する論文を数多く出していて、期待していたのですが残念な結果となりました。

IPMは、旧新両方残るようです。旧IPMは、CROSSOVERなしにBasicSolutionを得ることが出来ます。（通常のIPMがCROSSVOERで時間を食ってしまうことを回避できるメリットがあります。）

一方、CuoptのBarrierは、GPUによる実装です。以下に記述があるのですが、GH200は、F1仕様のGPUで

NVIDIA GH200搭載のサーバのお値段 - Vengineerの妄想

であり、市井のGPUでどうなるか良くわかりません。

Solve Linear Programs Using the GPU-Accelerated Barrier Method in NVIDIA cuOpt | NVIDIA Technical Blog

いずれにしても、Cuoptは、高速化したPDLPX、IPMにしてもGPUによるDirect factoring が魅力であり、WSL2で試してみる必要があると考えます。（欲しいのは業界最高性能のLpソルバです。）

課題がまた増えてしまいました。

■整数化課題

■開発ソースをGCC化

■VisualStudio2022　WSL2で、Cuoptを評価、実装

これでは、年内かかってしまうと思います。しかし、業界最速のLpソルバであることは、間違いないと思います。これで時間さえかければ、最後に残った超大規模のオープンナーススケジューリング問題（探索空間10の82911乗,宇宙の素粒子の数は10の100乗程度）を解ける筈です。なんとか年内に解決したいと思います。こんなにも早く実装して頂いたNVIDIAのChristopher Maesさんに感謝したいと思います。