Online Stochastic Combinatorial Optimization

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