A fast p-median solver.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
doc
.gitignore
COPYING
Makefile
README
README.md
SConstruct
bitarray.h
bitasm-amd64.h
bitasm-i386.h
bitasm.h
bitsperlong.h
bloomclimber.cc
bloomclimber.hh
city.hh
coordenadas1.txt
coordenadas2.txt
coordenadas3.txt
coordenadas4.txt
dataloader.cc
dataloader.hh
demandas1.txt
demandas2.txt
demandas3.txt
demandas4.txt
distancematrix.cc
distancematrix.hh
eda.cc
eda.hh
extramatrix.hh
glhillclimber.cc
glhillclimber.hh
gocup_data.hh
hillclimber.cc
hillclimber.hh
lineiterator.cc
lineiterator.hh
options.cc
options.hh
pmedian.cc
pmedproblem.cc
pmedproblem.hh
pmedsolver.cc
pmedsolver.hh
run_gocup.sh
sampleinitializer.cc
sampleinitializer.hh
solution.cc
solution.hh
utils.cc
utils.hh
vns.cc
vns.hh
vshop.cc
vshop.hh

README.md

gocup-pmed

author: Daniel Maturana (dimatura@puc.cl)

A fast implementation of the vertex substitution heuristic for the p-median problem. Various of the optimizations suggested by M. Resende y R. Wernicke ('On the implementation of a swap based local search procedure for the p-median problem', Proceedings of the fifth workshop on Algorithm Engineering, 2003) were used.

This implemenentation won the GOCUP 2008 contest.

Compilation and usage

The program was developed in C++ using GNU g++ in Ubuntu Linux Hardy Heron. It was also verified to compile and run under Windows XP using the GNU MingW toolchain. It has no external library dependencies. To compile, simply run make. The program is named pmedian and accepts various arguments. The simplest usage is "pmedian " where number is the problem to solve. It includes various more options which can are documented in the help message which is displayed with "pmedian -h".

Credits

The project includes Joerg Arndt's bitarray implementation, which is part of the FXT library. The library is under GPLv3 as well.

TODO

While the algorithm is implemented for the general case, the data loading code is specialized for the contest format, which is 2-D. During development I tested on the classical ORLIB instances, after applying the Floyd-Warshall algorithm. I'll eventually reincorporate the code to read the ORLIB format.