私と理論

数学の話を主に書きます

ネットワークフロー問題たちの関係を俯瞰する

ネットワークフロー好き好きマンとして,フローを布教したくなったので記事を書きました. ただし,フローの解説資料は既に素晴らしいものがたくさんあるので,今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います.

テーマは,数あるフローの問題の関係を整理することです. フローの問題たちには共通の歴史があり,共通の定式化があり,共通のアルゴリズムの思想があります. その「共通」の部分を理解することで,フローに対する理解が深まり,より面白いと感じられると僕は思っていて,そこについて書きます.

かなり基本的な内容しか書いてないので,強い人が得るものはあまりないかもしれません. あとこの記事はおきもちを書いてる部分が多いです.

また,この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません.この辺りは 保坂さんのスライド などが非常に分かりやすいので,そちらを参照してもらうと良いと思います.

そもそもネットワークフロー問題ってなんなんだ

簡単に言うと,「グラフ上で」「各辺に流体のようなものを流すときに」「各頂点における(流出量)−(流入量)に関する制約のもとで」「何らかの目的関数を最適化する」問題である,と言うことができます.

数学的に書くと以下のようになります.

  • 有向グラフ  G=(V, E) が与えられる.
  • 各辺  (i, j) \in E に「流体のようなもの」を流すことを考える.各辺の流量  x_{ij} からなるベクトル  x = [x_{ij} \mid (i, j) \in E] をフローと呼ぶ.
  • フローは,各頂点  i \in Vにおいて,実数  b_i によって指定される供給・需要制約を満たす必要がある.数学的に書くと, i \in V について  \partial x_i := \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} x_{ji} と定義したとき,  \partial x_i = b_i が成り立つ必要がある.
  • 何らかの目的関数を最適化するようなフローを求める.

本質的に重要なのは供給・需要制約です.  \partial x_i の定義の第一項は「頂点  i から流出するフロー量」を,第二項は「頂点  i流入するフロー量」を表しているので,

  •  b_i = 0 ならば流量保存則が成立している必要がある.
  •  b_i > 0 ならば流出が流入より大きい必要がある.このような頂点は供給点と呼ばれる.
  •  b_i \lt 0 ならば流入が流出より大きい必要がある.このような頂点は需要点と呼ばれる.

となります.

おきもちですが,ネットワークフロー問題の綺麗な構造は,供給・需要制約の性質の良さから来ているものだというイメージがあります.

他には辺ごとに「流せるフローの範囲の制約」がついてたりする場合もあります.

分野の概観

以下の図がフロー分野の概観になっています.ここに書かれているもの以外にもフローの問題はたくさんありますが,基本的なものはこの三つだと思います.

f:id:Theory_and_Me:20210401235911p:plain:w400
ネットーワークフロー分野の概観

この図の中で注目すべきポイントは以下です.

  1. 最短路問題 がフローに含まれています.最短路問題はフローとして説明されることは少ないですが,最短路がフローであることを意識すると分野の見通しが良くなります.

  2. 最小費用流問題は最短路問題と最大流問題の共通の一般化になっています.逆に言うと最短路問題も最大流問題も最小費用流問題の特殊ケースになっています.

1 について,最短路をフローとして捉えるのはフロー業界(?)ではかなり一般的です.フローer の聖書であるところの Ahuja, Magnanti and Orlin の "Network Flows: Theory, Algorithms, and Applications" (以下 Ahuja 本) も最短路問題→最大流問題→最小費用流問題を順に扱う,という流れになっています.

2 について,逆に言うと,最短路問題は「最小コスト」要素を,最大流問題は「容量」要素をそれぞれ最小費用流問題から切り出したものであると捉えることできます. これも僕が勝手に思っているだけの話ではなく, Ahuja 本にも同様の記述があります.

このような理解は解法を理解する際にも役に立ちます.後述しますが,最小費用流の最も基本的なアルゴリズムである最短路反復法は,「最小コスト」部分を最短路問題の方法論によって,「容量」部分を最大流問題の方法論によって解決したものであると解釈することができます.

ネットワークフロー問題たち

最短路問題

みなさんよく知っている,最適化問題の代表のようなやつです.わざわざ説明しなくてもいいかも知れませんが,一応問題を示しておきます.

  • 入力
    • 有向グラフ  G=(V, E)
    • 各辺  (i, j) \in E のコスト  c_{ij} \geq 0
    • スタートの頂点  s
    • ゴールの頂点  t
  • 出力:
    •  G における  s から  t へのパスで,パス中の辺の重みの和が最小になるもの

f:id:Theory_and_Me:20210405195735p:plain
最短路問題

さて,最短路問題はネットワークフローの問題として捉えられます. というのも,各辺のコストを「その辺にフローを 1 流すのに必要なコスト」とすると,最短路問題は「 s から  t へフローを 1 流す方法で,コストを最小にするものを求める問題」になるからです.(実はこれはコストが負の辺が含まれると怪しくて,これについては後述します)

最大流問題

ネットワークフローといえばこれを思い浮かべる人も多いんじゃないでしょうか?

以下のような問題です.

  • 入力
    • 有向グラフ  G=(V, E)
    • 各辺  (i, j) \in E の容量  u_{ij} \geq 0
    • スタートの頂点  s
    • ゴールの頂点  t
  • 出力:
    •  G における許容フローで,総流量が最大になるもの

ただし「許容フロー」と「総流量」は以下のように定義されます.

  • 許容フローとは,以下の二つの条件を満たすフローである:

    • 全ての  i \in V \setminus \{s, t \} に対して  \partial x_i = 0 が成り立つ.
    • 全ての  (i, j) \in E について  0 \leq x_{ij} \leq u_{ij} が成り立つ.
  • 総流量とは, \partial x_s =  -\partial x_t のことである.

f:id:Theory_and_Me:20210405200052p:plain
最大流問題

簡単にいうと,「ネットワーク上で, s から  t にできるだけ多くのものを運ぶ方法を求める問題」です.

最大流問題が特に重要視されるのは,問題自体の重要性も勿論ですが,二部グラフの最大マッチング,最小カット問題,(いわゆる)燃やす埋める問題など,重要な問題が最大流問題に帰着できるという要因も大きいと思われます.

最小費用流問題

知名度は最大流問題に劣る気もしますが(?),フロー界では非常に重要な最適化問題です.Ahuja 本にも "The minimum cost flow model is the most fundamental of all network flow problems. " という記述があるくらいです. 最大流問題は「できるだけ多く運ぶ」問題でしたが,最小費用流問題は「決まった量のものを」「できるだけ小さいコストで運ぶ」問題です. 最小費用流問題には定式化の仕方が色々あるのですが,代表的なものを二つ紹介します.

s-t フロー

 s から  t に総流量  B だけ流すという定式化です.

  • 入力
    • 有向グラフ  G=(V, E)
    • 各辺  (i, j) \in E のコスト  c_{ij} \geq 0
    • 各辺  (i, j) \in E の容量  u_{ij} \geq 0
    • スタートの頂点  s
    • ゴールの頂点  t
    • 総流量  B
  • 出力:
    •  G における許容フローで,総コストが最小になるもの

ただし,許容フローとは,以下の二つの条件を満たすフローです:

  •  i \in V \setminus \{s, t \} に対して  \partial x_i = 0  \partial x_s = B  \partial x_t = -B が成り立つ.
  • 全ての  (i, j) \in E について  0 \leq x_{ij} \leq u_{ij} が成り立つ.

f:id:Theory_and_Me:20210414211320p:plain
s-t フロー

b-フロー

 s t といった特別な頂点を考えずに,各頂点の需要・供給量が与えられるとする定式化です.

  • 入力
    • 有向グラフ  G=(V, E)
    • 各辺  (i, j) \in E のコスト  c_{ij} \geq 0
    • 各辺  (i, j) \in E の容量  u_{ij} \geq 0
    • 各頂点  i \in V における需要・供給値  b_i.ただし, \sum_{i \in V} b_i = 0 が成り立つものとする.
  • 出力:
    •  G における b-フローで,総コストが最小になるもの.

ただし,b-フローとは,以下の二つの条件を満たすフローです:

  •  i \in V に対して  \partial x_i = b_i が成り立つ.
  • 全ての  (i, j) \in E について  0 \leq x_{ij} \leq u_{ij} が成り立つ.

f:id:Theory_and_Me:20210405200307p:plain
b-フロー

b-フローは競プロ方言だとなぜか思いこんでいたのですが,Korte and Vygen の「組合せ最適化」などでも使われている一般的な用語のようです.

二つの定式化の関係

s-t フローと b-フローはほとんど同じ定式化で,片方をもう片方に簡単に変形することができます. これを確かめてみましょう.

  • (s-t フロー → b-フロー) こちらは簡単で,単に  b_s = B  b_t = -B  i \in V \setminus \{s, t \} に対して  b_i = 0 としてやれば OK です.

  • (b-フロー → s-t フロー)

    • 頂点  s, t を追加する
    •  b_i > 0 なる頂点  i について, s から  i に向けてコスト  0,容量  b_i の辺を引く
    •  b_i \lt 0 なる頂点  i について, i から  t に向けてコスト  0,容量  b_i の辺を引く

の手順で OK です.

f:id:Theory_and_Me:20210412215449p:plain
b-フローから s-t フローへの変形

どちらの定式化が良いのか

個人的には b-フローで考える方が良いと思っています.理由は以下です.

  • 負コストの辺の除去が簡単にできる (snuke さんの記事
  • 容量スケーリング法などの解法を用いる場合,アルゴリズム中で s-t フローではない形に問題をあえて変形することがあるため,最初から b-フローで考えた方が見通しが良い.(最も基本的な解法である最短路反復法では,s-t フローの形しか途中経過に出てこないのであまり気にならないけど)
  • LP (線形計画問題) としての定式化がとても綺麗に書けるので,双対を取るなどの LP を通した操作も見通しよく行える.

最大流問題は s-t フローの形であることが本質的でしたが,最小費用流問題では全く本質的ではなく,寧ろ b-フローの方が自然である印象です. misawa さんのライブラリ記事 でも b-フローの形が採用されていますし,上述の snuke さんの記事でも b-フローとして解釈することが推奨されています.Korte and Vygen の「組合せ最適化」や Ahuja 本でも b-フローで説明されていますね.

ただし,s-t フローにも,最大流との類似性から初心者がとっつきやすいという学習面での良さはあると思うので,初めはこちらで理解するのも良いと思います.

ネットワークフロー問題たちの関係

最短路問題は最小費用流問題の特殊ケース

まず,先に述べたように最短路問題は最小費用流問題の特殊ケースです.以下でこれを確認します.

最短路問題から,以下の手順で b-フローの問題を作ります.

  • 最短路問題におけるコスト  c の辺を,(コスト  c ,容量  1)の辺に置き換える
  •  b_s = 1  b_t = -1 とし,  i \in V \setminus \{s, t \} に対して  b_i = 0 とする

作られた b-フローの問題を解くことでもとの最短路問題を解くことができます.

f:id:Theory_and_Me:20210412220138p:plain
最短路問題→最小費用流問題

ただし,もとの最短路問題に負の辺がある場合,特に負閉路がある場合は注意が必要です.以下のように,もとの最短路問題と最小費用流問題で最適値が異なる場合を作ることができてしまいます.

f:id:Theory_and_Me:20210412221309p:plain
最適値が異なる場合

このため,「負閉路が存在しない最短路問題は最小費用流問題の特殊ケース」と言った方が安全かもしれません. 一般的に,負閉路がある場合の最短路問題や最小費用流問題は取扱いに注意が必要な場合が多いです.

ちなみに負閉路が存在する場合に単純な最短路(同じ頂点を二度以上通らないパスの中で最短のもの)を求める問題は一般には NP-Hard です(これが多項式時間で解けるとハミルトン路の存在を多項式時間で判定できてしまう).

最大流問題は最小費用流問題の特殊ケース

次に,最大流問題も最小費用流問題の特殊ケースであることを確認してみます.

最大流問題から,以下の手順で b-フローの問題を作ります.

  • 最大流問題における容量  u の辺を,(コスト  0 ,容量  u)の辺に置き換える
  • 頂点  t から 頂点  s に,(コスト  -1 ,容量  +\infty)の辺を張る
  •   i \in V に対して  b_i = 0 とする

作られた b-フローの問題を解くことでもとの最短路問題を解くことができます.ただし最適解は符号が逆になっていることに注意して下さい.

ちなみに,このように全ての   i \in V に対して  b_i = 0 である最小費用流問題は最小費用循環流問題とも呼ばれます.

f:id:Theory_and_Me:20210412220218p:plain
最大流問題→最小費用流問題

おきもちとして,最短路問題→最小費用流問題はかなり直感的な変形ですが,最大流問題→最小費用流問題は少しトリッキーな変形です. こういう部分にも現れているのですが,個人的には最小費用流問題は,最大流問題の一般化と捉えるよりも最短路問題の一般化として捉えるのが理解しやすいのではないかと思っています.

最短路反復法のおきもち

最短路反復法は,最小費用流問題を解くためのアルゴリズムの代表的なものです. アルゴリズム自体の説明は省略しますので 保坂さんのスライド などを参照して下さい.

最小費用流問題が最短路問題と最大流問題の共通の一般化であることを意識すると,最短路反復法がとても自然な解法に見えるという話をします.

最小費用流問題の難しい点は,

「コストは最小にする」「容量制約も守る」「両方」やらなくっちゃあならないってのが「最小費用流問題」のつらいところだな

f:id:Theory_and_Me:20210403083035j:plain
ジョジョの奇妙な冒険 53巻より

です.最短路問題で扱う課題と最大流問題で扱う課題を同時に倒す必要があるのです.

そこで,最短路反復法は,この二つの課題を今までの問題で用いた道具を用いて解決します. つまり,「コストを最小にする」部分を最短路を用いることによって,「容量制約は守る」部分を最大流問題を解く際に用いる残余グラフのアイデアで倒します

具体的には,「コスト付きの残余グラフ上でひたすら供給点から需要点への最短路を求めてそれに沿ってフローを流す」ということをします. 残余グラフ上のパスに沿ってフローを流すため容量制約は守られ,最短路にひたすら流すのでコストもなんとなく小さくなりそうな気がしてきます. これが最短路反復法です. 最小費用流問題が最短路問題と最大流問題の共通の一般化であることを意識すれば,最短路反復法はアルゴリズムとしてとても素直なものに見えてくるのではないでしょうか.

最短路反復は,現状での最短路を探してそこに流すのを繰り返すのでかなり単純な貪欲法だと捉えることができます.そんな雑な貪欲法でいいのかという気持ちになりますが,なんとこの出力は必ず最適解になることが証明できてしまいます!これはかなりびっくりするところで,最小費用流問題の綺麗な構造が現れている点でもあります.

実は,ネットワークフロー問題というのは妙に貪欲法がうまくいく問題群です.最短路反復法もそうですし,最大流問題に対するフォード・ファルカーソンのアルゴリズムもある意味貪欲法です.なぜ貪欲法がうまくいくのか,どんな問題で貪欲法がうまくいくのかという疑問は,離散凸解析という分野においてより抽象的な視点から分析されていたりします.

余談ですが,最短路反復法は1960年に伊理正夫という方(「数値計算の常識」という本でも有名ですね)が,他の海外の研究者と独立同時期に発見しました.また,「最短路反復法を行う時にポテンシャルを管理すると,辺のコストを全て非負にすることができるので,ダイクストラ法が使えて高速化できる」という初見では魔法のように見えるトリックは,1972年に冨澤信明という方が,これも他の海外の研究者と独立同時期に発見しました.この分野の発展は日本人の貢献に依るところも大きいようですね.

その他のネットワークフロー問題

今まで紹介した問題たちが代表的なネットワークフロー問題ですが,他にもネットワークフロー問題はたくさんあります.その一部を紹介します.この辺りは僕も理解していない部分も多いので,間違っていることを言っている可能性があります.何かありましたら教えて下さい.

  • 最小凸費用流問題. 最小費用流問題は単位流量あたりにかかるコストが枝に定義されていました.これは,各枝  (i, j) に流量  x_{ij} を引数とする線形のコスト関数  f_{ij}(x_{ij}) = c_{ij} \cdot x_{ij} が乗っていると考えることができます.このコスト関数を線形関数ではなく一般の凸関数にした問題を最小凸費用流問題といいます.最小凸費用流問題は,通常の最小費用流問題と似たような解法で効率的に解くことができます.AtCoder でも実は出題されたことがあります.詳しくは,Ahuja 本の14章を読むと良いです. 僕が一番好きなフローです

  • 一般化流問題. フローが各辺を通る間に増幅・減少するような問題設定も考えることができます.例えば,揮発性の液体を輸送するパイプネットワークにおいて,各パイプを通っている間に揮発によって一定割合で液体が減少してしまう,というような状況がこれに当てはまります.このような状況をモデリングしたのが一般化流問題です. 数学的には,各辺  (i, j)増幅率  \mu_{ij} > 0 が定義されており,需要・供給制約が   \sum_{j: (i, j) \in E} x_{ij} - \sum_{j: (j, i) \in E} \mu_{ji} \cdot x_{ji} = b_i に置き換えられます. 詳しくは,Ahuja 本の15章を読むと良いです.

  • 多品種流問題. ここまでのフローは一種類のフローを流す問題でしたが,一つのグラフ上で複数種類のフローを流す問題も考えられます.この問題を多品種流問題といいます.詳しくは Ahuja 本の17章にも乗っていますし,日本語の資料だと http://www.misojiro.t.u-tokyo.ac.jp/~hirai/papers/kouza.pdf などで解説されています.

  • パラメトリック最大流問題. 辺  (i, j) の容量が定数ではなく,パラメータ  \lambda を用いて  u_{ij}(\lambda) のような形で与えられている場合に,全ての  \lambda に対して最大流問題を一気に解く問題です.特殊な条件下では効率的に解くことができるようです.英語ですが McCormick のスライド で解説されています.

他にも劣モジュラ流やらM凸劣モジュラ流やら動的流やら色々あるようです.また,そもそもグラフ構造を定義していない状態から,抽象的なパス(みたいな概念)から始めてフローの理論を構築するというようなことも行われているようです(例えば この論文 を参照して下さい).気になる方は調べてみると良いと思います!

まとめ

フローは色々あって面白い!

公開前にこの記事を読んで有益なコメントを下さった Y.Y. さん (@ygussany) に感謝します.