Online compendium to the article: Algorithm Selection for the Graph Coloring Problem

Nysret Musliu, Martin Schwengerer

Learning and Intelligent OptimizatioN Conference (LION 7), Catania - Italy, Jan 7-11, 2013. Lecture Notes in Computer Science, to appear.

Abstract

We present an automated algorithm selection method based on machine learning for the graph coloring problem (GCP). For this purpose, we identify 78 features for this problem and evaluate the performance of six tate-of-the-art (meta)heuristics for the GCP. We use the obtained data to train several classiffication algorithms that are applied to predict on a new instance the algorithm with the highest expected performance. To achieve better performance for the machine learning algorithms, we investigate the impact of parameters, and evaluate different data discretization and feature selection methods. Finally, we evaluate our approach, which exploits the existing GCP techniques and the automated algorithm selection, and compare it with existing heuristic algorithms. Experimental results show that the GCP solver based on machine learning outperforms previous methods on benchmark instances.

Download article [bib]

Instances

Experimental Results

Heuristic Performance: Results of the evaluation on the instances. The result for an heuristic is the lowest number of colors for that a feasible coloring has been found in more than 50% of the runs. In addition, we add the best and worst result of the two greedy methods (RLF and DSATUR) and the best known solution (BKS) found so far.

Attributes: Basic attributes of the instances. Note that some values (e.g. regarding the greedy methods or local search probing) are extracted using random components.

Hardness Classification

Depending on the results of our evaluation, we classify each instance into one of the following categories:

• trivial, contains instances where we already get the best known solution during the computation of features,
• trivial2: all instances where, starting with the color number obtained by the greedy algorithms, no further improvements can been found by any search algorithm,
• easy: instances where the heuristics find better solutions than the greedy methods, but these results are found by at least 50% of the solvers and in at most 5 seconds,
• hard: all other instances which do not belong to one of the introduced categories are categorized as hard.

ARFF-Files

ARFF-files contain the attributes and the best heuristic for each instance. Note that for the algorithm selection, we focus on only on hard instances.

[1] Marco Chiarandini   Thomas Stützle, An Analysis of Heuristics for Vertex Colouring, In Ed. P. Festa, Proceedings of the 9th International Symposium on Experimental Algorithms 2010,
Lecture Notes in Computer Science, Springer

For more informations, contact me under: mschweng at kr.tuwien.ac.at