ナーススケジューリングで厳密解は得られるか？

現在の技術と計算機資源で、どんな問題でも厳密解が得られるようになったか？という問題についてです。

勿論、ナーススケジューリングは、NP困難な問題であるので、規模が大きくなれば自ずと答えは否です。しかしながら、通常遭遇する一般的な問題についての観測と感想です。
　現在開発中のソルバは、INRC-IIのほぼ全ての問題について既存のKnownBest記録を塗り替えることができますが、そのうち厳密解が得られたのはほんの僅かでした。（一週間廻しても証明できませんでした。）従って、この結果をもってしても、通常問題で厳密解を得ることは難しそうだということが言えます。 特に、INRC-IIの問題は、行制約のほとんどがソフト制約であり、ソルバ的には、難しい問題です。一方、SchedulingBenchmarkサイト問題は、行制約のソフト制約はありません。その結果、長大規模な問題を除いて、厳密解が得られています。
以上の、観測から、ナーススケジューリングの現状の技術では、世界最高性能のソルバをもってしても「厳密解が得られない問題もある」、ということをご理解頂きたいと思います。一方で、大きな規模でも厳密解が得られる場面もあります。この差についての考察は、後日に。

これまでは、厳密解を得ることに挑んできましたが、実用的には、近似解でも早く結果が欲しい訳で、その部分の改善が残っています。こちらは、根底から設計する必要はありません。厳密解を得るソルバに手を加えていけばよいです。しかしながら、未だアイデア段階であり、これからFeasibilityStudy・設計・実装となります。