R: Metaheuristics for solving the Graph Vertex Coloring Problem
gcp2x2
R Documentation
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)
Format
A data frame with 3133 observations on the following 6 variables.
alg
a factor with levels SAKempeFI and TSinN1
inst
a factor with levels DSJC500.5 and
DSJC500.9. Instances are taken from the DIMACS repository.
run
a numeric vector indicating the run to
which the observation belong.
best
a numeric vector indicating the best solution in
number of colors found in the corresponding run up to that time.
time
a numeric vector indicating the time since the
beginning of the run for each observation. A rescaling is applied.
titer
a numeric vector indicating iteration number
corresponding to the observations.
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.
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.
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