The Progressive Party Problem

A specification of the problem.. A collection of six variations of the progressive party problem in pseudo-boolean encoding, as described in Solving Linear Pseudo-Boolean Constraint Problems with Local Search. All problems contain boat capacities/crew sizes from (Smith et. al, 1996), but the selected host boats differ.

1.15M compressed tar file containing six `.opb' files (an equation format suitable for lp_solve, clp(PB) and WSAT(PB)). The tar archive contains

a) Hosts 1-12,16 (file ppp:1-12,16.opb)

b) Hosts 1-13 (the original problem)

c) Hosts 1,3-13,19 (file ppp:1,3-13,19.opb)

d) Hosts 3-13,25,26 (file ppp:3-13,25,26.opb)

e) Hosts 1-11,19,21 (file ppp:1-11,19,21.opb)

f) Hosts 1-9,16-19 (file ppp:1-9,16-19.opb)

The following paragraphs describe the background and history of the problem and were kindly provided by  H.P. Williams:

The problem was first stated by Peter Hubbard, computing officer in the
Mathematics department at Southampton University. Peter belongs to the
Sea Wych Owners Association and was at that time the Bembridge Rally
Organiser for this Association based at Bembridge in the Isle of
Wight,the island off the South Coast of England.He is now editor of
the Association Magazine.

Peter had to solve the problem stated below which he did heuristically
(and non optimally) but thought it would be interesting to see if
there were a better solution. He suggested it to H.P.Williams (Professor
of Operational Research) who formulated as an Integer Programme
Paul then suggested to Sally Brailsford that she try and solve it using a
commercial package.They quickly realised that it was a difficult model
to optimise and experimented with reformulations,relaxations and
ingenious cutting planes.In this way they managed to show, quite
easily, that a solution using only 12 Host boats was impossible but
were unable to prove (using all the most sophisticated harware,software
and techniques of Integer Programming) to find a solution using 13
Host boats or prove it impossible.Barbara Smith then managed to do
this using ILOG SolverILOG Solver although this does not seem a viable
method of PROVING  optimality. It also seems to be 'non-robust' in
some circumstances.

The problem therefore remains a 'challenge' but is very valuable in
highlighting the links between Constraint Logic Programming and Integer
Programming. . The problem was written up in :

S.C.Brailsford,P.M.Hubbard,B.Smith and H.P.Williams,
The Progressive Party Problem:A Difficult Problem of Combinatorial
Optimisation,Computers and Operations Research 23(1996) 845-856

The problem has now been looked at by many people following talks by
Sally Brailsford,Paul Williams and Barbara Smith.