M.Sc Student | Kikanian Levon |
---|---|

Subject | Rare Events for Determenistic and Stochastic Combinatorial Optimization Problems |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Emeritus Reuven-Yacov Rubinstein (Deceased) |

The Cross Entropy (CE) method for combinatorial optimization presents an
adaptive algorithm based on a random mechanism that transforms a deterministic
network into a stochastic one called the associated stochastic network. Incorporating
randomness in a given problem makes it possible to cast a given *combinatorial
optimization problem* onto the rare event probability estimation framework. Depending
on a particular problem we introduce the randomness in associated stochastic
network by making either (a) the nodes **V** random or (b) the edges **E**
random. More specifically, in the CE method we clearly differentiate between
the so called (a) *stochastic node networks* and (b) *stochastic edge
networks*.

We show empirically that after some finite number of iterations the CE
Algorithm will be able to *identify* with very high probability a very
small subset of the smallest tour values. In what follows, we shall show that *combinatorial
optimization problems can be solved simultaneously* with estimation of the
probabilities of rare events for associated stochastic network. This framework
enables us to establish tight connections between rare events and combinatorial
optimization.

In the class of problems which belong to *stochastic node networks*
we deal with the maximal cut problem, partition problems and maximum clique
problem, their associated stochastic networks and a number of algorithms for
generation of random cuts, partitions and cliques using **Bernoulli(p)**
distribution.

Considering the class of problems belonging to *stochastic edge
networks* we apply the CE method to deterministic and stochastic longest
path problem, traveling salesman problem and quadratic assignment problem.
Numerous modifications of the main CE algorithm were tested showing its robustness
and flexibility in solving different classes of problems. In numerous tables
and figures we present results of algorithm runs including case studies for
traveling salesman problem and quadratic assignment problem. The results
present the relative performance of CE method with artificially generated
problems and standard test problems available in the internet showing very good
performance in terms of relative errors (compared to the best known ones) of
the solutions obtained.

Our numerical studies suggest that in both stochastic node network and stochastic edge network cases the proposed CE method typically has polynomial complexity in the size of the network.