## gocup p-median

http://github.com/dimatura/gocup-pmed (C++)

In 2008 ISCI organized GOCup, an open
contest aimed at researchers and students which consisted in developing an
algorithm to find solutions to instances of the P-Median problem, a famous
NP-hard problem in Operations Research (OR) and Location Science (an academic
field which I first learned of during this contest).
The algorithms were judged on their speed and the quality of the solutions.

I didn't know much about OR beyond the basics of linear and combinatorial
programming, but after looking at the problem statement it seemed quite
familiar: it's a lot like clustering in machine learning. I could wrap my head
around clustering. After testing various heuristics, the classical Vertex
Substitution Heuristic (VSH) turned out to work best. VSH is actually very
similar to some clustering algorithms out there (e.g.
CLARANS). There was even
some back-and-forth on the original Affinity Propagation paper on whether
it was better than VSH.

Anyway, VSH worked great, and in order to make it faster I implemented a couple
of tricks in the literature (see report in the tarball for references) and
added some of my own fine-tuning. My entry won and I got a nice Sony laptop.

The code is GPLv3. There's a third party bitmap implementation included which
has its own license.