M.Sc Thesis | |

M.Sc Student | Libster Alexander |
---|---|

Subject | Entropy and Cloning Methods for Rare Events, Counting and Optimization |

Department | Department of Industrial Engineering and Management |

Supervisors | PROFESSOR EMERITUS Reuven-Yacov Rubinstein (Deceased) |

PROF. Leonid Mytnik | |

Full Thesis text |

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.