QUBO / MaxCut Explorer

小さな二値最適化問題を編集し、すべての割当・目的関数値・最適解をブラウザで確認するデモ。

English

例題を選ぶか、係数を直接編集してください。このアプリはすべての二値割当を評価します。選択中の解が大域最適解とどれくらい違うかを、最適化器をブラックボックスにせず確認できます。

これらのアプリは生成AIによって作成されています。

目的関数の規約

QUBOモードでは、上三角形式で与えた次の二次目的関数を最小化します。

f(x)=\sum_i Q_{ii}x_i+\sum_{i<j}Q_{ij}x_ix_j, \qquad x_i\in\{0,1\}.

x_i^2=x_i なので、対角成分は線形係数です。

重み付きMaxCutモードでは、次の目的関数を最大化します。

C(x)=\sum_{i<j}w_{ij}\mathbf{1}\{x_i\ne x_j\}.

\mathbf{1}\{x_i\ne x_j\} は、辺の両端が異なる側にあるとき 1、同じ側にあるとき 0 となる指示関数です。各ビットは頂点をカットのどちら側に置くかを表します。確認用に負の重みも入力でき、その場合は両端を同じ側に置く方向に働きます。

操作方法

グラフの頂点またはビットボタンを押すと、選択中の割当が変わります。QUBOでは値が有効になった二次項、MaxCutではカットされた辺を強調します。目的関数の図には、二進数順ですべての 2^n 個の値を表示します。棒または上位解の行を押すと、その割当を選択できます。最適解を選択を押すと、全列挙で得た大域最適解へ移動します。