2018年5月20日日曜日

MIPソルバーの評価

例のベンチでの評価結果です。厳密解を得るまでの時間を
まとめてみました。(NEOSサーバによる)Instance8だけは、5分内に厳密界を得ることができず、最良値を書いています。
なお、自分のエンジンについては、Pieter Smetさんの解を元に解析を進めてバグをFIXすることが出来、無事、厳密解1300を得ることが出来ました。


 CBCSCIPCplexGurobi
Instance11.81.670.150.27
Instance24.624.680.660.98
Instance3 30.33.11.62
Instance4 51.513.184.53
Instance5 235.0456.9134.39
Instance6  30.1514.7
Instance7  84.95113.54
Instance8(厳密解1300(300sec)  16651794 

2018年5月16日水曜日

Benchmark 評価

http://www.schedulingbenchmarks.org/

のうち最初の8題をやってみました。
最後の1題を除いてOptimum値が一致しました。

最後の1題、Instance8は、ベルギー、ルーヴェン・カトリック大学 Pieter Smetさんによる新しい解がOptimumとされています。 (CPLEXでも最適値は求まっていません。)

それまでは、長らくノッティンガムの1308という解がBestでした。私の解(開発中エンジン)は1301で、下記値と一致していません。サイトには、解のファイルも置いていますが、残念ながら、最新の結果を反映したものではありません。

そこで、Pieter Smetさんにお願いして、解を頂いて解析することにしました。
→頂きました。なおPieter Smetさんの論文は、レビュー中であり未だオープンになっていないそうです。

下記インスタンスは、去年のRAMP講演でも発表しましたが、SATにとって苦手なインスタンス郡です。厳密解が得られたのは、Instance1のみで、その他は、近似解で、規模が大きくなるに従い乖離
が大きくなる傾向にありました。
InstanceWeeksEmployeesShift typesBest known lower boundBest known solution
Instance1 281607607
Instance2 2142828828
Instance3 220310011001
Instance4 410217161716
Instance5 416211431143
Instance6 418319501950
Instance7 420310561056
Instance8 430413001300

2018年5月6日日曜日

海外ベンチマーク動向

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

ナーススケジューリングコンペティションは、過去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です。 この原因は、大体分かりましたが、述べるには余白が足りません。別の機会に。

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






2018年5月2日水曜日

池上先生の本が出ました

https://www.amazon.co.jp/%E3%83%8A%E3%83%BC%E3%82%B9%E3%83%BB%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%EF%BC%9A%E5%95%8F%E9%A1%8C%E6%8A%8A%E6%8F%A1%E3%81%A8%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0-%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA%EF%BC%9A%E6%9C%80%E9%81%A9%E5%8C%96%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0-%E6%B1%A0%E4%B8%8A-%E6%95%A6%E5%AD%90-ebook/dp/B07B4S2GMG

です。世界的に見ても、ナーススケジューリングに関するこれほどの本は、ないのではないでしょうか? 私は、取り組み始めて未だ数年ですが、研究の変遷等、「そうだったんだ」と腑に落ちる部分も多々あります。OR学会関係の書物は、数式が多いのに閉口しますが、数式は少ないので読み物としても面白く読めます。普通の学術・技術書にはない、その問題に至る過程や、苦闘の様子などが語られていて、一線を画するユニークな学術書になっています。

組み合わせ最適化に関心のある研究者、技術者、大学院生、学部生には必携の書でしょう。