### 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*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*