HiGHSがSCIP並みに

 HiGHSの性能向上が著しく、現時点でSCIP並みになっていると思われます。

こちらは、定番Visualizations of Mittelmann benchmarks | Interactive plots showing pairwise time differences for every instance and every solver (mattmilten.github.io)

ベンチマーク結果です。

NSPに関しては、SchedulingBenchmarksをInstance8まで行ってみました。Highs　Versionは、最新ソース1.22+α（改修済みVersionです）

驚くべきことにinstance7まで厳密解が得られています。instance8では、feasibleな解（実行可能解）が3600sec行っても得られていませんが、CBCと比較してみれば、オープンソルバとしては、素晴らしい結果であることが判明すると思います。

(現在世界最速と思われるスケジュールナースⅢAlgorithm3が59secで厳密解を証明しているのは、例外的な速さです。instance8は、Gurobiでも10分以上、Cplexで一時間以上を要すると思います。)

では、どうしてあのような少ない行数でハイレベルな結果が得られているか？ソースを眺めたのですが、良く分かりませんでした。特別なCutやBranching、Heuristicsを行っているように思えませんでしたし、Presolverは、多分SCIPに同じです。恐らくは、Domain Propagationが効いているのではないか？ということです。Domain　Propagationは、比較的新しい技術で、MIPソルバ内にSATソルバもどきがあるようなものです。SCIPの中身は、こちらが詳しい

https://imi.kyushu-u.ac.jp/~3rd_imi_ism_zib_ws/SCIP.pdf

また、マルチスレッド化の実装は、現在中途だと思うので、今後も性能向上は期待できると思います。

Algorithm2では、HIGHSによる実装になりますが、NSPに関しては、極小さい規模を除いて依然として皆様の使用には耐えません。逆に言えば、それだけNSP（探索空間が極めて広い問題分野）は難しいということでもあります。

しかし、現在シリーズでアップしているシフトが決まっておりタスクの最適化を行う問題（4直2交代等）では、十分に実用的です。（どの問題分野が得意かということは、ソルバによって異なります。この種の、行方向の自由度が狭い問題においてMIPソルバは有効です。）今後インタフェースがより強化されると思うので、もう少し使いやすい形態（実行途中のfeasible解の表示等）になると期待されます。

なお、上記搭載は、Al2として次回リリース時から適用になります。