多少リアルな搬送経路最適化を量子アニーリングで（続）

　前回の「公園56ヶ所への花壇配送のための搬送経路最適化」の続編。配送先の公園の間の道が何らかの理由で通行止めの場合に、うまく対応できるだろうか？

　実はこれは簡単そうだ。なぜなら、量子アニーリングでは、エネルギー関数（目的関数）の値が最低になる経路が求められるのだから、通行止めのある場合はエネルギー関数の値がぐんと大きくなるように設計すればよい。この例題では、公園を巡る総走行距離をエネルギー関数にしているので、通行止め区間の距離を仮想的に大きくすれば、その区間を含む経路は最適解として出てこないだろう。

　果たして、それでうまくいくのか？
Yes、結果は以下の図の通りである。このケースでは、地蔵橋公園(#52)と常盤公園(#53)の間が通行止めになったと仮定した。トラック２台、４台使用の場合を示したが、いずれも、量子アニーリング結果として、この通行止め区間を避けた最適経路（の近似解）が得られた。

ちょっと勇気づけられる結果だ。

多少リアルな搬送経路最適化を量子アニーリングで

　前回の記事では、TSP（巡回セールスマン問題）は量子アニーリングのための良い例題であることを述べた。今回は、これをもう一歩進めた、多少現実味のある搬送経路最適化問題を量子アニーリングで解いてみた。Fixstars Amplifyの無料オンラインセミナーの資料を参考にさせていただいた。

■課題：公園56ヶ所への花壇配送計画    
　これは筆者が勝手に設定した架空の問題である。区役所「緑と水の課」では区内の公園56ヶ所に、新たにミニ花壇を１セットづつ配送することにした。配送トラック（最大４台）は、「楓川久安橋公園」から出発し、配送後ここへ戻る。それらの総走行距離が最小になるようにしたい。また、できるだけ短時間に配送を完了することを念頭に、各トラックの訪問先の公園数は均等にする。 

　この問題、なんだか多少リアルっぽい（あり得る）ように思いませんか！

　図１には、全56ヶ所の公園の位置と、トラック１台を使った場合の最適配送経路の算出結果を示した。１台の場合は、明らかに、前回のTSPと同一の問題となる。出発地の「楓川久安橋公園」を除いて、残りの55の公園に配送することになる。

■トラック複数台を使った搬送経路の最適化
　複数台のトラックを使用する場合には、通常のTSPの解き方を若干変更した。まず、複数台のトラックが出発点からスタートしてここへ戻るため、経路の順番毎、および、公園毎のone-hot制約を外す必要がある。すなわち、トラックの台数分に応じて、該当するQUBO変数を1または0に定数化する。さらに、トラック毎の走行距離を得るために、制約条件の対象範囲を調整する必要がある。しかしながら、これらは微々たる変更なので特段の問題はないだろう。 

　実際、図２に示す量子アニーリング結果は、トラック2台と４台を使った場合の最適経路（に近いもの）になっているはずだ。図1、図２の上部にあるenergyの値は、総走行距離に相当する。（ただし、経度と緯度をスケーリングしているため、実際の距離ではないが。）トラック台数が増えるに従って、総走行距離は増えるが、台数分に応じた配送時間の短縮が得られるのである。

　これ以外にも興味深い近似解が得られたので以下に示す。（トラック３台、４台の場合）

■感想
　現実味のあるこのような配送計画（搬送経路最適化）が、量子アニーリングにより、かなり容易に解ける（最適解に近いものが得られる）ことを体験できた。量子アニーリングでは、一般に、短時間で大量の近似解が得られる。Google Maps上に結果を描画することも難しくないので、それを眺めれば、それらの中から真に実用的な解を見出せるだろう。

　一方、実際の配送計画問題では、以下のような制約も含まれるので、それらにも挑戦したい。コストとして、次の公園までの距離に加算できる制約であれば取り扱いは容易だ。

• 通行止め区間がある。
• 通過できる経路が定められている
• トラックの積載量に制限がある
• 配達先ごとに到着時間の制限がある
• 各配達先で作業時間が異なる
• 工場内のAGVでは、交差点制御、衝突回避なども考慮

　一例として、「通行止め区間がある場合」の検討結果はこちら。

-------------------

MATLAB EXPO 2022参加ミニ報告

　MathWorks社によるMATLAB EXPO 2022が本日（2022-05-25）東京台場で開催された。現地会場でのリアル開催は３年ぶりだ。でもまだコロナ禍、参加人数はかなり絞られた。過去の開催と同じホテルグランドニッコーの地下大広間だが、本来５人は着席できるテーブルに、３人分の椅子しか置かれていなかった。それでも、最初の基調講演には、ざっとみて、400人は参加していた。これに加えて、オンラインでの参加者は3,300人を超えたそうだ。機械学習とAIを、MatlabとSimlinkを用いて実務に活かそうとする流れは依然として持続している。

　ユーザからの報告、Mathworksからの技術紹介、ポスター、ライトニングトーク、各社の展示デモなど、従来開催と同様に多彩。中でも、自動運転関係が目についた。基調講演の四籠真人氏（本田技研）の他、梅沢翔氏（スバル）、鈴木元哉氏（いすゞ）、井上秀雄教授（神奈川工科大学）、町田和也氏（MathWorks）等の講演がそれだ。

　ここでは、四籠真人氏（本田技研）の話から、「自動運転はそんなに甘いものじゃない」ことを再認識できたので、それを思い出して簡単に書いてみる。まずはおめでたい話題から。レベル３（条件付き自動運転）の型式指定（多分、新型LEGEND）を2020年11月に国交省から初めて受けた時の感激は忘れられないとのことだ。レベル２（運転支援）とレベル３とのギャップは物凄く大きいのだ。

　基調講演タイトル「自動運転レベル３を実現した開発現場の挑戦と今後の展望」を聴講して...

• ホンダのレベル３では、2050年までに、新型LEGENDによる交通事故ゼロを目指す。
• 渋滞パイロット、ハンズオフモード、高度車線変更の実走行ビデオは素晴らしい。
• 運行設計領域（ODD）でないならば自動運転に入らないことが重要なコンセプト。
• 現場では、機能開発よりも安全性・信頼性開発を優先。
• 開発ゴールが存在しない。なぜ売っていいのかを自問の苦闘が語られた。
• 事故の削減は当然だが、自動運転による新たな事故を起こさないことが必須条件。
• リアルワールドのセンシングはとても泥臭い。
• カメラの誤認識はもちろん、情報認識は間違うのを前提とする必要がある。
• カメラ間違いには、逆光、影、雨や雪、道路補修の跡、タイヤの跡、余計な白線等々。
• 冗長設計では、何を冗長とするかが難しい。タイヤを８輪にすれば良いわけではない。
• 冗長設計は複雑を極め、完成させることは非常に難しいパズルを解くようなものだ。
• 安心感、ストレスフリーとは何なのか。
• 人間が無意識に行う妥当な操作、さらにはマナーに属する行動をどう取り入れるか。
• 不具合解析力が極めて重要。
• シミュレーション、実走行ともに重要であり、互いに補完する。
• シミュレーション1,000万通り、実走行100万キロのデータが開発に反映された。

自動運転の難しさをあたらめて知ることができたことが良かった。小生、「自然言語処理」には、捕まえどころのない曖昧さを感じていたのだが、自動運転も似たところがあるようだ。

Matlab Expo 2022 現地開催に参加した証

[補足] レポートが短くなってしまった理由
　この日の夕方のFixstars Amplifyオンラインセミナー「製造業における量子コンピュータ...」に参加するため、早々と切り上げ帰宅してしまった。

されど、巡回セールスマン問題（量子アニーリングの場合）

　TSP（巡回セールスマン問題）に対しては、従来コンピュータを利用した優れた解法が研究し尽くされたようです。しかし、これは、量子アニーリングの例題として有用なのでメモしておきます。ディープラーニングでのポピュラーな例題MNIST（手書き数字認識問題）に匹敵するくらいかも知れません。

■従来コンピュータを用いたTSP解法の状況
　よく目にする記事「30都市でも、現在のスーパーコンでは8億年かかるが、量子コンピュータなら一瞬」というのは、妥当性に欠けます。８億年というのは、特に工夫せずに総当たりの探索を行った場合でしょう。また、量子コンピュータで解ける、と言っても（量子トンネル効果で局所解を回避するとはいえ）一般には最適解が得られるとは限りません。

　現状のTSP解法の集大成は、Waterloo大学のProf. William CookによるConcorde TSPにあります。多様なアルゴリズムの構成で作られたソフトにより、実問題の85,900都市（VLSI応用）が解かれていますし、この名前のアプリも一般公開されています。これを使って、旧型のiPadでも、500都市が15秒で解けました。ですから、当面はTSPに関しては、量子コンピュータの出番は無さそうです。しかし、冒頭に述べた通り、良い例題として以下に検討します。

■量子アニーリングを用いたTSPの解法
　量子アニーリングによる解法の要点は以下に示す通りです。解法と言っても、「解法アルゴリズム」は与えません。コスト関数と制約条件を与えるのみです。ここに最大の特徴があるでしょう。（さらに詳細が必要な場合は、以下に示したURLを参照下さい。）

　これだけで十分良い解が得られることもありますが、コスト関数に加える制約条件の強さを（係数を掛けて）調整する必要がある場合もあります。さらに、コスト関数の縮小、回転対称性の除去、反転対称性の除去などの高度な修正を要する場合もあるようです。

■例題：東京都中央区の公園56ヶ所を回るTSP
　この公園56ヶ所の例題を、あるTSPソルバーで解き、実際にそのルートを全部歩いた報告があります。詳細は、図１に示したURLをご覧下さい。「最短経路だ！巡回セールスマン問題の研究ってすごいなあ」を実感するためとのことです。素晴らしい行動力！「楓川久安橋公園」を出発して、公園56ヶ所を約6.9時間かけて完歩したとのことです！計算上の所要時間と実際の歩行時間の比較などもなされています。

　これと同じ条件設定で、上述の量子アニーリングで解いた結果を図２に示します。最適解（最短）かどうかは分かりませんが、図１の結果とほぼ一致したルートが得られました。実際には、上述のコスト関数と制約条件を、Fixstars Amplify SDKの関数などを使って表現しました。ただし、公園間の距離は、実際の道路経由ではなく、直線距離で代用しています。

　ここでは、量子アニーリングを用いた基本的な利用を示しました。高度なチューニングは含めていませんが、もっと大規模な実用問題では、それらも検討することになるでしょう。本記事はそのきっかけにはなると思います。

新緑の季節

　新緑の季節となった。散歩道にある若葉も清々しい。残り少なくなった近所の田んぼも間もなく田植えとなる。

　不思議に満ちた植物の世界。採取した若葉、なぜ、周りがこんなに尖るのか。
　ボロノイ、フィボナッチ、フラクタルな構造も潜んでいるようだ。

　日本植物生理学会の「植物Q&A」に、「植物の葉になぜ鋸葉があるのか？」という質問があり、学界の権威者である先生からの回答が載っていました。「一言でいうと、これは難問で誰も答を知りません」と。安心しました。

量子アニーリングでは「数独」も「会議スケジューリング」も同じ

　新しい手法にはメリットとデメリットがある。しかし、量子アニーリングを検討し始めた現時点では、まず、メリットを追求するのが良い。その実績を積めば、次第に問題点にも気づき、改善提案もできるかもしれない。

（以下の３つの例題では、Fixstars AmplifyのWebページにあるデモプログラムを利用、または参考にさせていただいた。そのURLは、図４の中に示した。本記事の内容は、当方が独自に調査・試行した結果に基づいている。）

■量子アニーリングを用いた解法とは
　量子アニーリングを用いた解法の最大のメリットは、「問題毎に固有の解法アルゴリズムを考えなくて良い」ことだろう。それを明確するため、ここでは「数独」と簡単な「会議スケジューリング」、および「グラフ彩色問題」の３つを例に、これらがほとんど同じ問題として扱えることを述べたい。

　パズル数独は、よく知られたいくつかの制約条件のもとで、9 x 9 のマスに入れる数字を決める問題である。また、ここで扱う会議スケジューリングは、いくつかの制約条件のもとで（その仕様詳細はここに示したが）午前中に６つの会議を３つの会議室で行うために、各会議の開始時間を決める問題となる。３番目は、４色定理に基づくグラフ頂点彩色問題（典型的には地図の色塗り分け）である。

　量子アニーリングを行うためには、問題の仕様を、目的関数 and/or 制約条件として表現すれば良いのである。問題固有の解法アルゴリズム（解法手順）は与える必要がない。これは、現代の数理計画法からの影響を受けているとも言えよう。今回の例題はいずれも、目的関数は与えずに、制約条件だけを設定すればよいケースとなっている。ただし（この言葉がよく出るのだが）、実際にはSDKが、制約条件を反映した目的関数（エネルギー関数）を生成していると言える。イジングによる処理は本質的にそういうものだ。

　実際、図１に示した通り、これら３つの問題の構造はほとんど同じに見える。ただし、(a)と(b)では３次元QUBO配列、(c)は実質２次元QUBO配列となるが、その違いは問題ではなく、うまく行きそうだ。

■量子アニーリングによる解法の実行
　制約条件設定の詳細は略すが、３つの問題とも、Fixstars Amplify SDKを利用した短いPythonプログラムを作成することになる。その主要部は、制約条件を設定するために、QUBO変数（またはイジング変数）の一次または二次多項式による等式または不等式を生成するものだ。それを与えて量子アニーリングを実行し、その結果を得ることができた。図２〜図４に示す通り、数独、会議スケジューリング、グラフ頂点彩色とも極く短時間で正解が得られた。

■量子アニーリングのインパクト

　この結果を眺めていると、量子アニーリングが与えるインパクトは、段々に広く認知されると感じるのである。つまり、従来のプログラミング技術をあまり習得していない、いわゆる文系型の人々にも、組合せ最適化問題を解くことができる手段を与えることに繋がると思われる。問題を正確に表現するための制約条件の設定は、それほど容易ではなかろうが、問題毎の解法アルゴリズムを設計するのに比較すれば、格段に敷居は下げられる。

　一方、個々の問題については、従来コンピュータ上で動く高性能な解法を考案することに生きがいを感じる人もいるだろう。小生も実はその一人であった。人間による洗練されたアルゴリズムは、このような量子アニーリングによる「一般的解法」よりもはるかに（必要な演算回数という尺度での）性能が高い場合が多いだろう。

　しかし、量子アニーリングの利用は、（人間の貴重な時間を考えた場合の）実務における効率化や、必ずしもIT専門家に頼らなくても良いことを示唆する。もちろん、（この期待も大きいのだが）場合によっては、処理時間の観点からも、人間のアルゴリズムをはるかに凌駕する高性能を発揮するだろう。その期待が高まるのである。

出揃った量子アニーリング型コンピュータ/イジングマシン

　これまでの記事に書いて来たことですが、Fixstars Amplify SDKでは、これまで５社の量子アニーリング型コンピュータ/イジングマシンが使えたのですが、最近、さらに２社のマシンが追加になりました。組合せ最適化問題の効率的求解に対する実世界での需要がさらに高まっていることを反映しているようです。（新しい最後の２機はまだ試用していませんが。）現時点でFixstars Amplify SDKで使えるマシン：

• Fixstars Amplify AE
• D-Wave 2000Q/Advantage
• 日立 CMOS Annealing Machine
• 富士通 Digital Annealer
• 東芝 Simulated Bifurcation Machine
• 広島大学/NTT Data ABS QUBO Solver
• Gurobi Gurobi Optimizer（数理計画最適化ソルバーで有名な会社）

　７機種それぞれ特徴があり、必要に応じて選択して使えるのはとてもありがたい。しかも、どの機種も基本的には同一のSDKを利用できる点も素晴らしいですね。

　また、Fixstars Amplify SDK自体も、大幅なバージョンアップがなされ、Version 0.7.0となったことがアナウンスされました。実際、量子アニーリング型コンピュータ/イジングマシンへの（数理計画法でいうところの）、決定変数、minimize/maximize（目的関数）、subject to（制約条件）の設定と送信、アニーリング結果の受信に要する時間が、かなり短縮されたことが実感できました。

（追記）昨日（2022-5-10）成立した「経済保安法」の４本柱の一つは、先端技術の研究開発だ。その中には、「宇宙・AI・量子などの重要分野」と記されている。情報技術関係に携わっている人々にとって、「量子」の重みが増してくるのではなかろうか。
　ただ、本記事で話題にしている量子アニーリングが、すぐに現在の数理計画法にとって代ることはないだろう。長年に渡って蓄積された優れたアルゴリズムやノウハウの宝庫である数理計画法は、それどころか、量子アニーリングを用いた解法にも本質的な影響を与えているように感じられるのである。（もう一つのタイプの量子ゲートウェイコンピュータについては、小生はよく分からない。）そのうえで、全く新しいタイプのマシンを使った解法を学ベることに感謝し、何かすごいことができそうだという思いを持ち続けたい。

五月初旬の大山（神奈川県）（筆者撮影）

五月初旬の利尻岳（北海道）（利尻町ライブカメラから引用）

量子アニーリング（イジングモデル）で卒研発表会をスケジュール(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)とするかで、解への収束状況が異なることも分かりました。まだまだ未知の部分があります。

量子アニーリング（イジングモデル）で卒研発表会をスケジュール(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関数とすることになろう。→ 具体的な説明はこちらです。