最大同時多品種フロー問題の効率的アルゴリズ厶
学籍番号 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
∑P:a ∈ P x(P)≦ u(a) ∀a ∈ A
∑P: ∈ 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.