QUBO 問題のワークフロー
メモ
インストールが必要: この機能には、MATLAB Support Package for Quantum Computing が必要です。
2 次制約なしバイナリ最適化 (QUBO) 問題は、バイナリ変数における 2 次最適化問題です。背景情報については、QUBO 問題とはを参照してください。
QUBO 問題を解くには、まず問題を QUBO に変換し、その後タブー探索アルゴリズムを使用して解く必要があります。
問題の QUBO への変換
solve 関数は、QUBO 形式で表現された問題を解きます。N 個のコンポーネントをもつバイナリ変数 x(i) に対して、QUBO 目的関数は次の形式になります。
問題を QUBO として表現するには、実数の N 行 N 列の行列 Q、オプションの N ベクトル c、およびオプションのスカラー d を作成します。次のように QUBO 問題を作成します。
qprob = qubo(Q,c,d); % Or qprob = qubo(Q) or qprob = qubo(Q,c)QUBO 形式とイジング形式の相互変換方法を含む詳細については、QUBO 問題とはを参照してください。
一部の問題では、制約を QUBO 目的関数内のペナルティ項として表現します。Constraints in QUBO Problemsを参照してください。
タブー探索を使用した問題の求解
QUBO に対して solve を呼び出し、タブー探索アルゴリズムを使用して解を求めます。solve の構文は、次のようになります。
result = solve(qprob)
タブー探索は確率的アルゴリズムであるため、アルゴリズムを実行するたびに異なる結果が得られる場合があります。ペナルティ項を使用して問題に制約を追加し、最初に得られた解が実行不可能な場合は、solve を再実行することで実行可能解を探索できます。
タブー探索用のプロパティを含むタブー探索アルゴリズム オブジェクトを作成することで、solve のいくつかの側面を制御できます。指定したプロパティをもつタブー探索オブジェクトを solve に渡します。たとえば、solve に既定値より多くの時間と反復回数を使用させるには、次を入力します。
ts = tabuSearch(MaxTime=60,MaxIterations=1e7); result = solve(qprob,Algorithm=ts)
プロパティおよびその既定値の詳細については、tabuSearchを参照してください。
問題にペナルティ項として表現された制約が含まれている場合、一部の結果は制約に違反する可能性があります。Examine Solutions for Feasibilityを参照してください。
Optimization Toolbox を使用した単純な問題の代替解決法
QUBO 問題の変数の数が少数 (最大で 100 ～ 200 程度) であり、かつ Optimization Toolbox™ ライセンスを所有している場合は、QUBO を混合整数線形問題へ変換し、intlinprog を使用して解きます。intlinprog を使用する利点は、得られる解が最適であることが保証される点です。欠点としては、問題のサイズに制限があり、ソルバーの完了までに長時間かかる場合がある点です。詳細については、Verify Optimality by Solving QUBO as MILPを参照してください。
参考
関数
オブジェクト
qubo|tabuSearch|qaoa
