ペア制約に関する一考察

 スケジュールナースのペア制約は二つの種類があります。

１）禁止

２）AならばB

です。たとえば、Aの夜勤入りとBの夜勤入りが同じにならないように禁止する制約が１）になります。反対にAの夜勤入りとBの夜勤入りが常に同じく入る(プリセプタ・プリセプティ）の場合は、２）を両方向に適用します。つまり、

３A)Aが夜勤入りならBも夜勤入り　A→B

３B)Bが夜勤入りならAも夜勤入り　B→A

これで、プリセプタプリセプティの関係A==Bは出来ます。

証明：

（！A｜B）＆（A｜!B)＝！（A&！B）＆　！（！A&B)=！C＆！D＝!(C|D)=

=!(A^B)=A==B (同値、XORの否定）

　

　

＜問題の難易度＞

探索空間と解空間の話は前にしましたが

、禁止の場合は、それほど解空間は狭まらないと考えられます。実際、かなりの数のペアをハード禁止しても、解がないということは殆ど経験しません。

禁止は、OR的アプローチだと、A+B<=1

という表現が出来ます。各スタッフを独立の問題と捉えたとき、各Day列は、各スタッフの線形和制約となりますが、これと同じ種類の普通の制約の一種に過ぎないということです。なので、いかに多くのペア禁止制約があろうと、厳密解を求めるのに支障はありません。

ところが、A→Bは、かなり解空間を狭めます。A→Bは、Implicationとも呼ばれ、そのブール式は、！A＋Bとなります。AがTrueであれば、BがTrueであることを強要されることになります。これは、AとBの間に強固な結びつきを強いることになります。ペア制約がなければ、通常は、上で述べたような線形和の制約しかありません。つまり、スタッフ毎の制約は、各々スタッフ内で閉じており、各々独立したグラフで表現できます。スタッフ毎の閉じたグラフを線形和で緩く結んだ関係になっており、線形ソルバが得意とするところの関係に持ち込めます。スタッフ毎の制約がいかに複雑であっても閉じた各スタッフについては、閉じたグラフとなります。

A→Bが無ければ、各スタッフ固有の閉じたグラフに出来る。ソフト基数制約が入ると下のように複雑になるが、閉じた系であることに変わりはない。

ところが、A→Bが一つでもあると問題は複雑です。各スタッフを閉じた系として処理できなくなってしまうのです。複数のグラフをマージしようとすると指数関数的に複雑になり、多くの人が関われば、爆発してThe　Endとなります。

このことは、実務的には、よく遭遇する問題ではありますが、国際学会含めて、これを議論したPaperは見たことがありません。海外では、そのような要求がそもそもないのかは分かりませんが、簡単なペア禁止も含めて制約を見たことがありません。（日本では、プリセプタプリセプティは、ありますし、誰々さんと誰々さんが一緒に仕事をするのは嫌だ、という要求はよく遭遇あります。）

理論的解析は、困難です。A→Bの二人に限れば、なんとか厳密式を書くことが出来ると思いますが、それ以上は極めて困難です。ただ言えることは、解空間はかなり狭められる、ということだけです。プレセプタプリセプティの場合、解が存在しない確率はかなり高いです。なので、ハード制約ではなくソフト制約化が必須となります。

で、A→Bは、AL3はとても苦手です。一方禁止は上で述べたように線形ソルバにとっては、普通の制約なので、厳密解を得るのに障害になるとは考え難いです。なんとかA→BをAL3上で改善する方法を考えたのですが、やはり実装が難しい、というところで止まっています。改善策は、多分、存在すると思いますが。

とりあえず、現状A→Bがある場合は、AL1択です。(10人未満ならAL2もアリです)。新人が二人以上いたら、ベテラン何人以上みたいな制約がある場合は、AL1を選択してください。

A→B制約下で、厳密解を導くことは、極めて困難である、ということだけ記しておきます。