スキーレンタル問題とオンライン最適化
Rent all$50$500

$250

$100

Rent1$30$400

$150

Rent2

$15$300

Buy all$0

藤原 洋志 (豊橋技術科学大学)
スキーレンタル問題とオンライン最適化
藤原 洋志

1

概要
オンライン最適化の考え方
入力が徐々に与えられる場合の最適化
スキーレンタル問題を具体例として

関数最適化
強力なアルゴリズム性能解析手法

多状態スキーレンタル問題
スキーレンタル問題の拡張「最も易しいインスタンス」にも応用あり
スキーレンタル問題とオンライン最適化
藤原 洋志

2

オンライン最適化の位置づけ
アルゴリズムの研究• 厳密アルゴリズム• 近似アルゴリズム： 多項式時間でなるべく良い解を出力• オンラインアルゴリズム：
入力が徐々に与えられる場合になるべく良い解を出力• …

スキーレンタル問題とオンライン最適化
藤原 洋志「オンライン最適化」
Online optimization?
Online computation?
Online algorithm?
Online strategy?
必ずしも「アルゴリズム」に限らない3

Ski Rental Problem[Karlin&Manasse&Rudolph&Sleator 1988]

Rent

Buy

$50

$500

Once you buy skis, you can use them for free
You do not know how many times you aregoing skiing
Input: “111…1” with length = (# ski trips)

Objective: Minimize total cost
スキーレンタル問題とオンライン最適化
藤原 洋志

4

Ski Rental Problem[Karlin&Manasse&Rudolph&Sleator 1988]

Rent

Buy

$50

$500

Examples of Strategy
Rent skis
Buy skis
Rent 9 times then buy
Rent 3 times then buy
スキーレンタル問題とオンライン最適化
藤原 洋志

5

Application:
Computer Design and Economic Problems
Cache memory: Update orinvalidate?
Hard drive: Spin or stop?
Mobile phone: Flat rate orpay-as-you-go rate?
House: Rent or buy?
Factory: Work or stop?
スキーレンタル問題とオンライン最適化
藤原 洋志

6

Ski Rental Problem[Karlin&Manasse&Rudolph&Sleator 1988]

Rent

Buy

$50

$500

Examples of Strategy
Rent skis
Buy skis
Rent 9 times then buy
Rent 3 times then buy
スキーレンタル問題とオンライン最適化
藤原 洋志

7

Evaluation of Strategy
Rent

Buy

$50$500

競合比:
小さいほど良いStrategyCompetitive Ratio

Rent skis
Buy skis
Rent 9 times then buy
Rent 3 times then buy∞ (very bad)
10 (bad)1.9 (best)3.25 (not so bad)

スキーレンタル問題とオンライン最適化
藤原 洋志

8Evaluate Strategy byCompetitive Ratio
競合比
Competitive ratio =𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦 ′ 𝑠 𝑐𝑜𝑠𝑡max# 𝑠𝑘𝑖 𝑡𝑟𝑖𝑝𝑠 𝑜𝑓𝑓𝑙𝑖𝑛𝑒 𝑐𝑜𝑠𝑡

Compare to offline cost (= cost of player
who knows the future)
Take maximum = consider worst case
Smaller is better
スキーレンタル問題とオンライン最適化
藤原 洋志

9

Example 1: Rent skis
Rent

Buy

$50

$500

Cost = 50 + 50 + 50 + 50 + …
Keep skiing=∞

Worst-casescenario

forever!

If she knew it, she would buy:
Offline cost = 500

Competitive ratio = ∞ / 500 = ∞スキーレンタル問題とオンライン最適化
藤原 洋志

10

Example 2: Buy skis
Injured!

Rent

Buy

$50

$500

Cost = 500

Worst-casescenario
Stop skiing!

If she knew it, she would rent:
Offline cost = 50

Competitive ratio = 500 / 50 = 10
スキーレンタル問題とオンライン最適化
藤原 洋志

11

Example 3:
Rent 9 times then buy
Injured!

Rent

Buy

$50

$500

Cost = (50 + … + 50) + 500= 950

Worst-casescenario
Stop skiing!

If she knew it, she would buy first:
Offline cost = 500

Competitive ratio = 950 / 500 = 1.9
スキーレンタル問題とオンライン最適化
藤原 洋志

12

Example 4:
Rent 3 times then buy
Injured!

Rent

Buy

$50$500

Cost = (50 + 50 + 50) + 500= 650

Worst-casescenario
Stop skiing!

If she knew it, she would rent:
Offline cost = 4 * 50 = 200

Competitive ratio = 650 / 200 = 3.25
スキーレンタル問題とオンライン最適化
藤原 洋志

13

Best Strategy
for Ski Rental Problem
Rent

Buy

$50$500

Competitive ratio =𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦 ′ 𝑠 𝑐𝑜𝑠𝑡max# 𝑠𝑘𝑖 𝑡𝑟𝑖𝑝𝑠 𝑜𝑓𝑓𝑙𝑖𝑛𝑒 𝑐𝑜𝑠𝑡

Smaller is better
Strategy

Rent skis
Buy skis
Rent 9 times then buy
Rent 3 times then buy
スキーレンタル問題とオンライン最適化
藤原 洋志

Competitive Ratio∞ (very bad)Check why
10 (bad)best
1.9 (best)
3.25 (not so bad)14

Analysis via Competitive Ratio
Minimization of regret
Bad news: Sometimes, too pesimistic

We do not use test data!
People say “system works for all test data”
But, is test data reliable?

We do not use probabilistic distribution!
People say “system is 99.99% safe”
But then, 0.01% dangerous!

We achieve theoretical guarantee for worst case
Of course, competitive ratio is just one of measures
スキーレンタル問題とオンライン最適化
藤原 洋志

15

オンライン最適化の歴史
1970年代: ビンパッキング問題「オンライン」という用語は出てこないが、実質オンライン最適化

1980年代～: リストアクセス問題、キャッシュ問題、スキーレンタル問題、スケジューリング問題等々
競合比、ならし解析

スキーレンタル問題とオンライン最適化
藤原 洋志

16

オンライン最適化に対する研究方針
競合比上界の研究 = 性能の良いアルゴリズム・戦略の設計
アルゴリズムが与えられても、必ずしもその競合比が明らかではない
ことも競合比下界の研究 = アルゴリズム・戦略の改良限界の解明「情報が徐々に与えられる場合」と「一度に全て与えられる場合」の、違いの本質とは？
競合比 = max オンラインコスト
入力 オフラインコスト

様々なモデル

乱択アルゴリズム・混合戦略
Resource augmentation: オンライン側が少し有利であることを仮定
平均競合比: 入力が確率分布に従う場合の、（オンラインコスト）/（オフラインコスト）の期待値
スキーレンタル問題とオンライン最適化
藤原 洋志

17

スキーレンタル問題に対する結果
競合比上界=競合比下界=2 (以降連続モデル)[Karlin&Manasse&Rudolph&Sleator 1988]
乱択アルゴリズムを許すと、競合比上界=競合比下界=1.58[Karlin&Manasse&McGeogh&Owicki 1994]
スキー回数が指数分布に従う場合の、平均競合比基準での最適戦略 [Fujiwara&Iwama2002]
スキーレンタル問題とオンライン最適化
藤原 洋志18多状態スキーレンタル問題(Multislope Ski Rental Problem)[Augustine&Irani&Swamy 2004]

スキーレンタル問題の拡張: 部分的なレンタルを許す（後述）
任意の状態数（= レンタルオプションの数）を許す場合
競合比上界=4 [Bejerano&Cidon&Naor 2000]
競合比下界=3.62 [Damachke 2003]
以上2つは Online Investment Problem に対する結果からの帰結

状態数固定の場合
最適戦略を計算するアルゴリズム [Augustine&Irani&Swamy 2004]

状態数3(4)の場合: 競合比上界=競合比下界=2.47 (2.75)[Fujiwara&Kitano&Fujito 2011]
𝑘+1 𝑘+1
最も易しいインスタンスに対する最適戦略の競合比= 𝑘+1 𝑘+1 −𝑘𝑘[Fujiwara&Kitano&Fujito 2011]

状態数無限の場合最も易しいインスタンスの定式化と最適戦略の導出 [Fujiwara 2012]
スキーレンタル問題とオンライン最適化
藤原 洋志

19

関数最適化スキーレンタル問題とオンライン最適化
藤原 洋志

20

アルゴリズム設計ツールとしての最適化
近似保証や競合比の性能評価
線形計画
半正定値計画
非凸計画
関数最適化

オンラインアルゴリズムの設計
制約・変数が徐々に増える線形計画に対する主双対法
スキーレンタル問題とオンライン最適化
藤原 洋志

21

関数最適化
古典的には、最速降下線問題や懸垂線問題
端点条件と等式制約のみなら古典的議論で解ける
オイラー・ラグランジュ方程式

不等式制約を扱うには関数解析の議論一般には解けない
しかしアルゴリズム性能解析で出てくる具体的なインスタンスには、解析的に解が得られるものもスキーレンタル問題とオンライン最適化
藤原 洋志

22

関数最適化を用いたアルゴリズム性能解析の実例
無限次元の線形計画
無限状態スキーレンタル問題の最も易しいインス
タンスの定式化と最適戦略導出 [Fujiwara 2012]
SRPTスケジューリングアルゴリズムの競合比解析の改良 [Fujiwara&Sekiguchi 2012]

無限次元の凸計画
一方向通貨交換問題に対する平均競合比の解析 [Fujiwara&Iwama&Sekiguchi 2008]
スキーレンタル問題とオンライン最適化
藤原 洋志

23

有限次元/無限次元の線形計画
有限次元

無限次元

find𝑥 ∶ {1, … , 𝑛} → ℝ
minimize 𝑐, 𝑥
subject to 𝐴𝑥 − 𝑏 ≤ 0find𝑥 ∶ 0,1 → ℝ
minimize 𝐹(𝑥)subject to 𝐺 𝑥 ≤ 0 on [0,1]𝐿 = 𝑐, 𝑥 + 𝜆, 𝐴𝑥 − 𝑏𝜆 ∈ ℝ𝑚 (𝐴 ∈ ℝ𝑚×𝑛 のとき)

スキーレンタル問題とオンライン最適化
藤原 洋志

𝐿 = 𝐹 𝑥 + 𝜆, 𝐺(𝑥)𝜆の属する関数空間は𝐺に依存
しかし具体的なインスタンスについては、狭い空間を選び最適性十分条件を立てても、それを満たす𝑥, 𝜆が見つかったりする24

関数最適化:
具体的なインスタンスに対する実践的解法
1. 最適性十分条件を定式化•••

一般化KKT条件を参考に⋅,⋅ やラグランジュ乗数の空間は、解が見つかるように定めれば十分解やラグランジュ乗数の不連続点も考慮

2. 解空間を狭めたインスタンスを定式化し解く•

解空間の見極めには計算機実験も有効

3. 元の問題の最適性十分条件を満たすことを確認•

具体的なラグランジュ乗数を与える
スキーレンタル問題とオンライン最適化
藤原 洋志

25

多状態スキーレンタル問題

スキーレンタル問題とオンライン最適化
藤原 洋志

26

Multislope Ski Rental Problem[Augustine&Irani&Swamy 2004]

slope = option

Example of 4-slope instance:
Rent all

$50

$500

$250

$100

Snow wear costs $100
Rent1$30

$400

$150

Extension: Partial rental options

Rent2$15$300Buy all

スキーレンタル問題とオンライン最適化
藤原 洋志

$027

Multislope Ski Rental Problem[Augustine&Irani&Swamy 2004]

slope = option

Example of 4-slope instance:
Rent all

$50

$500

$250

$100

Snow wear costs $100
Rent1

$30

$400

$150

Extension: Partial rental options
Objective: Minimize total cost
Difficulty: # ski trips unknown

Rent2

スキーレンタル問題とオンライン最適化
藤原 洋志$15$300

Buy all$028

Strategy & Competitive Ratio
Competitive ratio =Rent all

𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦 ′ 𝑠 𝑐𝑜𝑠𝑡max# 𝑠𝑘𝑖 𝑡𝑟𝑖𝑝𝑠 𝑜𝑓𝑓𝑙𝑖𝑛𝑒 𝑐𝑜𝑠𝑡

$50

$500

$250

$100

Rent1$30

when & which option

Strategy:$400

$150

Rent2

(Rent all) 3 times  (Rent1) 1 time  (Buy all)

Cost = (50 + 50 + 50) + 100 + 30 + 400
= 730

$15
$300

Buy all$0Worst-casescenario

Stop skiing!

If she knew it, she would take a better strategy:
Offline cost = 100 + 5 * 30 = 250

Competitive ratio = 730/250 = 2.9
スキーレンタル問題とオンライン最適化
藤原 洋志

29

Strategy & Competitive Ratio
𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦 ′ 𝑠 𝑐𝑜𝑠𝑡Competitive ratio = max# 𝑠𝑘𝑖 𝑡𝑟𝑖𝑝𝑠 𝑜𝑓𝑓𝑙𝑖𝑛𝑒 𝑐𝑜𝑠𝑡

Rent all

$50

$500

$250

$100

Rent1

$30

$400

$150
$15

Rent2
(Rent all) 3 times  (Rent1) 1 time  (Buy all)Competitive ratio = 2.9$300

Buy all$0Best possible strategy (calculated by algorithm [AIS04])(Rent all) 2 times  (Rent1) 1 time  (Rent2) 4 times  (Buy all)Competitive ratio = 1.95
スキーレンタル問題とオンライン最適化
藤原 洋志

Bestpossible
for thisinstance30

Dynamic Power Management
Original motivation of multislope ski rantalOnscreen60W[Irani&Shukla&Gupta 2003]

1Wh

0.25Wh0.1WhStand by
Objective: Minimize energy
consumption while there is no userresponseState = energy-saving modeCost = (energy for idling) +(energy for resuming)

50W

0.4Wh

0.15WhHibernate

20W
0.30WhOff0W

Why energy?
 Energy forresuming!

Strategy: automatic transition after user leaves…
(On) 10 min  (Stand by) 1 hr  (Hibernate) 6 hrs  (Off)スキーレンタル問題とオンライン最適化
藤原 洋志

31

「インスタンス」と「入力」を切り分けましょう
インスタンス: レンタル・購入の価格設定

$50

$500

$250

$100
$30
$400

$150
$15
$300

$0

入力: スキーに行く回数

Stop skiing!

インスタンスに着目
スキーレンタル問題とオンライン最適化
藤原 洋志

32

「インスタンス」と「入力」を切り分けましょう
インスタンス: レンタル・購入の価格設定
入力: スキーに行く回数
競合比の上界・下界の解明は、言い換えれば、「最も難しいインスタンス」の追求
オンライン最適化においては、たいてい「最も易しいインスタンス」には興味なし
競合比=1のアルゴリズムが作れたりする

しかし多状態スキーレンタル問題においては、「最も易しいインスタンス」が非自明
実用的意義: 「最善の省電力モード設計」+「最善のモード遷移戦略」 = 「最善の省電力性能」
スキーレンタル問題とオンライン最適化
藤原 洋志

33

Our Interest:
Difference in Instances
Instance A

Instance B

$50

$500

$250

$100

$50

$500

$350

$200
$30

$10
$400

$150

$450

$350

$15

$5

$300

$450
$0$0

Two different rental stores
Which is easier?
Scaled costs and fractional model
スキーレンタル問題とオンライン最適化
藤原 洋志

34

Our Interest:
Difference in Instances
Instance A

Instance B

110.50.2

1

10.7

0.40.60.2
0.8

0.3
0.3

0.9

0.7

Difference in hardness!

0.6

0.1
0.9

00

Best possible strategy

Best possible strategy(0) 0.2  (1) 0.1  (2) 0.4  (3)(0) 0.4  (1) 0.1  (2) 2.0  (3)Competitive ratio = 1.95

Competitive ratio = 2.25

Easier!

スキーレンタル問題とオンライン最適化
藤原 洋志

Harder!

35

Our Interest:
Difference in Instances
Instance A

Instance B

11

0.5

0.2

1

1

0.7

0.4
0.6

0.2
0.8

0.3
0.3

Easier!

0.9

0.7
0.1

0.6

0.9
0Harder!

0Find EASIEST/HARDEST instance &Note:
best possible competitive ratio CR for hardest instance= matching UB&LB
in ordinary sense
スキーレンタル問題とオンライン最適化
藤原 洋志

36

Our Results# options23

4𝑘∞(classical)

for hardestinstance

2.00

2.47

2.75

<4?

for easiest
instance

2.00

1.80

1.73

𝑘 𝑘−1
𝑘 𝑘−1 − (𝑘 − 1)𝑘−𝑒~1.58
𝑒−1→[Karlin&Manasse&Rudolph&Sleator 1988]

𝑒~1.58𝑒−1this talk[Fujiwara&Kitano&Fujito
2011]

this talk[Fujiwara
2012][Bejerano&Cidon&Naor 2000]

スキーレンタル問題とオンライン最適化
藤原 洋志

37

Range of Best Possible Competitive Ratio
2-slope (i.e. classical)

easy
1.8

for (k+1)-slope
𝑘+1 𝑘+1
𝑘+1 𝑘+1 −𝑘 𝑘

1.73

e/(e-1) ~ 1.58

hard

23-slope

4-slope

2.47
matching UB & LB

2.75

arbitrary-slope
3.62

4from previous
results

スキーレンタル問題とオンライン最適化
藤原 洋志

38

3-slope Ski Rental
EasiestHardest
1

1

2/5

1

10.68
𝜀0.6

0.6

Asymptotic

100

Best possible strategy:(0) 1/2  (1) 1/2  (2)Best possible strategy:(0) 0.68  (2)or(0) 0.47  (1) 1/𝛿  (2)Competitive ratio = 9/5 = 1.8

Competitive ratio = 2.47

スキーレンタル問題とオンライン最適化
藤原 洋志

39

4-slope Ski Rental
EasiestHardest

11

21/37

9/37

110.700.40
𝜀128/37
28/37

12/37

10.70
𝜀2

16/37
16/37

Asymptotic

100

Best possible strategy:(0) 1/3  (1) 1/3  (2) 1/3  (3)Best possible strategy:(0) 0.23  (1) 1/𝛿1  (3)or(0) 0.40  (2) 1/𝛿2  (3)Competitive ratio = 64/37 ~ 1.73

Competitive ratio = 2.75

スキーレンタル問題とオンライン最適化
藤原 洋志

40

(k+1)-slope Ski RentalEasiest
11𝑟𝑖 = 𝑐 + (1 − 𝑐)(1 + 𝑘)𝑖𝑏𝑖,𝑗 = 𝑟𝑖 − 𝑟𝑖𝑏𝑖,𝑗𝑟𝑖

0Best possible strategy:(0) 1/k  (1) 1/k  (2) 1/k  …  (k+1)

Competitive ratio = 𝑐 =𝑘+1 𝑘+1
𝑘+1 𝑘+1 −𝑘 𝑘

スキーレンタル問題とオンライン最適化
藤原 洋志

Hardest instancefor arbitrary k isstill open
Known results:
3.62 < CR < 441

Corollary on Dynamic Power Management
Best instance + best strategy  Easiest instance makes sense
1screenBest possible competitive ratio𝑘 + 1 𝑘+1𝑒=→~1.58
𝑘+1𝑘𝑘+1−𝑘𝑒−10

decreases as k grows

Good news: More modes, better energy saving!
Bad news: Limit of improvement = 1.58!
スキーレンタル問題とオンライン最適化
藤原 洋志

42

How to get easiest/hardest instance
Solve a problem with form:
Minimize 𝑥 subject to 𝑀 𝑥 ≠ ∅Problem is not convex, but…
For all 𝑥 > 𝑥 ′ , 𝑀 𝑥 ⊃ 𝑀(𝑥 ′ ) holds
Find 𝑥 such that 𝑀(𝑥 ) is a singleton
Then, 𝑥 is a solution
スキーレンタル問題とオンライン最適化
藤原 洋志𝑥𝑀(𝑥)𝑥43What If Infinitely Many Options?
Easiest 4-slope instance1

Easiest infinite-slope instance
10.5710.24

11−𝑟

0.76

𝑟

0.76

0.32

𝑟

0.43

infinitely
many

0.43
00

strategy= real vector 𝑣: 0,1,2,3 → [0,1]strategy= real function 𝑓: [0,1] → [0,1]which option

which option

when

スキーレンタル問題とオンライン最適化
藤原 洋志

when44

まとめオンライン最適化の考え方
入力が徐々に与えられる場合の最適化
スキーレンタル問題を具体例として

関数最適化
強力なアルゴリズム性能解析手法

多状態スキーレンタル問題
スキーレンタル問題の拡張「最も易しいインスタンス」にも応用あり
スキーレンタル問題とオンライン最適化
藤原 洋志

45