組合せ最適化問題と厳密解法
• 最小木、ナップサック問題、ビンパッキング、
巡回セールスマン問題
• LPによる上界・下界
• 分枝限定法
• 帰着とNP完全性
組合せ最適化
・ 決定すべき変数が、組合せ的(集合の部分集合)であるような
数理計画問題を組合せ最適化という
E: 集合、
X : 実行可能な E の部分集合
F: 変数、E の部分集合、 f: 部分集合上で定義された目的関数
最小化
f(F)
制約条件 F ∈ X
(ただし、 X ⊆ 2E )
応用:広い
・ NP-hard。100変数ぐらいから解けなくなる
・ 誤差が多少あってよいなら、それなりに速く解ける
組合せ最適化:たとえば
・ マッチング問題、割当て問題、配送計画、ビンパッキン
グ、巡回セールスマン問題、施設配置問題、スケ
ジューリング、時間割作成問題、勤務表作成問題、
ナップサック問題、安定集合問題、分割問題、ネット
ワークデザイン問題、集合被覆問題、など
・ だいたい、NP-hard 問題
・ 個々の問題に、個別の解法が研究されている
10000変数くらいのものが解ける問題から、
50くらいでアップアップのものまで様々
01整数計画として定式化
・ 部分集合を決定する、という定式化では、一般の数理計画の
上に乗せずらい
・ そこで、通常の数理計画のテイストで定式化してみる
- E = { 1,…,n }
- F  (x1, x2,…,xn) で表す。
つまり、 F に i が入っているとき、xi = 1
最小化
f(x1, x2,…,xn)
制約条件 g(x1, x2,…,xn) ≦ b
x1, x2,…,xn ∈ { 0,1 }
・ 多くの場合、f,g は線形の式で記述できる
基礎的な問題
・ 数学的にきれいな構造がある
 基本的な解法がある
・ 直接的な応用はあまりない
 単純化した場面を想定して用いられる
・ 他の問題を解くとき、子問題として現れる
 他の問題の特殊ケースになっている
最小全張木問題
・ グラフ G=(V,E) と 枝のコスト w が与えられる
・ 家と家を電話線で結び、ネットワークを作る
・ どういう結び方にすると、コスト最小になるだろうか
5
6
3
8
4
7
2
01整数計画で定式化
・ グラフ G=(V,E) 枝のコスト w が与えられる
・ 選ぶものは枝なので、枝に変数を割り当てる
・ サイクルを作ってはいけないので、各サイクル(長さk)
に対して、その中の k-1 本以上は使ってはいけない、
という制約を入れる
最小化 Σwixi
制約 Σi∈C xi ≦ |C|
(全てのサイクル C について)
3
xi ∈ { 0,1 }
・ 制約式が指数本ある
5
6
8
4
7
2
クラスカル法
・ クラスカル法という方法を使うと、簡単に解ける
・ コストの小さい枝から採用していく
・ 無駄な枝(サイクルができる枝)は採用しない
5
6
3
8
4
7
2
クラスカル法の正当性
・ クラスカル法で最小木でないもの(偽者)が求まった!
・ 「最小木に含まれない偽者の枝」の中で、最も早く加えられたも
のを e とする
 e より先に加えられた枝は最小木と偽者で等しい
・ 最小木に e を加えるとサイクル C ができる
・ C には e より重い枝がある  入替ればもっと軽くなる
e
クラスカル法の計算時間
・ コストの小さい枝から採用していく
 枝をコストでソート
O( |E| log |E| )
・ サイクルができるかどうかのチェック
- 2分木を使って
O( log |V| )
- 最大 |E| 回
5
・ 合計 O( |E| log |E| ) 時間
6
3
8
4
7
2
プリム法
・ ある頂点を選ぶ
・ 頂点(集合)から出て行く枝で、コスト最小枝を採用
・ 新たにつながった頂点を集合に入れる
5
6
3
8
4
7
2
プリム法の正当性
・ プリム法で最小木でないもの(偽者)が求まった!
・ 「最小木に含まれない偽者の枝」の中で、最も早く加えられたも
のを e とする
 e より先に加えられた枝は最小木と偽者で等しい
・ 最小木に e を加えて、出来るサイクルに、 e より重い枝がある
 入替ればもっと軽くなる
e
プリム法の計算時間
・ ある頂点を選ぶ
定数時間
・ 頂点(集合)から出て行く枝で、コスト最小枝を採用
- 出て行く枝をヒープに入れる。1本あたり O( log |E| )
- 内部同士を結ぶようになった枝は消す
1本あたり O( log |E| )
- 消された枝は、2度とヒープに入らない
5
 合計 O( |E| log |E| ) 時間
6
3
8
4
7
2
難しい問題
・ 最小全張木問題は、組合せ最適化の中でも比較的簡単に
(多項式時間で)解ける問題
・ 他にも、最大マッチング、最小費用流、最短路などが、楽に
解ける(多項式時間で)問題
・ しかし、こういった簡単な問題はごくわずか
・ ほとんどは、NP完全(NP-complete)、あるいは NP困難(NPcomplete)とよばれる難しい問題のクラスに属する
・ (多項式時間のアルゴリズムが存在しないだろうと言われて
いる)
問題の帰着
・ 問題 A と問題 B があり、問題 B を変換すると、問題 A になる、あ
るいは、問題 A を解くと、+αの時間で問題 B が解けるとする
・ n 個の数の中から、k 番目に大きな要素を見つける問題
 ソートすると、O(n) 時間で見つかる
 この問題は、ソートをつかって解ける
・ こういった、問題 B を問題 A に変換すること、あるいは問題 A を
解くことで解く方法を、「問題 B を問題 A に帰着する」という
・ このとき、問題 B のほうが、+α以上の時間がかかる限り、問題 A
より易しい
・ 入出力に必ず O(n) 時間かかるので、上の例だと、ソートのほうが
難しい
充足可能性問題がNP困難
・ 多項式時間、指数時間かかりそうな問題の中で、他の問題が多
項式時間で帰着できる、最も難しい問題がNP困難問題
・ 充足可能性問題は、変数 x1,…,xn からなる論理式を満たす解が
あるかどうかを判定する問題
 変形して、連言標準形にしてあると思ってよい
・ コンピュータの回路を論理式で記述できるので、ということ
・非決定性チューリングマシンといって、指数個の可能性を平行し
て調べられるコンピュータの動作を論理式でシミュレートできる
・ 組合せ的な難しい問題が、このマシンなら多項式時間で解ける
・ その問題たちの中で、充足可能性問題は一番難しいことになる
(通常のコンピュータなら、指数時間かかりそう)
難しさの証拠
・ 充足可能性問題は、難しい問題のランドマーク
 この問題より難しければ、難しそう
・ 充足可能性問題より難しい問題を、NP困難問題とよぶ
・ 非決定性チューリングマシンで、多項式時間で解ける問題をNP
問題とよぶ
・ NPの問題で、 NP困難問題であるものをNP完全問題とよぶ
・ NP問題の中で、最も難しい問題の部分がNP完全問題
近似解法
・ NP完全問題は、ある意味、総当たりの解法を使わないと最
適解が求められない
・ そこで、時間をかけて最適解を求めるのではなく、短時間で
それなりに良い解を見つける、という解法が近似解法
・ 精度保障があるもの: 近似解法
(得られる解が、必ず、最適解の2倍以内、など)
・ 精度保証がないもの: 発見的解法(メタ・ヒューリスティック)
(精度保証はないが、実験的に良い解が得られることがわ
かっているもの、あるいはそう思われるもの)
・ 問題固有の性質を使うので、解法が細分化されている
(スケジューリング用、配送計画用、など)
組合せ最適化の近似解法
・ 様々な手法がある
最もよく使われる方法:
1. 整数条件を線形緩和する
xi ∈ { 0,1 }  0 ≦ xi ≦ 1
(解集合が広くなるので、最適解は悪くはならない)
2. 得られた問題の最適解を見つける
(一般に小数解。整数解なら元問題の最適解)
3. 得られた最適解を、何かしらのルールで整数に丸める
(実行不能にならないように丸める)
最大独立集合問題
・ グラフ G=(V,E) の独立集合(または安定集合):
G の頂点集合で、全ての頂点の組が枝で結ばれていないもの
・ G の最大独立集合: G の独立集合で、頂点数が最大のもの
・ 最大独立集合を求める問題は NP-hard
・ 各頂点に変数を割り当て、独立集合に含まれるとき1になる、と
して整数計画で定式化すると、枝の両端点が独立集合に含ま
れない、という制約から、以下の問題が得られる
max. ∑ xi
s.t. xi + xj ≦ 1
xi ∈ {0,1}
for ∀(i,j) ∈ E
最大独立集合のLPによる近似
・ 最大独立集合問題の整数計画の、整数条件を緩和する
max. ∑ xi
s.t. xi + xj ≦ 1
0 ≦ xi ≦ 1
for ∀(i,j) ∈ E
・ 全ての変数に1/2 を割当てたものが実行可能解
 それほど精度は良くないが、一応、上限は得られる
・ 各枝の片方だけが1になるように最適解を丸めると、独立集合
が得られる
・ 2部グラフの場合は最適解になる
工夫の仕方
そのままではうまく精度保証ができないことが多い
各問題の構造に大きく影響されるので、
個別に上手に解法を設計する必要がある
1. 緩和問題を作る
緩和の仕方を工夫して(余計な制約を入れて)
なるべく元問題に近い(または性質の良い)緩和問題を作る
2. 得られた問題の最適解を見つける
整数条件を残し、線形計画以外の方法を使うこともある
3. 得られた最適解を、何かしらのルールで整数に丸める
精度を保証するため、いろいろなテクニックを使う
最大独立集合のLP近似の改良
・ G の部分グラフで、任意の頂点の組が枝で結ばれているもの
をクリークとよぶ  独立集合の補グラフ
・ クリークの中からは、独立集合の頂点は1つしか選べない
 制約式が作れる
max. ∑ xi
s.t. ∑xi∈S xi ≦ 1
0 ≦ xi ≦ 1
for ∀クリーク S
・ 全てのクリークを求めると指数個あるので、適当なところだけを
選んで、制約式にする
最大独立集合のLP近似の改良 (2)
・ LPの解を丸めるときに、次数の小さい頂点から優先的に選ぶ
ようにすると、効率が良くなる
 星型のグラフが最悪(最良)のケース
・ 解の精度がもう少し良くなる
分枝限定法
・ 列挙問題を(変数を1つずつ固定して)いくつかに分割し、それぞ
れの最適解を求め、元の問題の最適解を求めるアルゴリズム
・ 基本的にどんな組合せ最適化
問題にも使える
・ 通常、指数時間か
かるが、厳密に
最適解を求める
ことができる
v1
v1, v2
v1
v1, v2
v1, v2
v1, v2
上界と下界による限定操作
・ 分子限定法は、計算を速くするために枝刈りを行う
(これ以上進んでも最適解がある見込みのないところは省略する)
・ 最小化問題を考える
・ これから解こうとしてい
る部分問題の解の下界
が、今までに見つけた
v1, v2
解(暫定解)よりも
大きかったら、
見込みなし
v1
v1
v1, v2
v1, v2
v1, v2
ナップサック問題
最大積載量のあるナップサックに荷物を詰める問題
・ 荷物はいくつかある
・ 荷物はそれぞれ重さが違う
・ 荷物はそれぞれ価値が違う
荷物の価値の合計が最大になる詰め込み方を求めよ
ナップサック問題 (2)
・ NP-complete 問題である
・ 動的計画法で、比較的簡単に解ける
・ 普通の問題では数理的に不要である変数を消すと問題がと
ても小さくなる
・ 近似解法もある
ビンパッキング問題
・ いくつかのビンに、物を詰め込む
・ 物はそれぞれ大きさがある(形は気にしない)
・ ビンの容積が決まっていて、詰め込む物の大きさの合計
は、容積以下でなければいけない
・ どういう詰め込み方をすると、ビンの数が最小になるだろ
うか
ビンパッキング問題 (2)
・ NP-complete 問題である
・ ビンの数が少ないと、ナップサック問題を使って解ける
巡回セールスマン問題
・ セールスマンがお客のいる都市を回って帰ってくる
・ どういうルートで回ると、移動距離が最短になるだろうか
問題の難度と解法
・ NP-hard 問題である
・ 厳密解法: 分枝限定法、分枝切除法など
・ 近似解法はNP-Hard
・ 発見的解法: 2-opt、挿入
距離が三角不等式を満たすと、いろいろなことが言える
・ 近似解法: 3/2近似アルゴリズム、ε近似アルゴリズム
(FPTAS)
・ 発見的解法: リン・カーニハン近傍探索
01整数計画として定式化
・ 決めるのは、都市の順番
 順番を決めるように定式化するのは困難
・ ルートに入る枝を選ぶ問題、として定式化
 都市 i の次に都市 j に行くとき、xij = 1 とする
最小化 Σwijxij
制約 Σi xij = 1 、 Σj xij = 1 (入る枝&出る枝 = 1)
Σi∈X, j∈V\X xij ≧ 2 ( X が島にならない)
xij ∈ { 0,1 }
・ またまた制約式が指数本ある
ハミルトンサイクルが解ける
・ 近似解法はNP-Hard: 巡回セールスマン問題の近似解
法でハミルトンサイクル問題が解ける
ハミルトンサイクル問題: 与えられたグラフに、全ての頂点
を通る(単純な)サイクルは存在するか?
問題の変換
移動時間をこのように設定しましょう
・ 頂点の間に辺がある 1
・ 頂点の間に辺がない +∞
ハミルトンサイクル‥ ‥ ‥ ‥ ‥ ‥
ハミルトンサイクルではない‥ ‥ ‥
有限の長さ
長さ無限大
問題の変換 (2)
・ 頂点の間に枝がある
・ 頂点の間に枝がない
1
+∞
経路がハミルトンサイクル
 枝だけ通る
 有限の長さ
経路がハミルトンサイクルではない
 枝ではない所を通る
 長さ無限大
近似解から元問題の解を得る
・ 近似アルゴリズムがあるとする
近似解の長さは
有限だよ
 有限の長さのサイクルがある  ハミルトンサイクルがある
近似解の長さは
無限だよ
 最適解の長さは + ∞/n 以上
 ハミルトンサイクルはない
NP-hard問題が解ける  NP-hard問題より同じか難しい
難しさの比較
・ 巡回セールスマン問題の近似アルゴリズムがあれば、ハミ
ルトンサイクル問題が解ける
 巡回セールスマン問題のほうが難しい
・ ハミルトンサイクル問題はNP-complete
 巡回セールスマン問題もNP-complete
まとめ
・ 基本的な組合せ最適化問題の紹介
・ NP完全問題と帰着の解説
・ 最小木問題のクラスカル法とプリム法の解説
・ 巡回セールスマン問題が、近似ですら NP-complete 問題
である証明
・ 巡回セールスマン問題の2近似アルゴリズム
・ 巡回セールスマン問題のセービング法
ダウンロード

Document