{"id":797,"date":"2009-08-05T14:40:23","date_gmt":"2009-08-05T18:40:23","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=797"},"modified":"2009-08-05T14:40:23","modified_gmt":"2009-08-05T18:40:23","slug":"graph-coloring-benchmark-system","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2009\/08\/05\/graph-coloring-benchmark-system\/","title":{"rendered":"Graph Coloring Benchmark System"},"content":{"rendered":"

For many<\/em> years, I have wanted to put together a system for keeping track of results in solving instances of various combinatorial optimization problems.\u00a0 This started back in the early 1990s when I was the coordinator for the DIMACS Challenge on Cliques, Coloring, and Satisfiability.\u00a0 This was pre-web, so everything was done via ftp and email.\u00a0 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).\u00a0\u00a0 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).<\/p>\n

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

Throughout all this, I was not satisfied with the state of information.\u00a0 What were the best solutions around?\u00a0 Results were scattered throughout the literature, sometimes in hard-to-find places.\u00a0 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.\u00a0 It was not enough for me to collect instances, I had to collect solutions, both values and colorings.\u00a0 And I had to be much more organized about tracking results.\u00a0 I was particularly interested in this since I do that for the Traveling Tournament Problem<\/a>, and I think that has greatly increased interest in the problem.<\/p>\n

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

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.\u00a0 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.\u00a0\u00a0 At this point, I think I can let the world see it, though it is a work in progress.\u00a0 I have grand plans for this, so I have called it ROIS: Registry for Optimization Instances and Solutions.<\/a> Right now, all it has the results from some graph coloring papers along with the instances.\u00a0 As I move along, I will include finding cliques in graphs, the traveling tournament problem, and who knows what else.\u00a0 Now that the basic code is there, it is extremely easy to add in new problems.<\/p>\n

There is a lot more to do.\u00a0 One key aspect that is not yet implemented is the ability to upload solutions and have them checked for correctness automatically.\u00a0 This clearly is a key component of the system and about the only way of keeping “wrong” results out.\u00a0 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.\u00a0 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).<\/p>\n

I’m entering in some of the published work now.\u00a0 Any comments you have on this would be very much appreciated.<\/p>\n","protected":false},"excerpt":{"rendered":"

For many years, I have wanted to put together a system for keeping track of results in solving instances of various combinatorial optimization problems.\u00a0 This started back in the early 1990s when I was the coordinator for the DIMACS Challenge on Cliques, Coloring, and Satisfiability.\u00a0 This was pre-web, so everything was done via ftp and … Continue reading “Graph Coloring Benchmark System”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,46],"tags":[],"class_list":["post-797","post","type-post","status-publish","format-standard","hentry","category-challenges","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/797","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=797"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/797\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=797"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=797"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=797"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}