Graph Coloring Benchmark Instances

Graph Coloring Benchmark Instances が以下のサイトからまとめて入手できます。以前（１９９０年代）は小さなインスタンスしか無かったのですが、かなり量とグラフの規模が大きくなったように思います。

Graph Coloring Benchmark Instances

例えば school1 は以下の規模（点数と枝数）になっています。
c FILE: school1.col
c
c Source: Gary Lewandowski (lewandow@cs.wisc.edu)
c Description: Class Scheduling Graph
c Final Schedules, all courses
c
p edge 385 19095

これらの SDP 緩和問題を解くと以下のような結果が出ます。

20 7.4e-11 3.5e-17 1.3e-19 +1.40e+01 +1.40e+01 1.0e+00 9.7e-01 1.00e-01

phase.value = pdOPT
Iteration = 20
mu = +7.4222480758903522e-11
relative gap = +2.0411523886283036e-09
gap = +2.8576133459523589e-08
digits = +8.6901245704579519e+00
objValPrimal = +1.4000000023462954e+01
objValDual = +1.3999999994886821e+01
p.feas.error = +3.5527136788005009e-15
d.feas.error = +5.0381731343430767e-15
total time = 1080.868564
main loop time = 1080.592744
total time = 1080.868564
file check time = 0.000000
file change time = 0.004132
file read time = 0.271688
SDPA end at [Tue Apr 8 13:51:54 2014]
ALL TIME = 1095.360062