M.Sc Thesis

M.Sc StudentLibster Alexander
SubjectEntropy and Cloning Methods for Rare Events, Counting
and Optimization
DepartmentDepartment of Industrial Engineering and Management
Supervisors PROFESSOR EMERITUS Reuven-Yacov Rubinstein (Deceased)
PROF. Leonid Mytnik
Full Thesis textFull thesis text - English Version


We present the so-called indicator-based minimum cross-entropy and the MCMC methods for combinatorial optimization (COP's), counting,

sampling and rare-event probability estimation as well as we present some new material including a new cloning algorithm and using CE for multi- event case and for constrained optimization problems. The main idea of the indicator-based minimum cross-entropy method, called the indicatorMinxEnt, or simply IME, is to associate with each counting or optimization problem an auxiliary single-constrained convex MinxEnt program of a spe- cial type, which has a closed-form solution. The main idea of the MCMC approach is to design a sequential sampling plan, where the “difficult" problem of estimating rare-event probability and counting the cardinality of a set is decomposed into “easy" problems of counting the cardinality of a sequence of related sets. Here we also propose a new algorithm, called the cloning algorithm. The main differences between the existing and the proposed algorithm is that the latter one has a special device, called the “cloning" device, which makes the algorithm very fast and accurate. We present efficient numerical results, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT and Hamiltonian cycles.