スラックの扱いに違いがある

最適値を求めるという目的は同じです。だから、最適値を速く正確に求められるならSATとMIPのどちらの方法を取ってもよいのです。

で、スケジュールナース上で、何が違うかというとスラックの実装の違いにあります。

新しいバージョンでは、許容エラーという言い方を止めて、「スラック」にしようと思っています。

スラックとは何か、というとソフト制約の幅になります。ソフト制約領域に入ると1ソフトエラーに対して、重みを乗算した値がコストとして発生します。例えば、夜勤回数が４回、スラックが３(旧許容エラー）のときを考えます。夜勤が５回の解の場合、重み２のとき、２ｘ１のコストが発生します。

しかし、どこまでもソフト領域が広がっていることはありません。この場合スラックは、３ですから、必ずハード制約でクリップされて、それ以上は、コストが発生しないように制約されます。この場合、４＋３＝７回までは、ハード制約に違反しないので解は存在し得ます。もしどうしてもハード制約を上回ることなしに解が存在しえないときは、「解がない」状態となります。逆に言うと、解が存在するならば、その解は、必ず夜勤回数７回以下になるということです。

SATでも、MIPでも上記スラックの挙動は同じです。違うのは、スラックの実装にあります。SATは、ブール値「０」か「１」しか変数として持てません。なのでスラックもバイナリ変数で持ちます。スラックが３のとき、最大－最小制約では、上側３個、下側３個のバイナリ変数を要します。SATの場合、スラックの幅が大きければ大きい程、必要な変数数が大きくなります。

これに対してMIPは、リニアソルバをベースとするので、スラックを１個の連続変数に割り当てることが出来ます。つまりどれだけ多くのスラックを確保したとしてもスラックは１個で済みます。(上下に１個のスラックを配置した場合でも２個で済みます）

つまり、SATでは、スラックが大きければ大きい程、メモリコストがかかるのに対して、MIPでは、スラックの大きさに不感です。

スケジュールナースAL1は、SATベースなので、上記SATの短所がそのまま当てはまります。一方AL3では、内部深層においては、リニアソルバベースにしています。整数化の最後だけは、SATソルバの表皮となる予定です。概念的にスラック∞という発想も可能ですが、そこまで行うかは、未だ決定していません。

いずれにせよ、真の最適値は、スラック範囲のどこかにあります。AL3が、何故ソフト制約だらけの規模の大きな勤務表で優位となるかを、なんとなくでも分かっていただけたら幸いです。

最初から「スラック」という言葉で実装すればよかったのですが、スケジュールナースⅠの時代は、未だ私がOR（オペレーションズリサーチ）を勉強する前だったので、知らなかったのが実相です。しかし、その知らなかった時代から、ソフト制約の必然概念を実装していた私は偉かった、ということでしょう。

いずれせよ、ユーザが、スラックを直接に弄れる勤務表ソフトは、スケジュールナース以外ないのでは？と思います。実は、それが、学術ベンチマークで??の、私の答えです。