|
|
|
|
|
|
|
One may encounter the Hamiltonian Cycle problem (HCP) in early youth trying to solve the famous ``Knight's tour puzzle'' : start at any square of the $8\times 8$ chess board visit every other square once and only once and return to the starting square. The solution was given by Euler in 1759 which may be regarded as the beginning of the era of HCP: given a graph, find a simple cycle that contains all vertices of the graph (Hamiltonian cycle (HC)) or prove that HC does not exist. With respect to this property - Hamiltonicity - graphs possessing HC are called Hamiltonian (The name of the problem owes to the fact that Sir William Hamilton investigated the existence of such cycles on the dodecahedron graph).
The HCP is known to be NP-hard and has become a challenge that attracts mathematical minds both in its own right and because of its close relationship to the famous Travelling Salesman Problem (TSP). An efficient solution of the latter would have an enormous impact in operations research, optimization and computer science. However, from a mathematical perspective, the underlying difficulty of the TSP is perhaps hidden in the Hamiltonian Cycle problem. Hence we focus on the latter. We consider HCP and the Hamiltonicity property by studying them from two, separate (yet related) analytical perspectives:
I. Hamiltonicity and Singularly Perturbed Controlled Markov Chains (CMC's)
II. Hamiltonicity and Parametric Nonconvex Optimization
Many of the successful classical approaches of discrete optimisation focus on solving a linear programming ``relaxation'' followed by heuristics that prevent the formation of sub-cycles. In our approach, we embed a given graph in a singularly perturbed CMC in such a way that we can identify Hamiltonian cycles with irreducible Markov chains and sub-cycles with non-exhaustive ergodic classes. Indirectly, this allows us to search for a Hamiltonian cycle in the frequency space of a CMC that is a ``nice'' polytope with a non-empty interior, thereby converting the original discrete problem to a continuous one.
The above embedding led to both theoretical insights and new computational approaches. If this approach continues to evolve successfully this may be one of the first times where dynamic, stochastic, control methods are used to treat a famous static optimisation problem.
|
|
|
|
|
|
|
|