最大同時多品種フロー問題の効率的アルゴリズ厶

学籍番号 90190003 藤重研究室 荒井崇行

1 序論

Garg--K"onemann[2]は最大同時多品種フロー問題に対して

任意のパラメタε＞０に対して最適解の

1-3ε倍以上の解をO*(1/(e^{2}m(k+m))+kM(n,m)

時間で求める事ができるアルゴリズムを提案した．但しkは品種数で

M(n,m)はn点m本のネットワーク上の最大フローを求めるのに必要な時間で

あり，O*(f)はO(flog^{O(1)}m)

を表すものとする．続いてFleischer[1]がこれに

改良を加え，O*(1/(e^{2}m(k+m)))時間で

近似解を得るアルゴリズムを提案した．さらに

Karakostas[3]が改良を加え，O(1/(e^{2}m^{2}))

時間で近似解を求めるアルゴリズムを提案した．本研究では計算機実験によって

[1,2]と [3]のアルゴリズムを比較する．また，独自の改良を加え，

近似精度の向上をはかる．

2 問題の定式化

最大同時多品種フロー問題は有向グラフG=(V,A)上で

定義される. 各枝a∈Aは正の容量 u(a)を持つ．品種の集合を Cとし，|C|=kと

する．

各品種j ∈ Cはソースとシンクのペア (sj,tj)と需要djを

持ち，問題の目的は，容量条件を満たし，全品種の需要のλ 倍を

同時に供給することができる最大のλとそのときのフローを求めるこ

とである．この問題は，以下の形で記述できる．

Maximize　λ

subject to

�捻:a ∈ P x(P)≦ u(a) ∀a ∈ A

�捻: ∈ P*j x(P) ≧ λ d(j) ∀j ∈ C

x(P)≧0 ∀P ∈ P*

ここで，ソース s_{j}からシンクtjまでのパスの集合を

P*j(1≦ j≦ k)とし，P*:=Uj ,P*jとする．

また，変数x(P)はパスPに沿って流すフローの合計を表す．

3 最大同時多品種フローのアルゴリズム

文献[2]のアルゴリズムの中心部分は,

枝長に相当する双対変数lを参照しながら最短路を用いてフローを少しずつ

割り当てるというもので,次で記述できる

initialize ∀a∈ A: l(a)=δ,x(a)= 0

for h=1to mlog1+ε(1+ε)/δ (Phase)

P={argmin}P∈P*l(P)

if l(P)<1

u=mina∈ P u(a)

∀a∈ P:x(a)=x(a)+u

∀a∈ P:l(a)=l(a)(1+ε/u)(u(a))

end if

end for

∀a∈ A:x(a)=x(a)/log1+ε(1+ε)/δ

End

R_+，R_{++}はそれぞれ非負実数，正実数全体の集合を表す．

文献[3] のアイデアは, 品種ごとに計算していた最短路の計算を,

始点を同じくする品種全てで利用してしまうというものである.

そのため，kがnと比べて大きい場合に，計算時間の

短縮を図ることができる．

4 諸アルゴリズムの計算機実験による比較

前述した２つのアルゴリズムの性能を調べた．

100点からなる問題例について

枝500本，1000本，品種数100，1000，5000のそれぞれのネットワークを10例ずつ

作成し各アルゴリズムの解が求まるまでの計算時間と，CPLEXによる厳密解と比べた近似精度の視点から両者を比較した．ε = 0.1を用いた．

その結果，[1,2]のアルゴリズムでは品種数の増大に伴って

実行時間が線形的に増加したのに対し，[3]のアルゴリズムでは実行時間が品種数に

依存しないことが確認された．

5 結論

実験によって全ての事例について厳密解に対する近似率 > 0.99以上を確認する

ことができた．また，計算時間については，問題の規模が小さい場合はCPLEXと

ほぼ同じであったが，品種数が増加するにつれて，[3]のアルゴリズムの優位

性を確認することができた．

参考文献

[1]

L. K. Fleischer: Approximating fractional multicommodity flows

independent of the number of commodities, SIAM Journal on Discrete

Mathematics (2000), pp. 505--520.

[2]

N. Garg and J. K"onemann: Faster and simpler algorithms for

multicommodity flow and other fractional packing problems. in

Proceedings of the 39th FOCS

(1998), pp. 300--309.

[3]

G. Karakostas: Faster approximation schemes for fractional

multicommodity flow problems. in Proceedings of the 13th

SODA (2002), pp. 166--173.