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
１
上界値21+1/3
x4
0
２
３
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
１
x4 1
x4
0
上界値21+1/5
２
x3
x3 1
0
上界値19+2/3
４
実行不能
３
上界値19+1/3
５
x2 1
６
x2
0
max 4 x1 14
s.t.
７
2 x1
x1
3
0 または 1
実行可能解は（0,1,0,1）のみ
暫定値19（＝上界値）
緩和問題の最適解（1,0,0,1）
上界値18＜暫定値なので終端
2015/7/3
14
上界値21
１
x4 1
x4
0
上界値21
２
x3
x3 1
0
５
x2 1
x2
６
暫定解（0,1,0,1）
最適解（0,1,0,1）
暫定値19（＝上界値）
最適値19
2015/7/3
x2 1
上界値19
４
実行不能
３
0
8
上界値19+1/3
x2
0
9
緩和問題の最適解
（1/2,1,1,0）上界値19
７
緩和問題の最適解
（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
ステップ２：漸化式
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
ステップ２：漸化式
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
最適値＝１９が求まる
最適解は， 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

Download Report