### Jacek Gondzio (University of Edinburgh)

#### Hamiltonian cycle problem, Markov decision processes and interior point methods

*Joint work with Vladimir Ejov and Jerzy Filar (University of South Australia).*

*Wednesday 8 May 2002 at 15.30, JCMB 6309*

##### Abstract

The Hamiltonian Cycle Problem (HCP) consists in finding a cycle in a
directed graph that enters every node exactly once, or determine that no such
cycle exists. A new approach to HCP is discussed. It is built upon:

- embedding the problem in a Markov Decision Process;
- reformulating the problem to a non-convex quadratic program;
- solving the latter with an interior point method.

The well-known example of HCP is the Knight's Tour Problem. It consists
in finding a cycle of the Knight through the k*k chessboard visiting every
square exactly once. We have applied our approach to solve a number of such
problems with the size of the board reaching 32*32.

Although at the moment our approach is an intellectual exercise rather
than the practical method for HCP, we have not lost hope to make it
competitive. In this talk we will report on the progress made so far.
In particular, we will discuss the use of interior point method for solving
non-convex quadratic programs and the use of interior point method within
the Branch and Bound procedure. Both these issues are crucial to make our
approach viable.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*