Jij 数理最適化入門セミナー第2回 「会議室割り当て問題で数理最適化の流れを体験しよう」
Jijでは10月31日－11月22日までの4週間、数理最適化入門オンラインセミナーを行なっています。
この記事は数理最適化入門セミナー第2回 「会議室割り当て問題で数理最適化の流れを体験しよう」の内容についての記事です。
Jijでは、誰もが最適化を行うためのツールとして、JijModeling、JijModeling-Transpiler、OpenJijの3つのライブラリーを提供しています。これらのツールは、JijModelingは数理モデルの構築を支援するツール、JijModeling-TranspilerはJijModelingで記述した数理モデルを別のモデラーへと変換するツール、そして、OpenJijはアニーリング用のソルバーとなっています。
今回はこれらのツールを使って、会議割り当て問題を解きながら数理最適化の流れを体験していきたいと思います。
今回使用するJijModeling、JijModeling-Transpiler、OpenJijは次のようにインストールすることができます。
今回のノートではそれぞれ以下のバージョンで実行しています。
会議室割り当て問題とは
会議室割り当て問題は、 個の会議が予定されているとき、 個の会議室に対して、各会議を被らないように割り当てるという問題です。
例えば、以下の左の表のような会議スケジュールを例にとって考えてみましょう。
上記では午前中に5個の会議が予定されていますが、使用可能な会議室が3つしかないとします。
まず、この会議スケジュールをそれぞれ時系列に並べ直してみます。
左の表を時系列順に並べ直したのが右の図です。
これを少し眺めると、会議4は会議2とかぶっておらず、会議5は会議1と会議3と被っていないことがわかります。
そこで、会議4は会議2の後に、会議5は会議1の後に行うことで、5個の会議を3部屋で行うことができることがわかります。
このように、問題サイズが小さければ比較的簡単に目で見て解くことができます。
しかし、問題サイズが大きくなると毎回このようにしてスケジューリングを組むのは面倒です。
今回は、この問題を数理最適化問題として定式化し、JijModelingとJijModeling-Transpilerそして、OpenJijを使って解いていこうと思います。
会議室割り当て問題における条件の整理
まずは、会議室割り当て問題を定式化するための手がかりとして、欲しい結果や制約条件を文章として書いていきましょう。
会議室割り当て問題で欲しいのは、上の小さい例で考えたように、「会議の被りがないように会議室をそれぞれの会議に割り当てた」結果です。
次に、この文章にした結果についてより詳細に考えてみます。
まず、「会議室をそれぞれの会議に割り当てる」という部分は、ある会議 に対して、会議室 を1つだけ割り当てるということです。
また、「会議の被りがない」の部分についても考えてみましょう。
これは、もし会議室 がある会議 に使われていたとしたら、その会議を行っている時間帯においては、会議室 に他の会議 に割り当てない、ということです。
以上をまとめると会議室割り当て問題の制約条件は次の2つとして書くことができます。
- ある会議 に対して、会議室 を1つだけ割り当てる
- ある会議 に会議室 が割り当てられた時、会議 を行っている時間帯においては、会議室 に他の会議 を割り当てない
また、この問題では、上記の2つの条件を満たした会議室スケジュールであればどんなスケジュールであっても構わないので、制約条件だけがある問題であることがわかります。
会議室割り当て問題の定式化
次に、会議室割り当て問題を定式化していきます。
決定変数
この問題で知りたいのは、各会議 に会議 を割り当てるかどうかなので、次のようなバイナリ変数 を決定変数として、定式化していきます。
制約条件 1 : ある会議 に対して、会議室 を1つだけ割り当てる
まず、「ある会議 に対して、会議室 を1つだけ割り当てる」を定式化していきます。
この条件は、ある会議 に対して、会議室を割り当てなかったり、複数の会議室を割り当てるようなことは内容にしろということです。
例えば、会議1に対して3つの会議室のうち1つを割り当てるという状況では、 のうちどれかが1になっていて、それ以外は必ず0でないといけないということです。
このような条件を定式化するにはone-hot制約と言われる制約が用いられます。
式としては、
と書くことができます。
これは、ある会議 について、会議室 について和を取ると1になるという制約です。 はバイナリ変数なので、1つが1ならそれ以外は全てが0になる必要があるので、この制約条件は確かに、想定した制約と同じものになっていることがわかります。
制約条件 2 : ある会議 に会議室 が割り当てられた時、会議 を行っている時間帯においては、会議室 に他の会議 を割り当てない
次に、「ある会議 に会議室 が割り当てられた時、会議 を行っている時間帯においては、会議室 に他の会議 を割り当てない」について考えてみます。
ここで、時間帯が被っている会議を とします。ここで は時間帯が被っている会議ののペアの集合です。
例えば、上記の例だと です。
さて、時間帯が被っている会議 に同じ会議室 が割り当てられることはないので、 と が について同時に1になることはないはずです。つまり、これらについて和を取ったとしても必ず1よりも小さくなるはずです。
そこで、この条件を
と定式化することができます。
ここで、 となっているのは、必ずしも会議室 が会議 のどちらかに割り当てられる必要はないからです。
ソルバーに合わせた定式化
問題によって定式化にはさまざまな方法があります。そのような定式化の中でどのような定式化を選ぶかの基準の一つに使いたいソルバーに合わせた定式化というものが挙げられます。
例えば、ここでは2つ目の制約を線形不等式制約として定式化しましたが、アニーリングを用いる場合では、不等式制約に比べて等式制約を用いた方が精度が出やすくなります。一方で、線形計画ソルバーを用いる際には、もちろん線形制約しか使えませんので、線形で定式化する必要があるます。
今回はアニーリングを用いますので、この線形不等式制約の2次等式制約への変形を紹介します。
(2)式は、2次等式制約として、
と変形することができます。
(3)式がなぜ、(2)式に対応しているかを見るには、下の表を見るとわかりやすいです。
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 2 | 1 |
表を見ると、 の時には、 であり、 の時にだけ、 となっていることがわかります。
なので、 という制約条件をかけることで、 が守られるのです。
以上から、会議室割り当て問題は、グラフ彩色問題として定式化できることがわかりました。
以上からグラフ彩色問題の数理モデルは
と記述することができます。
今回は、上でも述べたように目的関数がなく制約条件だけの問題になっています。
JijModelingを用いた数理モデルの実装
では、実際に会議室割り当て問題をJijModelingを用いて数理モデルを実装していきます。
まず初めに、モデリングで使う変数や定数を定義していきます。
次に、実際に問題を定式化していきます。
問題インスタンスの作成
次に今回解く問題のインスタンスを作成します。
ここではランダム30分から2時間程度の長さの会議をランダムに複数作成し、それらを会議室に割り当てていきたいと思います。
今回は、実行可能解が必ず存在する問題データを作っています。
今回は、会議室が6個の問題を生成します。
以下のコードで、どのような会議が作成された確認することができます
今回は合計で30個の会議が生成されました。
次に、こちらの与えられた会議表を時間帯が重なっている会議ペアを調べ、最適化に使うためのデータセットを作成していきます。
に渡すためにデータを辞書にまとめておきます。
数理モデルの変換と最適化計算
ここまでで、JijModelingを用いた数理モデルの実装と問題データの用意が終わりました。
次に、JijModelingで記述した問題をソルバーが解ける形に変換していきます。
この問題の変換にはJijModeling-Transpilerを用います。JijModeling-TranspilerはJijModelingで記述した数理モデルをさまざまなモデラーに変換するツールです。
現在、JijModeling-Transpilerを使うと、PyQUBOとPython-MIPへと変換することができます。
今回は、JijModelingをPyQUBOへと変換し、PyQUBOからQUBOを生成することで、OpenJijに問題を解かせたいと思います。
まずは、JijModeling-TranspilerとOpenJijをimportしておきます。
ここでは、JijModelingで作成した数理モデルとに入れためのデータである、そして、制約条件に対する重み係数であるを与えるとアニーリングまでやってくれるように計算を下のようにまとめておきます。
では、この を使って計算してみます。
得られた結果を可視化してみます。
今回は、時間が被っている会議が存在しないので、与えられた会議データから正しいスケジュールが得られました。
ここでは、実行可能解が得られましたが、実行可能解が得られていない場合でもとりあえず可視化してみることで、数理モデルのどこに問題があるかを見つけやすくなります。
おまけ : 線形計画ソルバーを用いた最適化
上では、アニーリングを用いて問題を解きました。ですが、厳密解ソルバーを使いたい時もあります。そこで、ここではJijModeling-Transpilerを用いてPython-MIPへと変換し、厳密解ソルバーを用いて最適化を行なっていきたいと思います。
まず、線形計画ソルバーを用いるので、線形の形で問題を記述するために式(1)と(2)で問題を定式化します。
先ほどと同じように、ijModelingで作成した数理モデルとに入れためのデータであるを渡して、最適化を行なってくれるように関数にまとめておきましょう。
実際に、最適化を行なって、結果を可視化してみます。
