https://www.topcoder.com/challenges/30081256
$A$人の労働者に対して$D$日間($D$は7の倍数)の仕事を割り振る。それぞれの日は$T$個のシフトに分かれていて、それぞれの労働者がシフト1回ごとに生産できる製品の数$s^a$と各日ごとの目標生産数$S^d$、および労働者$a$が$d$日目$t$番目のシフトに入れるかどうかの情報$r^{adt}$が与えられるので、与えられた制約を満たしながら、それぞれの日の生産数が目標生産数にできるだけ近くなるようなシフト表を作れ。
制約は以下の5つである。
この問題はデジタルアニーラのLarning Challengeですので、解法の概要およびコードはTutorialに記載されています(コンテスト期間中は、build_sleep_ruleの実装だけは公開されていませんでした。)。この記事では、Tutorialの内容について行間を埋める形で解説することを目指します。
前回と同様に、値を最小化することでスケジューリング問題が解けるようなquadratic polynomialを構成することを目指します。ここで $X_{adt}=1$のとき、$a$人目の労働者が$d$日目に$t$番目のシフトに入っていることを表します。今回の問題では、QUBOに落とし込みたい要素は次の6つです。
各日に雇用した労働者のシフト1回あたりの生産量の合計と各日の目標生産量との差が小さいほど値が小さくなるような関数として \begin{align*} \sum_d \left( \sum_{a,t} s^a X_{adt}-S^d \right)^2 &=\sum_d \left( \left( \sum_{a,t} s^a X_{adt} \right)^2 -2S^d\left( \sum_{a,t} s^a X_{adt} \right)+({S^d})^2 \right)\\ &=\sum_d \left( \left( \sum_{a_1,t_1} \sum_{a_2,t_2} s^{a_1}s^{a_2}X_{a_1dt_1}X_{a_2dt_2} \right)-2S^d\left( \sum_{a,t} s^a X_{adt} \right)+(S^d)^2 \right)\\ \end{align*} が作れます。
$r^{adt}=0$のとき、労働者$a$を$d$日目$t$番目のシフトに入れることはできません。重み係数$W$を導入して \begin{align*} W\sum_{adt}\left( 1-r^{adt} \right)X_{adt} \end{align*} とすればよいです。
ある労働者が$d$日目$T$番目のシフトで働いたとき、その労働者は$d+1$日目$0$番目のシフトに入ることはできません。これは \begin{align*} W\sum_{ad}X_{adT}X_{a(d+1)0} \end{align*} とすればよいです。
各$a,d$について、$\sum_t X_{adt}=0, 1$であれば制約を満たすので \begin{align*} W\sum_{ad}\left( \sum_t X_{adt} \right)\left( \sum_t X_{adt} -1 \right) &=\sum_{t_1}\sum_{t_2} X_{adt_1}X_{adt_2} - \sum_t X_{adt} \end{align*} とすればよいです。
制約4が満たされていると仮定すると、労働者ごとに1日に最大で1シフトしか入っていないと考えられるので、理想的には労働者ごとの各週の合計シフト数が$0,1,2,3,4,5$のときにペナルティなし、$6,7$のときにペナルティありとなるような関数を作れればよいはずです。そして、今回用いられている関数は \begin{align*} &W\sum_{w=1}^{D/7}\sum_a\left( \sum_{d=7(w-1)+1}^{7w}\sum_t X_{adt} +2y_{aw0}+5y_{awl}-4 \right)\left( \sum_{d=7(w-1)+1}^{7w}\sum_t X_{adt} +2y_{aw0}+5y_{awl}-5 \right)\\ &=W\sum_{w=1}^{D/7}\sum_a \left( \sum_{d_1,t_1}\sum_{d_2,t_2} X_{ad_1t_1}X_{ad_2t_2} + \left( 4y_{aw0}+10y_{aw1}-9 \right)\sum_{d,t} X_{adt} - 18y_{aw0} - 45y_{aw1} +20\right) \end{align*} となっています。
ここで、$\sum_{d=7(w-1)+1}^{7w}\sum_t X_{adt}$は労働者ごとの隔週のシフトの数に対応していて、$y_{aw0},y_{aw1}$は補助変数となっています。$y_{awp}\in\{0,1\}$なので、$2y_{aw0}+5y_{awl}$は$\{0,2,5,7\}$のいずれかの値をとり、最もペナルティの低くなるような値に変化します。よって、$\sum_{d=7(w-1)+1}^{7w}\sum_t X_{adt}$が$\{0,2,3,4,5\}$のときにペナルティが0になります。隣り合う2整数を掛けると必ず非負になるため、ペナルティが負になることはありません。ある労働者のある週の合計シフト数が1のとき、ペナルティの最小値は$(y_{aw0},y_{aw1})=(0,1),(1,0)$の場合で$2W$になっていますが、このことについては、1024bitという解空間の制限から変数を2つまでしか使えないことによるものであると説明されています。
この制約を実現するためには、各週の労働日数が0(雇わない)もしくは大きい値(雇って、たくさん働かせる)の場合にペナルティが小さく、そうでない場合に大きくなるような関数を作れればよいことがわかります。そのような関数として $$-W\sum_{w=1}^{D/7}\sum_a y_{aw1}$$ が使えます。制約5を考えると週の労働日数が0もしくは1のときに$y_{aw1}=1$となるので、そのような場合には負のペナルティ(ボーナス)がつくことになります。労働日数が1の労働者に関しては制約5で$2W$のペナルティがついているので、差し引き$W$のペナルティとなります。雇わない労働者が増えるほどスコアが高くなるので、雇用を減らしつつ、週に1日しかこない労働者を減らすことができます。
以上で、制約をすべてQUBOに変換することができました。よって、これらをすべて足し合わせた関数 $$H=\sum_d \left( \left( \sum_{a_1,t_1} \sum_{a_2,t_2} s^{a_1}s^{a_2}X_{a_1dt_1}X_{a_2dt_2} \right)-2S^d\left( \sum_{a,t} s^a X_{adt} \right)+(S^d)^2 \right)+W\sum_{adt}\left( 1-r^{adt} \right)X_{adt}+W\sum_{ad}X_{adT}X_{a(d+1)0}+\sum_{t_1}\sum_{t_2} X_{adt_1}X_{adt_2} - \sum_t X_{adt}+W\sum_{w=1}^{D/7}\sum_a \left( \sum_{d_1,t_1}\sum_{d_2,t_2} X_{ad_1t_1}X_{ad_2t_2} + \left( 4y_{aw0}+10y_{aw1}-9 \right)\sum_{d,t} X_{adt} - 18y_{aw0} - 45y_{aw1} +20\right)-W\sum_{w=1}^{D/7}\sum_a y_{aw1}$$ が最小になるような$X_{adt},y_{awp}$を見つけることで、スケジューリング問題を解くことができます。これで、スケジューリング問題をデジタルアニーラで解ける形に変換することができました。
Tutorialに載っているので、割愛。