海外ベンチマーク動向

最近の学術研究動向について述べます。

ナーススケジューリングコンペティションは、過去2回あり、最初のコンペ2010では、法政大の野々部先生が、2位になられています。

https://www.kuleuven-kulak.be/nrpcompetition

2回目(2015)は、RAMP講演でも述べましたが、私も参加しました。
http://mobiz.vives.be/inrc2/

こちらは、動的に勤務表問題を解くものであり、異色のベンチでした。ちょっとこれでは、性能比較しにくいということで、最近は、STATICにしたベンチマークでの論文が出ています。

1回目のベンチについては、ほぼ全部の最適解が分かっています。2回目のSTATIC　Versionでは、ほぼ最適解は、解けていません。（やっている人が少ないかもしれません。）

簡単なものから、未解決の超難問がそろっているのは、ノッティンガムの24の前奏曲です。

http://www.schedulingbenchmarks.org/

こちらは、2017に衝撃がありました。整数計画ソルバで大半の未解決問題が解かれてしまいました。　おそらくは、Gurobiだと思うのですが、こちらをキャッチアップするのは、容易でないでしょうが、目指しているは皆さん、そこだと思います。 ちなみにオープンソースで定評のあるCBCを使っても、解けるのは、もっともやさしい1-2問程度です。商用ソルバとの実力差は、いかんともしがたいです。

2014年度の結果は、こちらで、
http://www.schedulingbenchmarks.org/papers/computational_results_on_new_staff_scheduling_benchmark_instances.pdf

ここ数年で見ても急速に向上していることが分かると思います。整数計画ソルバ恐るべしです。

とはいえ、そのGurobiをもってしても、手ごわいのが池上先生のベンチです。（詳細は池上先生の著作をごらんください。）　ただ、池上先生のベンチは、SATソルバを持ってすると簡単に解けてしまうという不思議な世界がNSPです。　この原因は、大体分かりましたが、述べるには余白が足りません。別の機会に。

日本からも、学術用のコンピュータで作成したベンチではなく、あくまで人間が作成したベンチを公開していきたいと思います。ただ、その際に、自分だけが解ける問題だけを載せてもあまり説得力がないので、上記ベンチマーク結果についても、検証ができるようにしていきたいと思います。