クラッシックベンチマーク評価まとめ

 Gurobi・Cplex・Autoroster・ScheduleNurse3でクラッシックベンチマークデータ採取を行っていたのですが、データがまとまって上がってきました。

環境は、Gurobi・Cplexは、NEOS　SERVERで、Autoroster・ScheduleNurse3は、ローカルマシン（Rythen 5800X　8core 16threads 64GB)です。

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.)

最初のデータは、求解速度です。

これは、4社の内、一番速く解いた社の速度を１として他社と比較したグラフになっています。1位は、薄橙で示していますが、グラフは、それを平均化したものです。Optimality　Provened Timeは、最適解証明が出来るまでの時間、Optimality　Reached　Timeは、最適目的関数値に到達するまでの時間です。インスタンス数が少ないのは、多くのベンチが0秒で解かれているために除外してあるからです。

マシンの速度は2倍位違うかもしれない、ということを差し引いても、NSPは、NSP専用ソルバで解いた方が速い、というです。

にしても、これはちょっと差がありすぎるとは思います。体感的には天下のGurobiに対して100倍以上違うというのは、にわかには信じられないというのは、筆者も同じです。これは、現状でもMIPソルバでは、極端に時間のかかるインスタンス例が存在する、という風に捉えればよいのではないかと思います。（勿論モデリングや求解パラメータで違うとは思いますが。）

上のグラフから、AutoRosterの方がGurobiより優秀、というのは間違った見方です。上のグラフでは、時間比を示すために、最適解証明があるもの、あるいは、最適目的関数値に到達したものだけを集めています。そもそも最適化証明が得られなかったもの、あるいは、最適目的関数値に達しなかったインスタンスはカウント対象になりません。ですので、次のグラフを合わせて見て頂きたいと思います。（ご参考untitled (orsj.or.jp)）

下のグラフは、最適解証明にかかった全インスタンス郡の割合の時間推移グラフです。

スケジュールナースでは、150secもらえれば、全インスタンス100%の最適解証明が出来ていることが分かります。

しかし、他社では、10000sec行っても、例えばGurobiで、2割のインスタンス郡が最適解証明ができなかった、AutoRosterに至っては最下位、約４割の割合で、最適解証明が出来なかった、というグラフです。（分母は、全インスタンス数です）

ですので、二つ合わせてご覧頂きたいと思います。

さて、NSPの世界では、厳密解証明より、より重要なのが現実的な求解速度です。厳密解の証明は出来ないけれども、より早く実用的な解を示せれば価値がある、と考えられています。Tim Curtoisさんの論文にも、ユーザは30秒以上待ちたくない、でももしもっと良い解が得られるなら、10分(600sec)までは待つか？、という記述があります。確かに、NSPの世界では、私の感覚ですが、長くても３分です。ただし、私のユーザさんの中では、夜走らせて帰る（少しでも良い解＝少しでもスタッフ負荷軽減 または、スタッフ間の平等化という目的）というお客さまもいらっしゃいます。）

その意味で、次のグラフがそれを示しています。AutoRosterは、150秒内では、ScheduleNurse3に次ぐ結果となっておりこの目的志向に合致していることが分かります。

スケジュールナースは、どの指標でみても一位となっております。クラッシックベンチマーク郡の全インスタンスの厳密解証明が可能な世界初のソルバとなっています。

設計目標は、

■インスタンスによらず、3分以内でNear Optimalな性能を得ること。

■時間をかければできうる限り厳密解が得られること

■マルチコア時代に対応したアーキテクチャ

でしたが、クラッシックベンチマークについては、達成したと言えます。SchedulingBenchmarks/INRC1/INRC2　4weeks/8weeksについてもデータ採取中です。