Felipe Barriga Richards Blog

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

#!/bin/bash

if [ $# -ne 1 ]
then
	echo "Usage: "
	echo -e "\t ${0} solution_name"
	echo -e "\t Example:"
	echo -e "\t\t ${0} ppp"
	exit -1
fi

if [ ! -f $1.txt ]
then
	echo "There is no model file ${1}.txt"
	exit -1
fi

zimpl -t mps -O $1.txt && lp_solve -time -mps -presolve $1.mps  > $1.solution

#!/bin/bash

if [ $# -ne 1 ]
then
	echo "Usage: "
	echo -e "\t ${0} solution_name"
	echo -e "\t Example:"
	echo -e "\t\t ${0} ppp"
	exit -1
fi

if [ ! -f $1.solution ]
then
	echo "There is no solution file ${1}.solution"
	exit -1
fi

if [ ! -f $1.tbl ]
then
	echo "There is no table file ${1}.tbl"
	exit -1
fi

cat $1.tbl | while read a b c src dst
do
	dst2=`echo ${dst} | tr -d '"'`
	if [ ! -z src ]
	then
		if [ ${src:0:1} == "_" ]
		then
			exit 0
		fi
		sed "s/${src}/${dst2}/g" < $1.solution > $1.solution_tmp
		mv -f $1.solution_tmp $1.solution
	else
		exit 0
	fi
done

#!/bin/bash

if [ $# -ne 1 ]
then
	echo "Usage: "
	echo -e "\t ${0} solution_name"
	echo -e "\t Example:"
	echo -e "\t\t ${0} ppp"
	exit -1
fi

if [ ! -f $1.solution ]
then
	echo "There is no solution file ${1}.solution"
	exit -1
fi

rm -f ${1}.simplified_solution
cat $1.solution | while read a b c
do
	if [ ! -z "$a" -a ! -z "$b" ]
	then
		if [ ${a:0:1} != "_" -a $b == "1" ]
		then
			echo "${a} ${b}" >> ${1}.simplified_solution
		fi
	fi
done

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:

More Results