MyIPMSolverの評価

 内点法による実装ソルバの評価を行いました。名前をMyIPMSolverとしました。

インスタンスは、SchedulingBenchmarksとINRCⅡから、規模の大きなインスタンスです。比較対象としては、オープンソースのCLP,HIGHS,商用ソルバ郡は、NEOS　SERVERによる結果です。

結果としては、全てのインスタンスについて1位(王冠）となりました。黄色は2位オレンジは最下位です。また、参考として、最後にRyzen5800でのベンチマークを取っています。

グラフでは、背が低い程高性能を意味します。

＜商用ソルバとの比較＞

ただし、一般にIPMSolverは、IPMが結果が出た後、さらにSimplexのBasis形式に変換（Crossoverと呼ばれる）します。ユーザは、BranchAndBoundを行う場合に前の結果を使って（近い場所にある）演算を行います（WarmStart）。IPMの場合、殆ど場合、WarmStartが出来ない、もしくは行ったとしても効果がないことがあって、WarmStartが出来るSimplexSolverでResolveすることが多いのです。そのためには、Simplexで計算が出来るポイント解(Basis）を出力することが必要となります。

インスタンスによりますが、内点法で食う時間よりもCrossoverにかかる時間の方が大きい場合もあります。特に、巨大なインスタンスではその傾向が顕著になります。よって、上記結果は、MyIPMSolverがCrossoverを備えていませんのでフェアな比較になっていません。また、当然のことながら、NEOS SERVERとの比較ですので、なにがしかのハンデがあるのかもしれません。

＜何故COPTが悪い成績なのか？＞

商用IPMソルバは、インスタンスを見てSimplex/IPMを切り替えているのが普通です。大きくないインスタンスはSimplex,大きいインスタンスはIPMを使います。例えば、CPLEXのIPMがオンになるのは、Instance20から上です。ところがNEOS上にあるCOPTは、Simplex　Onlyの模様です。結果、巨大インスタンスが来ると悲惨な結果となってしまいます。

＜CROSSOVERはなくてもよいのか？＞

確かにBranch&Boundを行う場合、Simplexの方が良さそうな気がするのですが、NSP巨大インスタンスの場合、少し離れただけで、SimplexではとてもReasonableな時間内に解が出てきませんでした。よってNSPに限れば、Primal/Dual解が得られれば、Simplexを行う必要はなく、そのままIPMを使い続けた方が得策と考えています。（FirstOrderと違って十分な精度1e-8がIPMでは得られているので、数値的な問題は考えにくい。）

＜オープンソースソルバCLP,HIGHSとの比較＞

Crossoverを引いたとしても明らかな優勢を見てとれます。CLP/HIGHSを使うと、Instance21以上で解を得るには、一週間以上計算機を廻さないといけないません。これらのInstance郡については、今後MyIPMSolverを使用して世界記録更新を狙います。また、INRCⅡの巨大インスタンスについても、今まで3日以上かかっていました。このソルバを使えば、Reasonableな時間内に解を示せるようになると思います。(n120w8インスタンスRyzen5800比で見ると今までより約30倍速) つまり、今までAlgorithm4で、実用的な時間に解を示せなかった巨大インスタンスも示せるようになる、ということです。

<E31226 4コア3.3GHzとRyzen 5800X　8コア3.8GHzの比較>

ターボブーストの影響もあり正確な性能比較ではないのですが、ほぼ1/2の時間で済んでいます。クロックUp・IPCの効果もありますが、やはりコア数が倍になっている影響が大きいと思います。ちなみにハイパースレッドをONにして論理コア数16にしてやってみたのですが、予想通り、改善されるどころか悪化してしまいました。これは、前に示したようにOneコアあたりのCPUパイプラインをほぼ埋めるようなコーディングをました。他に廻すCPUリソース余裕がない為、と推測されます。（なお、Windows11は、RyzenL3キャッシュ問題のFix済みVersionを使用しました。）

ともあれ、まがりなりにも、マルチスレッドの効果はある、と言えそうです。擬似論理コアベースではなく、実論理コアベースで。