### Paul Williams (Mathematics, University of Southampton)

#### The progressive party problem: a difficult problem of combinatorial optimisation

*Friday 18 October 1996 at 13.00, JCMB 6206*

##### Abstract

This somewhat frivolous problem arose when organising a 'progressive party'
party at a yachting rally. The different ways of formulating and solving this
problem, however, led to interesting results concerning the inherent difficulty
of combinatorial problems.

Some yachts were to be designated hosts. The crews of the remaining yachts
would then visit the hosts for successive half-hour periods. A guest crew could
not revisit the same host and two guest crews could not meet each oher more
than once during the evening. Additional constraints were imposed by the
capacities of the host boats and the crew sizes of the guests.

For the uncapacitated problem some results on the minimum number of host
boats needed are provided by number theory. For the constrained problem
(with 39 yachts) integer programming was attempted. The resultant model was
immense. Linear Programming provided a lower bound and heuristics provided an
upper bound but the Integer Programme proved immpossible to solve.
The relatively new technique of Constraint Logic Programming managed to find
the best known solution in less than half an hour, but Linear Programming was
needed to prove optimality. This talk underlines the need for a sophisticated
approach to many combinatorial problems combining clever mathematics with
clever computer science.

### 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*