WHPPでの各社比較

Gurobi Optimizer version 9.5.0 build v9.5.0rc5

RosterViewerDemo4.3.5

IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 20.1.0.0

ScheduleNurse3　(Algorithm3　Feb.2022　to be released.)

でマシンは、Gurobi/CplexがNEOSサーバ。AutoRosterとScheduleNurse3がRythen5800X　64GB 8cores 16threads です。オレンジ色がついているのは、厳密解に到達しなおかつ厳密解証明が完了したことを示しています。

スケジュールナースⅢは、4秒で厳密解証明まで完了、AutoRosterは17秒、Gurobiは、4800秒でようやく厳密解に到達したことを示しています。Cplexは、厳密解に到達することなくタイムアウト(約8時間)でした。

このWHPPは、２Weeks　30Staffsで規模的には、小規模の部類に入ると思いますが、MIPソルバが苦戦していることが分かると思います。(マシンの違いはありますが、3桁求解速度が違います。) このインスタンスは、数理的な精度の問題を内在していて、解くのは難しいと思います。（実際、NearOptimalなソルバでやってみると、厳密解に到達出来ず、厳密解ソルバに設計変更を余儀なくされました。）

後でまとめますが、このようにMIPソルバが苦戦する例は、意外に沢山見つかります。ナーススケジューリング一つとっても一つのアルゴリズムだけで解くのは難しい、ということではないかと思います。

これらのベンチマークは、ノッティンガム大学のスピンアウトカンパニーが昔から提供しているもので、NSPにおける古典的ベンチマークと言ってよいでしょう。歴史のあるベンチマーク郡で、それぞれアカデミックなPaperがあります。現在のMIPソルバではかなりの部分を解けますが、当時は問題を一つ解くとPaperが一つ書ける位だったのです。（逆に言うと昨今のMIPソルバの進歩が著しい。）当時はメタヒューリスティクスが主流でした。

現在地は、小さいインスタンスではMIPソルバ、中規模でSAT系、大規模で再び数理的ソルバ、超大規模でメタヒューリスティクスといった風に、大まかにその得意領域を捉えることが出来ますが、上述のようにその範疇に必ずしもあてはまらないものあることが難しいところです。（結局何を選べばよいかユーザからすると良く分からない）こういった事情を背景として、NSPに限っての話ですがワンストップのソルバを目指してきました。それがスケジュールナースⅢアルゴリズム３になります。

厳密解は全てKnownですが、古典的リニア重みベンチマーク郡について、全ての厳密解を求められる世界初唯一無二のソルバ、それがスケジュールナースⅢです。