! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of ope

Size: px

Start display at page:

Download "! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of ope"

あきみあきます
5 years ago
Views:

1 mi max regret l m ( )

2 ! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of operatioal research, 197(2), ! Mi-max regret

3 k miimize subject to X c i x i i=0 x 2 X {0, 1}! h! NP k

4 Discrete scearioiiterval sceario! S c s =(c s 1,c s 2,...,c s ), s 2 S! Discrete sceario S={s 1, s 2,, s k }! Iterval sceario [c i, c i ] c i MMMMm m i ab\ 0 apple c i apple c i

5 Mi max! x s X val(x, s) = c s i x i! s val s = val(x s,s)! ( ) mi max x2x s2s i=1 val(x, s)

6 Mi max regret x s regret R(x, s) = val(x, s) x regret R max (x) = max s2s val s R(x, s) Mi-max regret u P mi R max(x) =mi max x2x x2x s2s val(x, s) val s

7 m! Discrete sceario (c s 1,c s 2,...,c s ), s 2 S = {s 1,s 2,...,s k }! Iterval sceario! Mi-max c s i, c s i 2 [c i, c i ] mi max x2x s2s! Mi-max regret val(x, s) mi R max(x) =mi max val(x, s) x2x x2x s2s val Iterval mi-max P P c i = c i s

8 ! a capital budgetig problem with ucertaity or imprecisio o the expected profits. max s.t. X p i x i i=1 X i=1 w i x i apple b x i 2 {0, 1}

9 Discrete sceario Iterval sceario b=12

10 discrete sceario

shortest path Spaig tree Discrete(c ost.) Mi-max NP-hard, pseudo-poly NP-hard, pseudo-poly Discrete(c ost.) Mi-max regret NP-hard, pseudo-poly NP-hard, pseudo-poly Discrete( o cost.

11 shortest path Spaig tree Discrete(c ost.) Mi-max NP-hard, pseudo-poly NP-hard, pseudo-poly Discrete(c ost.) Mi-max regret NP-hard, pseudo-poly NP-hard, pseudo-poly Discrete( o cost.) Mi-max Strogly Strogly assigmet Strogly kapsack NP-hard, pseudo-poly NP-hard, pseudo-poly Strogly Mi cut Poly Poly Strogly Mi s-t cut Strogly Strogly Strogly Discrete( o cost.) Mi-max regret Strogly Strogly Strogly Strogly Strogly Strogly Iterval Mi-max regret Strogly Strogly Strogly Poly Strogly

12 (Kouvelis ad Yu, 1997) Discrete mi-max regret Pm Il \g kx c 0 c s i i = k s=1 P I I x max s2s (val(x0,s) val s) apple k opt(i) discrete mi-max P

13 L = X s2s =mi x2x 1 k (val(x0,s) val s) 1 k X (val(x, s) val s) s2s 1 apple mi x2x k k max(val(x, s) s2s val s) =opt(i) U = max s2s (val(x0,s) val s) U apple X s2s(val(x 0,s) val s) =kl applek opt(i)

14 Discrete mi-max Pm Il \g c 0 i = max s2s cs i P I I x max s2s val(x0,s) apple k opt(i)

15 max s2s X i=1 c s i x 0 i apple X i=1 c 0 ix 0 i apple X i=1 c 0 ix i X X apple c s i x X X i = c s i x i i=1 s2s s2s i=1 X applek max c s i x i = k opt(i) s2s i=1 x Discrete mi-max P

16 (Yama et al. 2001) Iterval mi-max regret Pl g xm regret m c (x) mi l lk c (x) = ci if x i =1 c i if x i =0

17 val(x, s) X = apple val(x s,s) i2i(x)\i(x s ) c s i X i2i(x)\i(x s ) c i X i2i(x s )\I(x) c s i X i2i(x s )\I(x) c i = val(x, c (x)) val(x s,c (x)) (I(x) ={i x i =1}) apple val(x, c (x)) val(x,c (x)) c (x)

18 Iterval mi-max regret Pm x m c + (x ) mpm lk c + (x )= ci if x i =1 c i if x i =0

19 val(x,s) val(x c + (x ),s)= X i2i(x )\I(x c + (x ) ) c s i X i2i(x )\I(x c + (x ) ) c i X i2i(x c + (x ) )\I(x ) X i2i(x c + (x ) )\I(x ) c s i c i = val(x,c + (x )) val(x c + (x ),c+ (x )) x * c + (x * ) P al(x,s) val(x c + (x ),s) > 0 val(x,s) val s > val(x c + (x ),s) val s max s2s {val(x,s) val s} > max s2s {val(x c + (x ),s) val s} x Iterval mi-max regret P

20 (Kasperski ad Zieliski,2006) Iterval mi-max regret Pm Il \g c 0 i = 1 2 (c i + c i ) P I I x max s2s (val(x0,s) val s) apple 2 opt(i)

21 Tight example P e1 regret=1-0 e2 regret=2-0

22 Algorithms for the Mi-Max Regret Multidimesioal Kapsack Problem

23 多次元ナップサック問題 (MKP) : アイテム数 c j : アイテムjの利得 x j 0, 1 : アイテム j を選択しているか否か x j = 1: アイテム j を選択する x j = 0: アイテムjを選択しない a ij : i 番目の制約におけるアイテムjの重み b i : i 番目の制約におけるアイテムの重みの総和の許容量 max j=1 s. t. j=1 X: 1 かつ 2 を満たしている解 x の集合 c j x j a ij x j b i i = 1, 2,, m 1 x j {0, 1} j = 1, 2,, 2 item c j a 1j a 2j b 1 = 25 b 2 = 300 x = {1, 0, 1}{0, 1, 1}{1, 1, 1} 実行不可能解 x = 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0 実行可能解最適解 ( 利得の総和が最大になるようなアイテムの選び方 ) は {0, 0, 1}

24 Mi-Max Regret 多次元ナップサック問題 (MMR-MKP) regret について S = (c 1 S, c 2 S,, c S ) 任意の j = 1, 2,, について c j c j S c j + シナリオ F S, x = j=1 c S j x j F S = max x X F S, x R S, x = F S F(S, x) あるシナリオ S における, 実行可能解 x に対する regret

25 Mi-Max Regret 多次元ナップサック問題 (MMR-MKP) A をシナリオの集合とすると Z x = max S A R S, x = max S A (F S F S, x ) Z(x) の値が最小になるような x X を見つける問題 Mi-max regret 多次元ナップサック問題 (MMR-MKP) X = x {0, 1} j=1 a ij x j b i i = 1, 2,, m}

26 シナリオ固定アルゴリズム R S, x = F S F S, x = max y X j=1 c j S y j j=1 c j S x j に対して S を固定することで 1 変数の最大化問題として解くことができる中間シナリオ s 各アイテムjについて利得が (c + j +c j )/2となるようなシナリオ Lemma 中間シナリオ sのもとでのr 最適値の2 倍以内である s, x の最適値は MMR-MKP の

27 最悪シナリオのついての Lemma 最悪シナリオ : S (x) ある解 x に対して, regretr(s, x) を最大にするようなシナリオ最悪シナリオについての Lemma 任意の x X について, x j = 0 ならば c j S (x) = cj +, x j = 1 ならば c j S (x) = cj となるようなシナリオが最悪シナリオとなる.

28 MMR-MKP の定式化定式化シナリオの集合を A とすると MMR-MKP の定式化は以下 MMR-MKP: mi x X max S A R(S, x) = mi x X max S A F S F S, x 実行可能解 x に対する最悪シナリオを S x とすると MMR-MKP: mi x X [F S x F S x, x ] = mi x X [max y X j=1 S c (x) j yj j=1 = mi x X max y X j=1 c j S (x) xj ] c + j + c j x j c + j x j y j j=1 c j x j X = x {0, 1} j=1 a ij x j b i i = 1, 2,, m}

29 双対定理一般の線形計画問題に対して主問題 max j=1 s. t. j=1 双対問題 mi m i=1 s. t. i=1 u i 0 v j 0 c j x j a ij x j b i i = 1, 2,, m 0 x j 1 j = 1, 2,, b i u i + j=1 v j m a ij u i + v j c j j = 1, 2,, i = 1, 2,, m j = 1, 2,, 双対定理主問題と双対問題の両方が実行可能解を持つならば, そのどちらもが最適解を持ち, 双方の最適値は一致する.

30 双対定理を利用した MMR-MKP の変形 mi x X max y X j=1 c j + + c j x j c j + x j y j j=1 c j x j 0 y 1 に緩和し双対定理を利用最小化問題への統合 mi m i=1 b i u i + j=1 v j j=1 c j x j s. t. m i=1 a ij u i + v j c + j + c j x j c + j x j j = 1, 2,, u i 0 v j 0 j=1 a ij x j b i x j {0, 1} i = 1, 2,, m j = 1, 2,, i = 1, 2,, m j = 1, 2,,

計算結果実験環境は, Itel(R) Core(TM) i5-2430m CPU @ 2.40GHz 問題例については, 既存の多次元ナップサック問題の問題例を利用. c j + は c j ~ c j + δ, δ {0.05, 0.1, 0.

31 計算結果実験環境は, Itel(R) Core(TM) i5-2430m 2.40GHz 問題例については, 既存の多次元ナップサック問題の問題例を利用. c j + は c j ~ c j + δ, δ {0.05, 0.1, 0.15} の中からランダムに c j は c j δ ~c j, δ {0.05, 0.1, 0.15} の中からランダムに決定 = 100, m = 5, b i = α j=1 a ij i = 1, 2,, m 相対誤差 ( 双対 ):( 目的関数値 ( 双対 ) 最適目的関数値 )/ 最適目的関数値, 相対誤差 ( 中間 ):( 目的関数値 ( 中間 ) 最適目的関数値 )/ 最適目的関数値 α δ Time[s] ( 双対 ) Time[s] ( 中間 ) Time[s] ( 最適 ) 目的関数値 ( 双対 ) 目的関数値 ( 中間 ) 最適値相対誤差 ( 双対 ) 相対誤差 ( 中間 )

32 siu! m discrete mi-max P: k discrete mi-ma regret P: k (iterval mi-max P) iterval mi-max regret P: 2! iterval mi-max regret ( \a

OR#5.key

OR#5.key オペレーションズリサーチ１ Operations Research 前学期月曜３限(3:00-4:30) 8 整数計画モデル Integer Programming 経営Ａ棟１０６教室山本芳嗣筑波大学大学院システム情報工学研究科整数計画問題 2 凸包最小の凸集合線形計画問題変数の整数条件 ctx Ax b x 0 xj は整数 IP LP 3 4 Bx d!!!!!? P NP