層族制約つき資源配分問題への応用

第4.4.3節で提案した連続緩和法RELAXを，層族制約つき資源配分問題(Laminar) に適

用する．特に，目的関数が2次関数の場合の計算時間についての定理4.29を証明する．以下

では，(Laminar)がツリーネットワーク上の凸費用流問題として定式化されているものとする

（凸費用流の定式化については第4.1節を参照のこと）．層族F を表現するツリーネットワー クにおいては，任意のX∈ F ^に対してXの子をO(k)の計算時間で見つけることができる．

ただしkはX の子の数である．さらに，X ̸=N であればXの親をO(1)の計算時間で求め られる．(Laminar)の目的関数に用いられる各関数fX (X ∈ F) の評価が定数時間でできるこ とを仮定する．

まず，2次の目的関数をもつ(Laminar)の最適解x_∗∈Rⁿを求める方法を述べる．この問題 はツリーネットワーク上の2次凸費用実数値フロー問題と等価であるので，Tamirのアルゴリ ズム[90]でO(n²)の計算時間で解くことができる．ゆえに，Step 1のアルゴリズムRELAX は，目的関数が2次であれば，O(n²)の計算時間で行える．

次に，(Laminar)の最適解x_∗ ∈Rⁿを，どのようにして(Laminar)の実行可能解に丸める のかを述べる．ここでは，ネットワークフローの技巧を用いる．不等式ℓY ≤ x(Y) ≤ uY

(Y ∈ F)を定義する係数行列は完全ユニモジュラであるので，ある整数ベクトルy∈Z^nが存 在して，任意のY ∈ F ^に対して

(ℓY ≤) ⌊x_∗(Y)⌋ ≤y(Y)≤ ⌈x_∗(Y)⌉ (≤uY) (4.7) を満たし（[2, 84]などを参照）、従ってyが(Laminar)の実行可能解であることがわかる．ま

表4.3.離散凸最適化問題の計算量

問題クラス 近接定理の距離 目的関数が2次の場合の計算量

L_∞ L1 連続緩和 全体

(MC) n−1 (定理4.21)

—

n(n−1) (系4.22)

—

∗¹

—

∗¹ (定理4.23)

∗¹ [88]

(SC) ^↑

O(n2ⁿ) [31]

2(n−1) (定理4.27)

— ^{↑ ↑}

(Network) ^↑

n[31] ^↑

—

∗² [30]

∗² (定理4.31)

∗³ (系4.26) (Laminar) ↑ 2(n−1) (定理4.28)

—

— O(n²) [90]

O(n²) (定理4.29) O(n³) [90]

(Tree) ↑ ↑ —

O(nlogn) [30]

↑

∗⁴ (系4.26)

(Nest) ↑ ↑ —

O(nlogn) [30]

↑

∗⁴ (系4.26)

(GUB) ↑ ↑

↓[29]

—

↓[29]

—

↓[29]

(Simple) ↑ ↑

O(n) [98]

— O(n) [7]

— O(n) [33]

∗¹: O((n⁵+n⁴log(K_∞/n))(log(K_∞/n)/logn))

∗²: O(|V∥A|log(|V|²/|A|))

∗³: O(n²|A|+|V∥A|log(|V|²/|A|))

∗⁴: O(n²logn)

上段：本章による   下段：先行研究による

—：成果なし   

↑：上の欄に同じ 

↓：下の欄に同じ  網掛：本章による改善 た、任意のi∈N について{i} ∈ Fであるので，条件(4.7)から∥y−x_∗∥1< nを満たす。

式(4.7)を満たす整数ベクトルy ∈ Zⁿは，以下のようにすると O(n)の計算時間で求ま

る．各Y ∈ F についてℓ^′_Y =⌊x_∗(Y)⌋ かつu^′_Y =⌈x_∗(Y)⌉とする．任意のY ∈ F に対して ℓ^′_Y ≤y(Y)≤u^′_Y を満たすベクトルy∈Z^{nを求めるために，条件}

ℓ^′_Y ≤φY ≤u^′_Y (∀Y ∈ F), φN =K,

φX =∑

{φY |Y ∈ F, Y はXの子} (∀X∈ F, |X| ≥2) を満たすφY (Y ∈ F)の値を，以下のような方法で天下り的に求める．

Step 0: φN =Kとおく．

Step 1: φY の値がすべてのY ∈ F について求められていれば，y(i) =φ_{i} (i∈N) で定義されるベクトルy∈Zⁿを出力して，手続きを終了する．

Step 2: X ∈ F のうち，|X| ≥ 2 であり，かつ φX は既に求められているが，

X のすべての子Y についての φY の値が求められているわけではないものを取り 上げる．Y1, Y2, . . . , Yk ∈ F を X のすべての子とする．t = 1,2, . . . , k について，

∑k

t=1φYt =φXが成り立つように，ℓ^′_Yt あるいはu^′_Ytの値のどちらかを適切に選んで，

φYt の値とする．Step 1に戻る．

Step 2はO(k)の計算時間で実行できる．なぜなら，ℓ^′_Y, u^′_Y の値は u^′_Y =ℓ^′_Y またはu^′_Y =ℓ^′_Y + 1 (∀Y ∈ F),

∑k t=1

ℓ^′_Yt ≤ℓ^′_X ≤u^′_X ≤

∑k t=1

u^′_Yt

(∀X∈ F, |X| ≥2, Y1, Y2, . . . , Yk ∈ F はXの子)

の性質を満たすからである．|F| = O(n)であるので，上のアルゴリズムはO(n)の計算時間 で実行できる．このことから，アルゴリズムRELAXのStep 2はO(n)の計算時間で実行さ れることがわかる．

最後に，アルゴリズムRELAXのStep 3 がO(n²)の計算時間で実行されることを示す．

Step 2で得られるベクトルy^◦∈ Z^{n は}∥y^◦−x_∗∥1< nを満たすので，(Laminar)の近接定 理(定理4.28) より，(Laminar)のある最適解y_∗∈Z^{nが存在して，}

∥y_∗−y^◦∥1≤ ∥y_∗−x_∗∥1+∥x_∗−y^◦∥1<2(n−1) +n <3n

を満たすことがわかる．ゆえに，アルゴリズムRELAXのStep 3で用いられるNewGreedy は，定理4.12によりO(n)回の反復で終了する．

アルゴリズムNewGreedyの1反復あたりの計算時間はO(nTfunc)である。|F|= O(n)で あるので，目的関数の評価にかかる時間TfuncはO(n)である．従って，素朴に実装すると，

NewGreedyの各反復にはO(n²)の計算時間が必要である．この計算量は，ネットワークフ

ローの技巧を用いてO(n)に削減することができる。その手順は次の通りである．

ここでは(Laminar)をツリーネットワーク上の凸費用流問題として定式化しなおす．凸費

用流問題の，いわゆる残余ネットワークを構築する（[2]などを参照）．(Laminar) の与えら れた実行可能解 y ∈ Z^{n について，有向グラフ}Gy = (V, Ay)を作る．グラフの頂点集合は V ={vY |Y ∈ F}とし，枝集合Ayは

Ay ={(v_p(Y), vY)|Y ∈ F \ {N}, y(Y)< uY} ∪ {(vY, v_p(Y))|Y ∈ F \ {N}, y(Y)> ℓY} とする．枝の長さは次のように定める．

• (vp(Y), vY)の形の枝は，その長さをfY(y(Y) + 1)−fY(y(Y))とする．

• (vY, v_p(Y))の形の枝は，その長さをfY(y(Y)−1)−fY(y(Y))とする．

さて，fY は凸関数であるので，

[fY(y(Y) + 1)−fY(y(Y))] +[

fY(y(Y)−1)−fY(y(Y))]

≥0

である．このことから，グラフGy が負の長さの有向閉路をもたないことがわかる．

i, j ∈N について，ベクトルy−χi+χj が(Laminar)の実行可能解であるためには，頂 点v_{i}からv_{j}までの有向パスが存在することが必要十分である．あるi, j ∈ N について y−χi+χjが実行可能解であれば，fsum(y−χi+χj)−fsum(y)の値は，頂点v_{i}からv_{j}まで の最も短い有向パスの長さに等しい．ただし，y^′∈Z^{nについて}fsum(y^′) =∑

Y∈FfY(y^′(Y)) とする．ネットワーク構造を定めている（無向）グラフGyはツリーであるので，ある頂点か ら他の頂点への最短路は1つに定まる．線形時間グラフ探索アルゴリズムを用いると，定め られたi∈N に対して，すべてのj ∈N に対してv_{i}からv_{j}までの有向の最短路の長さ を，O(n)の計算時間で求めることができる．同様に，定められたi∈N に対して，すべての j ∈N に対して，逆向きのv_{j}からv_{i}までの最も短い有向路の長さを，O(n)の計算時間 で求めることができる．このことから，アルゴリズムNewGreedyの各反復がO(n)の計算時 間で実行できることがわかる．

これまでの議論をまとめると，目的関数が2次であれば，(Laminar)をO(n²)の計算時間 で解くことができる．従って，定理4.29が証明された．(Nest)と(Tree)は(Laminar)の特殊 ケースであるので，定理4.29の系として，次の結果が得られる．

系 4.30. 問題(Nest)と問題(Tree)は，目的関数が2次であれば，O(n²)の計算時間で解く ことができる．

定理4.25(i)により，(Nest)と(Tree)のそれぞれの連続緩和問題である(Nest)と(Tree)は，

どちらも(Laminar)に必要なO(n²)よりも少ないO(nlogn)の計算時間で解くことができる．

しかしながら(Nest)や(Tree)でも，Step 3にO(n²)の計算時間がかかるため，アルゴリズム RELAX全体の計算量が削減できるわけではない．(Nest)と(Tree)の目的関数が2次の場合 に，O(nlogn)の計算時間で解けるアルゴリズムが存在するかどうかは，未解決問題である．