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.
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
