טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentVaisman Radislav
SubjectStochastic Enumeration Methods for Counting, Rare-Events
and Optimization
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Ofer Strichman
Professor Emeritus Reuven-Yacov Rubinstein (Deceased)
Full Thesis textFull thesis text - English Version


Abstract

In this research thesis we present a series of papers that deal with problems under a rare events settings. Main results obtained are:


1. A generic randomized algorithm, called the splitting is presented. The latter is used for combinatorial optimization, counting and sampling uniformly on complex sets, such as the set defined by the constraints of an integer program. We adopt the classical randomized algorithm scheme that uses a sequential sampling plan to decompose a "difficult " problem into a sequence of "easy " ones. The splitting combines Markov Chain Monte Carlo (MCMC) sampler and specially designed splitting mechanism. Our algorithm runs in parallel multiple Markov chains by making sure that all of them run in steady-state at each iteration.


2. We present an adaptation of the well-known Permutation Monte Carlo (PMC) method for estimation rare events in flow networks. PMC was originally developed for reliability networks, but, as we show in our last article, can be successfully adapted for stochastic flow networks, and in particular for estimation of the probability that the maximal flow in such a network is above some fixed level, called the threshold.

3. Finally, we present a new generic stochastic enumeration (SE) algorithm

for counting #P complete problems such as the number of satisfiability assignments and the number of perfect matchings (permanent). We show that SE presents a natural generalization of the classic sequential algorithm in the sense that it runs in parallel multiple trajectories instead of a single one and employs a polynomial time decision making oracle to prevent the exploration of empty trajectories (dead ends) and thus overcomes the difficulty of the rare events.