## 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:

- Model: ppp.txt
- Data (8 boats, 2 periods): ppp_008_2.txt

## 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

## 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 |

## 0 Comments until now

## Add your Comment!