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.

Don’t Forget to Vote!

If you are an INFORMS member (if you are interested in operations research, why aren’t you a member?), you should have received an email yesterday directing you to a website to vote for the next set of members of the Board of Directors.  That email has all the information you need to vote:  your member number and a code word.  You go to the website, enter those two numbers, get a form and spend a minute or two voting.  The candidate bios and platform statements are clickable from the ballot, so you don’t even have to research before hand (though if you want to, the candidate information is available).  A few points:

  • Your vote really does count.  The year before I got elected President, the Presidential vote resulted in a tie.  One extra vote either way would have prevented a run-off.
  • The candidates are chosen by a Nominating Committee (something the Past President chairs), though people can put themselves on the ballot by petition.  The latter used to happen more often:  it seems pretty rare these days.
  • INFORMS uses approval voting, where you can vote for as many candidates as you want for each position.  In many cases, I end up voting for all of the proposed candidates.  This is particularly true if I do not know the candidates, or I know them both equally well, and if I think they will do about equally well in positions.  Sometimes I have stronger feelings, so vote for one (or decidedly don’t vote for one!).  While it is equivalent in terms of the winner to vote for none as to vote for all, in terms of meeting quorum requirements, it is better to vote for all.  By the way, approval voting works much better when there are three or more candidates (or more than one position to be filled from the same set of candidates).  Approval voting to choose the winner between two candidates, as this election is, doesn’t add much (though I like the opportunity to vote for all or, rarely, none).
  • A number of candidates are running unopposed.  INFORMS allows its Vice Presidents to have two terms in a position.  Often, the nominating committee will decide to run someone up for reelection unopposed.  It doesn’t always happen, but it is the norm.
  • INFORMS does not announce number of votes in an election.  I was on the Board when that rule was created (and may even have formulated the rule).  The ideas was to not embarrass candidates who lose a blow-out election.  Now, I am not 100% convinced this is a good rule:  there is information in the votes (for instance, knowing the number who voted for none of the candidates versus those who voted for all).  Even the nominating committee does not know the number of votes, so, for instance, a candidate who came very close to winning might not get nominated again, while a candidate that the electorate soundly rejected might get renominated the next year.  Perhaps it is time for INFORMS to rethink this rule.

I sat on the INFORMS Board for six years, and am now completing six years on the IFORS Board.  Sitting on boards is generally interesting and rewarding (it is sometimes mind-numbingly dull, but I treat that as useful training in discipline).  I have met some really fascinating and wonderful people through the boards, and those contacts have been useful years after our terms ended.

We should be greatful that people are willing to give their time to boards like INFORMS.  If you are a member, now would be a good time to spend a couple minutes voting.