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:
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.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
