| Preface
 Sample Chapter - Download PDF (76 KB) | ix |
|
| 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
Sample Chapter - Download PDF (42 KB) | 229 |
|
