Splitting Method for Counting and Optimization
Reuven Y. Rubinstein, Ad Ridder, Radislav Vaisman · Wiley series in probability and statistics · 2013
This chapter deals with the splitting method for counting, combinatorial optimization, and rare-event estimation. Two different splitting algorithms for counting are discussed. The first based on a fixed-level set and the second on an adaptive level set. The chapter explains that the splitting method is suitable for solving combinatorial optimization problems, such as the maximal cut or traveling salesman problems, and thus can be considered as an alternative to the standard cross-entropy and MinxEnt methods. It deals with two enhancements of the adaptive splitting method for counting. The first is called the direct splitting estimator and is based on the direct counting of |X*|, while the second is called the capture-recapture estimator of |X*|. The chapter also shows that the splitting algorithm can be efficiently used for estimating the reliability of complex static networks. Finally, it presents supportive numerical results for counting, rare events, and optimization. Controlled Vocabulary Terms Inter-rater reliability; Monte Carlo methods