eaf (version 1.0)

gcp2x2: Metaheuristics for solving the Graph Vertex Coloring Problem

Description

Two metaheuristic algorithms, TabuCol (Hertz et al., 1987) and simulated annealing (Johnson et al., 1991), to find a good approximation of the chromatic number of two random graphs. The data here has the only goal of providing an example of use of eafplot for comparing algorithm performance with respect to both time and quality when modelled as two objectives in trade off.

Usage

data(gcp2x2)

source

M. Chiarandini (2005). Stochastic local search methods for highly constrained combinatorial optimisation problems. Ph.D. thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany. page 138.

Details

Each algorithm was run 10 times per graph registering the time and iteration number at which a new best solution was found. A time limit corresponding to 500*10^5 total iterations of TabuCol was imposed. The time was then normalized on a scale from 0 to 1 to make it instance independent.

References

A. Hertz and D. de Werra. Using Tabu Search Techniques for Graph Coloring. Computing, 1987, 39(4), 345-351.

D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon. Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning. Operations Research, 1991, 39(3), 378-406

Examples

data(gcp2x2)
## maybe str(gcp2x2)