量子アニーリングについて

組み合わせ最適化は、ナーススケジューリングを包括する広範囲な問題領域です。

「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記 (hatenablog.com)

それでは、古典的数理的解法で、ナーススケジューリング問題はどこまで解けているか？ということを少し論じてみたいと思います。

ナーススケジューリングの黎明期は、メタヒューリスティクスによる解法が主で、タブサーチ等が用いられました。

その後、MIPソルバーの発展によって、Gurobi・Cplexを始めとする数理的ソルバは、従来の解を更新、なおかつ、そのうちの超大規模を除く殆どを厳密解として提示出来るようになりました。(INRC1・SchedulingBenchmarks)　

そこで、INRC2では、問題をより大規模にして、なおかつ問題を複雑にしてMIPソルバーでは解きにくい形態としています。実際、INRC2問題は、MIPソルバーでは、殆ど解けていません。（実インスタンス形態としては、インスタンスによるのですが、どちらかというと、INRC2に近い実感があります。）

現在、MIPソルバーで、かなり解けるようにはなったけれども、全てが解ける訳ではありません。また、MIPソルバー間、AutoRoster等のナーススケジューリングソルバ間でも、性能の差がある、というのが現在地になります。

それでは、StateOfArtのソルバで、一体どこまで解けているか？という問いに対する回答が、スケジュールナースⅢになります。

現在、スケジュールナースⅢでの数理的解法結果を一連のベンチマークとしてデータを採取中です。実務問題については、未だ課題が山積していますが、少なくともベンチマークについては、動いており現在公開に向けバージョンアップしたバージョンAlgorithm3としてチューニング準備中です。ちなみにAlgorithm2は、MIPソルバそのもので、10人以下でしたらそこそこ動きますが、あくまで商用でないMIPソルバだとこんなもんです、程度で殆ど実用的ではありません。Algorithm1は、従来通りで変わりません。Algorithm4は、バージョンアップしていますがAlgorithm3の特殊形態です。Algorithm3は、汎用化した数理的ソルバです。

Algorithm3が、ナーススケジューリング問題の古典的解法によるStateOfArtと言い切ってよいと思います（GurobiでもCplexでもなく）。

一つ指摘しておきたいことは、必ずしもMIPソルバが全能ということではなく、これは容易に解けるだろうと思われる小さな問題でも、MIPソルバで解けなかったり、意外に時間がかかる事例が散見されることです。例えば　

Benchmarks | What is Schedule NurseⅢ (nurse-scheduling-software.com)

で、GPost/GPostB,BCDT-Sep,WHPP,Valouxis-1、ikegami-3Shiftxx 等です。これらは、人工的・機械的にベンチマーク用として造られたものではなく、実務問題をモデリングしていることにご注意ください。GPostは、僅か8人ですが、数理的に解くのは難しい部類にはいります。

ベンチマークは、アカデミック上の特定の実装が有利に働くような意図が背景にあり、必ずしも実問題にマッチしていません。実務問題とは基本的に異なりますが、INRC2に関しては、シフト形態は別にしてほどよくハード・ソフト制約がブレンドされ実務用途に近いと思います。

どのようなインスタンスでも安定して、短時間にNear Optimal(Ex.30sec/1min) 、時間をかければ厳密解に到達できることが、ソルバに求められる要件です。

いずれにせよ、今後はスケジュールナースⅢが一つの指標になると言い切ってよいと思います。