Numerical methods to solve the Hamiltonian cycle problem
(M Haythorpe, J Filar, V Ejov, G Nguyen and A Eshragh with W Murray, V Borkar and N Litvak)
The Hamiltonian cycle problem (HCP) is an important problem in both graph
theory and computer science. A member of the famous NP-complete set of
problems, any efficient solution to the HCP would have far-reaching benefits
for thousands of other NP-complete problems. A Hamiltonian cycle is a simple
cycle the visits every vertex in a graph. The HCP then is to determine, for
a given graph, if any Hamiltonian cycles exist. One method of approaching
the HCP has been to embed the HCP in a Markov decision processes (MDP)
model, where a controller attempts to navigate a simple cycle through the
graph. Using the techniques available in MDP, we are able to construct
various optimisation models that are equivalent to the HCP. These models are
able to take advantage of the inherant sparsity in the graphs and contain
simple, linear, constraints. Various techniques are used to solve these
models, including branch and bound, interior point method, and mixed integer
solvers. A software package containing a compilation of all of these methods
will be produced.
Publications
Ali Eshragh, Jerzy A. Filar and Michael Haythorpe, A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem, Annals of Operations Research, DOI 10.1007/s10479-009-0565-9.
Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem (to appear in Mathematics of Operations Research)
Funding
ARC (2006 – 2010), “Doubly Stochastic Matrices & The Hamiltonian Cycle
Problem”.
Leading CI: Prof JA Filar, Overseas Investigators: Prof VS Borkar (Tata Institute
of
Fundamental Research, Mumbai, India), Prof W Murray (Stanford University, USA)