Document

整数計画問題(Integer Programming)
n
min
ci xi
i 1
n
s.t.
aij x j
bi ,
i 1,
,m
j 1
xi
0
i 1,
xi : 整数 i
2015/7/3
,n
J
1
(0-1)ナップサック問題の例
max 4 x1 5 x2 12 x3 14 x4
s.t.
2 x1 3 x2
xi
5 x3
6 x4
0 または 1 i 1,
9
,4
欲張り法の解:(1,0,1,0),目的関数値16
けちけち法の解:(0,0,1,0),目的関数値12
いずれも最適解ではない
(最適解は(0,1,0,1)でした)
2015/7/3
2
近似解法・発見的解法の役割
近似解法(発見的解法)は,方法により求ま
る(近似)解が異なる
(大域的)最適性は保証されない
計算時間は早い
メタ戦略の初期解や探索解の生成に有効
2015/7/3
3
分枝限定法(ぶんしげんていほう)
全列挙法の一つ
小さな問題に分割して,そのすべてを解くとい
う考え方に基づく方法
探索の途中で,不要な場合分けを省略するこ
とで,計算時間を短縮する
2015/7/3
4
ナップサック問題で考える
n
max
ci xi
i 1
n
s.t.
ai xi
b,
xi
0 or 1 i 1,
,n
i 1
問題の分割:一部の変数の0-1割り当てを固定
探索:すべての変数の0-1割り当てを調べる
2015/7/3
5
分枝図
x1
x2
x3
0
(0,0,0)
2015/7/3
0
x3 1
(0,0,1)
0
x1 1
x2
x2 1
0
x3 1
(0,1,0)
(0,1,1)
x3
x3
0
(1,0,0)
0
x2
x3 1 x3
(1,0,1)
1
0
x3 1
(1,1,0)
(1,1,1)
6
探索の過程は,分枝図で表現できる
それぞれの節点は,部分問題に対応
一部の変数を固定した0-1ナップサック問題
問題のサイズは原問題より小さい
既知の実行可能解の中で最も良いものを暫
定解という
2015/7/3
7
分枝図
x1
x1
0
x1 1と固定した
x1 1
0 1ナップサック問題
0, x2 1と固定した
x2 0
0 1ナップサック問題
x3
0
(0,0,0)
2015/7/3
x3 1
(0,0,1)
x2
x2 1
0
x3 1
(0,1,0)
(0,1,1)
x3
x3
0
(1,0,0)
0
x2
x3 1 x3
(1,0,1)
1
0
x3 1
(1,1,0)
(1,1,1)
8
分枝操作
一つの変数を固定して(二つの)問題(子問
題)を生成すること
限定操作
部分問題が実行不能
部分問題の最適解が暫定値より良くない
ときに,その下の探索を省略すること
2015/7/3
9
分枝図
部分問題の
x1
x2
x3
0
(0,0,0)
0
x3 1
(0,0,1)
0
x2 1
x1 1
実行不能
0
x3 1
(0,1,0)
(0,1,1)
x3
探索しない
2015/7/3
x2
x3
0
(1,0,0)
最適値<暫定値
0
x2
x3 1 x3
(1,0,1)
1
0
x3 1
(1,1,0)
(1,1,1)
探索しない
10
ナップサック問題の限定操作の例
LP緩和問題
n
max
ci xi
i 1
n
s.t.
ai xi
b, 0
xi 1 i 1,
,n
i 1
はナップサック問題の最適解の上界値を与える
部分問題の上界値が暫定値以下であればそ
の下を探索する必要はない(最大化問題であ
ることに注意)
2015/7/3
11
分枝限定法の実行例
max 4 x1 5 x2 12 x3 14 x4
s.t.
2 x1 3 x2
xi
5 x3
6 x4
0 または 1 i 1,
9
,4
暫定解:欲張り法の解(1,0,1,0),暫定値16
緩和問題の解:(0,0,1,2/3),上界値21+1/3
ci ai の大きい順から1 を割り当て,端数を分数で埋める
暫定値<上界値なので,子問題を作成
2015/7/3
12
暫定解(1,0,1,0),暫定値16
x4 1
1
上界値21+1/3
x4
0
2
3
max
4 x1 5 x2 12 x3 14
max
4 x1 5 x2 12 x3
s.t.
2 x1 3x2
s.t.
2 x1 3x2
xi
5 x3
3
0 または 1 i 1,2,3
xi
5 x3
9
0 または 1 i 1,2,3
緩和問題の最適解(0,0,3/5,1)
緩和問題の最適解(1,2/3,1,0)
上界値21+1/5→子問題を作成
上界値19+1/3
2015/7/3
13
暫定解(1,0,1,0),暫定値16
上界値21+1/3
1
x4 1
x4
0
上界値21+1/5
2
x3
x3 1
0
上界値19+2/3
4
実行不能
3
上界値19+1/3
5
x2 1
6
x2
0
max 4 x1 14
s.t.
7
2 x1
x1
3
0 または 1
実行可能解は(0,1,0,1)のみ
暫定値19(=上界値)
緩和問題の最適解(1,0,0,1)
上界値18<暫定値なので終端
2015/7/3
14
上界値21
1
x4 1
x4
0
上界値21
2
x3
x3 1
0
5
x2 1
x2
6
暫定解(0,1,0,1)
最適解(0,1,0,1)
暫定値19(=上界値)
最適値19
2015/7/3
x2 1
上界値19
4
実行不能
3
0
8
上界値19+1/3
x2
0
9
緩和問題の最適解
(1/2,1,1,0)上界値19
7
緩和問題の最適解
(1,0,1,0)上界値16
いずれも暫定解を超えないので終了
上界値18
15
動的計画法
最適性の原理に基づく方法
効率的な列挙法の一つ
最短路問題のダイクストラ法は動的計画法の
一つ
2015/7/3
16
0-1ナップサック問題に対する動的計
画法の例
f ( j , k ) : 要素1 ~ jからいくつか選んで, 容量kの
ナップサックに詰める場合の最適値
j
max
ci xi
i 1
j
s.t.
ai xi
k,
xi
0 or 1 i 1,
,j
i 1
2015/7/3
17
f ( j , k )は以下の漸化式によって与えられる
f (1, k )
0, 0 k
c1 , a1
k
a1
b
f ( j , k ) max f ( j 1, k ), f ( j 1, k
j
j 1,2,
2,3,
, n, k
aj) cj
b
, nの順にそれぞれすべてのk
0,1,
, bを計算
f (n, b)は最適値
2015/7/3
18
動的計画法の実行例
max 4 x1 5 x2 12 x3 14 x4
s.t.
2 x1 3 x2
xi
5 x3
6 x4
0 または 1 i 1,
9
,4
ステップ1: f (1, k )を計算
f (1, k )
2015/7/3
0, k
4, k
0,1
2,3,
,9
19
ステップ2:漸化式
f (2, k )
max f (1, k ), f (1, k a2 ) c2 , k
0,
,9
に従ってf (2, k )を計算.
f (2,3)
max f (1,3), f (1,3 3) 5
max 4,0 5
5
f (2,5)
max f (1,5), f (1,5 3) 5
max 4,4 5
9
要素 j\容量 k
1
0 1 2 3 4 5 6 7 8 9
0 0 4 4 4 4 4 4 4 4
2
2015/7/3
20
ステップ2:漸化式
f (2, k )
max f (1, k ), f (1, k a2 ) c2 , k
0,
,9
に従ってf (2, k )を計算.
f (2,3)
max f (1,3), f (1,3 3) 5
max 4,0 5
5
f (2,5)
max f (1,5), f (1,5 3) 5
max 4,4 5
9
要素 j\容量 k
1
2
2015/7/3
0 1 2 3 4 5 6 7 8 9
0 0 4 4 4 4 4 4 4 4
0 0 4 5 5 9 9 9 9 9
21
以下,これを繰り返す
要素 j\容量 k
1
2
0 1 2 3 4 5 6 7 8 9
0 0 4 4 4 4 4 4 4 4
0 0 4 5 5 9 9 9 9 9
3
19
4
最適値=19が求まる
最適解は, f (4,9) f (3,3) 14よりx4 1
f (3,3)
f ( 2,3)よりx3
0
のように,逆に辿ることで得られる.
2015/7/3
22
動的計画法の計算量はO(nb)(擬多項式)
nがある程度大きい場合は,単純な全列挙よ
りも早い.
0-1ナップサック問題に対しては,要素数が1
万くらいでも分枝限定法であっという間に解
ける
2015/7/3
23
演習課題
動的計画法の表を完成させて,例題の解を求
めよ.(締切:7月9日(木)12時 Ⅳ系事務室)
要素 j\容量 k
1
2
0 1 2 3 4 5 6 7 8 9
0 0 4 4 4 4 4 4 4 4
0 0 4 5 5 9 9 9 9 9
3
4
2015/7/3
19
24