ORGANIZING A SOCIAL EVENT - A DIFFICULT PROBLEM OF COMBINATORIAL OPTIMIZATION

This interesting problem arose in the context of organizing a ''progre ssive party'' at a yachting rally. Some yachts were to be designated h osts; the crews of the remaining yachts would then visit the hosts for six successive half-hour periods. A guest crew could not revisit the same host, and two guest crews could not meet more than once during th e evening. Additional constraints were imposed by the capacities of th e host yachts and the crew sizes of the guests. Although this problem has many of the classical features of combinatorial optimization probl ems, it does not belong to any previously known class of problem. Inte ger programming formulations which included all the constraints result ed in very large models and all attempts to find a solution failed. Ho wever by solving a simple relaxation of the problem using linear progr amming we obtained a lower bound for the solution, which combined with a feasible solution obtained (spectacularly easily) by constraint pro gramming led to an optimal solution. We describe our computational exp erience and discuss the features of this problem which account for the failure and success of the two approaches. Copyright (C) 1996 Elsevie r Science Ltd