量子アニーリング（イジングモデル）で卒研発表会をスケジュール(2)

【要旨】スケジュール(1)の続編です。その記事の末尾に書いた[別法]を具体的に示します。Fixstars Amplify SDKで提供される、量子アニーリング向けの様々な制約の与え方に関するメモでもあります。

■例題：いくつかの制約のある会議のスケジューリング

　今回は、図１に示すような会議スケジューリングを行います。人手でも解ける簡単な例題ですが、量子アニーリングにおける様々な制約を与える上で参考にして戴けるかと思います。

　６つの会議（A〜F）を３つの会議室（K0、K1、K2）で、9:00 - 11:50の間に行うとします。どの会議をどの会議室で行うかは、図の通りに予め決まっています。問題なのは、参加者の都合と一つの会議室では（当然ですが）同時に複数の会議はできないことから、時間帯が重なることが許されない会議が図のように決まっていることです。なお、同一会議室での会議の入替え、および、参加者が移動する会議間には10分間の余裕が必要とします。これらを全て満たすスケジュールを、量子アニーリングで求める問題です。

■量子アニーリングによるスケジューリングの結果

　離散化した時間の個数（10分単位）と会議の数の積の個数分のQUBO変数を用意しました。そのQUBOを変数を用いて、図１に示された制約の全てを表現できます。今回は、Fixstars Amplify SDKの関数penalty、sum、sum_poly、equal_toなどを利用しました。

　結論を先に示します。図２(a)は、これらの制約を与えた量子アニーリングの実行結果です。会議毎に１つだけ存在する、北向きの赤い矢印のセットが（一つの）解を示しています。図２(b)はこれを見やすく可視化したものです。図１(a)の赤矢印は、会議の開始時刻を示していますので、それが図２(b)では赤丸で表現されています。

■penalty関数を用いた制約の与え方

　上で与えた制約のうち、「所定の会議同士の時間帯の重複を許さない」という制約を、penalty関数で表現する方法を図３に示しました。

　これ以外に、「各会議のQUBO変数は、必ずただ一つの時間点において１となる」というone-hot制約は、sum_poly関数とequal_to関数を用いて表現できます。penalty関数による制約とこれらの制約を全て加算した形の最終的な制約を量子アニーリングに与えることができました。

■別解もたくさん得られるのがいいところ

　この解法では、たくさんの解が短時間で得られるのが良いところです。例えば、図２の解の場合、会議Eの出席者で「朝、会議前にもうちょっとコーヒータイムが欲しい」という人が多いとします。しかし、単に会議Eを遅らせると、その終了が会議Aの開始と重なってしまうので、まずい。でも、図４のような別解ならOKですね！

　この別解では、EとDが入れ替わっていますが、同時にAとBもこのように入れ替える必要がありました。今回は演習用のため問題が簡単すぎたかも知れませんが、今後、もっと複雑な問題で本領を発揮できるでしょう！

■所望の解を得るには何度かの試行が必要

　この規模のスケージューリングでも、解が得られない（制約条件を全ては満たせない）状況になることもあります。その場合は、アニーリングのタイムアウトを長めにすることで上手く行くことがあります。日立CMOS Annealing マシンを利用する場合は、タイムアウトをアニーリングの温度パラメータ（初期値、ターゲット値、下降ステップ数、ステップ長）の調整で行えます。（こちらにある、イジングエディタの左欄詳細設定の温度設定の解説図が分かりやすいです。）

　しかしながら、タイムアウトは一つの要因に過ぎず、制約条件をどのように与えるかも効いてきます。この例では、会議の長さに応じて、これ以降の時刻では開始できないという制約があるのですが、それをpenalty関数で上記のように与えるか、それとも、その時刻領域のQUBO変数を定数(0)とするかで、解への収束状況が異なることも分かりました。まだまだ未知の部分があります。