Computational Combinatorics

Month: December, 2012

Computational Combinatorics Roundup: November-December

We continue our monthly update of collecting research papers (or blog posts!) that were posted in the previous month+\varepsilon (or were missed by previous lists). So far, I’ve just been watching the arXiv updates and my Google Scholar updates. Please comment or send me an email if you have an addition. (You can even tell me about papers when you see them, and I’ll add them to the next one!)

I’ve added my own short synopsis in italics based on a cursory glance through the papers. These are not reviews which verify their correctness or quality.
Read the rest of this entry »

Using TreeSearch for Parallel Computation

The previously described process of combinatorial search was extremely abstract on purpose. All of the computational experiments I design are implemented using TreeSearch. TreeSearch is my own software library for running combinatorial search in a parallel environment. It abstracts the notion of a search tree into a few basic operations, which are then implemented for each individual experiment. This allows the interface for managing thousands of parallel jobs to be common among all of the other projects in my SearchLib software collection.

This library is a C++ implementation of the recursive search, including the augmentation step, pruning, and outputting solutions. In addition, the library manages tracking statistics and distributing independent jobs to a supercomputer. Today, we’ll discuss how to use TreeSearch for your own computational experiment. If you don’t want to use my code, you can use it as an example for how to manage a large number of parallel jobs.
Read the rest of this entry »