12019/7/12

組合せ最適化問題は難しい !?

 最適解を求めるには全列挙（しらみつぶし）が 必要

 近年は，

0-1

計算機とアルゴリズムの発展

GuRobi，CPLEX，SCIPなどのパッケージ

最長路問題の例（0-1変数60000個，10分から20分）



LP

（

0-1

（

(0-1) Integer Linear Programming

 

 

   ^{j J}  ⁿ  

x

n i

x

m i

b x

a x c

i

i n

j

j ij n

i

i i

, ,

1 1

, 0

, ,

1 0

, ,

1 ,

s.t.

min

1 1



















 







または整数

例題：（ 0-1 ）ナップサック問題

 欲張り法の解：（

1,0,1,0

16

 けちけち法の解：（

0,0,1,0

12

（最適解は（

0,1,0,1

 ^{1 , , 4} 

1 0

9 6

5 3

2 s.t.

14 12

5 4

max

4 3

2 1

4 3

2 1

 

















i x

x x

x x

x x

x x

i または

近似解法・発見的解法の役割

 近似解法（発見的解法）は，方法により求ま る（近似）解が異なる

 （大域的）最適性は保証されない

 計算時間は短い

 メタ戦略の初期解や探索解の生成に有効

分枝限定法（ぶんしげんていほう）

 全列挙法の一つ

 小さな問題に分割して，そのすべてを解くとい う考え方に基づく方法

 探索の途中で，不要な場合分けを省略するこ とで，計算時間を短縮する

ナップサック問題で考える

問題の分割：一部の変数の

0-1

0-1

 ^{i n} 

x b

x a

x c

i n

i

i i n i

i i

, ,

1 1

or 0 ,

s.t.

max

1 1

 



 







分枝図

1 0

x x₁ 1

2 0 x

3 0

x x₃ 1 x₃ 0 x₃ 1 x₃  0 x₃ 1 x₃  0 x₃ 1

2 1

x x₂  0 x₂ 1

) 0 , 0 , 0

( (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)

 探索の過程は，分枝図で表現できる

 それぞれの節点は，部分問題に対応

一部の変数を固定した

0-1

 既知の実行可能解の中で最も良いものを暫 定解という

分枝図

1 0

x x₁ 1

2 0 x

3 0

x x₃ 1 x₃ 0 x₃ 1 x₃  0 x₃ 1 x₃  0 x₃ 1

2 1

x x₂  0 x₂ 1

) 0 , 0 , 0

( (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)

ナップサック問題 と固定した 1

0

1 ,

0 ₂

1





 x x

ナップサック問題 と固定した

1 0

1 1



 x

 分枝操作

一つの変数を固定して（二つの）問題（子問 題）を生成すること

 限定操作

部分問題が実行不能，または

部分問題の最適解が暫定値より良くない ときに，その下の探索を省略すること

分枝図

1 0

x x₁ 1

2 0 x

3 0

x x₃ 1 x₃ 0 x₃ 1 x₃  0 x₃ 1 x₃  0 x₃ 1

2 1

x x₂  0 x₂ 1

) 0 , 0 , 0

( (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)

実行不能

探索しない

部分問題の

最適値＜暫定値

探索しない

ナップサック問題の限定操作の例



LP

はナップサック問題の最適解の上界値を与える

 部分問題の上界値が暫定値以下であればそ の下を探索する必要はない（最大化問題であ

 ^{i n} 

x b

x a

x c

i n

i

i i n i

i i

, ,

1 1

0 ,

s.t.

max

1 1

 





 







分枝限定法の実行例

暫定解：欲張り法の解（

1,0,1,0

16

0,0,1,2/3

21+1/3

数で埋める を割り当て，端数を分

の大きい順から1

i

i a

c

 ^{1 , , 4} 

1 0

9 6

5 3

2 s.t.

14 12

5 4

max

4 3

2 1

4 3

2 1

 

















i x

x x

x x

x x

x x

i または

１

２ ３

4 1

x x₄ 0

暫定解（_1,0,1,0），暫定値₁₆ 上界値_21+1/3





1 0

3 5

3 2

s.t.

14 12

5 4

max

3 2

1

3 2

1

















i x

x x

x

x x

x

i または ^{0 1}





9 5

3 2

s.t.

12 5

4 max

3 2

1

3 2

1















i x

x x

x

x x

x

i または

緩和問題の最適解（_0,0,3/5,1） 上界値_21+1/5→子問題を作成

緩和問題の最適解（_1,2/3,1,0） 上界値19+1/3

１

２ ３

4 1

x x₄ 0

暫定解（_1,0,1,0），暫定値₁₆ 上界値_21+1/3

1 0

3 2

s.t.

14 4

max

1 1 1

 または



 x

x x

緩和問題の最適解（_1,0,0,1） 上界値_19+1/3 上界値_21+1/5

４ ５

3 1

x x₃ 0

実行不能

６ ７

2 1

x x₂ 0

実行可能解は（_0,1,0,1）のみ 暫定値₁₉（＝上界値）

上界値_19+2/3

１

２ ３

4 1

x x₄ 0

上界値₂₁

上界値_19+1/3 上界値₂₁

４ ５

3 1

x x₃ 0

実行不能

６ ７

2 1

x x₂ 0

暫定解（_0,1,0,1）

上界値₁₉

上界値₁₈

8 9

2 1

x x₂ 0

緩和問題の最適解

（1/2,1,1,0）上界値19 緩和問題の最適解

（_1,0,1,0）上界値₁₆ いずれも暫定解を超えないので終了

最適解（

0,1,0,1

動的計画法

 最適性の原理に基づく方法

 効率的な列挙法の一つ

 最短路問題のダイクストラ法は動的計画法の 一つ

0-1 ナップサック問題に対する動的計 画法の例

 ^{i j} 

x k

x a

x c

k j

k j f

i j

i i j i

i i

, ,

1 1

or 0 ,

s.t.

max

~ 1 :

) , (

1

 



 



場合の最適値 ナップサックに詰める

の 容量

からいくつか選んで，

要素

 

b k

n j

c a

k j

f k

j f k

j f

b k

a c

a k k

f

k j f

j j















 









 

, , ,

3 , 2

) ,

1 (

), ,

1 (

max )

, (

,

0 ,

) 0 , 1 (

) , (

1 1

1



て与えられる は以下の漸化式によっ

は最適値

を計算 の

の順にそれぞれすべて )

, (

, ,

1 , 0 ,

, 2 , 1

b n f

b k

n

j    

動的計画法の実行例

ステップ

1:

 ^{1 , , 4} 

1 0

9 6

5 3

2 s.t.

14 12

5 4

max

4 3

2 1

4 3

2 1

 

















i x

x x

x x

x x

x x

i または

 





 

9 , ,

3 , 2 ,

4

1 , 0 ,

) 0 ,

1 (

) , 1 (

k  k k

f

k

f

ステップ２：漸化式

 

を計算．

に従って

( 2 , )

9 , ,

0 ,

) ,

1 ( ),

, 1 ( max

) , 2

(

k f

k c

a k

f k

f k

f     

要素 j＼容量 k

0 1 2 3 4 5 6 7 8 9

1

0 0 4 4 4 4 4 4 4 4

2

   









max )

5 , 2 (

5 5

0 , 4 max 5

) 3 3

, 1 ( ), 3 , 1 ( max

) 3 , 2 (

























f f

f

f f

f

ステップ２：漸化式

 

を計算．

に従って

( 2 , )

9 , ,

0 ,

) ,

1 ( ),

, 1 ( max

) , 2

(

k f

k c

a k

f k

f k

f     

要素 j＼容量 k

0 1 2 3 4 5 6 7 8 9

1

0 0 4 4 4 4 4 4 4 4

   









max )

5 , 2 (

5 5

0 , 4 max 5

) 3 3

, 1 ( ), 3 , 1 ( max

) 3 , 2 (

























f f

f

f f

f

以下，これを繰り返す

最適値＝１９が求まる 最適解は，

要素 j＼容量 k

0 1 2 3 4 5 6 7 8 9

1

0 0 4 4 4 4 4 4 4 4

2

0 0 4 5 5 9 9 9 9 9

3

4

19

より

より 0 )

3 , 2 ( )

3 , 3 (

1 14

) 3 , 3 ( )

9 , 4 (

3

4











x f

f

x f

f

 動的計画法の計算量は

O(nb)



n



0-1

1

演習課題

動的計画法の表を完成させて，例題の解を求 めよ．（締切

:7

18

(

)16

Ⅳ系事務室）

要素 j＼容量 k

0 1 2 3 4 5 6 7 8 9

1

0 0 4 4 4 4 4 4 4 4

2

0 0 4 5 5 9 9 9 9 9

3

4

19