Marco Colombo (University of Edinburgh)

A branch-and-cut approach to solve the Hamiltonian cycle problem
Wednesday 10 March 2004 at 15.30, JCMB 6206

Abstract

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.

Seminars by year

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