Online Stochastic Combinatorial Optimization
Pascal Van Hentenryck, Russell Bent
- 出版商: MIT
- 出版日期: 2006-10-01
- 售價: $1,430
- 貴賓價: 9.5 折 $1,359
- 語言: 英文
- 頁數: 236
- 裝訂: Hardcover
- ISBN: 0262220806
- ISBN-13: 9780262220804
海外代購書籍(需單獨結帳)
買這商品的人也買了...
-
$580$568 -
$2,980$2,831 -
$2,980$2,831 -
$3,040$2,888 -
$780$616 -
$1,330Computational Molecular Biology: An Algorithmic Approach
-
$1,225Discrete and Combinatorial Mathematics: An Applied Introduction, 5/e (IE-Paperback)
-
$560$476 -
$680$537 -
$490$382 -
$2,600$2,548 -
$1,150$1,093 -
$580$458 -
$780$741 -
$1,180$1,121 -
$550$435 -
$650$507 -
$1,080CMMI: Guidelines for Process Integration and Product Improvement, 2/e
-
$450$356 -
$990Artificial Intelligence for Games (Hardcover)
-
$1,200$948 -
$880$836 -
$580$522 -
$350$315 -
$147算法設計與分析-C++語言描述(第3版)
相關主題
商品描述
Description
Online decision making under uncertainty and time constraints represents one of the most challenging problems for robust intelligent agents. In an increasingly dynamic, interconnected, and real-time world, intelligent systems must adapt dynamically to uncertainties, update existing plans to accommodate new requests and events, and produce high-quality decisions under severe time constraints. Such online decision-making applications are becoming increasingly common: ambulance dispatching and emergency city-evacuation routing, for example, are inherently online decision-making problems; other applications include packet scheduling for Internet communications and reservation systems. This book presents a novel framework, online stochastic optimization, to address this challenge.
This framework assumes that the distribution of future requests, or an approximation thereof, is available for sampling, as is the case in many applications that make either historical data or predictive models available. It assumes additionally that the distribution of future requests is independent of current decisions, which is also the case in a variety of applications and holds significant computational advantages. The book presents several online stochastic algorithms implementing the framework, provides performance guarantees, and demonstrates a variety of applications. It discusses how to relax some of the assumptions in using historical sampling and machine learning and analyzes different underlying algorithmic problems. And finally, the book discusses the framework's possible limitations and suggests directions for future research.
Pascal Van Hentenryck is Professor in the Department of Computer Science at Brown University. He is the author or editor of several MIT Press books.
Russell Bent is a Ph.D. graduate of Brown University, where he worked on online optimization. He recently joined the technical staff of Los Alamos National Laboratories.
Table of Contents
Preface
1. Introduction 1
1.1 From A Priori to Online Stochastic Optimization 1
1.2 Online Stochastic Combinatorial Optimization 2
1.3 Online Anticipatory Algorithms 4
1.4 Online Stochastic Combinatorial Optimization in Context 5
1.5 Organization and Themes 13
I. ONLINE STOCHASTIC SCHEDULING
2. Online Stochastic Scheduling 19
2.1 The Generic Offline Problem 19
2.2 The Online Problem 20
2.3 The Generic Online Algorithm 20
2.4 Properties of Online Stochastic Scheduling 22
2.5 Oblivious Algorithms 23
2.6 The Expectation Algorithm 24
2.7 The Consensus Algorithm 26
2.8 The Regret Algorithm 27
2.9 Immediate Decision Making 30
2.10 The Suboptimality Approximation Problem 31
2.11 Notes and Further Reading 33
3. Theoretical Analysis 35
3.1 Expected Loss 35
3.2 Local Errors 36
3.3 Bounding Local Errors 38
3.4 The Theoretical Results 40
3.5 Discussion on the Theoretical Assumptions 41
3.6 Notes and Further Reading 43
4. Packet Scheduling 45
4.1 The Packet Scheduling Problem 45
4.2 The Optimization Algorithm 46
4.3 The Greedy Algorithm is Competitive 50
4.4 The Suboptimality Approximation 51
4.5 Experimental Setting 53
4.6 Experimental Results 54
4.7 The Anticipativity Assumption 60
4.8 Notes and Further Reading 66
II. ONLINE STOCHASTIC RESERVATIONS
5. Online Stochastic Reservations 71
5.1 The Offline Reservation Problem 71
5.2 The Online Problem 72
5.3 The Generic Online Algorithm 73
5.4 The Expectation Algorithm 74
5.5 The Consensus Algorithm 74
5.6 The Regret Algorithm 75
5.7 Cancellations 77
6. Online Multiknapsack Problems 79
6.1 Online Multiknapsack with Deadlines 79
6.2 The Suboptimality Approximation 81
6.3 Experimental Results 89
6.4 Notes and Further Reading 98
III. ONLINE STOCHASTIC ROUTING
7. Vehicle Routing with Time Windows 103
7.1 Vehicle Dispatching and Routing 103
7.2 Large Neighborhood Search 107
7.3 Notes and Further Reading 112
8. Online Stochastic Routing 113
8.1 Online Stochastic Vehicle Routing 113
8.2 Online Single Vehicle Routing 116
8.3 Service Guarantees 118
8.4 A Waiting Strategy 120
8.5 A Relocation Strategy 121
8.6 Multiple Pointwise Decisions 122
8.7 Notes and Further Reading 125
9. Online Vehicle Dispatching 127
9.1 The Online Vehicle Dispatching Problems 127
9.2 Setting of the Algorithms 128
9.3 Experimental Results 129
9.4 Visualizations of the Algorithms 138
9.5 Notes and Further Reading 149
10. Online Vehicle Routing with Time Windows 153
10.1 The Online Instances 153
10.2 Experimental Setting 155
10.3 Experimental Results 156
10.4 Notes and Further Reading 165
IV. LEARNING AND HISTORICAL SAMPLING
11. Learning Distributions 171
11.1 The Learning Framework 171
11.2 Hidden Markov Models 172
11.3 Learning Hidden Markov Models 174
11.4 Notes and Further Reading 182
12. Historical Sampling 185
12.1 Historical Averaging 185
1.2 Historical Sampling 186
V. SEQUENTIAL DECISION MAKING
13. Markov Chance-Decision Processes 193
13.1 Motivation 193
13.2 Decision-Chance versus Chance-Decision 194
13.3 Equivalence of MDCPs and MCDPs 196
13.4 Online Anticipatory Algorithms 199
13.5 The Approximation Theorem for Anticipative MCDPs 202
13.6 The Anticipativity Assumption 208
13.7 Beyond Anticipativity 210
13.8 The General Approximation Theorem for MCDPs 214
13.9 Notes and Further Reading 218
References 219
Index 229