Graph Coloring Benchmark System

For many years, I have wanted to put together a system for keeping track of results in solving instances of various combinatorial optimization problems.  This started back in the early 1990s when I was the coordinator for the DIMACS Challenge on Cliques, Coloring, and Satisfiability.  This was pre-web, so everything was done via ftp and email.  During that Challenge, David Johnson and I collected a large number of instances suitable for finding cliques and graph coloring (I also collected a number of satisfiability instances).   Lots of people tried a number of methods on these instances, and they became the “DIMACS Instances”, and have appeared in many, many papers (the resulting DIMACS volume is by far my most referenced work).

In 2002, David and I joined with Anuj Mehrotra to run some further workshops with an emphasis on graph coloring.  In 2008, a special issue of Discrete Applied Mathematics came out with ten or so papers from those workshops.

Throughout all this, I was not satisfied with the state of information.  What were the best solutions around?  Results were scattered throughout the literature, sometimes in hard-to-find places.  Worse, there seemed to be some inconsistencies (feasible solutions with values better than lower bounds) and no clear way of determining where the fault lay.  It was not enough for me to collect instances, I had to collect solutions, both values and colorings.  And I had to be much more organized about tracking results.  I was particularly interested in this since I do that for the Traveling Tournament Problem, and I think that has greatly increased interest in the problem.

But life is busy, and I never quite got around to putting the system together.  When I spent a year in New Zealand, I did some work on it, but moved on to other things.  I couldn’t get a doctoral student interested in it, so things kinda lay fallow.

A few days ago, the file I had on this churned to the top of the stack, and I refound the code I was working on.  And, while I do have some really pressing things to do (both editorial and survey article writing), I have spent some time advancing the code.   At this point, I think I can let the world see it, though it is a work in progress.  I have grand plans for this, so I have called it ROIS: Registry for Optimization Instances and Solutions. Right now, all it has the results from some graph coloring papers along with the instances.  As I move along, I will include finding cliques in graphs, the traveling tournament problem, and who knows what else.  Now that the basic code is there, it is extremely easy to add in new problems.

There is a lot more to do.  One key aspect that is not yet implemented is the ability to upload solutions and have them checked for correctness automatically.  This clearly is a key component of the system and about the only way of keeping “wrong” results out.  It is unclear how to handle lower bounds in the same way due to the lack of a succint certificate, but even handling one side is better than nothing.  I also need to add lots of things for sorting columns in different ways, but that is all pretty trivial (a good project for lazy mornings).

I’m entering in some of the published work now.  Any comments you have on this would be very much appreciated.