「実行不可能」との戦い
「メンバーは5人、勤務は日勤と夜勤の二種類しかありません」 今、小さな病院の担当の方に勤務シフト作りについて伺っています。 「毎日日勤は2人、夜勤は1人は必要です。夜勤空けは休み。それとは別に各人週に1日は休みを入れ、夜勤の担当回数は週あたり1日から2日です」 ここまではごく普通。 「新人の E さんは、ベテランのAさん、あるいはBさんとペアで夜勤に入れるようにしてください」良くある話ではあります。 「ベテラン二人は夜勤1日との約束になってます」了解。 モデルのタイプはまさにマス目埋め の典型で、要求を書き下すことに何の難しさもありません。 まずは、この５名（A,B,C,D,Eさん）一週間分の勤務シフト表を作ってみることにしました。
さて、「実行不可能」との戦いの始まりです。 なぜなら、この設定だとすべての制約を満足する勤務シフト表は作れないからです。
昔の数理最適化ソルバーの場合
古典的な数理最適化ソルバー(厳密解法)にこの条件を入力してみましょう。結果は
「実行不可能(エラー xx番)」
制約条件を満たす解が存在しないので、解析できない、という意味です。 制約を満たす中で最適な答を探すアルゴリズムにとって、 確かに想定外なのはわかるのですが、理由くらい教えてほしい。
「すいません、条件が厳しすぎて結果が出ないんですが」
「え？なぜですか」
「それが私にもわからないんです、でも数学的に答がないことはわかりました!」
「...」
前回に言ったような特殊ケースでなければ、これを喜んでくれるお客さんは居ません。
制約充足問題への変形
こんなとき古くから伝わる智恵として、制約を「努力目標」として記述し、 違反を零にできないまでも最小化する、という形（制約充足問題）に問題を変形する、という手があります。 制約充足問題をやはり古典的な分枝限定法による厳密解法で解いてみましょう。 今度は無事結果が出ました! 違反の最小値は 1、結果は以下です。夜勤明けを「－」で区別して表示しています。
「一箇所違反が出てしまうようですが、結果出ました」
「でも、新人の E さんが一人で夜勤をやってしまってますけど..」
「だって、一箇所は違反が出てしまうのは数学的に仕方ないんです!」
「...」
「数学的」事実をタテに妙に強気に出てはなりません。 ここで「最適解は実は沢山あるかも」と気をまわしていたら、 次のような答え方になったかもしれません。
「Eさんの制約違反の重みを大きく設定すれば、違反しない解が出るかもしれません。
大丈夫です。制約すべてに重みを設定できるようにすれば、お好みの解が自由自在です!」
「...」
がんばっているのはわかるのですが、制約はざっと 9 種類。 お客さんは結果が欲しいのであって、 こんな重みの調整に苦労するくらいならば自分でシフト表、作りますよね。
複数の答を出す(メタヒューリスティクスの適用)
今我々が持っている手段の中で最も訴求力がありそうなのは、 同じ目的関数の答を複数個出すこと。 アルゴリズムを古典的解法からメタヒューリスティクスに切り換えると実現できます。 例えば次のような感じの答が沢山得られます。
月曜に誰も夜勤をやらない解:
ベテランの B さんやむなく週2回で夜勤をする解:
何回か実行して出てきた解を分類すると、最初に出た「新人が単独勤務」解、 「どこかの日の夜勤担当なし」解、「ベテラン週2回」解、 が出るようです（私としては、いつか Web 検索のように、 これら候補解が違反量でランキングされて複数出すようにすればもっと数理最適化は馴染みのあるものになると思っています）。 どんな方向性の解が良いかはお客さんに選んでもらいましょう。 若干のお手数をかけますが、「完成品」の答を選ぶのは9個の重みを設定するよりも良い手段ではあります。 ここまでわかれば、あの deep-learning も及ばない人間知性の働きであるところの 「帰納的推論能力」のおかげでこの問題が解けない理由に気付くことができるでしょう。すなわち、 いずれかの日で（Aさん - Eさん）あるいは（Bさん - Eさん）の組みあわせで夜勤をしてしまうと、 残りの6日の夜勤を3人で担当せねばならない。 その 3人のうち一人は Aさんか Bさんなので、 合計して担当できる夜勤の回数は５回。要するに一日分足りないわけです。 Eさんが2回夜勤をするケースも考えられますが、これも C さん D さんが2人で5回の夜勤をしなければならないので無理、というわけでした。
ごく単純な制約でも組みあわせると相互作用して引き起こされる上、解消の方向性が一意ではない。 数理最適化を実務的に応用しようとする場合、 そのエネルギーの少なからざる部分がこの「実行不可能」との戦いに費される理由になっています。
