ジョブショップスケジューリング問題への応用 “Job Shop Scheduling Solver based on Quantum Annealing” by D. Venturelli, et al. (2015).
文献情報 概要 組合せ最適化問題の一つであるジョブショップスケジューリング問題を定式化し、これをD-Wave Twoにより解いた。 問題 ジョブショップスケジューリング問題(JSP:Job Shop Scheduling Problem)とは、機械を用いて複数のジョブを処理する場合に、全体の稼働時間やコストを最小にする問題である。各ジョブには複数のオペレーションが含まれ、各オペレーションには実行する機械に対して所要時間が決まっている。今回は以下の制約のもとで、オペレーションを機械に割り当てて、全てのジョブが完了するまでにかかる時間を最小化する。 最適化問題の定式化 組合せ最適化問題の種類: ジョブショップ・スケジューリング問題変数: $x_{i,t} \in \{0,1\}$ (オペレーション$O_i$が時刻$t$に始まるとき$1$, そうでなければ$0$)目的関数: $$ H_T(\bar{x}) = \eta h_1(\bar{x}) + \alpha h_2(\bar{x}) + \beta h_3(\bar{x}) $$ ただし、$\eta, \alpha, \beta >…
組合せ最適化問題のイジングモデル表現 “Ising formulations of many NP problems” by Andrew Lucas (2014)
文献情報 タイトル: Ising formulations of many NP problems 著者: Andrew Lucas (Google Scholar) 書誌情報: Frontiers in Physics 2, 5 (2014). (doi: 10.3389/fphy.2014.00005) 概要 近年、NP完全、あるいはNP困難な組合せ最適化問題の断熱量子最適化（AQO, Adiabatic Quantum Optimization）を用いた解法が注目されている。全ての組合せ最適化問題はIsingスピングラスの基底状態探索へと定式化することが可能であり、そのための手法としてAQOを用いる。 本論文では、組合せ最適化問題の累計パターンを集めたKarpの21のNP完全問題 (Karp’s 21 NP-complete problems)を含む組合せ最適化問題のIsingスピングラスによる定式化のハミルトニアンを網羅している。 取り扱われている組合せ最適化問題 分割問題 (Partitioning Problems) 数分割 (Number Parti…
最大クリーク問題への応用 “Finding Maximum Cliques on the D-Wave Quantum Annealer” by Guillaume Chapuis et al. (2018)
文献 概要 あるグラフの部分グラフのうち、それに含まれる任意の二点間に辺があるような部分グラフで最大のものを最大クリークと呼ぶ。与えられたグラフから最大クリークを発見する問題は最大クリーク問題と呼ばれており、これはNP困難であると知られている。本論文はこの最大クリーク問題のD-Wave 2Xを用いた解法について述べている。 解き方 グラフをG=(V, E)と表し、Vは点の集合、Eは辺の集合とする。グラフGに対して、辺のある二点間の辺をなくし、辺のない二点間に辺を張った（辺の集合Eに対して補集合$\overline{E}$を考える）グラフH=(V, $\overline{E}$)を考える。このとき、グラフHの独立集合S (どの二点間も辺で継がられてない点の集合)はグラフGではクリークに他ならない。つまり、最大クリーク問題と最大独立集合は表裏一体の関係となっており、このことを利用してグラフG最大クリークを求めるために、グラフHの最大独立集合問題を見つけることを試みる。この問題の読み替えは、のちで用いる変数の数や目的関数の表現をより簡便にする意味がある。 最適化問題の定式…
整数ナップサック問題のIsing表現ハミルトニアン：Knapsack with Integer Weights
文献情報 概要 組合せ最適化問題の類型のひとつにナップサック問題がある。これをIsing模型（変数が1 or -1）と等価な形式であるQUBO形式（変数が1 or 0）によって表現した。 ナップサック問題とは 導入 ナップサック問題にはいくつかの種類があるが、今回扱うのは以下のような形式の問題である。 いま、N個の荷物（荷物1、荷物2、・・・荷物N）をがあり、それぞれの荷物についてその荷物の「重さ」と「価値」が分かっているとする。これらの荷物をナップサックに詰め込んで運びたいが、ナップサックには容量があるので持っていく荷物の重さの合計はこの容量を越えてはならない。この条件の下、持っていく荷物の価値の合計を可能な限り大きくするにはどの荷物を持っていくのが良いか？ QUBO表現による定式化 適化変数: $x_{\alpha} \in \{0,1\}$ (荷物$\alpha$をナップサックに入れれば$1$,入れなければ$0$)補助変数: $y_n$ (自然数$m$を表すとき左から$m$番目の$y_m$が$1$,それ以外の全ての$y_{n (n\neq m)}$は$0$)目的関数: $$ \m…
交通渋滞緩和のための経路選択への応用 “Traffic Flow Optimization Using a Quantum Annealer” by Florian Neukart, et al. (2017).
文献情報 概要 交通渋滞を緩和するために複数台の車の経路選択を組合せ最適化問題として定式化し、これをD-Wave 2Xにより解いた。 方法 方針 古典: 現時点の位置から目的地までの経路を各車両ごとに3つ用意する量子: 各車両の取る経路を目的関数を最小化するように選択する 最適化問題の定式化 組合せ最適化問題の種類: 二値整数線型計画問題変数: $q_{ij} \in \{0, 1\}$ (車$i$が経路 $j \in {1, 2, 3}$を取れば$1$, そうでなければ$0$)目的関数: $$ \mathrm{Obj} = \sum_{s\in S} \left( \sum_i \sum_j \sum_{s \in S_{ij}} q_{ij} \right)^2 + \lambda \sum_i \left( \sum_j q_{ij} – 1 \right)^2 $$ 用いたデータセット 公開データセットのT-Drive trajectory datasetの中から、北京の街の中心と北京空港の間を行き来する418台の車のGPSデータを今回の問題の対象として抽出した。ま…