gcp2x2: Metaheuristics for solving the Graph Vertex Coloring Problem

In eaf: Plots of the Empirical Attainment Function

Metaheuristics for solving the Graph Vertex Coloring Problem

Description

Two metaheuristic algorithms, TabuCol (Hertz et al., 1987) and simulated annealing \citepJohAraMcGSch1991, 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

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

\insertRef

ChiarandiniPhDeaf (page 138)

References

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

\insertAllCited

Examples

data(gcp2x2)

eaf documentation built on Sept. 11, 2024, 8:45 p.m.