MDDサイズは、Kに比例する

幅０の係数制約について考えてみます。幅0とは、

ΣCoeff[i]＊Ｘ[i]≦K、ΣCoeff[i]*X[i]≧K

と、最大・と最小がKに一致した問題です。

K＝0のMDDグラフです。幅１であることが分かります。選択肢がありません。

X[i]＝0　∀i

であることを要求しているので当然です。

K＝１のMDDグラフです。0または１の2種選択肢があります。

K＝４のMDDグラフです。定常状態では、5つの選択肢（幅）となります。

K＝10のMDDグラフです

一般にイメージされがちなのは、最大・最小が同じなら、K＝１でも、K＝１０でも同じ解空間では？と思いがちですが、実態は、全く異なり、ほぼKに比例するということです。

幅0が効くのは、最後だけであって、そこから離れれば離れる程、幅は広くなり最終的にK幅となります。ざっくり、問題の難易度は、Kに比例するということです。

これを勤務表作成問題に当てはめると、

■制約日数が長ければ長い程難しくなる

■スタッフ人数が多ければ多いほど難しくなる

ということが理解されると思います。

例えば、夜勤人数１名（１名以上１名以下）と夜勤人数１０名（１０名以上１０名以下）では、夜勤人数１０名の方が１０倍程度、上で見たようにノード変数数が増えるので、それだけ解きにくくなる、ということです。月数が12カ月になれば、さらにノード数は、12倍となります。全体としては、120倍難しくなります。これが、combinatorial explosion組み合わせ爆発の源です。

ナーススケジューリング問題は、NP困難であることが証明された問題であり、問題が大規模になれば、やがてReasonableな時間内に解くことは出来くなる、ことが分かっています。しかし、数学が証明しているのは、それだけであり、この規模なら解けない、と断じている訳ではありません。私達研究者は、神様が決めた限界を突破することはできませんが、解ける限界範囲を出来る限り伸ばそう！と日々努力しているということです。