The Hamiltonian Cycle Problem (HCP) is the problem to find a cycle in a graph such that all vertices are visited exactly once. This problem is easily stated, but unfortunately it's an extremely difficult integer programming problem.
In this talk I will present a nonconvex quadratic formulation of the HCP, together with the Branch-and-Cut framework that guides the interior-point solver towards an integer solution.
A preliminary implementation exists, and numerical results are given for different types of cutting planes. The results suggest that the nonconvex quadratic formulation outperforms a linear formulation for large scale problems.
Current 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
