はじめに

Survivable Network Design Problem (SNDP)はネットワーク設計に関する組合せ最適化問題の一種です。

最近、SNDPの基本的な内容について勉強をしていましたので、概要を紹介します。

問題の概要

最初に、SNDPとはどういった問題なのかを紹介します。

モチベーション

電線や水道管、インターネット網や道路など、現実世界の様々なインフラ網は複雑なネットワークを形成しています。
このようなネットワークは、障害に対して頑健であることが望ましいです。ネットワークのどこか一部が切断された際に、機能が停止してしまうようでは困ります。
例えば、道路であれば、災害や道路工事などによって道路が一部封鎖されたとしても、迂回路が存在すれば、人や物の配送ができます。
このような冗長性をもったネットワークを、できるだけ低コストに作成したい、というのがSNDPのモチベーションになります。

例えば、下図のようなネットワークであれば、2本までであれば、どの道路が封鎖されていたとしても、あらゆるノードから病院へアクセス可能です。

道路を過剰に設置してしまうと、設置・整備コストがかかりますので、できる限り少ないコストで、このような冗長性をもったネットワークを設計することが目的となります。

最適化問題としての表現

上記で説明したモチベーションに基づき、数学的な表現で問題を記述します。

入力として、グラフ$G=(V,E)$と、枝コスト$c:E \to \mathbb{R}$が与えられます。また、任意の頂点対$u,v \in V$に対し、どの程度の冗長性が必要かを表す要求接続強度$k(u,v) \geq 0$が与えられます。先ほどの図の例であれば、2箇所までの封鎖に耐えられる、すなわち最低3つの経路が必要になるので、$k(u,v)=3$となります。$k(u,v)=0$のときは、繋ぐ必要がない場合に相当します。

このとき、$G$の部分グラフ$H$のうち、$u,v$をつなぐ辺素なパスが$k(u,v)$本以上存在するようなもので、枝コストの合計が最小なものを求める問題となります。

辺素なパスとは、グラフ上で枝を1本も共有しないようなパスのことを指します。類似の概念に、始点と終点以外に頂点を共有しないパスを表す点素なパスというものも存在します。点素であれば、常に辺素になります。

点素なパスを求めるようなSNDPも同様に考えることができます。
辺素、点素どちらのケースであっても、SNDPはNP困難であることが知られています。

関連する最適化問題

SNDPと関連性の高い最適化問題について、簡単に紹介します。

経路探索問題

グラフ上の二点$s,t \in V$を結ぶパスが存在するかどうかは幅優先探索などを用いることで多項式時間で計算可能です。

一方で、$k \geq 2$に対し、$s,t$を結ぶ$k$-辺素なパスが存在するかどうかを判定する問題は、NP完全であることが知られています。

ネットワーク設計問題

すべての頂点対$u,v \in V$に対し、$k(u,v)=1$である場合、すなわちすべての頂点が連結であるような最小コストのネットワークを設計する問題は最小全域木問題と同値です。したがって、多項式時間で最適解を求めることが可能です。

一方で、$k(u,v) \leq 1$、すなわち要求接続強度が最大1であっても、つなぐ必要のある頂点が限られるケースは、最小シュタイナー木問題を含むため、NP困難となります。

最小シュタイナー木問題は、頂点部分集合$U \subset V$が連結になるような部分グラフで、枝コストが最小のものを求める問題で、NP困難であることが知られています。SNDPの言葉で表現すると、すべての$u,v \in U$に対して、$k(u,v)=1$のケースといえます。

問題に対するアプローチ

先述したとおり、SNDPはNP困難であるため、大きなインスタンスでは厳密に解くことが困難です。そのため、近似アルゴリズムの研究や、固定パラメータ容易性に関する研究が盛んです。

本記事では、SNDPに対する2-近似アルゴリズムである反復丸め法について説明します。反復丸め法は、SNDPに対する手法として、Jain[1]によって使用されたことで、有名になったものと認識しておりますが、SNDP以外の最適化問題でも用いられることがある汎用的な手法です。

反復丸め法

最初に反復丸め法に関する一般的な説明を行います。反復丸め法は以下の手順で実行されます。

解きたい問題を0-1整数計画問題として定式化する。
元の問題を線形緩和した問題を用意し、これの最適解を求める。
得られた最適解のうち、$x_i^{*}=0$ となった変数を$0$に固定、$x_i^{*} \geq 1 / \alpha$となった変数を$1$に固定する。
残った変数のみであらためて最適化計算を行い、すべての変数の値が固定されるまで繰り返す。

このアルゴリズムを適用するためには、繰り返しの際に、少なくとも一つ以上、上記の条件を満たす変数が存在するような最適解が存在する必要があります。
もし上記の条件を満たせば、このアルゴリズムは$\alpha$-近似アルゴリズムになります。

SNDPに対する反復丸め法

SNDPを整数計画問題として定式化すると以下のようになります。

\displaylines{
\min \sum_{e \in E}c_e x_e  \\
\mathrm{s.t.} 
\sum_{e \in \delta_{G}(S)} x_e \geq f(S) \quad \forall S \subseteq V
}

$x_e$は枝$e$をネットワークに採用するかどうかのバイナリ変数です。

$\delta_{G}(S)$は、枝の片方の点が頂点部分集合$S$に属しており、もう一方が$V \setminus S$に属しているような辺の集合です。すなわち、グラフカットの枝に相当します。
また、$f(S)$は要求接続強度を表します。記事の冒頭で用いた表現を用いるのであれば、以下のように書き下すことができます。

f(S) = \max_{u \in S, v \in V \setminus S} k(u,v)

これでSNDPを整数計画問題として記述できましたが、一点気を付けるべきポイントがあります。それは、式中で頂点部分集合$S$に関する制約がありますが、部分集合の数は、一般にグラフの頂点数$n$に対して$\mathrm{O}(2^n)$です。したがって、全てを記載しようとすると、問題のサイズが指数的になってしまいます。

一方で、直感的には、SNDPを解くために、あらゆるパターンの部分集合を考慮する必要はないように感じます。実際、Jainの論文[1]では、問題の離散的構造を利用して、この部分を解決しているようですが、詳細は理解できていないので、この記事では省略させていただきます。気になる方は元論文[1]を読んでみてください。

発展的な研究

SNDPに関する研究の方向性として、いくつかのパターンが存在します。

まず、理論的なものとして、計算クラスに関連するものです。多くのグラフ上の最適化問題で行われているものではありますが、一般のグラフ上ではNP困難であっても、木グラフや平面グラフなど、特定のクラスのグラフ上では多項式時間解法が存在したり、よりよい近似比のアルゴリズムが存在する問題が数多く存在しており、SNDPに関しても同様の研究が行われています。また、次数や接続要求のパラメータなどを利用した固定パラメータ容易性に関する研究も多く存在しています[2,3,4]。

また、SNDPを元に、より発展的な課題を設定するものがあります。様々なタイプが考えられると思いますが、個人的に興味を惹かれたものについて、紹介します。

次数制限付きのSNDP

SNDPに対する解の一つとして、ハブとなるような頂点を$k$個定めて、残りの頂点をすべてそこに繋ぐようなネットワークの作り方が考えられます。もちろん、これが最適になるかどうかはインスタンスによりますが、シンプルな解法の一つです。

一方で、実用上このような解法が運用に耐えられないケースも考えられます。特に、障害発生時には負担が一部に集中することになるため、あまり望ましくないことがあります。

このような課題を解決するため、SNDPを設計する際に、各頂点の次数に制限をかけるような派生問題が考えられています[5,6]。

次数制限を設けた場合、最小全域木問題でもNP困難になることが知られています。例えば、すべての頂点に次数2以下となるような制限を設けた場合、全頂点を通る最小重みのパスを求めることに相当するため、最小ハミルトンパス問題と等価になります。

確率計画法の適用

SNDPではどのようなエッジの故障の仕方に対しても一定の頑健性を持ったネットワークを構築します。考え方次第ではありますが、極端に都合の悪い場所に障害が集中するようなケースも考慮しているとも言えます。この傾向は高い接続要求度を持つ際により顕著になります。別の言葉で表現するのであれば、SNDPはロバスト最適化の一種と考えられます。

そこで、多少極端なケースには目をつむり、不通となる確率を現実的な確率以下に抑えることを考えてみます。すなわち、確率計画法のような考え方を適用した研究が存在します[7]。
この際には、完全に疎なパスが複数存在する必要はなく、一定の確率でエッジが故障した際に、何かしらパスが存在している確率が高ければよいので、SNDPの定式化からは外れてしまう気もしますが、関連するトピックとして紹介してみました。

まとめ

本記事ではネットワーク設計問題の一種であるSurvivable Network Design Problem (SNDP)について紹介しました。近年、国内ではインフラの老朽化が話題となっているのもあり、保守コストを抑えた上で、十分な頑健性をもったネットワークを構築する、というのは重要なテーマの一つだと考えております。

私もまだまだ勉強中ではあるのですが、この記事が何かのお役に立てば幸いです。

参考文献