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

要旨：前回の記事では、卒研発表会のスケジューリングを量子アニーリング型マシン（以後、簡単のためにイジングマシンと呼ぶ）で解くことにしました。未完成でしたので、今回、改めて挑戦し、所望のスケジュールを作成することができました。実際に行われた卒研発表会のデータを使っていますので、当時作成された発表会プログラムとの比較検討も含めました。小さいながら、実問題をイジングマシンで解いたことで、新たに分かったことも多いです。[末尾に[注]別法を追加しました。2022-5-7]

　今回も、Fixstars Amplifyが提供しているチュートリアルのPythonプログラムを参考にさせていただきました。

 ■課題(改訂版)：卒研発表会プログラムの作成
　図１は、ある大学の情報工学科の卒研発表会の実データである。図1(a)のように、19の研究室に４名〜10名の発表者がいる。発表は５つの教室で並列に行われ、一人当たりの持ち時間は１スロット（= 持ち時間10分+予備1分）、研究室入れ替えに１〜２スロット程度とする。9:30〜12:40を午前の部、昼休みを挟んで、13:40から午後の部を開始。最長でも、全体を17:00頃には終了させる。

　これは単なる箱詰め問題ではなく、図１(b)のような研究室間の依存性もある。すなわち、教員は自分の研究室の発表にはもちろん参加するが、評価担当の他の研究室の発表も聞く必要があるからだ。例えば、教員bは、研究室L01に属するが、L06とL11の発表にも参加する。したがって、L01とL06、L01とL11、L06とL11のいずれの対でも、発表時間帯に重なりがあってはいけない。

 ■結果：ジングマシンを利用した発表会スケジュールの完成
　結果を先に示す。イジングマシンを利用して得られた解（の一つ）は図２の通りである。これは、上記の要求仕様を全て満たしている。終了時間などは一目瞭然だが、上で述べた研究室間の依存性の保持はこの図では分かりにくいので、改めて、図３にその検証データを示した。図３内の赤字の情報から、図１(b)に示した依存性は全て満たされていることが分かるだろう。

■実際に使われた卒研発表会のプログラムとの比較　
　図４は、実際に行われた卒研発表会のスケジュールテーブルである。どのように作成されたかは不祥だが、恐らく、人手による試行錯誤で決められたと考えられる。全体の終了時間は、図４では17:15であり、図２は16:47となっている。イジングマシン利用の方は、淡々と規定の研究室交代時間をとっているのに対して、人手作成では、場合によって多めの交代時間としているためだろう。

　ここで注目すべき点がある。研究室L04には、２名の教員（e, f）が属している。だが、教員f（図４に赤字で示した）は、自分の研究室と同じ時間帯に、別の研究室L00の評価に参加している。これは上記の仕様から外れるのだが、人手では良い解が見つからなかったためと推測される。イジングマシンを使った結果の図２ではこの問題は解決されている。

　一方、人手作成には人間味あふれる配慮も組み込まれていた。イジングマシンの方は冷たく（というほどではないが）整然としたスケジュールになっている。例えば、図４の午前中の教員b, cは、午前中は教室を移動する必要がなく、そのままその教室に居ればよいのだ。いずれの教室もすぐ近くなので、このような配慮は必須とも思えないが、情報工学科の伝統として続いているのかも知れない。

■どのようにイジングマシンを利用するのか
　今回の方式の概略は、前回の記事に示したのとほぼ同じである。イジングマシンは魔法のようなマシンであるが、一発で完全な解が得られるわけではない。
　今回のケースでは、目的関数として、各教室での終了時間のバラツキをできだけ小さくすることとし、これに、さらに次のような制約条件を付加して解く：
　（１）各研究室は、いずれかの教室に必ず１度だけ配置される。
　（２）各教室の終了時間は（午前、午後とも）、規定の最小/最大の範囲となること。

　このような条件下で、イジングマシンから、一度に大量の解（今回の場合は、１回で100〜200個程度）が得られるのである。確率的な要因があるので、実行の度にその状況は変わる。

　ここで最も重要なことがある。このような方法では、図１(b)に示した研究室間の依存性を満たすことができないのである。なぜならば、イジングマシンから得られるのは、研究室をどの教室に配置するかという解なのであり、研究室の発表が実際に重なるか否かは、時間的にスケジュールしてみないと決まらない。安全サイドに、依存のある研究室を全て同じ教室へ配置することも考えれるが、それでは、スケジュール長が著しく長くなるだろう。

　どうしたものか！
　その答えが、以前読んだことがある、西森秀稔教授（東京工業大学）と大関真之教授（東北大学）よる以下の書にあった。哲学的な一節から、重要なヒントが得られたのである。

 　その一節を引用させていただく。

「きっちりと厳密解が得られなければ"成功"とは言えないと思う人もいるだろう。だが、それは狭く考えすぎだ。多くの近似解を短時間に出力するのに使えるサンプリング用のマシンと見れば、失敗を別の方向へと生かせる。必ずしも完全には思い通りに行かなかったときのあきらめと切り替えの素早さ、とにかく新しい道に進んでみようという前向きの発想が、イノベーションを生み出す鍵となる好例...」

　これだ！

　今回の場合、上に述べた通り、依存性を特に考慮しない解が大量にいくらでも得られる。その中には、かなりよく依存性を満たすものも含まれるはずだ。得られた解が依存性を完全に満たすか否かを検査するPythonプログラムを作って、（その解において各教室単位で適当にスケジューリングし）機械的にどんどん調べれば良いのだ。人の頭に負担はかからない。イジングマシンは、従来のコンピュータとはまるで異なるものなのだから、利用の仕方も違う。こんなやり方も正当なのだ！「新しい酒は新しい革袋に盛れ」と。実際、図２に示した完全な解は、こうして（極く短時間で）得られたものなのだ。

【注】別法もある。Fixstars Amplify SDKでは複雑な制約をpenalty関数で与えることができるので、その利用も考えられる。その場合、時間軸を離散化し（例えば10分間隔）、その１単位毎に研究室数のQUBO変数を生成する。そして、依存のある研究室同士の、一定区間のQUBO変数の積がゼロになる（同時に起こることを意味する1にはならない）という制約をpenalty関数とすることになろう。→ 具体的な説明はこちらです。