V. Ejov, J. Filar, J. Gondzio
We consider the Hamiltonian cycle problem embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We show that Hamiltonian cycles (if any) correspond to the global minima of a suitably constructed indefinite quadratic programming problem over the frequency space. We show that the above indefinite quadratic can be approximated by quadratic functions that are ``nearly convex" and as such suitable for the application of logarithmic barrier methods. We develop an interior-point type algorithm that involves an arc elimination heuristic that appears to perform rather well in moderate size graphs. The approach has the potential for further improvements.
Key words: Hamiltonian cycles, Markov Decision Processes, Interior Point Methods, Non-convex Optimization.