ネットワーク上の被覆型施設配置問題について
藤重研究室 新 浩治
1.序論
施設を設置する際に，その最適な位置を求める問題を施設配置問題という．
各点の要求に対して複数個の施設からフローを供給するネットワークに
関して，最小の施設数で各点の要求容量を満足する配置を求める
総合被覆型施設配置問題(総合被覆問題)を解く,多項式時間の
アルゴリズムが,田村,菅原,仙石,篠田 [1] によって提案されている．
本論文では，このアルゴリズムの正当性について，数理計画法に基づいた
別証明を与える．さらに施設の設置費用を考慮した最小費用総合被覆
問題を提起する．
2.総合被覆問題
点集合V,枝集合Eからなる無向ネットワーク N=(V,E,c,h)を考える．
ここで，cは各枝 e in E の枝容量 c(e)を表す非負整数値関数であり，hは
各点 v in V の要求容量 h(v)を表す非負整数値関数である．
点集合 Xから点 vへの最大フロー値をf(X,v)と表す．点集合Vの空でない
真部分集合をカットと呼び，カットWについて，g(W)=sum c(u,v)(u in W,v in V-W)を
Wのカット容量と呼ぶ．U subseteq V が任意の v in Vに対して f(U,v) geq
h(v) となるとき， Uは Nの h-総合被覆であるという．
総合被覆のうちで要素数最小なものを求める問題である総合被覆問題は，
W subseteq Vが W=V であるか，または
g(W) < max{h(v) | v in W}
であるとき，Wを未充足集合と呼ぶ．未充足集合で，真部分集合として
未充足集合を含まないものを極小な未充足集合という．
また，W subseteq V に対して，
h(W) = max{h(v) | v in W}
と定義する．h(v)=h(W)となる点 v in W を Wの要求容量最大点という．
田村,菅原,仙石,篠田[1]によるアルゴリズムは以下の通りである．
Step 1 V = {v_1, ... ,v_n}を h(v_1) leq ... leq h(v_n)
となるように並べる．U := V, j: = 1 とする．
Step 2 U-{v_j} が Nを総合被覆するならば，
U := U-{v_j}.
Step 3 j=nのとき Uを出力して終了．
そうでなければ j := j+1 として Step 2へ．
3.正当性の証明
極小未充足集合を W_1, ... ,W_m と表す．行列 A = (a_{ij})を，
a_{ij}= 1 (v_j in W_i)
0 (v_j notin W_i)
によって定める．また，x_j=0,1であり，v_jが解であるとき x_j=1とする．
無向フローネットワークの性質より，以下の補題が成り立つ．
補題1 次のような部分行列が存在しない．
j k(i_2) k(i_1)
j
j
k()は行 i の最も右の非零列を表す．
総合被覆問題を整数計画法を用いて定式化する．
Min . sum_j=1^n x_j
s. t . sum_j=1^n a_{ij}x_j geq 1 (i=1, ... ,m)
x_j=0,1 (j=1, ... ,n)
緩和問題
Min . sum_j=1^n x_j
s. t . sum_j=1^n a_{ij}x_j geq 1 (i=1, ... ,m)
x_j geq 0 (j=1, ... ,n).
とその双対問題
Max . sum_i=1^m y_i
s. t . sum_i=1^m a_{ij}y_i geq 1 (j=1, ... ,m)
y_i=0,1 (i=1, ... ,m)
を考える．
相補性条件は以下の通りである．
(i) x_j neq 0 であるような j について
sum_i=1^m a_{ij}y_i =1 .
(ii) 1< sum_i=1^n a_{ij}x_j であるような j について
y_i=0 .
相補性条件(i),(ii)を満たすよう，アルゴリズムの実行中に y
を適当な(0,1)-ベクトルに定めることができる．
次の yの実行可能条件が成立することを示す．
sum_{i=1}^m a_{ij}y_i leq 1 (j=1, ... ,n)
y_i geq 0 (i=1, ... ,n).
v_jに対応する x_j =0 であり，かつその点を共有する Wが2つ存在する
(それらを$W_1,W_2$ とする)．このとき W_1,W_2に対応する y_1,y_2が
おのおの1であるということを仮定する．
この仮定のもとでは，W_1,W_2について，お互い異なる要求容量最大点を
持ち，かつその一方の最大値を，他方が共有していないということが言える．
しかし，そのような事態は補題1 より矛盾する．
つまり a ... y_1 =1 のときは，必ず a ... y_2 =0 となり，
a ... y_1 =0 のときは，必ず a ... y_2 =1 となっていることがわかる．
このどちらの場合も和は１である．よって x_j =0 においても，制約条件
は成り立つ．
以上より，アルゴリズム終了時の x は緩和問題における最適解である．
この解は 0,1 であるので，元の問題の制約条件をも満たす．
したがって元の問題の最適解となり，アルゴリズムの正当性が証明できた．
参考文献
[1]田村,菅原,仙石,篠田：無向フローネットワークにおける総合被覆問題
について, 電子情報通信学会論文誌,J81-A(1998),863-869.