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.