Introduction

Here is a model to solve the Progressive Party Problem using ZIMPL as the modeling language and lp_solve as the solver. This model is to minimize the number of host boats.

Model

The model need optimizations but it works. The data is separated from the code so is easy to change the instance to test. You only need to change 4 lines in the code and replace the instance. All the files are .txt because wordpress don’t allow me to upload files with other extensions. Originally the model is .zpl and the data is .dat

Model:

Results

After running ZIMPL and lp_solve a solution file will be created and then parsed with the scripts that are in another section of this page. I do several test changing the params of lp_solve and you can check the results on the “Benchmark parameters” section. The only instance that I can resolve is the one with 8 boats and 2 periods, the other take to much time.

Then you can see the solution file (I remove some lines without useful information with the script simplify_solution.sh):

isGuest$boat1 1
isGuest$boat3 1
isGuest$boat4 1
isGuest$boat6 1
isHost$boat2 1
isHost$boat5 1
isHost$boat7 1
isHost$boat8 1
visit$boat1$boat2#1 1
visit$boat1$boat5#2 1
visit$boat3$boat2#2 1
visit$boat3$boat5#1 1
visit$boat4$boat2#1 1
visit$boat4$boat7#2 1
visit$boat6$boat5#2 1
visit$boat6$boat7#1 1
meet$boat1$boat4#1 1
meet$boat1$boat6#2 1
meet$boat3$boat1#2 1
meet$boat4$boat1#1 1
meet$boat6$boat1#2 1

After interpreting it this is what you get:

Host:  2 5 7 8
Guest: 1 3 4 6

Visits:
boat1: 2 5
boat3: 5 2
boat4: 2 7
boat6: 7 5


If you see there is no error on the solution but there is a problem in the model because it says that boat3 meet boat1 in period 2 (meet$boat3$boat1#2 1) and that isn’t true ! If someone find the solution please send an email.

Complementary Scripts

 

Spoiler Inside: Translate model and execute solver: solve.sh SelectShow

 
Spoiler Inside: Replace the variables name on solution file: translate.sh SelectShow

 
Spoiler Inside: Simplify the solution file: simplify_solution.sh SelectShow

 

Benchmark of lp_solve params

I make some test to see how the different parameters affect the speed of lp_solve. The instance tested is the one with 8 boats and 2 periods under a Core 2 Duo at 1.73GHz. Also I try replacing the constrain “forall in Boat – {guest} do” with “forall in Boat with (guest != host) do”. Here is a table showing the results:

    constrain             params           CPU time [in seconds]  
(guest != host) none 197.72
(guest != host) -presolve 104.58
(guest != host) -Bd 659.82
(guest != host) -Bd -presolve 786.86
Boat – {guest} none 242.47
Boat – {guest} -presolve 76.2
Boat – {guest} -presolvem 95.17
Boat – {guest} -presolveq 150.51
Boat – {guest} -presolves 171.44
Boat – {guest} -presolvel 171.84
Boat – {guest} -presolver 225.69
Boat – {guest} -presolvecold 242.02
Boat – {guest} -presolvek 244.67
Boat – {guest} -presolvefd 247.02
Boat – {guest} -presolverowd 248.04
Boat – {guest} -presolvebnd 249.06
Boat – {guest} -presolveb 250.35


More Results

    boats         periods         min hosts found         time [seconds]             instance file        
4 1 2 0.01 ppp_004_1.txt
5 1 2 0.1 ppp_005_1.txt
6 1 3 0.15 ppp_006_1.txt
7 1 3 3.69 ppp_007_1.txt
8 2 4 76.2 ppp_008_2.txt
9 3 ? ? ppp_009_3.txt
10 2 ? ? ppp_010_2.txt
21 6 ? ? ppp_021_6.txt