INRC2の再実装 exactly one

 世界記録更目的のため、細部まで詰めて再設計を行っています。スケジュールナースベースではなく別なフレームワーク上での設計になります。

最初は、Exactly　One。

スケジュールナースが内部で持っている唯一と言ってよい最も基本的な制約の実装になります。具体的には、シフトは、１スタッフ・１日あたり１個である。２個以上でも０個でもない、１個である、という制約です。

グラフ上でこれを表現すると、最初の２日は、

Earlyでなければ、Day、Dayでなければ、Late,LateでなければNight,NightでなければRestとなります。シフト数は休みを含めて５個であり、必ず５個のうちの１個のシフトが選択されています。

全体では、このパターンが続いて、２８日＋７＝３５日パターンとなります。

INRC問題のパターンは、１カ月の場合２８日ですが、先月の分を７日分見ており、３５日として解いています。

Exactly One制約は、グラフ上ではシンプルに表現出来ていることが分かります。

ところで、Exactly　Oneは、例えば数独のラージサイズ版、１００ｘ１００は、多数のExactly One制約が出現します。こうした場合のExactly Oneの実装は、巨大になります。Native表現では、At least one && At most oneですから、１個以上かつ２個は、ＮＧになります。AtleastOneは、ＯＲかつ全ての２個の組み合わせで２個があってはいけない（Atmostone）を実装することになります。その場合、例えば２５個では２５C2となり、無視できない大きさになります。これが、スケジュールナースでシフトは、２５個以下を推奨している理由です。Exactly Oneの実装は、学術問題でもあり、例えば、

Jingchao Chen. A New SAT Encoding of the At-Most-One Constraint - ModRef 2010.pdf (uu.se)

があります。しかし、そうした場合でもグラフ上の表現は、シンプルであることがグラフを使うメリットです。