טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentLevon Kikanian
SubjectRare Events for Determenistic and Stochastic Combinatorial
Optimization Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Emeritus Rubinstein Reuven-Yacov (Deceased)


Abstract

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.