多品種流と距離空間

多品種流と距離空間

平井広志 

東京大学大学院情報理工学研究科 

!

日本オペレーションズ・リサーチ学会  2014年秋季研究発表会 

北海道科学大学，8/28-29 

講演の内容

1. 背景：ネットワークフロー/マルチフロー 

•

•

2. 本研究：Tight spanを使う双対理論の展開 といくつかの未解決問題の解決  

3. 最近の研究から：グラフ上の離散凸関数

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

最大(s,t)-フロー ＝ 最小(s,t)-カット

最大フロー最小カット定理 (

)

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

最大フロー問題

s

t

フローの整数性，効率的アルゴリズム

最大(s,t)-フロー ＝ 最小(s,t)-カット

最大フロー最小カット定理 (

)

3

2 2

2 3 1

1

3 1

4 1 2

10 2

8

3

2

マルチフロー

s

sʼ t tʼ

u

3

2 2

2 3 1

1

3 1

4 1 2

10 2

8

3

2

マルチフロー

s

sʼ t tʼ

u

(s,t)-フロー

3

2 2

2 3 1

1

3 1

4 1 2

10 2

8

3

2

マルチフロー

s

sʼ t tʼ

u

(s,t)-フロー

(sʼ,tʼ)-フロー

3

2 2

2 3 1

1

3 1

4 1 2

10 2

8

3

2

マルチフロー

s

sʼ t tʼ

u

(s,t)-フロー

(sʼ,tʼ)-フロー

(s,u)-フロー

3

2 2

2 3 1

1

3 1

4 1 2

10 2

8

3

2

マルチフロー

s

sʼ t tʼ

u

(s,t)-フロー

(sʼ,tʼ)-フロー

(s,u)-フロー

・・・

• 応用上自然なモデリング 

• ^{様々な問題定式化} 

• NP困難性と隣り合わせ 

• ^{整数性の破れ}

s

sʼ t

tʼ

• 応用上自然なモデリング 

• ^{様々な問題定式化} 

• NP困難性と隣り合わせ 

• ^{整数性の破れ}

s

sʼ t

tʼ

1/2

1/2

• 応用上自然なモデリング 

• ^{様々な問題定式化} 

• NP困難性と隣り合わせ 

• ^{整数性の破れ}

s

sʼ t

tʼ

1/2 1/2

1/2

• 応用上自然なモデリング 

• ^{様々な問題定式化} 

• NP困難性と隣り合わせ 

• ^{整数性の破れ}

s

sʼ t

tʼ

1/2 1/2 1/2

1/2

• 応用上自然なモデリング 

• ^{様々な問題定式化} 

• NP困難性と隣り合わせ 

• ^{整数性の破れ}

MFMC型定理は「一般に」は知られていないが．．．

s

sʼ t

tʼ

1/2 1/2 1/2

1/2

3

2 2

1 3 1

1

3 1

4 2 1

10 2

8

3

2

s

t

Max (s,t)-flow + (sʼ,tʼ)-flow sʼ

tʼ

2品種フロー

3

2 2

1 3 1

1

3 1

4 2 1

10 2

8

3

2

s

t

Max (s,t)-flow + (sʼ,tʼ)-flow

= Min { (ssʼ,ttʼ)-cut, (stʼ, tsʼ)-cut } フローの半整数性

sʼ

tʼ

2品種フロー

最大 最小カット定理(Hu 1963) 

3

2 2

1 3 1

1

3 1

4 2 1

10 2

8

3

2

s

t

Max (s,t)-flow + (sʼ,tʼ)-flow

= Min { (ssʼ,ttʼ)-cut, (stʼ, tsʼ)-cut } フローの半整数性

sʼ

tʼ

2品種フロー

最大 最小カット定理(Hu 1963) 

3品種フローでは類似の定理は 

知られていない：k>0, 1/k-整数性なし

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

s

t u

一様多品種フロー: Lovasz 76, Cherkassky 77 

Max (s,t)-flow + (t,u)-flow + (u,s)-flow

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

s

t u

一様多品種フロー: Lovasz 76, Cherkassky 77 

Max (s,t)-flow + (t,u)-flow + (u,s)-flow

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

s

t u

一様多品種フロー: Lovasz 76, Cherkassky 77 

Max (s,t)-flow + (t,u)-flow + (u,s)-flow

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

s

t u

一様多品種フロー: Lovasz 76, Cherkassky 77 

Max (s,t)-flow + (t,u)-flow + (u,s)-flow

3

2 2

1 3 1

1

3 1

4 1 2

10 2

8

3

2

s

t u

一様多品種フロー: Lovasz 76, Cherkassky 77 

Max (s,t)-flow + (t,u)-flow + (u,s)-flow

フローの半整数性

= Min {(s,tu)-cut + (t,su)-cut + (u,st)-cut}/2

Q.どのような問題クラスでMFMC型定理が 

成立するか？

Q.どのような問題クラスでMFMC型定理が  成立するか？

本研究で扱うのは 

この問題に対する「一つの切り口」

Q.どのような問題クラスでMFMC型定理が  成立するか？

MFMC型定理 〜

Max フロー = Min ＊＊＊

1/k-整数性 (k:定数) 離散的 本研究で扱うのは 

この問題に対する「一つの切り口」

無向ネットワーク

c : E Z₊

枝容量

S V

ターミナル集合

µ : S

2 Z₊

フロー価値

最大化問題一般形

S

(V, E, c)

(V, E, c)

s

t s

無向ネットワーク

c : E Z₊

枝容量

S V

ターミナル集合

µ : S

2 Z₊

フロー価値

最大化問題一般形

S

(V, E, c)

(V, E, c)

s

t

P

f (P )

流量

s

無向ネットワーク

c : E Z₊

枝容量

S V

ターミナル集合

µ : S

2 Z₊

フロー価値

最大化問題一般形

S

(V, E, c)

(V, E, c)

s

t

P

f (P )

流量

µ(s, t)f (P )

価値

s

無向ネットワーク

c : E Z₊

枝容量

S V

ターミナル集合

µ : S

2 Z₊

フロー価値

最大化問題一般形

S

(V, E, c)

(V, E, c)

s

t

P

f (P )

流量

µ(s, t)f (P )

価値

s

Max.

P :e P

f (P ) c(e) (e E)

s.t.

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

f (P ) 0 (P : S-^パス)

Q. どんなμならMFMC型定理が成り立つか？

1 1

1 1

1 1

1 1

1 1

1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

s t s

t

s t s

t

sʼ tʼ

sʼ tʼ

成立 成立

s t u s

t u

不成立 成立

μ

Max.

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

s.t. ^・・・

Q. どんなμならMFMC型定理が成り立つか？

1 1

1 1

1 1

1 1

1 1

1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

s t s

t

s t s

t

sʼ tʼ

sʼ tʼ

成立 成立

s t u s

t u

不成立 成立

μ

Max.

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

s.t. ^・・・

本研究：この問題の背景にある理論の展開＆解決

1956: Ford-Fulkerson      MFMC定理 

1971: 翁長-角所, 伊理 

      フロー・メトリック双対性  1978~  Karzanov, Lomonosov          クラス分類 

1998: Chepoi, Karzanov 

         Tight span を使うアプローチ

研究の流れ

1956: Ford-Fulkerson      MFMC定理 

1971: 翁長-角所, 伊理 

      フロー・メトリック双対性  1978~  Karzanov, Lomonosov          クラス分類 

1998: Chepoi, Karzanov 

         Tight span を使うアプローチ

1956: Aronszajn-Panitchpakdi 

       hyperconvexity  1964: Isbell 

         Injective hull 

!

1984: Dress 

         Tight span of metric 

研究の流れ

1956: Ford-Fulkerson      MFMC定理 

1971: 翁長-角所, 伊理 

      フロー・メトリック双対性  1978~  Karzanov, Lomonosov          クラス分類 

1998: Chepoi, Karzanov 

         Tight span を使うアプローチ

1956: Aronszajn-Panitchpakdi 

       hyperconvexity  1964: Isbell 

         Injective hull 

!

1984: Dress 

         Tight span of metric  2006: Hirai 

   Tight span of dissimilarity

研究の流れ

1956: Ford-Fulkerson      MFMC定理 

1971: 翁長-角所, 伊理 

      フロー・メトリック双対性  1978~  Karzanov, Lomonosov          クラス分類 

1998: Chepoi, Karzanov 

         Tight span を使うアプローチ

1956: Aronszajn-Panitchpakdi 

       hyperconvexity  1964: Isbell 

         Injective hull 

!

1984: Dress 

         Tight span of metric  2006: Hirai 

   Tight span of dissimilarity

2007 (OR学会へ向かう電車内)〜 本研究

研究の流れ

Japanese Theorem: フロー・メトリック双対性

1971: 翁長-角所, 伊理

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max. s.t. ^{f :マルチフロー}

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max. s.t. ^{f :マルチフロー}

= _Min.

e E

c(e)l(e)

s.t. l(P ) µ(s, t)

l(e) 0 (e E )

LP-dual

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max. s.t. ^{f :マルチフロー}

= _Min.

s.t.

l(e) 0 (e E )

Jp定理 e E

c(e)d

(e)

d

(s, t) µ(s, t) (s, t S )

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max. s.t. ^{f :マルチフロー}

= _Min.

s.t.

xy E

c(xy )d(x, y )

d(s, t) µ(s, t)

d : V ^{上のメトリック}

(s, t S )

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max. s.t. ^{f :マルチフロー}

d(x, x) = 0 (x V )

d(x, y) + d(y, z) d(x, z) (x, y, z V ) d(x, y) = d(y, x) 0 (x, y V )

= _Min.

s.t.

xy E

c(xy )d(x, y )

d(s, t) µ(s, t)

d : V ^{上のメトリック}

(s, t S )

実は, Jp定理はさらに精密化できる (H. 09)

Min. s.t.

xy E

c(xy)d(x, y)

d : metric on V

d|^S µ

実は, Jp定理はさらに精密化できる (H. 09)

Min. s.t.

xy E

c(xy)d(x, y)

d : metric on V

d|^S µ

μで決まる距離空間      と部分空間の族  T

_{ ^T

_}

実は, Jp定理はさらに精密化できる (H. 09)

Min. s.t.

xy E

c(xy)d(x, y)

d : metric on V

d|^S µ

μで決まる距離空間      と部分空間の族  T

_{ ^T

_}

= ^Min.

s.t.

xy E

c(xy )D ( (x), (y ))

: V T

(s) T

(s S )

(V, E, c)

S

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max.

xy E

c(xy)D( (x), (y))

Min.

: V T_µ

s.t.

=

(T_µ, D)

距離空間

(s) T_µ,s (s S)

x

y

(V, E, c)

S

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max.

xy E

c(xy)D( (x), (y))

Min.

: V T_µ

s.t.

=

(T_µ, D)

距離空間

(s) T_µ,s (s S)

x

y

(x) (y)

(V, E, c)

S

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max.

xy E

c(xy)D( (x), (y))

Min.

: V T_µ

s.t.

=

(T_µ, D)

距離空間

(s) T_µ,s (s S) ポテンシャル

x

y

(x) (y)

(V, E, c)

S

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max.

xy E

c(xy)D( (x), (y))

Min.

: V T_µ

s.t.

=

(T_µ, D)

距離空間

(s) T_µ,s (s S) 境界条件

ポテンシャル

x

y

(x) (y)

(V, E, c)

S

P : (s, t)-^パス

µ(s, t)f (P )

s, t S

Max.

xy E

c(xy)D( (x), (y))

Min.

: V T_µ

s.t.

=

(T_µ, D)

距離空間

(s) T_µ,s (s S) 境界条件

ポテンシャル

ポテンシャル差

x

y

(x) (y)

Tight span (Isbell 64, Dress 84)

の極小な点全体

T_µ,s := {p(s) = 0} T_µ ^{D(p, q) := p q}

T

:= { p R

| p(s) + p(t) µ(s, t) (s, t S ) }

Tight span (Isbell 64, Dress 84)

の極小な点全体

T_µ,s := {p(s) = 0} T_µ ^{D(p, q) := p q}

T

:= { p R

| p(s) + p(t) µ(s, t) (s, t S ) }

p(s) p(t)

0

T_µ T_µ,s

s t u

Max. (s,t)-flow  

        + (t,u)-flow 

       + (u,s)-flow

p(s)

p(t)

p(u)

p(s) + p(t) 1

p(t) + p(u) 1

p(s) + p(u) 1

s t

u

1/2

Max. (s,t)-flow  

        + (t,u)-flow 

       + (u,s)-flow

s t u

1/2

Max. (s,t)-flow  

        + (t,u)-flow 

       + (u,s)-flow

s t u

1/2

Max. (s,t)-flow           + (t,u)-flow         + (u,s)-flow

= Min.

xy E

c(xy)D( (x), (y))

の形 〜 双対問題の形

T

s t u

1/2

Max. (s,t)-flow           + (t,u)-flow         + (u,s)-flow

= Min.

xy E

c(xy)D( (x), (y))

次元が低いと離散化される の形 〜 双対問題の形

T

s t u

1/2

Max. (s,t)-flow           + (t,u)-flow         + (u,s)-flow

= (1/2)Min. (s,tu)-cut          + (t,su)-cut  

       + (u,st)-cut  次元が低いと離散化される

の形 〜 双対問題の形

T

dim T

2 ^なら T

^{上のグリッドグラフ によって} Max.

xy E

c(xy)d ( (x), (y))

= ^Min.

: V V ( )

s.t.

(s) T_µ,s (s S)

T

は

組合せ的最大最小定理 

の貼り合わせ

l₁

dim T

2 ^なら T

^{上のグリッドグラフ によって} Max.

xy E

c(xy)d ( (x), (y))

= ^Min.

: V V ( )

s.t.

(s) T_µ,s (s S)

は

組合せ的最大最小定理 

の貼り合わせ

フローの離散性

dim T

2

[H. STOCʼ10, 14]

定理

[Karzanov 98, H. 09]

定理

dim T

3 1/k-整数性なし(任意のk>0)

予想: 1/4-整数性

•

•

•

DISOPT 11, Ann. Combin. 12 

•

•

最近の研究紹介

グラフ上に離散凸関数を導入する試み H. 2012~

離散凸解析(室田，藤重，塩浦，田村,・・・) 

〜 整数格子   上の凸関数理論 Z

最大フロー = 最小カット

最小費用フロー問題の双対

動機: ネットワークフロー問題の双対問題は     離散凸関数の最小化

劣モジュラ関数の最小化

L 凸関数の最小化

L 凸関数最小化の典型例 Min. 

s.t. 

i,k

b_ik|x_i y_k| +

i,j

c_ij|x_i x_j|

L 凸関数最小化の典型例 Min. 

s.t. 

i,k

b_ik|x_i y_k| +

i,j

c_ij|x_i x_j|

Min. 

i,k

b_ikd (x_i, y_k) +

i,j

c_ijd (x_i, x_j)

s.t. 

グラフ   上の施設配置問題(ゼロ拡張問題)

L 凸関数最小化の典型例 Min. 

s.t. 

i,k

b_ik|x_i y_k| +

i,j

c_ij|x_i x_j|

Min. 

i,k

b_ikd (x_i, y_k) +

i,j

c_ijd (x_i, x_j)

s.t. 

グラフ   上の施設配置問題(ゼロ拡張問題)

=パスの特殊ケース

L 凸関数最小化の典型例 Min. 

s.t. 

i,k

b_ik|x_i y_k| +

i,j

c_ij|x_i x_j|

Min. 

i,k

b_ikd (x_i, y_k) +

i,j

c_ijd (x_i, x_j)

s.t. 

グラフ   上の施設配置問題(ゼロ拡張問題)

マルチフローの離散双対もこの型の問題

=パスの特殊ケース

Q. 整数格子をグリッドグラフと見るとき 

L 凸関数の類似物が定義できるグラフは何か？

Q. 整数格子をグリッドグラフと見るとき 

L 凸関数の類似物が定義できるグラフは何か？

H. 2012 ~  

向き付け可能モジュラグラフ上のL凸関数

Q. 整数格子をグリッドグラフと見るとき 

L 凸関数の類似物が定義できるグラフは何か？

H. 2012 ~  

向き付け可能モジュラグラフ上のL凸関数

• マルチフローの離散双対 

• ゼロ拡張問題の可解性分類 (SODAʼ13) 

• 最小費用一様マルチフロー問題に対する

高速アルゴリズム (2014)

向き付け可能モジュラグラフとは

例：パス，木，超立方体，グリッドグラフ，モジュラ束，

メディアングラフ，それらの直積や貼り合わせ

最小費用流問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

最小費用流問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

n

最小費用流問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

最小費用一様マルチフロー問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

n

n

最小費用流問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

最小費用一様マルチフロー問題の双対

Min.    g (x)

x = (x₁, x₂, . . . , x_n)

s.t.

n n

(新)L凸関数最小化

まとめ

• 古典的フロー・メトリック双対性(Jp定理) の一つの現代的展開 

• 劣モジュラ最適化・離散凸解析との合流(?) 

• ^{新しい関連:}  

論文，解説文，スライド等 平井のページ 

http://www.misojiro.t.u-tokyo.ac.jp/~hirai/

ご静聴ありがとうございました．