ナーススケジューリング問題 最適の分かれ目は、僅か数セルで決まる

 ナーススケジューリング問題を組み合わせ最適化問題とみたときのお話です。

INRC2 の最適解を数理ソルバで求める過程において、Branch＆Boundという作業を行います。具体的には、勤務表のセルを一つづつ決めていく作業を考えます。これは、問題を分割し、分割したサブ問題について解く作業でもあります。

頭から一体何セル決定すれば、最適化解を決定ずけるか？

という問題を考えたとき、最小何セルのシフト群Aを決定すれば、最適化解が決定ずけられるか？という問題です。言い換えると、A集合のうち、一つでも外したとき、最適化解には決して至らないような集合Aを求める問題です。最適化解の定義は、それよりも良い目的関数値になる整数解が存在しない解とします。

直感的にも、Keyになる人のシフトを決定すると、その後の勤務表のアウトラインが決まってしまう、ということは経験的にあるのではないかと思います。それと同じ類の問題です。

最適化ベンチマーク問題において、どういう関係になっているだろう？というのをやってみました。具体的には、LP問題を解いて既知のUB解に最小で迫る組み合わせ？をやってみればその関係が分かります。（ノードを順に決定していったとき、Lp=UB-gcdを超えたときの最小ノード数(セル数)が、最適化解を決定ずけると考えます。）

答えは、僅か数ノード（数セル）です。つまり、Keyとなる人達の最初の数セルの内、一つでも誤ると、もう最適解に到達することはない、ということが言えます。ナーススケジューリング問題は、複雑に縦横の糸が絡み合ったことに特徴があります。その絡みにおいても重要なノードがある、ということの裏返しでもあると思います。否、その絡みがあるからこそ、重要なノードが余計に際立つということではないか？と解釈しています。

SCIPで、SAT系のConflictパラメータを使って重要ノードの特定に生かすという実装があります。

Achterberg2009_Article_SCIPSolvingConstraintIntegerPr.pdf (zib.de)

が、今回やってみた中では、なんらかの法則性を見出すことはできませんでした。多量に学習させれば、もしかしたら、機械学習により見出すことができるのかもしれませんが、今回やってみた中では、事前にそれを割り出すことはできませんでした。

スタッフ数１００人を超える２カ月という超大規模問題でもそうなので、市井の問題でも、そのような関係になっていることが予想されます。

とりあえずは、最適化ベンチマーク問題でのお話ですが、私にとっても新鮮な驚きだったので報告まで。