2018年5月31日木曜日
2018年5月29日火曜日
新しい解の発見
ほとんどのインスタンスは、既に解かれてしまっています。
解のOptimumが未知のインスタンスは、あまりありません。狙い目は、解かれていないInstance15、そしてInstance19以上です。Instance19以上は、超巨大なインスタンスで、開発中のソルバーも、悪戦苦闘していますが、このレベルだと、現在、コンパイルすら通らない有様です。ところが、Instance15は、なんとかなりそうなのでやってみました。
今日現在、
http://www.schedulingbenchmarks.org/
のインスタンス15のKnownBestValueは、3834です。この値は、Pieter Smet さんが10時間回したBest値です。
数時間回したら、3831を発見してしまいました。この解は、多分、人類未踏の解です。ナーススケジューリングの歴史に名を残せそうです。
大規模インスタンスに対する改善を行って、他のインスタンスについても新しい解を得ることが6月の目標です。実は、このベンチマークのインスタンスは、実務から言うと特殊でして、このインスタンスセットについて、飛び切り優秀だとしても実務インスタンスの性能向上にはほとんど役にたちません。実務インスタンスに応用するには、もう一段手を加える必要があります。それが終了して、製品化実装を行って、初めて世にでることになります。発想から一年以上かかっています。
解のOptimumが未知のインスタンスは、あまりありません。狙い目は、解かれていないInstance15、そしてInstance19以上です。Instance19以上は、超巨大なインスタンスで、開発中のソルバーも、悪戦苦闘していますが、このレベルだと、現在、コンパイルすら通らない有様です。ところが、Instance15は、なんとかなりそうなのでやってみました。
今日現在、
http://www.schedulingbenchmarks.org/
のインスタンス15のKnownBestValueは、3834です。この値は、Pieter Smet さんが10時間回したBest値です。
数時間回したら、3831を発見してしまいました。この解は、多分、人類未踏の解です。ナーススケジューリングの歴史に名を残せそうです。
大規模インスタンスに対する改善を行って、他のインスタンスについても新しい解を得ることが6月の目標です。実は、このベンチマークのインスタンスは、実務から言うと特殊でして、このインスタンスセットについて、飛び切り優秀だとしても実務インスタンスの性能向上にはほとんど役にたちません。実務インスタンスに応用するには、もう一段手を加える必要があります。それが終了して、製品化実装を行って、初めて世にでることになります。発想から一年以上かかっています。
2018年5月20日日曜日
MIPソルバーの評価
例のベンチでの評価結果です。厳密解を得るまでの時間を
まとめてみました。（NEOSサーバによる）Instance8だけは、5分内に厳密界を得ることができず、最良値を書いています。
なお、自分のエンジン(ScNurse2)については、Pieter Smetさんの解を元に解析を進めてバグをFIXすることが出来、無事、厳密解1300を得ました。この解を得るまでに907秒かかりました。
なお、これ以上良い解はない、という証明には、さらに時間がかかります。MIPソルバーの方は、CuttingPlaneという数学的な方法で、LowerBoundを上げているので、解が見つかってから証明終了までさほど時間がかかりません。
RosterBoosterは、ノッティンガム大学のスピンオフ会社です。300sec以内に解けていないものが多いです。赤字で記したのがそのインスタンスでのBestSolverです。ScNurse2は、実装上の最適化チューニングを施していません。（未だ余力があります）
まとめてみました。（NEOSサーバによる）Instance8だけは、5分内に厳密界を得ることができず、最良値を書いています。
なお、自分のエンジン(ScNurse2)については、Pieter Smetさんの解を元に解析を進めてバグをFIXすることが出来、無事、厳密解1300を得ました。この解を得るまでに907秒かかりました。
なお、これ以上良い解はない、という証明には、さらに時間がかかります。MIPソルバーの方は、CuttingPlaneという数学的な方法で、LowerBoundを上げているので、解が見つかってから証明終了までさほど時間がかかりません。
RosterBoosterは、ノッティンガム大学のスピンオフ会社です。300sec以内に解けていないものが多いです。赤字で記したのがそのインスタンスでのBestSolverです。ScNurse2は、実装上の最適化チューニングを施していません。（未だ余力があります）
| CBC | SCIP | Cplex | Gurobi | RosterBooster | ScNurse2 | ScNurse2備考 | |
| Instance1 | 1.8 | 1.67 | 0.15 | 0.27 | 0 | 0.47 | |
| Instance2 | 4.62 | 4.68 | 0.66 | 0.98 | 0 | 0.5 | |
| Instance3 | 30.3 | 3.1 | 1.62 | 1002(300sec) | 1.15 | ||
| Instance4 | 51.5 | 13.18 | 4.53 | 10 | 1.11 | ||
| Instance5 | 235.04 | 56.91 | 34.39 | 21 | 3.54 | ||
| Instance6 | 30.15 | 14.7 | 1952(300sec) | 6.15 | |||
| Instance7 | 84.95 | 113.54 | 1062(300sec) | 218.5 | |||
| Instance8(300sec) | 1665 | 1794 | 1528(300sec) | 1301 | 1300(907sec) |
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のみで、その他は、近似解で、規模が大きくなるに従い乖離
が大きくなる傾向にありました。
のうち最初の8題をやってみました。
最後の1題を除いてOptimum値が一致しました。
最後の1題、Instance8は、ベルギー、ルーヴェン・カトリック大学 Pieter Smetさんによる新しい解がOptimumとされています。 （CPLEXでも最適値は求まっていません。）
それまでは、長らくノッティンガムの1308という解がBestでした。私の解(開発中エンジン）は1301で、下記値と一致していません。サイトには、解のファイルも置いていますが、残念ながら、最新の結果を反映したものではありません。
そこで、Pieter Smetさんにお願いして、解を頂いて解析することにしました。
→頂きました。なおPieter Smetさんの論文は、レビュー中であり未だオープンになっていないそうです。
下記インスタンスは、去年のRAMP講演でも発表しましたが、SATにとって苦手なインスタンス郡です。厳密解が得られたのは、Instance1のみで、その他は、近似解で、規模が大きくなるに従い乖離
が大きくなる傾向にありました。
| Instance | Weeks | Employees | Shift types | Best known lower bound | Best known solution |
| Instance1 | 2 | 8 | 1 | 607 | 607 |
| Instance2 | 2 | 14 | 2 | 828 | 828 |
| Instance3 | 2 | 20 | 3 | 1001 | 1001 |
| Instance4 | 4 | 10 | 2 | 1716 | 1716 |
| Instance5 | 4 | 16 | 2 | 1143 | 1143 |
| Instance6 | 4 | 18 | 3 | 1950 | 1950 |
| Instance7 | 4 | 20 | 3 | 1056 | 1056 |
| Instance8 | 4 | 30 | 4 | 1300 | 1300 |
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です。 この原因は、大体分かりましたが、述べるには余白が足りません。別の機会に。
日本からも、学術用のコンピュータで作成したベンチではなく、あくまで人間が作成したベンチを公開していきたいと思います。ただ、その際に、自分だけが解ける問題だけを載せてもあまり説得力がないので、上記ベンチマーク結果についても、検証ができるようにしていきたいと思います。
ナーススケジューリングコンペティションは、過去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学会関係の書物は、数式が多いのに閉口しますが、数式は少ないので読み物としても面白く読めます。普通の学術・技術書にはない、その問題に至る過程や、苦闘の様子などが語られていて、一線を画するユニークな学術書になっています。
組み合わせ最適化に関心のある研究者、技術者、大学院生、学部生には必携の書でしょう。
です。世界的に見ても、ナーススケジューリングに関するこれほどの本は、ないのではないでしょうか？ 私は、取り組み始めて未だ数年ですが、研究の変遷等、「そうだったんだ」と腑に落ちる部分も多々あります。OR学会関係の書物は、数式が多いのに閉口しますが、数式は少ないので読み物としても面白く読めます。普通の学術・技術書にはない、その問題に至る過程や、苦闘の様子などが語られていて、一線を画するユニークな学術書になっています。
組み合わせ最適化に関心のある研究者、技術者、大学院生、学部生には必携の書でしょう。
登録:
投稿 (Atom)