• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
32
0
0

読み込み中.... (全文を見る)

全文

(1)

min max regret

l

m

(2)

!

Aissi, H., Bazgan, C., & Vanderpooten, D.

(2009). Min–max and min–max regret

versions of combinatorial optimization

problems: A survey. European journal of

operational research, 197(2), 427-438.

(3)

k

!

h

!

NP

k

minimize

n

X

i=0

c

i

x

i

subject to x

2 X ⇢ {0, 1}

n

(4)

Discrete scenarioiinterval scenario

!

S

!

Discrete scenario

S={s

1

, s

2

, …, s

k

}

!

Interval scenario

c

i

MMMMm

m

i

ab\

c

s

= (c

s1

, c

s2

, . . . , c

sn

),

s

2 S

[c

i

, c

i

]

0

 c

i

 c

i

(5)

Min

max  

!

x

s

!

s

!

(

)

min

x2X

max

s2S

val(x, s)

val

s

= val(x

s

, s)

val(x, s) =

n

X

i=1

c

si

x

i

(6)

Min

max

regret  

x

s

regret

x

regret

Min-max regret

u

P

R(x, s) = val(x, s)

val

s

R

max

(x) = max

s2S

R(x, s)

min

x2X

R

max

(x) = min

x2X

max

s2S

val(x, s)

val

⇤ s

(7)

m

!

Discrete scenario

!

Interval scenario

!

Min-max

!

Min-max regret

min

x2X

max

s2S

val(x, s)

min

x2X Rmax(x) = minx2X maxs2S val(x, s) val ⇤ s

(c

s1

, c

s2

, . . . , c

sn

),

s

2 S = {s

1

, s

2

, . . . , s

k

}

c

si

,

c

si

2 [c

i

, c

i

]

Interval min-max P P

c

i

= c

i

(8)

 

!

a capital budgeting problem with

uncertainty or imprecision on the

expected profits.

max

n

X

i=1

p

i

x

i

s.t.

n

X

i=1

w

i

x

i

 b

x

i

2 {0, 1}

(9)

Discrete scenario

Interval scenario

(10)
(11)

Discrete(c onst.) Discrete(c onst.) Discrete( non const.) Discrete(n on const.) Interval Min-max Min-max regret Min-max Min-max regret Min-max regret shortest

path NP-hard, pseudo-poly NP-hard, pseudo-poly Strongly NP-hard Strongly NP-hard Strongly NP-hard Spanning tree NP-hard, pseudo-poly NP-hard, pseudo-poly Strongly NP-hard Strongly NP-hard Strongly NP-hard assignment NP-hard NP-hard Strongly

NP-hard Strongly NP-hard Strongly NP-hard knapsack NP-hard,

pseudo-poly NP-hard, pseudo-poly Strongly NP-hard Strongly NP-hard NP-hard Min cut Poly Poly Strongly

NP-hard

Strongly NP-hard

Poly Min s-t cut Strongly

(12)

(Kouvelis and Yu, 1997)

Discrete min-max regret Pm

Il \g

P

I’

I’

x’

discrete min-max P

c

0i

=

k

X

s=1

c

si

k

max

s2S

(val(x

0

, s)

val

⇤ s

)

 k · opt(I)

(13)

U = max

s2S

(val(x

0

, s)

val

⇤ s

)

U

X

s2S

(val(x

0

, s)

val

s

)

=kL

k · opt(I)

L =

X

s2S

1

k

(val(x

0

, s)

val

⇤ s

)

= min

x2X

1

k

X

s2S

(val(x, s)

val

s

)

 min

x2X

1

k

k max

s2S

(val(x, s)

val

⇤ s

)

(14)

Discrete min-max Pm

Il \g

P

I’

I’

x’

c

0i

= max

s2S

c

s i

max

s2S

val(x

0

, s)

 k · opt(I)

(15)

max

s2S n

X

i=1

c

si

x

0i

n

X

i=1

c

0i

x

0i

n

X

i=1

c

0i

x

i

n

X

i=1

X

s2S

c

si

x

i

=

X

s2S n

X

i=1

c

si

x

i

k · max

s2S n

X

i=1

c

si

x

i

= k

· opt(I)

x Discrete min-max P

(16)

(Yaman et al. 2001)

Interval min-max regret Pl

g

xm

regretn m

     

mi l

lk

c (x)

c (x) =

c

i

if x

i

= 1

c

i

if x

i

= 0

(17)

val(x, s)

val(x

s

, s)

=

X

i2I(x)\I(xs)

c

si

X

i2I(xs)\I(x)

c

si

X

i2I(x)\I(xs)

c

i

X

i2I(xs)\I(x)

c

i

= val(x, c (x))

val(x

s

, c (x))

 val(x, c (x))

val(x

c (x)

, c (x))

(I(x) =

{i | x

i

= 1

})

(18)

Interval min-max regret Pm

x n m

     m

Pm

lk

c

+

(x

) =

c

i

if x

i

= 1

c

i

if x

i

= 0

c

+

(x

)

(19)

val(x⇤, s) val(x⇤c+(x), s) = X i2I(x⇤)\I(x⇤ c+(x⇤)) csi X i2I(x⇤ c+(x⇤))\I(x⇤) csi X i2I(x⇤)\I(x⇤ c+(x⇤)) ci X i2I(x⇤ c+(x⇤))\I(x⇤) ci = val(x⇤, c+(x⇤)) val(xc⇤+(x), c+(x⇤)) x* c+(x*) P

val(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

}

(20)

(Kasperski and Zielinski,2006)

Interval min-max regret Pm

Il \g

P

I’

I’

x’

c

0i

=

1

2

(c

i

+ c

i

)

max

s2S

(val(x

0

, s)

val

⇤ s

)

 2 · opt(I)

(21)

Tight example

P

•  e1 regret=1-0

(22)

Algorithms for the Min-Max

Regret Multidimensional

(23)

多次元ナップサック問題(MKP)

𝑛: アイテム数 𝑐𝑗: アイテム𝑗の利得 𝑥𝑗 ∈ 0, 1 : アイテム𝑗を選択しているか否か 𝑥𝑗 = 1:アイテム𝑗を選択する 𝑥𝑗 = 0:アイテム𝑗を選択しない 𝑎𝑖𝑗: 𝑖番目の制約におけるアイテム𝑗の重み 𝑏𝑖: 𝑖番目の制約におけるアイテムの重みの総和の許容量 max 𝑗=1𝑛 𝑐𝑗𝑥𝑗 s. t. 𝑗=1𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1, 2, … , 𝑚 ① 𝑥𝑗 ∈ {0, 1} 𝑗 = 1, 2, … , 𝑛 ② 𝑋: ①かつ②を満たしている解𝑥の集合 𝑏1 = 25 𝑏2 = 300 𝑥 = {1, 0, 1}{0, 1, 1}{1, 1, 1} 実行不可能解 𝑥 = 0, 0, 0 , 1, 0, 0 , 0, 1, 0 , 0, 0, 1 , 1, 1, 0 実行可能解 最適解(利得の総和が最大になるようなアイテムの選び方)は{0, 0, 1} item 1 2 3 𝑐𝑗 8 16 30 𝑎1𝑗 5 12 20 𝑎2𝑗 100 200 300

(24)

regretについて 𝑆 = (𝑐1𝑆, 𝑐2𝑆, … , 𝑐𝑛𝑆) シナリオ 任意の𝑗 = 1, 2, … , 𝑛について 𝑐𝑗− ≤ 𝑐𝑗𝑆 ≤ 𝑐𝑗+ 𝐹 𝑆, 𝑥 = 𝑗=1𝑛 𝑐𝑗𝑆𝑥𝑗 𝐹∗ 𝑆 = max𝑥∈𝑋𝐹 𝑆, 𝑥 𝑅 𝑆, 𝑥 = 𝐹∗ 𝑆 − 𝐹(𝑆, 𝑥) あるシナリオ𝑆における, 実行可能解𝑥に対するregret

Min-Max Regret 多次元ナップサック問題

(MMR-MKP)

(25)

Min-Max Regret 多次元ナップサック問題

(MMR-MKP)

𝐴をシナリオの集合とすると 𝑍 𝑥 = max𝑆∈𝐴𝑅 𝑆, 𝑥 = max𝑆∈𝐴(𝐹∗ 𝑆 − 𝐹 𝑆, 𝑥 ) 𝑍(𝑥)の値が最小になるような𝑥 ∈ 𝑋を見つける問題 Min-max regret 多次元ナップサック問題 (MMR-MKP) ※ 𝑋 = 𝑥 ∈ {0, 1}𝑛 𝑗=1 𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 ∀𝑖 = 1, 2, … , 𝑚}

(26)

シナリオ固定アルゴリズム

𝑅 𝑆, 𝑥 = 𝐹∗ 𝑆 − 𝐹 𝑆, 𝑥 = max𝑦∈𝑋 𝑗=1 𝑛 𝑐𝑗𝑆𝑦𝑗 − 𝑗=1 𝑛 𝑐𝑗𝑆𝑥𝑗 に対して、 𝑆を固定することで1変数の最大化問題とし て解くことができる 中間シナリオ 𝑠・・・各アイテム𝑗について、利得が (𝑐𝑗++𝑐𝑗−)/2となるようなシナリオ Lemma 中間シナリオ 𝑠のもとでの𝑅 𝑠, 𝑥 の最適値は、MMR-MKPの 最適値の2倍以内である

(27)

最悪シナリオのついてのLemma

最悪シナリオ: 𝑆′(𝑥) ある解𝑥に対して, regret𝑅(𝑆, 𝑥)を最大にするよ うなシナリオ 最悪シナリオについてのLemma 任意の𝑥 ∈ 𝑋について, 𝑥𝑗 = 0 ならば 𝑐𝑗𝑆′(𝑥) = 𝑐𝑗+ , 𝑥𝑗 = 1 ならば 𝑐𝑗𝑆′(𝑥) = 𝑐𝑗− となるようなシナリオが最悪シナリオとなる.

(28)

MMR-MKPの定式化

・定式化 シナリオの集合を𝐴とすると、MMR-MKPの定式化は以下 MMR-MKP: min𝑥∈𝑋max𝑆∈𝐴𝑅(𝑆, 𝑥) = min𝑥∈𝑋max𝑆∈𝐴 𝐹∗ 𝑆 − 𝐹 𝑆, 𝑥 実行可能解𝑥に対する最悪シナリオを𝑆′ 𝑥 とすると MMR-MKP: min𝑥∈𝑋[𝐹∗ 𝑆′ 𝑥 − 𝐹 𝑆′ 𝑥 , 𝑥 ] = min𝑥∈𝑋[max𝑦∈𝑋 𝑗=1𝑛 𝑐𝑗𝑆′(𝑥)𝑦𝑗𝑗=1𝑛 𝑐𝑗𝑆′(𝑥)𝑥𝑗] = min𝑥∈𝑋 max𝑦∈𝑋 𝑗=1𝑛 𝑐𝑗+ + 𝑐𝑗−𝑥𝑗 − 𝑐𝑗+𝑥𝑗 𝑦𝑗𝑗=1𝑛 𝑐𝑗−𝑥𝑗 ※ 𝑋 = 𝑥 ∈ {0, 1}𝑛 𝑗=1 𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 ∀𝑖 = 1, 2, … , 𝑚}

(29)

双対定理

一般の線形計画問題に対して 主問題 max 𝑗=1𝑛 𝑐𝑗𝑥𝑗 s. t. 𝑗=1𝑛 𝑎𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1, 2, … , 𝑚 0 ≤ 𝑥𝑗 ≤ 1 𝑗 = 1, 2, … , 𝑛 双対問題 min 𝑖=1𝑚 𝑏𝑖𝑢𝑖 + 𝑗=1𝑛 𝑣𝑗 s. t. 𝑖=1𝑚 𝑎𝑖𝑗𝑢𝑖 + 𝑣𝑗 ≥ 𝑐𝑗 𝑗 = 1, 2, … , 𝑛 𝑢𝑖 ≥ 0 𝑖 = 1, 2, … , 𝑚 𝑣𝑗 ≥ 0 𝑗 = 1, 2, … , 𝑛 双対定理 主問題と双対問題の両方が実行可能解を持つならば, そのどちらもが 最適解を持ち, 双方の最適値は一致する.

(30)

双対定理を利用した

MMR-MKPの変形

min𝑥∈𝑋 max𝑦∈𝑋 𝑗=1 𝑛 𝑐𝑗+ + 𝑐𝑗−𝑥𝑗 − 𝑐𝑗+𝑥𝑗 𝑦𝑗 − 𝑗=1 𝑛 𝑐𝑗−𝑥𝑗 0 ≤ 𝑦 ≤ 1に緩和し、 双対定理を利用 最小化問題への統合 min 𝑖=1𝑚 𝑏𝑖𝑢𝑖 + 𝑗=1𝑛 𝑣𝑗𝑗=1𝑛 𝑐𝑗−𝑥𝑗 s. t. 𝑖=1𝑚 𝑎𝑖𝑗𝑢𝑖 + 𝑣𝑗 ≥ 𝑐𝑗+ + 𝑐𝑗−𝑥𝑗 − 𝑐𝑗+𝑥𝑗 𝑗 = 1, 2, … , 𝑛 𝑢𝑖 ≥ 0 𝑖 = 1, 2, … , 𝑚 𝑣𝑗 ≥ 0 𝑗 = 1, 2, … , 𝑛 𝑗=1 𝑛 𝑎 𝑖𝑗𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1, 2, … , 𝑚 𝑥𝑗 ∈ {0, 1} 𝑗 = 1, 2, … , 𝑛

(31)

計算結果

・実験環境は, Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz

・問題例については, 既存の多次元ナップサック問題の問題例を利用. ・𝑐𝑗+は𝑐𝑗~ 𝑐𝑗 + 𝛿 , 𝛿 ∈ {0.05, 0.1, 0.15}の中からランダムに 𝑐𝑗−は 𝑐𝑗 − 𝛿 ~𝑐𝑗, 𝛿 ∈ {0.05, 0.1, 0.15}の中からランダムに決定 ・𝑛 = 100, 𝑚 = 5, 𝑏𝑖 = 𝛼 𝑗=1𝑛 𝑎𝑖𝑗 𝑖 = 1, 2, … , 𝑚 ・相対誤差(双対):(目的関数値(双対)−最適目的関数値)/最適目的関数値, 相対誤差(中間):(目的関数値(中間)−最適目的関数値)/最適目的関数値 α 𝜹 Time[s] (双対) Time[s] (中間) Time[s] (最適) 目的関数 値(双対) 目的関数 値(中間) 最適値 相対誤差 (双対) 相対誤差 (中間) 0.25 0.05 6.19 2.74 74.38 194.83 258.1 194.83 0 0.32 0.5 0.05 1.31 1.35 47.72 148.89 148.89 148.89 0 0 0.75 0.05 1.68 0.68 9.12 146.74 169.18 121.68 0.20 0.39 0.25 0.10 15.92 10.45 555.56 474.18 492.16 474.18 0 0.03 0.5 0.10 5.35 2.55 230.60 450.3 534.46 450.3 0 0.18 0.75 0.10 0.96 0.67 42.79 288.78 290.62 246.63 0.170 0.178 0.25 0.15 18.79 18.34 3005.59 888.51 888.51 879.26 0.0001 0.0001 0.5 0.15 7.03 4.96 1427.41 690.39 737.88 688.2 0.003 0.072 0.75 0.15 1.27 0.53 361.64 539.33 539.33 518.2 0.04 0.04

(32)

siu

!

m

discrete min-max P: k

discrete min-ma regret P: k

(interval min-max P)

interval min-max regret P: 2

!

interval min-max regret

(

参照

関連したドキュメント

Characterizing the cases where the greedy choice fails, we prove that this maximal weight is, as a function of m, asymptotically independent of max(p, q), and we provide an

Given a space Ω endowed with symmetry, we define ms(Ω, r) to be the maximum of m such that for any r-coloring of Ω there exists a monochromatic symmetric set of size at least m..

Follow with a post- directed application of ametryn (e.g. Refer to the specific ametryn product label for further directions. Apply Eradicane or Sutan or equivalent EPTC or

Should Buyer purchase or use SCILLC products for any such unintended or unauthorized application, Buyer shall indemnify and hold SCILLC and its officers, employees,

Cheetah Max may be applied as a preplant surface or preemergence burndown application or as a postemergence application with hooded spray equipment in cotton and as a preplant

When environmental conditions and plant stage are conducive to rapid disease development, use Serenade MAX in a rotational program with other registered fungicides..

Appropriate herbicides may include atrazine, Accent ® , bentazon (e.g. Basagran), Beacon, Moxy (bromoxynil), Exceed, Marksman, or 2,4-D. If the postemergence application includes

LED lighting solutions enabling our customers to meet and exceed worldwide power management regulations (efficiency, standby power, low quiescent current, PFC…) at cost parity