Progressive Party


This is a benchmark problem which was introduced in 1995 by Brailsford, S., Hubbard, P., Smith, B., Williams, H.: Organizing a social event – a difficult problem of combinatorial optimization. Computers Ops Res 23 (1996) 845–856. The problem is to organize a party at a yachting club over multiple time periods. Some of the boats in the club are designated as host boats, their owners stay on their boats during the whole party and expect visitors from other boats. For safety reasons, each host boat has a guest capacity, which may not be exceeded. The teams coming from the non-host boats stay together, and move in each time period, never visiting a host boat twice. The idea is for each host team to meet new people in each time period. In order to improve interaction between teams even further, two guest teams may only meet once, i.e. if they have been assigned to the same host boat in some time period, they may not meet again in another time period, even at another host boat. In the original problem, the party was scheduled for six time periods (of 30 minutes duration), improved results allow us to extend the party to ten time periods.

Party Time!

When this problem was presented initially, it was a show-case application for constraint programming, as earlier attempts to solve the problem with Integer Programming had failed, while the constraint solution was obtained in 26 minutes. Later improvements reduced the execution times significantly, but also found solutions with Integer Programming. The best current results were reported for a constraint-based local search method in Van Hentenryck, P., Michel, L.: Constraint-Based Local Search. MIT Press, Boston (2005)

To learn more

My short note in the 2009 CPAIOR conference Progress on the Progressive Party Problem presents some current results for ECLiPSe. More details and some model variants are used in chapter 10 of my ECLiPSe ELearning course.

Advertisements

About hsimonis

Researcher at the Insight Centre for Data Analytics, University College Cork, Ireland
This entry was posted in 2009, benchmark, CP-AI-OR, ECLiPSe, Personnel. Bookmark the permalink.

3 Responses to Progressive Party

  1. Alastair Andrew says:

    Hi Helmut,

    Great blog, I’m really enjoying your postings. One question, I thought the first reference to the PPP was in B. M. Smith, S. C. Brailsford, P. M. Hubbard, and H. P. Williams. The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared. Constraints, 1(1–2):119–138, Sept. 1996. available from here. That’s certainly the citation I see more commonly in the literature. Barbara Smith’s homepage seems to indicate that the work appeared as a Technical Report then a paper at CP 95 and finally was revised to become the article in the Constraints journal.

    • hsimonis says:

      Note: I fixed a HTML mismatch in the previous comment.

      On the topic, I’m still waiting for clarification. As both papers have the same set of authors, the question of precedence is perhaps not that pressing. I also seem to recall that I found some detail of some side constraints only in one of the papers.

    • Barbara Smith says:

      Alastair is quite right. The first paper on the PPP is the one that eventually appeared in the Constraints journal. The journal paper was a revision of one that had been published in the proceedings of the Constraint Programming conference in 1995, and had previously been presented at a couple of workshops. That paper gives the constraint programming point of view. The other paper, that appeared in Computers and Operations Research, gives a more OR point of view, and the journal paper was the first version of that. It may have appeared in print before the Constraints paper, though in the same year (I can’t now remember). But in my view, the Constraints paper is the one that introduced the problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s