数理最適化の基本 - グラフ・ネットワーク理論入門 #組合せ最適化

この記事の目的

数理最適化問題の解法に応用されるグラフ・ネットワーク理論について、基本から応用例まで確認します。

グラフ・ネットワーク理論の基本

1. グラフ・ネットワークとは

私たちがグラフと聞くと図1のような折れ線グラフや棒グラフを想像しますが、グラフ理論とは、頂点と辺を用いて表される模式図で、様々な社会構造や物の仕組みをモデル化し、問題解決に応用する理論です。

図1

このグラフ理論や後述するネットワーク理論を応用すれば、自動車交通網、トラックや船の物流経路、電気や水道などのインフラ網、電信電話通信網、工場内の工程ルート、医療や化学の分野まで、様々な場面における計画・問題解決を有効に行うことができます。

一例ですが、東京のJR線である山手線、中央線(快速)、中央・総武線の一部をグラフを用いて表現したものが図2です。

図2

ネットワークとは、頂点や枝に輸送量や時間、コストなどの数量を記載したものです。
図3にネットワークの例を示します。移動時間を赤数字で示しています。

図3

2. グラフ・ネットワークの基本

グラフとは、頂点の集合と、頂点と頂点を連結する辺で構成する図形です。辺のことを枝、または弧と呼びます。

頂点集合Vと枝の集合Eを用いると、グラフGは以下のように表記できます。

グラフG\quad G=(V,E)

頂点$V_i$を始点、頂点$V_{i+1}$を終点とし、始点から終点へ枝の方向を識別して描いたグラフを有向グラフと呼びます。また、始点と終点を識別せず枝を描いたグラフを無向グラフと呼びます。

無向グラフのうち、異なるすべての頂点同士を連結したグラフを完全グラフと呼びます。

有向グラフのうち、番号を付けた頂点集合について、任意の2つの頂点のペアを取り出したとき、番号の小さい方の頂点を始点、大きい方の頂点を終点としてペアの頂点を枝で連結したグラフを有向路と呼びます。なお、任意の頂点のペアにおいて、必ずしも枝が存在する必要はありません。また、有向路のうち、枝の方向を識別しないグラフを路と呼びます。これらの有向路または路のうち、同じ頂点を繰り返さないグラフを初等的であると言います。

有向路または路であり、終点から始点に枝が連結されているグラフを有向閉路または閉路と呼びます。

全ての辺をちょうど1度だけ通る閉路をオイラー閉路と呼びます。一筆書きが該当します。
また、ある頂点v1を出発し、頂点集合Vのうちv1以外の全ての頂点を一回ずつ通って元の頂点に戻る路のことをハミルトン閉路と呼びます。

どの2頂点間も路が存在するグラフを連結であると呼びます。
連結で閉路を含まないグラフを木と呼びます。全ての頂点を含む木を全域木と呼びます。

3. グラフ・ネットワーク理論を応用した数理最適化問題

グラフ・ネットワーク理論を数理最適化問題へ応用することができます。
数理最適化問題の典型問題(標準問題)のうち、グラフ・ネットワーク理論を用いた問題には以下のようなものがあります。

　1. 最短路問題
　2. 最大流問題
　3. 最小費用流問題
　4. 最大マッチング問題(頂点被覆問題)
　5. 最大カット問題
　6. 巡回セールスマン問題
　7. 配送計画問題

以降の応用編で、これらの典型問題について詳しく見ていきます。

グラフ・ネットワーク理論の応用

1. 最短路問題

　読み方：さいたんろもんだい
　英語：shortest path problem
有効グラフのうち、各枝に長さや運賃などの値が与えられているネットワークで、頂点$V_s$から頂点$V_e$へ向かう有向路について、その枝の長さの和が最小となる経路を探す問題です。

最短路問題は私達の生活に身近な問題で、例えば電車の乗り換え経路や自動車で目的地に向かう際のカーナビによる道路の選択などがあります。

最短路問題の定式化です。

各枝を(i,j)\in Eと表す。\\
枝(i,j)の長さをc_{ij}とする。\\
スタート地点をs、ゴール地点をeとする。\\
x_{ij}を決定変数とする。(0:経路を選択する,1:経路を選択しない)\\
目的関数\quad\sum_{(i,j)∊E}^{}c_{ij}x_{ij}\;→\;最小化する\\
制約条件(1)\quad\sum_{(s,i)\in E}^{}x_{si}-\sum_{(i,s)\in E}^{}x_{is}=1\quad (スタート地点の出入り条件)\\
制約条件(2)\quad\sum_{(e,i)\in E}^{}x_{ei}-\sum_{(i,e)\in E}^{}x_{ie}=-1\quad (ゴール地点の出入り条件)\\
制約条件(3)\quad\sum_{(i,j)\in E}^{}x_{ij}-\sum_{(j,i)\in E}^{}x_{ji}=0\quad (中間地点の出入り条件)\\
制約条件(4)\quad x_{ij} \geq 0

2. 最大流問題

　読み方：さいだいりゅうもんだい
　英語：maximum flow problem
あるネットワークに物を流す際に、各枝に定められた流量制限を満たしながら、最大限に物を流す場合の解(方法)を求める問題です。

このモデルは、水道管の給水量や自動車交通量を計画するモデルに適用することができます。
流量制限は、水道管の場合は流れる水の量、交通量の場合は道路を走ることができる自動車の台数に対応付けられます。

最大流問題のネットワーク図の例を示します。

最大流問題の定式化です。

スタート地点をs、ゴール地点をeとする。\\
t_{ij}を枝(i,j)の流量、u_{ij}を枝(i,j)の流量制限とする。\\
スタート地点sからの流出量をf(\textbf{t})とする。\\
目的関数\quad f(\textbf{t})\;→\;最大化する\\
制約条件(1)\quad 0\leq t_{ij} \leq u_{ij}\quad(i,j)\in E\\
制約条件(2)\quad\sum_{j:(i,j)\in E}^{}t_{ij}-\sum_{k:(k,i)\in E}^{}t_{ki}=0\quad i\in V \backslash \{s,e\}\\
制約条件(3)\quad\sum_{j:(s,j)\in E}^{}t_{sj}-\sum_{k:(k,s)\in E}^{}t_{ks}=f(\textbf{t})

制約条件(1)は、各枝に流れる流量がその枝の流量制限の範囲内であることを示します。
制約条件(2)は、スタート地点s及びゴール地点eを除く頂点において、流入量の和と流出量の和が等しいことを意味します。
制約条件(3)は以下のように導出します。

ゴール地点eにおける流出量は無いため、以下が成立します。

\sum_{j:(e,j)\in E}^{}t_{ej} - \sum_{k:(k,e)}^{}t_{ke} = 0 - \sum_{k:(k,e)}^{}t_{ke}

右辺は、

右辺=-\sum_{i\in V \backslash \{e\}}^{}\Bigg(
\sum_{j:(i,j)\in E}^{}t_{ij}-\sum_{k:(k,i)\in E}^{}t_{ki} \bigg)\\
=-\sum_{i\in V \backslash \{s,e\}}^{}\bigg(
\sum_{j:(i,j)\in E}^{}t_{ij}-\sum_{k:(k,i)\in E}^{}t_{ki} \Bigg)\\
-\bigg( \sum_{j:(s,j)\in E}^{}t_{sj}-\sum_{k:(k,s)\in E}^{}t_{ks}\bigg)\\
=-f(\textbf{t})

3. 最小費用流問題

　読み方：さいしょうひようりゅうもんだい
　英語：minimum cost flow problem
工場や荷物集荷所などのネットワークにおいて、供給点から需要点まで荷物を送るときの費用が最小となる解を求める問題です。
ネットワーク内には、それぞれ複数の需要点、供給点、配送経路、中継地点があり、各配送経路において、配送可能量と費用が定められています。
さらに製品は一種類とし、どの供給点から配送しても構いません。

最小費用流問題のネットワーク図の例を示します。

最小費用流問題の定式化です。

h_{ij}を枝(i,j)の配送量、c_{ij}を枝(i,j)の費用とする。\\
b_{i}を頂点iにおける供給量とする。\\
目的関数\quad \sum_{(i,j)\in E}^{}c_{ij}h_{ij}\;→\;最小化する\\
制約条件(1)\quad\sum_{j:(i,j)\in E}^{}h_{ij}-\sum_{k:(k,i)\in E}^{}h_{ki} = b_i\quad \forall i\in V\\
制約条件(2)\quad0\leq h_{ij} \leq u_{ij}\quad \forall (i,j)\in E

制約条件(1)は、各頂点において、搬出する配送量から搬入する配送量を引いた量が供給量(需要量)となること表す式で、流量保存制約と言います。
制約条件(2)は、各枝の容量制約です。

4. 最大マッチング問題(頂点被覆問題)

　読み方：さいだいまっちんぐもんだい
　英語：max cut problem
無効グラフ$G=(V,E)$について、枝の部分集合Mに含まれるどの2本の枝も端点を共有しないとき、Mをマッチングと言い、最大マッチング問題ではグラフの中で要素数が最大となるマッチングを求めます。

別の言い方をすると、条件に合致するできるだけたくさんのペアを作ることと言えます。例えば、仕事と求職者のマッチング、複数団体への予算の割り当てや物資の分配、スポーツの対戦相手の組み合わせなどが考えられます。

最大マッチング問題と同じ性質の問題に、頂点被覆問題(vertex cover problem)があります。頂点の部分集合$V_p$に対して、どの枝についても少なくとも枝の一方の端点がに$V_p$含まれるXを求める問題です。

最大マッチング問題の解法は、変数を変形することで最大流問題に置き換えます。
　・2つの部分集合$V_1$と$V_2$を作る。
　・各枝を$V_1$から$V_2$への有向枝とする。
　・スタート地点sとゴール地点eを追加し、これらを含む新たな有向枝集合$E`$を作る。
　・各枝$(i,j)$の容量(流量制限)$u_{ij}$を以下のように定義する。
　　(i)$(i,j)\in E'の場合、u_{ij}=1$
　　(ii)$(i,j)\in Eの場合、u_{ij}=\infty$

最大マッチング問題のイメージです。

5. 最大カット問題

　読み方：さいだいかっともんだい
　英語：maximum cut problem
各枝$(i,j)\in E$に重み$w_{ij}$が与えられている無効グラフ$G=(V,E)$において、頂点集合$V$を2つの部分集合$V_1$,$V_2$に分けた際に、$i\in V_1$及び$j\in V_2$を満たす重み$w_{ij}$の総和が最大となるような解を求める問題です。

重み付きのグラフのノードを二つのグループに分割す問題とも言えます。

相対関係のある人や団体のグループ分け、人と商品など相互関連のある集合の分割などに応用できます。

最大カット問題のネットワーク図の例を示します。

最大カット問題の定式化です。

x_iを決定変数とする。(1：V_1へ入れる場合,\;-1：V_2へ入れる場合)\\
重みについて、w_{ij}=w_{ji}とする。\\
枝を持たない2つの頂点間の重みは0とする。\\
目的関数\quad \frac{1}{4}\sum_{i\in V}^{}\sum_{j\in V}^{}w_{ij}(1-x_ix_j)\;→\;最大化する\\
制約条件(1)\quad x_i^2 = 1 \quad \forall i

6. 巡回セールスマン問題

　読み方：じゅんかいせーるすまんもんだい
　英語：traveling salesman problem
巡回セールスマン問題とは、営業マンがn個の都市を、ある都市を出発し、残りの全ての都市を一回ずつ訪問して、元の都市に戻ってくる経路において、移動距離を最小にする訪問順序を求める問題です。

各都市を頂点とし、枝の長さを都市間の移動距離としてネットワーク図を作成及びモデル化し、このモデルを用いて解を求めます。
巡回セールスマン問題の解はハミルトン閉路となります。

巡回セールスマン問題の定式化です。

x_{ij}を決定変数とする。(1：枝(i,j)を通る,\;0：枝(i,j)を通らない)\\
また、ある頂点eに連結する枝の決定変数をx_eとして書き表すとする。\\
c_{ij}を枝(i,j)の距離とする。\\
目的関数\quad \sum_{(i,j)\in E}^{}c_{ij}x_{ij}\;→\;最小化する\\
制約条件(1)\quad \sum_{e\in \delta(\{u\})}^{}x_e = 2\quad (u\in V)\\
制約条件(2)\quad \sum_{e\in E(S')}^{}x_e \leq |S'|-1\quad (S'⊂V,|S'|\geq 2)\\
制約条件(3)\quad x_{ij} \in \{0,1\}\quad (i,j) \in E

制約条件(1)について、頂点の部分集合$S$に対して端点の一方が$S$に含まれ、他方が含まれていない枝の集合を$\delta(S)$とします。各頂点に接続する枝の本数は2本である条件を表しています。頂点の部分集合はいろいろな取り方ができ、その有効な全ての部分集合において成り立つ条件です。ただし、取り方が成立しない部分集合もあり、この場合の部分集合は対象外となります。

制約条件(2)について、複数の部分閉路に分かれてしまわないように、頂点集合$V$の要素数2以上の真部分集合$S'\;(S'⊂V,|S'|\geq 2)$に対して、$S'$に両端点が含まれる枝の数が$|S'|-1$以下であることの条件を表しています。記号$|\;|$は要素数を表しています。

7. 配送計画問題

　読み方：はいそうけいかくもんだい
　英語： vehicle routing problem
配送計画問題は、複数の運搬車で一つの拠点から複数の配送先へ荷物を配送する問題を扱うものです。
この問題では、運搬車の積載容量制限や配送業務の時間枠制限などの制約条件を含めることもあります。

巡回セールスマン問題を一般化したもので、それぞれの運搬車の配達ルートを順に決めながら、最終的に最も効率的なルートを割り出します。

配送計画問題のネットワーク図のイメージの例を示します。

応用編の説明は以上です。

ご意見など

ご意見、間違い訂正などございましたらお寄せ下さい。

数理最適化の基本 - グラフ・ネットワーク理論入門