Document

均等多品種フローの
最大化アルゴリズムにおける
効率の実際的改善
2003年9月25日コンピュテーション研究会
中央大学大学院理工学研究科情報工学専攻
二瓶浩一
浅野孝夫
均等多品種フローの最大化問題
(Maximum Concurrent Flow Problem)
需要: 1
1/2
1
1/2
需要: 1
均等多品種フローの最大化問題
(Maximum Concurrent Flow Problem)
需要: 2
2/5
1
3/5
需要: 3
発表の流れ






問題定義
研究概要
従来手法
提案手法
計算機実験
まとめと今後の課題
問題定義

入力

グラフ

辺の容量
品種




始点
終点
需要
問題定義

目的


全品種のフローの合計が辺容量を超えない．
正の実数に対して，すべての品種で
となる．
これらの条件を満たす最大の
を求めること．
問題定義
言いかえると，目的は
である．
ただし
とする．
問題の難しさ
線形計画問題として定式化可能
多項式時間で最適解が求まる
インスタンス
s2
5
6
s1
4
3
4
t2
5
4
4
6
t1
LP定式化
最適解
問題の難しさ
線形計画問題として定式化可能
多項式時間で最適解が求まる
実際には非常に長い計算時間が必要
近似アルゴリズムの研究が行われている
これまでの研究
Shahrokhi and 辺容量がすべて1の場合の
1990
Matura
FPTAS
任意容量の場合のFPTAS
1995 Leighton et al.
（ランダム化アルゴリズム）
1995 Radzik
任意容量の場合のFPTAS
（決定性アルゴリズム）
2002 Karakostas
任意容量の場合のFPTAS
（最新手法）
FPTAS
誤差パラメータに対して，


近似率：
計算時間：
と
の多項式時間
のアルゴリズムをFPTAS （Fully Polynomial
Time Approximation Scheme）という．
研究概要
Karakostasのアルゴリズムは最適解が大き
くなるほど，計算時間が増加する．
計算時間が最適解の大きさに依存しない
手法の提案．
Karakostasのアルゴリズム
誤差パラメータに対して，
 近似率：
 計算時間：
のアルゴリズム．
Karakostasのアルゴリズム
s2
5
6
s1
4
3
4
t2
5
4
4
6
t1
Karakostasのアルゴリズム

各辺の容量を長さに変換する．
を計算し，辺の長さ
とする（この例では
を
）．
Karakostasのアルゴリズム
2.75
s2
2.7
1
3.46
2.25
s1
3.38
辺eを通るフローの合計
4.5
3.38
t2
2.7
3.38
3.38
2
3.55
2.25
2.32
t1
長さ：
Karakostasのアルゴリズム
となったら反復終了．

反復前：
反復後：

このとき，各辺のフローは容量を超えている
ため，スケール・ダウンする．
倍
Karakostasのアルゴリズムの欠点


最適解が大きいインスタンスほど計算時間
が増加する．
最適解が1未満のインスタンスに対しては，
近似保証が成立しない．
最適解が小さくなるようにインスタンスを変
換し，Karakostasのアルゴリズムで解く．
インスタンスの変換
s2
5
6
s1
4
3
4
最適解は2となる
t2
5
4
4
6
t1
提案手法
すべての品種の需要をα倍すると，最適解
が1/αになることが示せる．
1.
2.
3.
別のアルゴリズムで実行可能解を求め，そ
れをαとして，インスタンスを変換する．
変換したインスタンスをKarakostasのアル
ゴリズムで解く．
得られた解をα倍して出力する．
提案手法
を求めるアルゴリズム


アルゴリズムMF
各品種の最大フローを求め，フローが辺容量以
下になるようする．

アルゴリズムIMF
アルゴリズムMFを反復させる．
アルゴリズムMF
s2
5
6
s1
4
3
4
t2
5
4
4
6
t1
アルゴリズムMF
s2
(3 5) 5
(6 0) 6
(0 4) 4
(1 3) 4
s1
t2
(3 3) 3
(4 4) 5
(4 0) 4
(0 4) 4
(6 0) 6
t1
(品種1 品種2) 容量
アルゴリズムMF
s2
(3 5) 5
(6 0) 6
(0 4) 4
(1 3) 4
s1
t2
(3 3) 3
(4 4) 5
(4 0) 4
(0 4) 4
(6 0) 6
t1
(品種1 品種2) 容量
品種2を5/8倍
アルゴリズムMF
s2
(6 0) 6
s1
(3 25/8) 5
(0 5/2) 4
(1 15/8) 4
(3 15/8) 3
t2
(4 5/2) 5
(4 0) 4
(0 5/2) 4
(6 0) 6
t1
(品種1 品種2) 容量
緑の辺で容量の
1.625倍のフロー
すべてのフローを
1/1.625倍する
アルゴリズムIMF

残余容量グラフ
s2
1.23
2.31
s1
2.46
2.23
t2
1
2.46
1.54
2.31
3.07＋0.69
t1
3.76
アルゴリズムIMF

残余容量グラフ
s2
1.77
s1
1.77
2.23
t2
0.46
2.46
0.71
1.48
品種2にパス
が存在しない
t1
反復終了
解析（近似率）
アルゴリズムMFとアルゴリズムIMFは近似
保証
を達成する．

アルゴリズムMF：解析はタイト

アルゴリズムIMF：タイトでない？
解析（計算時間）

アルゴリズムMF：

アルゴリズムIMF：
は，最大フローの計算時間を表す．
アルゴリズムMFとIMFの比較

辺の密度を変化させたとき



辺の密度が増加すると反復数が増加する．
（点数：10，品種数：10のとき，辺数90で反復数
は7回程度）
計算時間は，反復数に依存する．
得られる解についても同様．
（点数：10，品種数：10のとき，辺数90で1.6倍）
アルゴリズムMFとIMFの比較

品種数を変化させたとき



反復数はほとんど変化しない．
（点数：10，辺数：45の場合，3回程度）
計算時間も同様．
（点数：10，辺数：45の場合，3倍程度）
得られる解もほとんど変化しない．
（反復した場合，平均して1.3倍程度）
アルゴリズムIMF

点数： 45，辺数： 1000，品種数： 100，ε： 0.1
平均
アルゴリズムIMFの計算時間 [s]
Karakostasのアルゴリズムの
計算時間 [s]
Karakostasのアルゴリズムの解が
1になるときの提案手法の解
1.199
74.475
0.589
インスタンスの変換
s2
6
s1
5
4
3
λ＝
1.02
3.76
×
4
t
5
＝3.84
2
4
4
6
t1
提案手法

は実行可能解なので，すべての品種の需
要を倍したインスタンスの最適解は1以上
になる．

が最適解に近ければ，Karakostasのアル
ゴリズムを実行するのに必要な計算時間が
大きく減少する．
計算機実験

実験内容




辺数と品種数の変化
誤差パラメータの変化
グラフの規模の変化
マシンスペック


CPU： Intel Pentium4 2.4 GHz
メモリ： 512 MB
計算機実験
各インスタンスについて，
方法1： Karakostasのアルゴリズムをそのまま実行．
方法2：アルゴリズムMFでαを求め，Karakostasのア
ルゴリズムを実行．
方法3：アルゴリズムIMFでαを求め，Karakostasの
アルゴリズムを実行．
を比較した．
計算機実験

ランダムに生成したインスタンスに対して，す
べての品種の需要を変化させ，解が
1, 2, 4, 8,…, 256, 512
となるようにして，方法1, 2, 3を実行した．

同一条件で20個のインスタンスを生成して，
実験を行った．
計算機実験
90
方法1
方法2
方法3
80
計算時間 [s]
70
60
50
40
30
20
10
0
1
10
100
1000
解λ
点数: 20, 辺数: 95, 品種数: 285, ε: 0.1のときの結果の一例
辺数，品種数の変化
点数
辺数
品種数
ε
20
95
95
0.1
20
95
285
0.1
20
285
95
0.1
20
285
285
0.1
8
6
辺数, 品種数
10
285, 285
285, 95
95, 285
95, 95
285, 285
285, 95
95, 285
95, 95
辺数，品種数の変化
12
最小値
平均値
最大値
良
4
2
0
誤差パラメータの変化
点数
辺数
品種数
ε
20
190
190
0.05
20
190
190
0.1
20
190
190
0.2
誤差パラメータの変化
9
最小値
平均値
最大値
8
7
6
良
5
4
3
2
1
0
0.05
0.1
0.2
0.05
0.1
0.2
ε
規模の変化
点数
辺数
品種数
ε
10
45
45
0.1
20
190
190
0.1
30
435
435
0.1
規模の変化
18
最小値
平均値
最大値
16
14
12
良
10
8
6
4
2
0
10
20
30
10
20
30
点数
考察



すべての場合で，
より
の方が小さ
い値になった．
解が非常に小さい場合には，Karakostasの
アルゴリズムの方が短い計算時間で解が求
まった．
提案手法は，解の大きさによらず，常に一定
の計算時間で解が求まった．
まとめ

Karakostasのアルゴリズムをもとにして，計
算時間を改善した．

解が非常に小さいときには，Karakostasの
アルゴリズムの方が短い計算時間である
が，提案手法は解の大きさによらず計算時
間が一定なので，有用であるといえる．
今後の課題


を求めるアルゴリズムの改善．
計算時間の理論的な短縮．

Download Report