prob013: progressive party problem

proposed by Toby Walsh
tw@cs.york.ac.uk

References

The problem was proposed in The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared , Barbara M Smith, S C Brailsford, P M Hubbard & H P Williams, Research Report 95.8, March 1995. A revised version appears in Proceedings of First International Conference on Principles and Practice of Constraint Programming (CP'95), Springer Verlag LNCS 976, pp 36-52, Cassis, September 1995. A further revised version appears in Constraints, vol. 1, pp. 119-138, 1996. (Abstract)

The problem appears in several other papers.

P. Galinier and J.K. Hao, Solving the progressive party problem by local search. in "Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization", Chapter 29, pp418-432, S. Voss, S. Martello, I.H. Osman and C. Roucairol (Eds.), Kluwer Academic Publishers, 1998.

Organizing a Social Event - A Difficult Problem of Combinatorial Optimisation. Sally C. Brailsford, Peter M. Hubbard, Barbara M. Smith and H. Paul Williams, Computers and Operations Research, 23, pp. 845-856,1996.

Solving Linear Pseudo-Boolean Constraint Problems with Local Search. In Proceedings of the 14th National Conference on Artificial Intelligence, AAAI-97, Providence, RI, 1997. Postscript, Postscript slides. There is also an unpublished appendix with extended experimental results.

Domain-Independent Local Search for Linear Integer Optimization. PhD dissertation accepted by the Technical Faculty of the University des Saarlandes, in October 1998. (abstract. postscript. compressed postscript)