基数制約とソフト許容エラー数との関係

 基数制約とは、数を数える制約のことで、一般に不等式になります。（LP制約としては、基数制約しかないとも言えます。ORから見ると、AND・OR制約は、基数制約の特殊形です。）

Σxi <=Max

Σxi <=Min

単純な例で、30日中休みを8回だけ取る制約を考えます。この場合の探索空間（ありえる状態空間）は、どうなるでしょうか？

計算方法は、30C8-30C7です。30個から、8個取る組み合わせ、つまり

Σxi <=8から

Σxi <=7を引き算すれば、Σxi>=8 && Σxi<=8となります。

これをExcelで計算したのが上のテーブルです。組み合わせ数が、381万程度となります。

ソフト許容を1とした場合は、(8,8)→(9,7)に拡大されます。以下同様です。

ソフト許容を３とした場合は、探索空間が14倍に増えることを意味します。ソフトエラーまで含めれば、それだけ満たす可能性が増えることを意味しますが、同時に探索負荷が重くなる（時間がかかる）ことを意味します。

ちなみに、日数を31にしただけでも結構な違いがあります。これが月ごとの難易度の違いの原因です。

また、それ以上に休み数の違いがドラスティックな違いを生むことが分かります。

基数制約単体に限れば、上のように組み合わせ数は計算できますが、現実の制約は、制約郡であり複雑です。その総数を計算するのは容易ではありませんが、離散解法（グラフ解法）により個々のRoster（個々人）毎に正確に求めることは可能です。しかし、Rosters全体でみたときに、現実時間内に総数を求めることは、小さなインスタンスを除けば大変に難しいです。（出来ないと言った方がよいかもしれません）。

ソフト許容を無限に許せば、探索負荷が重くなるのは、想像できると思います。一方で、全てをハード制約にすれば、簡単に解のない事態になってしまいます。適度なソフト制約化が、Reasonableな時間で解を得る鍵となります。