Hamiltonian Cycles And The Space Of Discounted Occupational Measures: Investigating Hamiltonian Cycles Through Extreme Points Of Certain Polytopes By Random Walks

In 2000, a new polytope defined by the Discounted Occupational Measures (DOM) was developed for the Hamiltonian Cycle Problem (HCP). In this monograph, we exploit geometric properties of extreme points of that polytope. In particular, we refine the feasible region induced by that polytope into a narrower one. We show that the problem of finding a Hamiltonian cycle in a given graph is equivalent to the problem of finding a common extreme point of two especially constructed polytopes. Correspondingly, we develop new optimization models, as well as, random walk algorithms, to solve HCP. In addition, we develop a new hybrid algorithm for the HCP by synthesising DOM and the Cross Entropy method. Finally, we present algebraic properties of the class of stochastic matrices induced by a Hamiltonian cycle. These theoretical results are used to develop a new polytope containing all possible Hamiltonian solutions corresponding to a given graph.

Dr Ali Eshragh received his B.Sc. and M.Sc. in industrial engineering from Sharif University of Technology, Tehran. In 2008, he was awarded the IPRS scholarship to pursue his PhD at the University of South Australia, Adelaide. He received his PhD in August, 2011. He is currently a postdoctoral research fellow at the University of Adelaide.