集合被覆問題
行数 $m$，列数 $n$ の $0$-$1$ 行列 $A=[a_{ij}]$ と費用ベクトル $c =[c_j]$ が与えられたとき， 以下の問題を集合被覆問題(set covering problem)とよぶ．
$$ \begin{array}{l l l} minimize & \sum_{j=1}^n c_j x_j & \\ s.t. & \sum_{j=1}^n a_{ij} x_j \geq 1 & i=1, 2, \ldots, m \\ & x_j \in \{0,1\} & j=1, 2, \ldots, n \end{array} $$集合被覆問題は，可能なパターンを列挙して，パターンによって対象を被覆（カバー）するために使うことができる． 我々はすでに，以下の問題を集合被覆問題に帰着して解いた．
- クリーク被覆問題: 極大クリークを列挙してから，点もしくは枝をカバーするクリークを抽出する．
- 配送計画問題： 実行可能な（容量制約を満たす）ルートを列挙してから，すべての顧客を被覆するルートを抽出する． その後，2回以上訪問している顧客をルートから削除する．
- 空輸送最小化問題：Euler閉路をもつようにしてから，単純閉路を列挙し，最小費用の閉路を抽出する．
このアプローチは，他の様々な実際問題に適用可能である．特に，列挙するパターンに制約が多い場合に有効である．
動的最適化
すべての $j$ に対して $c_j = 1$ の場合を考え，動的最適化を適用する．
列 $j$ に対して $a_{ij}=1$ になっている行の集合を表す以下の集合 $S_j$ を導入する． $$ S_j =\{ i \in \{1, 2, \ldots, m\} | a_{ij}=1 \} \ \ \ j=1, 2, \ldots, n $$
制約の添え字 $i=1, 2, \ldots, m$ の部分集合 $C$ と変数の添え字を $k (\leq n)$ 番目までに制限した部分問題 （最適値を $f(k,C)$ と記す）を以下のように定義する．
$f(k,C)$ の値は，$k$ 番目の変数を $1$ にするか，$0$ にするかのいずれかであるので，以下の再帰方程式を得る．
$$ f(k,C) = \min \{ f(k-1,C), f(k-1,C \setminus S_k)+1 $$上の再帰方程式を初期条件 $f(0,\cdot)= \infty$，$f(\cdot,\emptyset)=0$ の下で解くことによって， 元の問題の最適値 $f(n,\{1, 2, \ldots, m\})$ を $O(n 2^m)$ 時間・空間で得ることができる．
def scpdp(m, n, S):
def f(k, Cover):
if len(Cover) == 0:
return 0, 0
if k < 0:
return 99999999.0, -1
FS = frozenset(Cover)
if (k, FS) in memo:
return memo[k, FS]
Cover0 = Cover.copy()
Cover1 = Cover0.difference(S[k])
if f(k - 1, Cover1)[0] + 1 < f(k - 1, Cover0)[0]:
min_value = f(k - 1, Cover1)[0] + 1
sol = 1
else:
min_value = f(k - 1, Cover0)[0]
sol = 0
memo[k, FS] = min_value, sol
return memo[k, FS]
memo = {}
C = set(range(m))
opt_val, sol = f(n - 1, C)
x = [0 for i in range(n)]
for k in range(n - 1, -1, -1):
value, sol = memo[k, frozenset(C)]
if sol == 1:
x[k] += 1
C = C.difference(S[k])
if len(C) == 0:
break
return opt_val, x
m = 16
n = 50
p = 0.1
random.seed(1)
elements = set(range(m))
S = {}
for i in range(n):
S[i] = set([])
if i < m:
S[i].add(i) # to be feasible
for e in elements:
if random.random() <= p:
S[i].add(e)
if len(S[i]) == 0:
S[i] = set([random.randint(0, m - 1)]) # to avoid empty set
print("S=", S)
opt_val, x = scpdp(m, n, S)
print("Optimal value=", opt_val)
print("Solution=", x)
cover = set([])
for idx,i in enumerate(x):
if i==1:
cover = cover|S[idx]
print(f"S[idx] = ",S[idx])
print("Covered=", cover)
メタヒューリスティクス
集合被覆問題に対して，以下のメタヒューリスティクスが提案されている．
M. Yagiura, M. Kishida and T. Ibaraki, A 3-Flip Neighborhood Local
Search for the Set Covering Problem, European Journal of Operational
Research, 172 (2006) 472-499このアルゴリズムは、3反転近傍と呼ばれる大きな近傍を用いた局所探索法に 基づくアルゴリズムである。 3反転近傍とは、現在の解から同時に3つの変数を反転させることによって得ら れる解集合であり、その大きさは $O(n^3)$ である。 大きな近傍を用いることによって解の精度の向上が期待できるが、近傍内の全 ての解を列挙して調べると計算時間が非常に大きくなる。 この隘路を解決するため、解の質を悪くすることなく効率的に近傍を探索する 工夫を行っている。
実行可能領域と実行不可能領域を交互に訪れるように探索を制御する戦略的振動を用いている． 実行不可能解をペナルティ関数によって評価しつつ、ペナルティ係数を探索状況に応じて適応的に調節することによって戦略的振動を実現している。
さらに、大規模な問題例にも対応できるように、Lagrange緩和問題から得 られる情報を用いて、変数 $x_j$ の一部を $0$ または $1$ に固定することにより問題 サイズの縮小を行っている。 なお、このとき固定する変数は状況に応じて繰り返し修正を行っている。
このメタヒューリスティクスをPythonから呼び出して使用する． このコード自体はオープンソースではないが，研究用なら筆者に連絡すれば利用可能である． 詳細は，付録1の OptCover を参照されたい．
集合被覆問題のベンチマーク問題例は，以下のサイトからダウンロードできる．
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
https://sites.google.com/site/shunjiumetani/benchmark
http://www.co.mi.i.nagoya-u.ac.jp/~yagiura/scp/
Pythonから呼び出すための関数を準備する．
folder = "../data/scp/"
file_name = folder + "scp510.txt"
# file_name = folder+"scpd5.txt"
# file_name = folder + "scp41.txt"
timelimit = 1
sol = scpmeta(file_name, timelimit)
print(sol)
f = open(file_name, "r")
data = f.readlines()
m, n = list(map(int, data[0].split()))
cost = {}
a = defaultdict(list)
data_ = []
for row in data[1:]:
data_.extend(list(map(int, row.split())))
count = 0
for j in range(1, n + 1):
cost[j] = data_[count]
count += 1
for i in range(m):
num_cols = data_[count]
count += 1
for j in range(num_cols):
a[i].append(data_[count])
count += 1
model = Model()
x = {}
for j in range(1, n + 1):
x[j] = model.addVar(vtype="B", obj=cost[j], name=f"x({j})")
model.update()
for i in range(m):
model.addConstr(quicksum(x[j] for j in a[i]) >= 1, name=f"Cover({i})")
model.optimize()
集合パッキング問題
行数 $m$，列数 $n$ の $0$-$1$ 行列 $A=[a_{ij}]$ と利得ベクトル $v =[v_j]$ が与えられたとき， 以下の問題を集合パッキング問題(set packing problem)とよぶ．
$$ \begin{array}{l l l} maximize & \sum_{j=1}^n v_j x_j & \\ s.t. & \sum_{j=1}^n a_{ij} x_j \leq 1 & i=1, 2, \ldots, m \\ & x_j \in \{0,1\} & j=1, 2, \ldots, n \end{array} $$集合被覆（分割，パッキング）問題は（巨大な問題例でなければ）商用の数理最適化ソルバーで比較的短時間で求解できる．