使い方
- グラフを描く: 盤の空いたところをクリックすると頂点を置けます。 2 つの頂点を続けてクリックすると、その間の辺を追加または削除します。 頂点はドラッグで動かせ、右クリックで削除できます（頂点は最大 32）。
- 自動で作る: +NODE でランダムに頂点を加えます。 テンプレート（Delaunay、単位円グラフ、正則グラフ、完全グラフ）を選んで Generate を押すと、今ある頂点の間に辺を張ります。 Cycle・Grid・Hypercube・BinTree はグラフ全体を置き換えます。Spread は頂点どうしの間隔を広げます。
- 問題を選ぶ: 色数・k・p・パスの本数などのパラメータを取る問題もあります。 s–t の問題では、Shift クリックで s を、Ctrl クリックで t を指定します。 シュタイナー木では Shift クリックで端点を切り替え、最短路木では Shift クリックで根を指定します。
- Solve を押すと探索が始まります。公開版のデモでは探索は最長 10 秒で打ち切られ、 下の表で印のある問題ではそれより早く止まります。 ソルバーが解を改善するたびに表示が更新されます。
- 盤の下には、0/1 変数と、解いた QUBO（または HUBO）の式が表示されます。
このデモは資源の限られた AWS Lambda 上で動いています。 デスクトップ PC 上の QUBO++ は数倍速く動きます。
22 の問題
| 問題 | 求めるもの | 早く止まる | 解説 |
|---|---|---|---|
| 最大独立集合 | 互いに辺で結ばれていない頂点の、最大の集合 | 最大独立集合 | |
| 最小頂点被覆 | すべての辺に接する頂点の、最小の集合 | 頂点被覆 | |
| 最大クリーク | どの 2 頂点も辺で結ばれている頂点の、最大の集合 | クリーク | |
| 最小支配集合 | どの頂点も集合に入るか集合の頂点と隣り合う、最小の集合 | 支配集合 | |
| 最密 k 部分グラフ | 間の辺が最も多い $k$ 頂点 | ||
| 最大多様性 | 互いの距離の和が最大の $k$ 点（辺は不要） | 最適値 * | |
| 最大マッチング | 頂点を共有しない辺の、最大の集合 | 完全マッチング | マッチング |
| 最小極大マッチング | それ以上辺を足せないマッチングのうち最小のもの | 極大マッチング | |
| シュタイナー木 | 端点をすべてつなぐ、長さ最小の辺の集合 | 最適値 | |
| 最大カット | 2 つのグループの間の辺が最も多い分け方 | 最大カット | |
| 最小二分割 | 同じ大きさの 2 つに分け、間の辺を最も少なくする分け方 | 二分割 | |
| 最小 s–t カット | 取り除くと s と t が分かれる、最少の辺 | 最適値 | |
| クリーク分割 | 各グループがクリークで、グループ内の辺が最も多い分け方 | ||
| p-メディアン | 各頂点から最寄りの施設までの距離の和が最小になる $p$ 施設 | 最適値 | |
| ハミルトン路 | すべての頂点を 1 回ずつ通る路 | 見つかった時点 | |
| ハミルトン閉路 | すべての頂点を 1 回ずつ通る閉路 | 見つかった時点 | |
| 最短路（s→t） | s から t への最短路 | 最適値 | |
| k 本の辺素なパス（s→t） | 辺を共有しない s から t への $k$ 本のパスで、長さの和が最小のもの | 最適値 | |
| 最短路木 | 根からすべての頂点への最短路 | 最適値 | |
| 巡回セールスマン | すべての頂点を回る最短の巡回路 | TSP | |
| 頂点彩色 | 隣り合う頂点が同じ色にならない塗り分け | 見つかった時点 | グラフ彩色 |
| 辺彩色 | 同じ頂点に接する辺が同じ色にならない塗り分け | 見つかった時点 | 辺彩色 |
「最適値」: サーバーが厳密なアルゴリズム（ダイクストラ法、最大流、最小費用流、動的計画法、列挙）で最適値を求め、 探索がその値に達した時点で止まります （* 最大多様性は、$k$ 点の選び方が $2\times 10^6$ 通り以下のときだけ）。 「見つかった時点」: 条件を満たす解が見つかった時点で止まります。 「完全マッチング」: すべての頂点を覆うマッチングが見つかれば、その時点で止まります。 それ以外の問題は制限時間まで探索します。
グラフ問題を QUBO にする
QUBO（Quadratic Unconstrained Binary Optimization、制約なし二次二値最適化）は、 2 次以下の多項式を最小にする 0/1 の変数の値を求める問題です。 量子アニーリングやイジングマシンが扱う問題の形式で、QUBO++ はこれを通常の CPU や GPU で解きます。
どの問題も、選ぶものごとにバイナリ変数を使います。 頂点ごと（選ぶか）、辺ごと、あるいは頂点と色の組ごとです。 たとえば最大独立集合では、頂点 $v$ を選ぶとき $x_v=1$ として、次の式を最小にします。
\[-\sum_{v} x_v \;+\; 2\sum_{(u,v)\in E} x_u x_v\]2 つめの和は、辺の両端を両方選んだときのペナルティです。
最小支配集合の「どの頂点も支配される」という条件 $x_v + \sum_{u \in N(v)} x_u \ge 1$ のような制約は、
QUBO++ の cons() で書きます。ソルバーは補助変数（スラック変数）を使わずに、これを直接扱います。
どの問題も、QUBO++ の ABS3 ソルバーが CPU 上で解きます。
表の解説ページに、定式化と QUBO++ のプログラムが詳しく説明されています。
自分のコンピュータで動かす
QUBO++ の Python 版である PyQBPP は、Linux（x86-64・ARM64）と、WSL 経由の Windows で動きます。
pip install pyqbpp