# HAMILTONIAN CYCLES, CONTROLLED MARKOV CHAINS AND NONCONVEX OPTIMIZATION

##
Jerzy A. Filar

### University of South Australia

### Résumé:

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.