最小集合被覆問題
$U$ を全集合とし、${\cal F}={S_0, S_1, \ldots S_{m-1}}$ を $U$ の部分集合族とする。 部分族 $\cal S\subseteq \cal F$ が $U$ の全要素を被覆する場合、すなわち
\[\begin{aligned} \bigcup_{S_j\subseteq \cal S}S_j &= U. \end{aligned}\]最小集合被覆問題とは、最小の要素数を持つ集合被覆 $\cal S$ を求める問題である。 ここでは重み付きバージョンを考察する。各部分集合 $S_j$ に重み $w_j$ が与えられ、目標は最小の総重みを持つ集合被覆を見つけることである。
最小集合被覆問題のHUBO定式化
この問題をHUBO問題として定式化する。 $U={0,1,\ldots, n-}$とし、$m$個の集合 $S_0, S_1, \ldots, S_{m-1}$ が与えられる。 $m$ 個の二値変数 $x_0, x_1, \ldots, x_{m-1}$ を導入する。 ここで $x_j=1$ となるのは $S_j\in\cal S$ である場合に限る。
各要素 $i\in U$ について、以下の式を定義する：
\[\begin{aligned} c_i &=\prod_{j: i\in S_j}(1-x_j) && (0\leq i\leq n-1) \end{aligned}\]選択された部分集合のいずれも $i$ を含まない場合、$i$ は被覆されない。 この場合、$i\in S_j$ を満たすすべての $j$ に対して $x_j=0$ が成り立つため、 $c_i=1$ となる。 一方、少なくとも1つの選択された部分集合が$i$を含む場合、$i\in S$を満たすある$j$に対して$x_j=1$となり、項$(1−x_j)$は0となるため、$c_i=1$となる。 したがって、以下のペナルティ項は、すべての要素がカバーされた場合にのみ0となる：
\[\begin{aligned} \text{制約条件} &=\sum_{i=0}^{n-1}c_i \end{aligned}\]目的は、選択された部分集合の総重量を最小化することである：
\[\begin{aligned} \text{目的関数} &=\sum_{j=0}^{m-1}w_jx_j \end{aligned}\]これで、重み付き最小集合被覆問題に対するHUBO目的関数を次のように構築できる：
\[\begin{aligned} f &= \text{目的関数}+P\times\text{制約条件}, \end{aligned}\]ここで $P$ は、目的関数よりも実現可能性を優先させるのに十分な大きさの正の定数である。
最小集合被覆問題のためのQUBO++プログラム
以下のQUBO++プログラムは、要素数$n=10$、部分集合数$m=8$の重み付き最小集合被覆インスタンスに対するHUBO式を構築する：
#include <set>
#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"
int main() {
const size_t n = 10;
qbpp::Vector<qbpp::Vector<size_t>> cover = {
{0, 1, 2}, {2, 3, 4}, {4, 5, 6}, {6, 7, 8},
{9, 0, 1}, {1, 3, 5, 7, 9}, {0, 3, 6, 9}, {1, 4, 7, 8}};
qbpp::Vector cost = {3, 4, 3, 2, 3, 4, 3, 3};
auto m = cover.size();
auto x = qbpp::var("x", m);
auto c = qbpp::expr(n);
for (size_t j = 0; j < n; ++j) {
c[j] = 1;
}
for (size_t i = 0; i < m; ++i) {
for (size_t j : cover[i]) {
c[j] *= (1 - x[i]);
}
}
auto objective = qbpp::sum(cost * x);
auto constraint = qbpp::sum(c);
auto f = objective + 1000 * constraint;
f.simplify_as_binary();
auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
auto sol = solver.search();
std::cout << "objective = " << objective(sol) << std::endl;
std::cout << "constraint = " << constraint(sol) << std::endl;
for (size_t i = 0; i < m; ++i) {
if (sol(x[i]) == 1) {
std::cout << "Set " << i << ": " << cover[i] << " cost = " << cost[i]
<< std::endl;
}
}
}
このプログラムは、 x $m=8$ 個の二値変数のベクトルを定義し、 c $n=10$ 個の式からなるベクトルを構築する。
各式 c[j] は要素 $j\in U$ に対応し、初期値は 1 です。
各部分集合 $S_i$ および各要素 $j\in S_i$ について、 c[j] を
(1 − x[i])を乗算する。
その結果、 c[j] 少なくとも1つの選択された部分集合が要素 jをカバーする場合に限り0となり、それ以外の場合は1のままとなる。
ペナルティ項の制約は、 cの全要素の和として定義され、全ての要素がカバーされた場合にのみ0となる。
重み付き objective は cost と xの内積として定義される。
これらは HUBO 式に統合される
定数1000は実現可能性を優先させるため十分に大きく設定される。
その後、完全探索ソルバーを用いて最適解を求めます sol。
プログラムは次の値を出力する objective と constraintの値を出力し、最後に選択された全部分集合を列挙する。例えば出力は次の通り：
objective = 11
constraint = 0
Set 0: {0,1,2} cost = 3
Set 2: {4,5,6} cost = 3
Set 3: {6,7,8} cost = 2
Set 6: {0,3,6,9} cost = 3
この出力は、総コスト11の実現可能な集合被覆が得られたことを示している。
最小集合被覆問題に対するQUBO定式化
上記のHUBO定式化には3次以上の項が含まれる可能性があるため、必ずしもQUBO表現とは限りません。 QUBO定式化を得るために、被覆制約を再記述します。
各要素 $i\in U$ について、以下を定義する
\[\begin{aligned} c_i &=\sum{j: i\in S_j} x_j && (0\leq i\leq n-1) \end{aligned}\]$c_i\geq 1$ ならば、少なくとも1つの選択された部分集合 $S_j$ が $i$ をカバーしている $c_i=0$ ならば、選択された部分集合は $i$ をカバーしていない したがって、カバー制約を QUBO++ 形式で次のように表現できる：
\[\begin{aligned} \text{制約} &= \sum_{i=0}^{n-1} (c_i\geq 1) \end{aligned}\]この制約は、全要素がカバーされた場合にのみ最小値0を取る。 この定式化に基づき、QUBO++プログラムは以下のように修正できる：
auto c = qbpp::expr(n);
for (size_t i = 0; i < m; ++i) {
for (size_t j : cover[i]) {
c[j] += x[i];
}
}
auto constraint = qbpp::sum(1 <= c <= +qbpp::inf);
このプログラムでは、式 1 <= c[j] <= +qbpp::inf は全ての
jに対して生成され、それらの和が制約変数constraintに格納される。
備考。 項
1 <= c[j] <= +qbpp::infは内部的に補助的な二値変数 を導入する可能性がある。その結果、最終的な式はQUBOソルバーで処理可能となり、 カバレッジ制約の意図した意味を保持したままとなる。
この修正により、本プログラムはHUBO版と同等の最適解を生成する。