First Nurse Scheduling Competitionとは？

 2010年に第一回目のCompetitionが開催されました。主要論文は以下です。

https://www.sciencedirect.com/science/article/pii/S0377221711011362

https://www.researchgate.net/publication/261565830_New_approaches_to_nurse_rostering_benchmark_instances

https://www.researchgate.net/profile/Tulio_Toffolo/publication/264120532_Integer_Programming_Techniques_for_the_Nurse_Rostering_Problem/links/589ae7a7aca2721f0db15292/Integer-Programming-Techniques-for-the-Nurse-Rostering-Problem.pdf?origin=publication_detail

この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１０分以内　（Early5問、Late5問、Hidden5問）

■Long 10時間以内　（Early5問、Late5問、Hidden5問）

です。Early/Lateは、競技会前に提示されていた問題、Hiddenは、競技会で初めて提示された問題です。Early/Lateについては、対策を練ることができますが、Hiddenは、どのような問題出るか不明なため、後に述べるEvalatorとの解釈の違い、ソフトの実装不具合の影響が出る可能性があります。実際ノッティンガム大学の成績を見ると、Hiddenで０点の部分があります。Curtoisさんの論文でも言及されていますが、上記問題があったようです。