|
|
|
|
|
|
|
We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of state-action frequencies induced by the MDP's stationary policies. In recent years, this approach to the HCP has led to a number of alternative formulations and algorithmic approaches involving researchers from a number of countries including the authors and A. Rubinov, from Australia. In this lecture we focus on a specific embedding due to E. Feinberg from SUNY at Stony Brook. The latter leads to a suitably constructed indefinite quadratic programming problem over a polytope. It is known that whenever a given graph possesses Hamiltonian cycles all global minima of this indefinite program are attained at extreme points of the feasible region induced by these cycles. Also, the nonnegative objective function attains the lower bound of zero at these global minima. We present a Branch & Bound type algorithm that solves the HCP (and in the process the above global optimisation problem for Hamiltonian graphs). At each branch of the algorithm, only a linear program needs to be solved and the dimensions of the successive linear programs are shrinking rather than expanding. We present a theoretical argument demonstrating that an upper bound on the number of nodes of the branch-and-bound tree is much smaller than what might have been expected. Finally, we present some numerical results. This is a joint work with V. Ejov, M. Haythorpe, and G. Nguyen.
|
|
|
|
|
|
|
|