ベンチマークテストとは？
コンピュータの処理性能を比較・評価するために行われるテストのことです。ナーススケジューリング問題は、学術問題、組み合わせ最適化の一分野であり、1980年代から、様々なアルゴリズムが研究開発されてきました。
で、新しいアルゴリズムを学術発表するときに、アルゴリズムの優劣を論じたいのですが、皆、発表者が別々のテスト環境で行っていたのでは比較にならない訳です。
そこで、様々な基準となるベンチマークテストが発表されてきました。
日本では、成蹊大学の池上先生が発表したベンチマークテストが、国際学会で多く参照されています。このベンチマークは、実際の看護の現場に行ってモデリングしたインスタンス（勤務表の評価ルールをモデル化した実体）であり、 日本の勤務実態に最も近く、実用的な性能を測る上でも重要なベンチマークテストとなっています。
ベンチマークテスト結果
菅原システムズでは、公開されている全てのベンチマークテストに対して、結果を公開 しています。
少し分かりずらいので、いくつか要点を見てみましょう。
下のグラフは、古典的ベンチマークテスト群における、解けるまでのスピード比較です。
Auto Rosterというのは、イギリス名門、ノッティンガム大学からスピンアウトした会社の製品です。Gurobiは、言わずと知れた世界最高の汎用MIPソルバ、Cplexは、IBMです。
テスト環境が違うので、厳密な比較ではないのですが、それでも大雑把に言って、10倍、100倍というオーダでスケジュールナースが高速ということが言えると思います。Optimality Provenは、最適解証明付の時間比、Optimality Reachedは、最適解に達するまでの時間比です。
例えば、具体的な池上先生のベンチマークで見てみましょう。縦軸は、目的関数値の変化です。目的関数値とは、不満足度を現わし、エラーの重みにエラー数を掛けたものの総和です。理想的には、0ですが、物理的限界により0にはならないことがあります。
例えば、毎日の必要夜勤数を割り当てられなかったものがあったり、スタッフの希望休み全部を入れられないと、それだけ目的関数値は大きくなります。しかし、物理的にこれ以上は目的関数値を小さく出来ないという値が存在します。それを「最適値」と呼んでいます。
スケジュールナースは、数秒で最適解に到達し、10秒以内に最適解であることを認識しています。対して、Gurobiは、100秒以上を要しています。Cplexは、数千秒を要し、Autorosterは、最適値にすら達していない、ということが分かります。
このGurobi結果は、例えば、こちら のデータでも裏付けされています。
上図で急降下している赤線がスケジュールナースですが、以下のログをプロットしたものです。スケジュールナースの目的関数値減少の様子になります。
ハード制約を全て満たす解が見つかるまで1秒程度ですが、この段階では、目的関数値が数万以上でありスタッフ休み希望を含む多くの制約が未だ満足していません。
4秒程度で、最適値に到達していますが、この段階では、未だ最適値かどうかは分かっていません。（後になって、これが最適値だったということが分かります。）
5秒程度で、タイムアウトを待たずに終了しており、最適性証明まで完了していることが分かります。
このとき、重み100のエラーは0であることから、下記スタッフ希望は全て通ったことが分かります。
次のグラフは、別なベンチマークテスト群New Scheduling Benchmarksでのグラフになります。
このGurobi結果も、例えば、こちら のデータでも裏付けされています。
最適化ソルバの最適化能力
単に速度比較で見ていますが、例えば、池上先生のベンチマークで10秒という時刻で見ると、スケジュールナース以外のソフトは、全く解けていない状態（解が存在しない）ということになります。100秒で見れば、他のソルバで解が存在するけれども、未だ、休み希望が満たされていない箇所が多数ある、ということであり、1000秒のCplexで見れば、物理限界に対して数倍の必要シフトが不足または超過していることを、
示しています。
何でテストをしたのかということが明示されていることが重要てす。ナーススケジューリング問題は、規模に応じて指数関数的に難しくなる性質があり、さらに易しいのもあれば難しいのもありえる千差万別のものだからです。公開されているベンチマークテストで物理限界、真の最適値まで到達し、なおかつ最適である証明まで出来ていれば安心できる「能力」があると考えられます。また、より多くのベンチマーク結果が公開されていれば、より安心できる能力があると考えてよいでしょう。
以上見てきたように、
最適化ソルバの性能は、人員割り当てとスタッフの休み希望の両立をどれだけできるか? に直結しています。
知の巨人である世界最強のソルバGurobiをもってしても、未だナーススケジューリング問題は、依然難しい問題なのです。巷の市販ソフトは、推して知るべしですが、お使いのソルバは、どうでしょうか？
スタッフの休み希望が入らない、毎日の夜勤スタッフを割り当てられない、または、その両方を同時には満足できない等、ナーススケジューリング問題を解決するには、どうしたらよいでしょうか？
心配はご無用、安心してください。月額480円スケジュールナースの最適化能力を使いこなせばよいだけです。個人でも使用でき書籍 やサポート もしっかりしています。
ベンチマークテスト種類
下記4つの種類に分けられると思います。
1. 古典的ベンチマークテスト群
2. New Scheduling Benchmarks
3. Nurse Scheduling Competition Ⅰ
4. Nurse Scheduling Compeitiion Ⅱ
古典的ベンチマークテスト群
池上先生のベンチマークテストを含む古典的ベンチベンチマーク群です。これらは、各国の当時の実情に応じたモデリングが主だと思います。
Scheduling Benchmarks
24のエチュードのように24の規模に分かれています。
2014年に発表された当時は、その半分程度のインスタンス群しか最適値は知られていませんでしたが、MIPソルバ発展により、2023年現在では、未解決問題は、残り2インスタンスとなっています。
これ以降、人工的(機械的に）コンピュータが生成したベンチマークが用いられるようになりました。
こちら で、記録更新情報を見ることが出来ますが、Tak.Sugawara(筆者）の名前がいくつもあります。
Nurse Scheduling Competition Ⅰ
2010年、一回目の競技会が開催されました。Sprint/Medium/Long のカテゴリがあります。競技会前に公開されたインスタンスと競技会時に公開された(hidden)インスタンスに分かれています。
主要論文は以下です。
https://www.sciencedirect.com/science/article/pii/S0377221711011362
このCompetitionは、私がNSPに取り掛かる以前のものです。法政大学の野々部先生が3位に入賞されています。一番上は、第一位になった方の論文です。(購入しないと見れません。）2番目は、おなじみのノッティンガム大学チームです。3番目は、競技会以降に発表された論文でCOIN Cut Generatorにも多大な貢献をされているSantosさんです。MIPソルバーを使って、LB値(Lower Bound)を求めています。また、MIPソルバーのベンチマーク問題MIPLIB2017としても提供されているようです。
成績順で、MIPソルバー＋メタ解法のHybrid型、ノッティンガム大学のBranch＆Price型、野々部先生のメタ解法（Tab Search) ということのようです。
10年以上前の競技会ではありますが、昨今でも、このインスタンスを使ったメタ解法の論文が出されています。
https://www.sciencedirect.com/science/article/pii/S1319157818300363
今回、1ヶ月以上かけて全ての問題を解いてみたのですが、私が実務で取り扱っているNSP問題とは、全くかけ離れたもので、正直別世界です。が、欧米では、そのようなパターンが主流のようですので、国際化においては、避けて通れない問題でもあります。
成果としては、全問題で、KnownBest解、ほぼ全ての問題で厳密解を提示できます（上記報告LB値をいくつか更新しています。）
また、Sprint問題については、全問題で、10秒以内にKnownBest解に到達し、ほぼ全ての問題で10秒以内に厳密解を示すことが出来ます。いずれもAlgorithm4によるものです。
問題の種類としては、Sprint/Medium/Longの３種類あり
■Sprint 10秒以内 （Early10問、Late10問、Hidden10問）
■Medium 10分以内 （Early5問、Late5問、Hidden5問）
■Long 10時間以内 （Early5問、Late5問、Hidden5問）
です。Early/Lateは、競技会前に提示されていた問題、Hiddenは、競技会で初めて提示された問題です。Early/Lateについては、対策を練ることができますが、Hiddenは、どのような問題出るか不明なため、後に述べるEvalatorとの解釈の違い、ソフトの実装不具合の影響が出る可能性があります。実際ノッティンガム大学の成績を見ると、Hiddenで０点の部分があります。Curtoisさんの論文でも言及されていますが、上記問題があったようです。
Nurse Scheduling Competition Ⅱ
2015年、2回目の競技会です。競技会時は、1週間毎に制約が提示されるダイナミックインスタンスが用いられました。
が、その後の研究論文では、インスタンス全体を静的な制約として解釈する論文が主流となっています。
この競技会では、シフトのみならずタスクの概念が追加されており、規模、複雑度において、随一の難しい問題となっています。
敢えて、MIPソルバが解けないようなテストを狙ったと思われるふしもあり、現在でも最適値は、知られていないインスタンスが多数あります。現在のところ、全インスタンスにおいて、スケジュールナースの結果の全てがKnownBests(世界記録)になります。これを上回る結果は筆者が知る限り、報告されていません。
ナーススケジューリング問題を解くアルゴリズムの動向
当初、タブサーチ、遺伝的アルゴリズム、焼きなまし法に代表されるようなメタヒューリスティックな解法が主でした。
汎用MIPソルバの驚異的な進展により、ナーススケジューリング問題において、過去解けなかった問題も、組み合わせ最適化問題として解ける例も出てくるようになりました。
しかし、それは最新の商用ソルバの話であって、非商用ソルバ
の場合は、依然として非力です。
最適化問題として解けた場合の利点は、「これより良い解はないです」ということが言い切れることです。
メタヒューリスティックな解法のみの場合、現在の解が最適かどうかは、分からないので探索打ち切りはタイムアウトによることになります。
しかし、数理的解法で最適であることが分かったならば、探索を直ぐに打ち切ることが出来ます。
言うなれば、人員捻出の物理限界が明らかになる訳ですから、「諦めがつく」、という精神健康上の効果もあります。看護師勤務表で言えば、
「あなたの休み希望は通らない。なぜならリソースの物理限界だから。ソフトの能力の問題、増してや私の配置能力の問題ではなく、物理限界なのよ。文句があるなら..に言って！」
ということが言える訳です。これが、人手による解、もしくは、メタヒューリスティックな解だと、そうは言えなくて突っ込みどころが残ってしまうでしょう。
看護師と看護師長は、多くの場合、人生初の勤務表作成 公表というより晒される気分
に見られるように緊張関係にあります。看護師との折衝は、意外に多くの時間を取られるので、この効果は大です。
しかしながら、ナーススケジューリング問題は、NP困難な問題の一つであり、規模が大きくなれば、現実的な時間内には、解けなくなることが分かっている
種の問題です。
現在においても、全てがMIPソルバで解けている訳ではなく、むしろ多くの実務問題が最適値不明のままの状態であることは変わりがありません。
現在のナーススケジューリング問題の課題については、実務と研究者としての両側面から、Qiita記事 の「ナーススケジューリング問題は、現状どこまで解けているか？」で書いています。