「実行不可能」との戦い - 最適化一口話

「メンバーは5人、勤務は日勤と夜勤の二種類しかありません」 今、小さな病院の担当の方に勤務シフト作りについて伺っています。 「毎日日勤は2人、夜勤は1人は必要です。夜勤空けは休み。それとは別に各人週に1日は休みを入れ、夜勤の担当回数は週あたり1日から2日です」 ここまではごく普通。 「新人の E さんは、ベテランのAさん、あるいはBさんとペアで夜勤に入れるようにしてください」良くある話ではあります。 「ベテラン二人は夜勤1日との約束になってます」了解。 モデルのタイプはまさにマス目埋め の典型で、要求を書き下すことに何の難しさもありません。 まずは、この５名（A,B,C,D,Eさん）一週間分の勤務シフト表を作ってみることにしました。 さて、「実行不可能」との戦いの始まりです。 なぜなら、この設定だとすべての制約を満足する勤務シフト表は作れないからです。 昔の数理最適化ソルバーの場合 古典的