Fast Sequential Monte Carlo Methods for Counting and Optimization

REUVEN Y. RUBINSTEIN, DSC, was Professor Emeritus in the Faculty of Industrial Engineering and Management at Technion-Israel Institute of Technology. The author of over 100 articles and six books, Dr. Rubinstein was also the inventor of the popular score-function method in simulation analysis and generic cross-entropy methods for combinatorial optimization and counting. AD RIDDER, PHD, is Associate Professor of Operations Research at Vrije Universiteit Amsterdam. His research interests include rare event simulation, applied probability problems, queuing models, and Monte Carlo methods. RADISLAV VAISMANis the author of numerous journal articles, and his research interests include rare event simulation, randomized algorithms, and on-line planning.

• Preface xi1. Introduction to Monte Carlo Methods 12. Cross-Entropy Method 62.1. Introduction 62.2. Estimation of Rare-Event Probabilities 72.3. Cross-Entrophy Method for Optimization 182.3.1. The Multidimensional 0/1 Knapsack Problem 212.3.2. Mastermind Game 232.3.3. Markov Decision Process and Reinforcement Learning 252.4. Continuous Optimization 312.5. Noisy Optimization 332.5.1. Stopping Criterion 353. Minimum Cross-Entropy Method 373.1. Introduction 373.2. Classic MinxEnt Method 393.3. Rare Events and MinxEnt 433.4. Indicator MinxEnt Method 473.4.1. Connection between CE and IME 513.5. IME Method for Combinatorial Optimization 523.5.1. Unconstrained Combinatorial Optimization 523.5.2. Constrained Combinatorial Optimization: The Penalty Function Approach 544. Splitting Method for Counting and Optimization 564.1. Background 564.2. Quick Glance at the Splitting Method 584.3. Splitting Algorithm with Fixed Levels 644.4. Adaptive Splitting Algorithm 684.5. Sampling Uniformly on Discrete Regions 744.6. Splitting Algorithm for Combinatorial Optimization 754.7. Enhanced Splitting Method for Counting 764.7.1. Counting with the Direct Estimator 764.7.2. Counting with the Capture–Recapture Method 774.8. Application of Splitting to Reliability Models 794.8.1. Introduction 794.8.2. Static Graph Reliability Problem 824.8.3. BMC Algorithm for Computing S(Y) 844.8.4. Gibbs Sampler 854.9. Numerical Results with the Splitting Algorithms 864.9.1. Counting 874.9.2. Combinatorial Optimization 1014.9.3. Reliability Models 1024.10. Appendix: Gibbs Sampler 1045. Stochastic Enumeration Method 1065.1. Introduction 1065.2. OSLA Method and Its Extensions 1105.2.1. Extension of OSLA: nSLA Method 1125.2.2. Extension of OSLA for SAW: Multiple Trajectories 1155.3. SE Method 1205.3.1. SE Algorithm 1205.4. Applications of SE 1275.4.1. Counting the Number of Trajectories in a Network 1275.4.2. SE for Probabilities Estimation 1315.4.3. Counting the Number of Perfect Matchings in a Graph 1325.4.4. Counting SAT 1355.5. Numerical Results 1365.5.1. Counting SAW 1375.5.2. Counting the Number of Trajectories in a Network 1375.5.3. Counting the Number of Perfect Matchings in a Graph 1405.5.4. Counting SAT 1435.5.5. Comparison of SE with Splitting and SampleSearch 146A. Additional Topics 148A.1. Combinatorial Problems 148A.1.1. Counting 149A.1.2. Combinatorial Optimization 154A.2. Information 162A.2.1. Shannon Entropy 162A.2.2. Kullback–Leibler Cross-Entropy 163A.3. Efficiency of Estimators 164A.3.1. Complexity 165A.3.2. Complexity of Randomized Algorithms 166Bibliography 169Abbreviations and Acronyms 177List of Symbols 178Index 181