טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentDolgin Andrey
SubjectRandomized Algorithms with Splitting
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Emeritus Reuven-Yacov Rubinstein (Deceased)
Professor Leonid Mytnik
Full Thesis textFull thesis text - English Version


Abstract

We present a new generic randomized algorithm, called the splitting or cloning algorithm, for combinatorial optimization, counting and sampling uniformly on complex sets, such as the set defined by the constraints of an integer program. Similar to the original classic randomized algorithms our one uses a sequential sampling plan to decompose a "difficult" problem into a sequence of "easy" ones. It presents, in fact, a combination of MCMC (Markov Chain Monte Carlo), like the Gibbs sampler, with a specially designed splitting mechanism. The latter runs in parallel multiple Markov chains by making sure that all of them run in steady-state at each iteration.

Main results obtained are:


1. We show that the splitting algorithm can be efficiently used not only for optimization and counting but for generating uniform samples on discrete sets. Without introducing a proper splitting mechanism, MCMC fails. Thus, in spite of the common consensus on the classic MCMC as being a universal tool for generating samples on complex sets, we found that it fails to generate points uniformly distributed on discrete sets, such as the set defined by the constraints of an integer program. We provide valid statistical tests supporting the uniformity of generated samples by the splitting method.

2. We show how to incorporate the classic capture-recapture method into the splitting algorithm in order to obtain a low variance estimator for the counting quantity representing, say the number of feasible solutions on the set of the constraints of an integer program.

3. We present a combined version of the splitting and cross-entropy (CE) algorithms and provide some complexity results.

4. We present supportive numerical results, while solving quite general counting problems, like counting the number of satisfiability assignments in a SAT problem, counting the number of feasible colorings in a graph, calculating the permanent, the number of Hamiltonian cycles, the number of 0-1 tables, and calculating the volume of a polytope, as well as solving integer and combinatorial optimization, like TSP, knapsack and set-covering problems.