KCTLIB -- Best known solutions

Best known solutions for:

• the benchmark set by Blesa and Xhafa [1] generated using a software tool by Jørnsten and Løkketangen [3]
• the benchmark set by Blum and Blesa [2]

Best known solutions for the benchmark set by Blesa and Xhafa

The state-of-the-art results for this benchmark set are currently obtained by the ACO approach by Blum and Blesa [2]. The best known solution values and the results of this ACO approach are shown in the table below. All the results are for cardinality 20 (the reasons are historical: these 35 graphs have always been solved for this cardinality). However, the running times and the standard deviation (10 trials for every problem) of the ACO approach indicate that nowadays for cardinality 20 these problems are not really a challenge. The application of bigger cardinalities might be interesting.

	Best	ACO
Instance	Known	Best	Average		Avg. Time
g25-4-01.dat	219	219	219	0	0.006
g25-4-02.dat	607	607	607	0	0.005
g25-4-03.dat	464	464	464	0	0.005
g25-4-04.dat	620	620	620	0	0.018
g25-4-05.dat	573	573	573	0	0.018
g50-4-01.dat	460	460	460.399	1.264	0.186
g50-4-02.dat	421	421	421	0	0.029
g50-4-03.dat	565	565	565.299	0.948	0.245
g50-4-04.dat	434	434	434	0	0.016
g50-4-05.dat	387	387	387	0	0.073
g75-4-01.dat	366	366	366	0	0.073
g75-4-02.dat	295	295	295	0	0.397
g75-4-03.dat	412	412	412	0	0.576
g75-4-04.dat	430	430	430	0	0.491
g75-4-05.dat	284	284	284	0	0.014
g100-4-01.dat	363	363	364.5	2.415	0.526
g100-4-02.dat	335	335	335.3	0.948	0.318
g100-4-03.dat	412	412	412	0	0.016
g100-4-04.dat	442	442	442	0	0.028
g100-4-05.dat	388	388	388	0	0.627
g200-4-01.dat	308	308	308	0	0.105
g200-4-02.dat	299	299	299	0	0.092
g200-4-03.dat	300	300	300	0	0.048
g200-4-04.dat	304	304	304	0	0.465
g200-4-05.dat	357	357	357	0	0.053
g400-4-01.dat	253	253	253	0	0.084
g400-4-02.dat	328	328	334.3	8.367	1.028
g400-4-03.dat	302	302	302.1	0.316	0.721
g400-4-04.dat	306	306	306	0	1.131
g400-4-05.dat	320	320	320.5	1.581	1.675
g1000-4-01.dat	263	263	265.199	2.529	5.25
g1000-4-02.dat	281	281	283.399	3.098	3.729
g1000-4-03.dat	289	289	289	0	1.022
g1000-4-04.dat	298	298	298	0	2.248
g1000-4-05.dat	268	268	268	0	0.372

Best known solutions for the benchmark set by Blum and Blesa

We provide 20 text files containing the best known solutions for the benchmark graphs by Blum and Blesa. All graphs are solved for several cardinalities ranging over the whole range of possible cardinalities. (Last update: January 19, 2006.)

• bb15x15_1.gg
• bb15x15_2.gg
• bb45x5_1.gg
• bb45x5_2.gg
• bb33x33_1.gg
• bb33x33_2.gg
• bb100x10_1.gg
• bb100x10_2.gg
• bb50x50_1.gg
• bb50x50_2.gg
• g400-4-01.g
• g400-4-05.g
• g1000-4-01.g
• g1000-4-05.g
• steinc5.g
• steind5.g
• steinc15.g
• steind15.g
• steine5.g
• le450_15a.g

• Bibliography