European Journal of Operational Research 151 (2003) 379–388

www.elsevier.com/locate/dsw

A variable neighborhood search for graph coloring

C
edric Avanthay a, Alain Hertz b, Nicolas Zufferey c,*

a
Private business corporation, Lausanne CH-9000, Switzerland
b
D

epartement de math
enie industriel, E
cole Polytechnique, Montr

ematiques et de g
eal, Qu

ebec, Canada H3C 3A7
c
Department of Mathematics, Swiss Federal Institute of Technology, Lausanne CH-1015, Switzerland

Abstract

Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial
solution which improve each time the value of an objective function until a local optimum is found. Several meta-
heuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For
example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet
been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this
new method to the graph coloring problem.

2003 Published by Elsevier B.V.

Keywords: Variable neighborhood search; Graph coloring

1. Introduction nealing [22], GRASP [8], adaptative multi-start [2])

have led to much improved results for many
Let S denote the set of solutions of a combi- combinatorial problems. Hansen and Mladenovic
natorial optimization problem. For a solution have recently [18,23] proposed a new optimization
si 2 S let N ðsi Þ denote the neighborhood of si which technique called variable neighborhood search
is defined as the set of neighbor solutions in S ob- (VNS for short). The main idea of this new method
tained from si by performing a local change on it. is to use various neighborhoods during the search.
A descent method usually visits a sequence Given an incumbent s, a neighbor solution s0 is
s0 ; . . . ; sn of solutions, where s0 is an initial solu- generated according to one of these neighbor-
tion, sn is a local optimum, and siþ1 2 N ðsi Þ, hoods, and a local search is then applied to s0 in
8i ¼ 0; . . . ; n
1. In recent years, local search order to obtain a local optimum s00 . If s00 is better
techniques have been proposed which extend this than s, then s00 becomes the new incumbent; oth-
scheme in order to get out of local optima. These erwise, a different neighborhood is considered in
techniques (e.g. tabu search [16,17], simulated an- order to try to improve upon solution s. This
process is repeated until no neighborhood leads to
an improvement of the incumbent.
*
Corresponding author.
Given a graph G ¼ ðV ; EÞ with vertex set V and
E-mail addresses: cav@elca.ch (C. Avanthay), alain.hertz@ edge set E, and given an integer k, a k-coloring of G
gerad.ca (A. Hertz), nicolas.zufferey@epfl.ch (N. Zufferey). is a function c : V ! f1; . . . ; kg. The value cðxÞ of

0377-2217/$ - see front matter
2003 Published by Elsevier B.V.

doi:10.1016/S0377-2217(02)00832-9
380 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388

a vertex x is called the color of x. The vertices with value of the k-GCP is zero, this means that G has a
color r (1 6 r 6 k) define a color class, denoted Vr . legal k-coloring. The chromatic number of G can
If two adjacent vertices x and y have the same be determined by first computing an upper bound
color r, vertices x and y are called conflicting ver- (for example by means of a constructive method)
tices, the edge ½x; y is called a conflicting edge, and and then solving a series of k-GCPs with decreas-
r is called a conflicting color. If there is no con- ing values of k until no legal k-coloring can be
flicting edge, then the color classes are called stable obtained. This strategy will be called the partition
sets, and the k-coloring is said legal. The graph approach since each k-GCP aims to determine a
coloring problem (GCP for short) is to determine partition of the vertex set V of G into a fixed
the smallest integer k (called chromatic number of number k of stable sets. For a fixed integer k, and a
G) such that there exists a legal k-coloring of G. k-coloring c, let f ðcÞ denote the number of con-
The aim of this paper is to propose an adaptation flicting edges induced by c. Many local search
of the VNS to the GCP. methods have been proposed for minimizing f .
The paper is organized as follows. In Section 2, For example, a tabu search is described in [19], and
we review some famous heuristic methods for simulated annealing algorithms can be found in
graph coloring. We then present in Section 3 the [5,20]. Genetic algorithms and hybrid methods
basic VNS as well as some possible extensions. have also been successfully applied to this problem
The proposed adaptation of the VNS method to (e.g. [6,9,13]).
the GCP is described in Section 4, and computa- Another approach for solving the GCP is to
tional experiments are reported in Section 5. successively build the stable sets of a legal k-col-
oring by repeatedly identifying a maximal stable
set in G and removing it from the graph. With this
2. Heuristic methods for graph coloring strategy, the GCP is reduced to the solution of
successive maximal stable set problems. Various
The GCP is an NP-hard problem [12]. Exact efficient heuristic methods have been proposed for
solution methods have been developed by several finding a large stable set in a graph (e.g. [10,11,
researchers (e.g. [3,4,24]) but all these exact 14]). The partition approach can be combined with
methods can only be applied to problems of rel- this strategy by first removing stable sets until the
atively small size (no more than 100 vertices). remaining graph G0 has no more than a given
This certainly explains why many heuristic number of vertices, and then applying the partition
methods have been proposed for getting an upper approach on G0 . Such combined methods are de-
bound on the chromatic number of a graph. A scribed for example in [9,19]. Nowadays, the most
survey of the most famous heuristic graph col- efficient heuristic method for the GCP is due to
oring methods can be found in [25]. The simplest Galinier and Hao who have proposed an hybrid
ones are construtive methods which color each method that combines a genetic algorithm with a
vertex in turn with the smallest possible color. tabu search [13].
The quality of the resulting coloring strongly
depends on the order in which the vertices are
scanned. A well-known such constructive method 3. Description of the VNS method
is the DSATUR algorithm [3], which is based on
a dynamic ordering of the vertices: the next vertex Let N ðtÞ ðt ¼ 1; . . . ; tmax Þ denote a finite set of
to be colored is the one having the largest number neighborhoods, where N ðtÞ ðsÞ is the set of solutions
of different colors already assigned to its adjacent in the tth neighborhood of s. Most local search
vertices. methods use only one type of neighborhood, i.e.
Given a fixed integer k, we consider the opti- tmax ¼ 1. The basic VNS [18,23], which is described
mization problem, called k-GCP, which aims to in Table 1, tries to avoid being trapped in local
determine a k-coloring of G such that the number minima with the help of more than one neigh-
of conflicting edges is minimized. If the optimal borhood.
 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388 381

Table 1
The basic VNS
1. Initialisation
– Determine an initial solution s
– Set t ¼ 1
2. Repeat the following until a stopping condition is met
2.a Shaking. Generate a point s0 at random from the tth neighborhood of s ðs0 2 N ðtÞ ðsÞÞ
2.b Local search. Apply some local search method with s0 as initial solution; let s00 be the so obtained local optimum
2.c Move or not. If s00 is better than the incumbent s, move there (i.e. set s ¼ s00 ), and continue the search with N ð1Þ (i.e. set t ¼ 1);
otherwise set t ¼ ðt mod tmax Þ þ 1

The stopping condition of a VNS may be, for We stop the VNS algorithm when MaxVNS it-
example, an upper bound on the CPU time, a erations have been performed without improving
maximum number of iterations, or a maximum the incumbent s. We have set MaxVNS ¼ jV j. Pre-
number of iterations between two improvements liminary experiments have shown that a larger
of the incumbent. Observe that a solution s0 gen- value for MaxVNS does not lead to a significant
erated in step 2.a is obtained by randomly choos- improvement of the algorithm. As local search
ing it in the tth neighborhood. This way of doing method in step 2.b we use the Tabucol algorithm
may avoid cycling which might occur if any de- described in [19] which is a tabu search that fol-
terministic rule was used. The local search method lows the partition approach. Given a solution s,
used in step 2.b can be a simple descent method, or Tabucol generates a neighbor solution s0 by
a more powerful technique such as a tabu search changing the color of a conflicting vertex. This
or a simulated annealing. means that a conflicting vertex x in a color class Vr
The above basic VNS can be viewed as a de- is moved to a new color class Vj , and the pair ðx; rÞ
scent algorithm since the incumbent s is modified is introduced in the tabu list (i.e. vertex x cannot be
only if the local optimum s00 obtained in step 2.b is moved back to Vr for some iterations). Tabucol is
better than s. Without much additional effort, it is stopped when Maxtabu consecutive moves have
possible to transform this basic VNS into a de- been performed without improving the best solu-
scent–ascent method: in step 2.c set also s ¼ s00 with tion found so far. A large value for Maxtabu in-
some probability even if s00 is worse than the in- duces a large CPU time for the VNS algorithm,
cumbent. Another possible variant of the basic while a too low value does not offer enough time to
VNS is to choose solution s0 in step 2.a as the best Tabucol to improve on s0 . Here again, preliminary
solution in a subset of neighbors randomly gen- experiments have shown that Maxtabu ¼ 10  jV j is
erated in N ðtÞ ðsÞ. a good compromise. Also, we have chosen value
10 for the length of the tabu list.
In the three next subsections we describe the
4. Adaptation of VNS to the k-GCP various neighborhoods used in our adaptation of
the VNS method to the k-GCP. These neighbor-
In order to solve the GCP, we have decided to hoods can be divided into three groups:
follow the partition approach. For a fixed k, we
consider as a solution to the problem any k-col- • the vertex neighborhoods which change the color
oring c. By denoting Er the collection of edges of G of some conflicting vertices,
with both endpoints in Vr , the objective function f • the class neighborhoods which change the color
is defined asPthe total number of conflicting edges, of some or all vertices of a conflicting color,
i.e. f ðsÞ ¼ kr¼1 jEr j: The initial solution generated • the non-increasing neighborhoods which change
in step 1 of the VNS algorithm is randomly chosen the color of some vertices without increasing the
among all possible solutions. total number of conflicting edges.
382 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388

4.1. Vertex neighborhoods x (called origin vertex) and move it into the best
possible other color class Vj . Since s is a local op-
We describe below five neighborhoods which timum, this move will create new conflicting ver-
modify the incumbent s by changing the color of tices in Vj . We then choose at random a new
some conflicting vertices. conflicting vertex y 2 Vj and assign to it the best
(1) The basic neighborhood: From a solution s possible new color l. This second move will
we generate a neighbor solution in N ð1Þ ðsÞ as fol- probably create new conflicts in Vl in which case
lows. We randomly choose a conflicting vertex x we assign the best possible color to a new con-
and move it from its current color class to the best flicting vertex in Vl . This sequence of changes is
possible other one (i.e. the new color class for x is executed as long as possible, taking care of not
chosen among those having the smallest number of changing the color of a vertex more than once. We
vertices adjacent to x). Such a move may create repeat this process by performing successively i
new conflicting vertices. We successively apply i such sequences of changes, with i origin vertices,
such changes on s to obtain a neighbor solution s0 . where i is randomly chosen in f1; . . . ; imax ð2Þ
g. The
On the one hand, a low value for i induces a ð2Þ
upper bound imax on i decreases gradually from 20
neighbor solution s0 which is very close to s. On the to 5 when IVNS increases from 0 to MaxVNS .
other hand, a large value for i will create a (3) The grenade neighborhood: From a solution
neighbor solution s0 which is very different from s, s we generate a neighbor solution in N ð3Þ ðsÞ as
and the generation of a neighbor solution can follows. We first randomly choose a conflicting
therefore be seen, in this case, as a restart. We have vertex x (called grenade) and we move it into the
decided to randomly choose i in f10; . . . ; ið1Þ max g, best possible other color class Vj . We then se-
where ið1Þmax depends on the number IVNS of it- quentially move each new conflicting vertex from
erations which have been performed without Vj into the best possible other color class. This
improving the incumbent s as follows: we set process is repeated with i different grenades, where
ið1Þ
max ¼ 100 each time the incumbent s is improved i is randomly chosen in f1; . . . ; imax ð3Þ
g. The upper
(i.e. when IVNS is set equal to 0), and we linearly ð3Þ
bound imax on i decreases gradually from 40 to 1
ð1Þ
decrease imax down to the value 20 which is reached when IVNS increases from 0 to MaxVNS .
when IVNS ¼ MaxVNS . Such a choice means that we (4) The firework neighborhood: From a solution
perform large changes on the incumbent s when s we generate a neighbor solution in N ð4Þ ðsÞ as
IVNS has a small value, while small changes are follows. We first randomly choose a conflicting
preferred when s has not been improved for a vertex x (called firework) and move it into the best
long time. The idea behind this choice is to per- possible other color class Vj . We then consider
form a kind of diversification each time s is im- every new conflicting vertex as a grenade (see
proved, and to gradually switch to intensification above). This process is repeated with i different
when IVNS increases. The upper and lower bounds fireworks, where i is randomly chosen in f1; . . . ;
ð1Þ ð2Þ ð5Þ ð4Þ ð4Þ
on imax (as well as on imax ; . . . ; imax defined below) imax g. The upper bound imax on i decreases gradu-
result from preliminary experiments. Notice also ally from 30 to 1 when IVNS increases from 0 to
that we have imposed a lower bound of value 10 MaxVNS .
on i. The reason is that we use the basic neigh- (5) The permutation neighborhood: From a so-
borhood for moving to a new region of the solution lution s we generate a neighbor solution in N ð5Þ ðsÞ
space, while the task of Tabucol (which uses i ¼ 1) as follows. We first randomly choose a conflicting
is to carefully explore this new region. Notice that vertex and move it from its current color class Vr
when generating a neighbor of s, we take care of into the best possible other color class Vj . Among
not changing the color of a vertex more than the new conflicting vertices in Vj , we choose one
once. having the smallest number of adjacent vertices in
(2) The chain neighborhood: From a solution s Vr , and move it into Vr . We successively perform i
we generate a neighbor solution in N ð2Þ ðsÞ as fol- such permutations, where i is randomly chosen in
lows. We first randomly choose a conflicting vertex ð5Þ ð5Þ
f1; . . . ; imax g. The upper bound imax on i decreases
 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388 383

gradually from 50 to 10 when IVNS increases from 0 tion (Maxtabu is set equal to jV j), while forbidding
to MaxVNS . any change on V  (i.e. the addition of a vertex into
V  and the removal of a vertex from V  are con-
4.2. Class neighborhoods sidered as tabu moves).

In these neighborhoods, we modify a solution 4.3. Non-increasing neighborhoods

by first selecting a conflicting color, and then
changing the color of some or all vertices having In these neighborhoods, we generate a neighbor
that color. We propose below four such neigh- solution by changing the color of some vertices,
borhoods. In what follows, we denote V  the color but without increasing the total number of con-
class which contains the largest number of con- flicting edges. This means that the neighbor solu-
flicting vertices, and p its number of vertices. tion s0 is such that f ðs0 Þ 6 f ðsÞ.
(6) The empty–refill neighborhood: From a so- (10) The Culberson neighborhood [6,7]: From a
lution s we generate a neighbor solution in N ð6Þ ðsÞ solution s ¼ ðV1 ; . . . ; Vk Þ we generate a neighbor
as follows: we first empty V  by successively solution in N ð10Þ ðsÞ as follows. We first remove the
moving each of its vertices into the best possible f ðsÞ conflicting edges in G. We thus get a partial
other color class. We then refill V  by successively subgraph G0 for which the partition ðV1 ; . . . ; Vk Þ
choosing p other vertices (new conflicting vertices corresponds to a legal k-coloring c. We then con-
when possible) and moving all of them into V  . sider any permutation p of the k colors and any
(7) The stable set neighborhood: From a solution ordering of the vertices such that vertex x is before
s we generate a neighbor solution in N ð7Þ ðsÞ as vertex y if pðcðxÞÞ < pðcðyÞÞ. We finally construct a
follows: we first randomly choose a conflicting new k-coloring ðV10 ; . . . ; Vk0 Þ of G0 by coloring each
vertex x 2 V  , and create an ordered list L ¼ vertex in turn with the smallest possible color. The
ðv1 ; . . . ; vjV j Þ of the vertices in V , where v1 ¼ x, the partition s0 ¼ ðV10 ; . . . ; Vk0 Þ is a neighbor solution of
p
1 last elements of L are the vertices of s with at most f ðsÞ conflicting edges. This process
V 
fxg, and the elements v2 ; . . . ; vjV j
p cover the is illustrated in Fig. 1.
remaining vertices of V (in a random order). We (11) The subgraph neighborhood [15]: From a
then construct a maximal stable set W in a greedy solution s ¼ ðV1 ; . . . ; Vk Þ we generate a neighbor
fashion, by scanning the ordered list L. Finally, we solution in N ð11Þ ðsÞ as follows. We first sequentially
move each vertex which is in V  but not in W into remove conflicting vertices from G in order to
the best possible other color class, and we move obtain a maximal induced subgraph G0 of G
into V  each vertex which is in W but not yet in V  . without any conflicting edge. We then permute the
(8) The empty class neighborhood: From a so- colors in G0 according to the permutation p which
lution s we generate a neighbor solution in N ð8Þ ðsÞ minimizes the number of conflicting edges having
as follows: we first empty V  by successively one endpoint in G0 and one outside G0 . This best
moving each of its vertices into the best possible permutation is obtained by solving a bipartite
other color class. We thus obtain a partition of V weighted matching problem (also called assignment
into k
1 color classes. We then briefly apply the problem) [1]. More precisely, consider the complete
Tabucol algorithm (Maxtabu is set equal to jV j) in bipartite graph B ¼ ðN1 [ N2 ; AÞ where N1 ¼ N2 ¼
order to minimize the number of conflicts in these f1; . . . ; kg, and the cost Cij of the edge ði; jÞ 2 A
k
1 color classes (i.e. the addition of a vertex into linking i 2 N1 with j 2 N2 is equal to the number of
V  is considered as a tabu move). edges linking a vertex of color i outside G0 to a
(9) The tabu class neighborhood: From a solu- vertex of color j in G0 . Let M be a perfect matching
tion s we generate a neighbor solution in N ð9Þ ðsÞ as of minimum cost in B. The total cost of the edges
follows. We first reduce V  to a stable set by se- in M corresponds to the number of conflicting
quentially moving each of its conflicting vertices edges in the k-coloring obtained from s by as-
into the best possible other color class. We then signing color j to a vertex of color i in G0 if and
briefly apply the Tabucol algorithm to this solu- only if the edge linking i 2 N1 to j 2 N2 belongs to
384 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388

Fig. 1. The Culberson neighborhood.

M. Many polynomial algorithms have been pro- • Two Leighton graphs: le450.15c and le450.15d.
posed for the solution of the bipartite weighted They both have 50 vertices and a known chro-
matching problem (see for example [1]). This matic number 15.
process is illustrated in Fig. 2. • One random graph: DSJC500.5 with 500 verti-
ces, edge density 0.5, and with unknown chro-
4.4. Comparison of the neighborhoods matic number.

In order to analyze the efficiency of each pro- Notice that each one of these nine instances
posed neighborhood, we have implemented eleven defines in reality a set of k-GCPs with different
different VNS algorithms, each one using a single values of k. In the second line of Table 2, we
neighborhood (i.e., tmax ¼ 1). As mentioned in [13], indicate the value of k for which we try to find a
differences between efficient algorithms can not be legal k-coloring. Then, for each neighborhood,
observed on instances of small size (with less than we give the average number of conflicting edges
300 vertices). The comparison of the neighbor- obtained after 4 runs of the VNS algorithm (with
hoods has therefore been performed on nine in- the fixed k of the second line), using only the
stances of medium size. We have first generated considered neighborhood. In the last line we
four random graphs with 500 vertices and edge give, for comparison, the average results ob-
density 0.5, denoted R500.1, R500.2, R500.3 and tained with Tabucol, also after 4 runs on each
R500.4. We have then taken the five following instance. To get comparable CPU times we have
instances from [21]. stopped each run of Tabucol after MaxVNS 
Maxtabu ¼ 10  jV j2 iterations without improve-
• Two flat graphs: flat300.28 and flat300.26. They ment of the best solution obtained so far. Bold
both have 300 vertices and a known chromatic numbers indicate that the considered VNS algo-
number (28 and 26, respectively). rithm has found solutions which are in
 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388 385

3 1 2 3
A B C F
The incumbent s with
2 conflicting edges.
D E
1 2

3 1 2 3 A maximal induced subgraph G'

A of G without conflicting edges.
B C F

D E
1 2 Consider the permutation p such
that π(1)=2, π(2)=1 and π(3)=3.

3 2 1 3
A B C F
The neighbor s' of s does not
contain conflicting edges.
D E
1 2

Fig. 2. The subgraph neighborhood.

Table 2
Comparison of the neighborhoods
Instance
R500.1 R500.2 R500.3 R500.4 DSJC500.5 le450.15c le450.15d flat300.28 flat300.26
k 49 49 49 49 49 15 15 31 31
Chain 2.5 4 3.75 3.25 4.5 0 0 1.75 0
Firework 1.75 5 4.5 4 4 0 0 2.25 0
Grenade 2 4.5 3.25 3.75 4.25 0 0.25 1.5 0
Permutation 1.75 5.5 4.5 3.5 6 0.25 2 2 0
Basic 2 5.5 5 7.75 8 83.75 46 2.5 0
Stable set 2.5 4.5 3.75 3 5.5 2.5 1 2.5 1.25
Empty–refill 2.5 3.5 5.5 3.75 4.25 2 0 2 1
Empty class 2.5 3 5.25 3.75 4.75 11.5 16.75 1.25 0
Tabu class 7 9.75 9.25 10 13 26.5 17.75 6 4.75
Culberson 8 12.5 17.5 10.75 13.25 162.25 163.5 7.25 6.25
Subgraph 12.5 16.25 14 16.5 16.75 160.75 168 8 6.75
Tabucol 1.75 6 8 3.5 9 162.25 160.75 2.5 1.5

average at least as good as those produced by neighborhoods, while the stable set, empty–refill
Tabucol. and empty class neighborhoods are the best among
Notice first that for each instance, except the class neighborhoods. The non-increasing
R500.1, we have been able to improve on Tabucol neighborhoods are not competitive at all. Con-
results by using a VNS approach. Table 2 clearly sidering the above results, we have decided to use
shows that the chain, firework and grenade neigh- only these six best neighborhoods. Tests on larger
borhoods are the best ones among the vertex instances have confirmed that the five rejected
386 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388

neighborhoods do not help improving the perfor- tation of f2; 3; 4; 6; 7; 8g (among the 720 possible
mance of the VNS algorithm. ones):

4.5. The proposed VNS algorithm • vertex first, class second permutations: p1 ¼
2; 3; 4; 6; 7; 8, p2 ¼ 4; 3; 2; 8; 7; 6;
We have combined the six best neighborhoods • class first, vertex second permutations: p3 ¼
N ð2Þ ðsÞ, N ð3Þ ðsÞ, N ð4Þ ðsÞ, N ð6Þ ðsÞ, N ð7Þ ðsÞ and N ð8Þ ðsÞ 6; 7; 8; 2; 3; 4, p4 ¼ 8; 7; 6; 4; 3; 2;
to obtain the proposed VNS algorithm which is • alternating permutations: p5 ¼ 2; 6; 3; 7; 4; 8, p6 ¼
described in Table 3. Since the algorithm stops 6; 2; 7; 3; 8; 4.
when the incumbent has not been improved for
MaxVNS ¼ jV j iterations, we change from a The six permutations have been tested on the
neighborhood to another one when jV j=6 itera- nine instances described in Section 4.4. The results
tions are performed with a same neighborhood are reported in Table 4. We first recall in the first
without improving s. The order in which the six lines the results obtained using only one neigh-
neighborhoods are considered can influence the borhood. The best average number of conflicting
quality of the solution produced by the VNS al- edges is indicated with bold numbers. We then
gorithm. We have tested the six following permu- report the results obtained by combining the six

Table 3
The proposed VNS for the k-GCP
1. Initialisation
1.a Randomly generate a k-coloring of G
1.b Set IVNS ¼ 0 and t ¼ 1
1.c Consider a permutation p of f2; 3; 4; 6; 7; 8g
2. Repeat until IVNS ¼ jV j
Set ItVNS ¼ ItVNS þ 1
2.a Shaking. Generate a random solution s0 in N ðpðtÞÞ
2.b Local search. Apply Tabucol to s0 and stop when 10  jV j have been performed without improving the best known solution.
Let s00 be the so obtained local optimum
2.c Move or not. If s00 is better than s, then set s ¼ s00 , t ¼ 1 and IVNS ¼ 0; otherwise, set t ¼ t þ 1 if IVNS is a multiple of djV6 je

Table 4
Comparison of the orderings
Instance
R500.1 R500.2 R500.3 R500.4 DSJC500 le450.15c le450.15d flat300.28 flat300.26
k 49 49 49 49 49 15 15 31 31
Chain 2.5 4 3.75 3.25 4.5 0 0 1.75 0
Firework 1.75 5 4.5 4 4 0 0 2.25 0
Grenade 2 4.5 3.25 3.75 4.25 0 0.25 1.5 0
Stable set 2.5 4.5 3.75 3 5.5 0.25 2 2 0
Empty–refill 2.5 3.5 5.5 3.75 4.25 2 0 2 1
Empty class 2.5 3 5.25 3.75 4.75 11.5 16.75 1.25 0

p1 2.5 3.75 4.5 2.5 3.25 0 0 2.5 0

p2 1.5 4.5 3 2.25 5 0 0 2.25 0
p3 2 3 5.25 3.75 4.25 0 0 2.25 0
p4 3.5 4.5 2.75 2.25 5.75 0 0 2.75 0
p5 2 3.5 3.75 1.75 5 0 0 2.25 0
p6 2.25 3.25 5.25 3.75 5.75 0 0 0.75 0
 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388 387

neighborhoods. Bold numbers indicate that the algorithm had at least one successful run (a suc-
considered permutations has produced solutions cessful run is one which finds a legal k-coloring for
which are in average at least as good as those the fixed k). The five results reported for GH are
obtained using only one kind of neighborhood. taken from [13]. We do not know what can be
Notice first that the average number of conflicting obtained by this algorithm on the 6 other in-
edges has been reduced for instances R500.1, stances. In column best known we indicate the
R500.3, R500.4, DSJC500 and flat300.28. It can smallest value of k for which a legal k-coloring has
however be observed that no permutation clearly ever been found by an algorithm [13]. Average
appears as a winner. We have therefore decided to computational times for the VNS algorithm (over
choose a random permutation of f2; 3; 4; 6; 7; 8g at the 4 runs) are given in the last column, for each
point 1.c of the above VNS algorithm. instance. Notice that Tabucol requires approxi-
mately the same CPU time since we stop each run
2
of Tabucol after MaxVNS  Maxtabu ¼ 10  jV j it-
5. Comparisons between VNS and other methods erations without improvement of the best solution
obtained so far. We have used a Silicon Graphics
To further analyze the performance of the Indigo2 machine (195 MHz, IP28 processor). To
proposed VNS algorithm, we have compared the get a point of comparison, we have run program
results it produces with those obtained by Tabucol dfmax found at ftp://dimacs.rutgers.edu/pub/chal-
and the genetic hybrid algorithm (GH for short) lenge/graph/benchmarks/volume/Machine/.
proposed by Galinier and Hao [13], which com- Our machine respectively needed 0.02, 0.69,
bines a tabu search with a genetic algorithm. The 6.06, 37.65, 145.50 seconds to solve instances
three algorithms have produced the same results r100:5:b, r200:5:b, r300:5:b, r400:5:b, r500:5:b, and
on all benchmark problems in [21], except on the the Sun Sparc 10/Model 41 (using gcc and the
random graph DSJC1000.5 (with 1000 vertices ‘‘-O’’ optimization option) needed 0.04, 1.04, 9.06,
and edge density 0.5), on the flat graph flat1000.76 56.33, 218.69 seconds, respectively.
(with 1000 vertices and chromatic number 76), and As can be observed, the VNS algorithm always
on the instances studied in Section 4. We therefore produces better results than Tabucol. Notice that
only report results obtained on the nine instances the VNS algorithm repeatedly uses Tabucol each
of Section 4, as well as on these two additional time it enters step 2.b. This clearly demonstrates
graphs with 1000 vertices. that the use of more than one neighborhood may
The proposed VNS algorithm as well as Tabu- be very useful for escaping local optima. The VNS
col have been run 4 times on each instance, and we algorithm is however not competitive with GH,
report in Table 5 the smallest k with which each which means that a good exchange of information

Table 5
Comparison between Tabucol, GH and our VNS method
Graph Tabucol VNS GH Best known CPU time of VNS (minutes)
DSJC500.5 51 49 48 48 45
DSJC1000.5 94 90 83 83 180
R500.1 50 49 – – 45
R500.2 51 50 – – 45
R500.3 51 50 – – 45
R500.4 51 50 – – 45
le450.15c 18 15 15 15 5
le450.15d 18 15 – 15 5
flat300.28 32 31 31 31 15
flat300.26 32 31 – 26 15
flat1000.76 93 89 83 83 180
388 C. Avanthay et al. / European Journal of Operational Research 151 (2003) 379–388

among a population of solutions seems to be more [8] T. Feo, M. Resende, Greedy randomized adaptative
important than the use of several neighborhoods search, Journal of Global Optimization 6 (1995) 109–133.
[9] C. Fleurent, J.A. Ferland, Genetic and hybrid algorithms
on a unique solution.
for graph coloring, Annals of Operations Research 63
(1996) 437–461.
[10] C. Fleurent, J.A. Ferland, Objected-oriented implementa-
6. Conclusion tion of heuristic search methods for graph coloring,
maximum clique, and satisfiability, in [21], 1996, pp. 619–
652.
We have developed an adaptation of the vari-
[11] C. Frieden, A. Hertz, D. de Werra, Stabulus: A technique
able neighborhood search method to the graph for finding stable sets in large graphs with tabu search,
coloring problem. Our VNS algorithm is however Computing 42 (1989) 35–44.
not competitive with the hybrid algorithm GH [12] M. Garey, D. Johnson, Computers and intractibility: A
proposed by Galinier and Hao, which combines a guide to the theory of NP-completeness, W.H. Freeman
and Company, New York, 1979.
tabu search with a genetic algorithm, and which is
[13] P. Galinier, J.-K. Hao, Hybrid evolutionary algorithms for
for the moment the best known coloring algo- graph coloring, Journal of Combinatorial Optimization 3
rithm. Their algorithm benefits from the advan- (1999) 379–397.
tages of both solution approaches: while genetic [14] M. Gendreau, P. Soriano, L. Salvail, Solving the maximum
algorithms are well adapted for determining good clique problem using a tabu search approach, Annals of
Operations Research 41 (1993) 385–403.
regions in the search space, local search techniques
[15] C. Glass, Seminar at the Department of Mathematics,
have proven to be successful in determining high Swiss Federal Institute of Technology, Lausanne, Switzer-
quality solutions in identified good regions of the land, 1999.
search space. The next step for improving the re- [16] F. Glover, Tabu search––Part I, ORSA Journal of Com-
sults produced by the GH algorithm could be to puting 1 (1989) 190–206.
[17] F. Glover, Tabu search––Part II, ORSA Journal of
replace the tabu search used in GH by a VNS
Computing 2 (1990) 4–32.
method. [18] P. Hansen, N. Mladenovic, An introduction to VNS, in: S.
Voss, S. Martello, I.H. Osman, C. Roucairol (Eds.), Meta-
Heuristics: Advances and Trends in Local Search Para-
References digms for Optimization, Kluwer Academic Publishers,
Boston, 1998.
[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: [19] A. Hertz, D. de Werra, Using tabu search techniques for
Theory, Algorithms and Applications, Prentice Hall, graph coloring, Computing 39 (1987) 345–351.
Englewood Cliffs, NJ, 1993. [20] D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon,
[2] K.D. Boese, A.B. Kahng, S. Muddu, A new adaptative Optimization by simulated annealing: An experimental
multi-start technique for combinatorial global optimiza- evaluation, Part II: Graph coloring and number partition-
tions, Operations Research Letters 16 (1994) 101–113. ing, Operations Research 39 (1991) 378–406.
[3] D. Br
elaz, New methods to color vertices of a graph, [21] D.S. Johnson, M.A. Trick (Eds.), Cliques, Coloring and
Communications of ACM 22 (1979) 251–256. Satisfiability, DIMACS Series in Discrete Mathematics
[4] J.R. Brown, Chromatic scheduling and the chromatic and Theoretical Computer Science, vol. 26, American
number problem, Management Science 19 (1972) 456–463. Mathematical Society, 1996.
[5] M. Chams, A. Hertz, D. de Werra, Some experiments with [22] S. Kirkpatrick, C.D. Gelatt, M. Vecchi, Optimization by
simulated annealing for coloring graphs, European Journal simulated annealing, Science 220 (1983) 671–680.
of Operational Research 32 (1987) 260–266. [23] N. Mladenovic, P. Hansen, Variable neighborhood search,
[6] D. Costa, A. Hertz, O. Dubuis, Embedding of a sequential Computers in Operations Research 24 (1997) 1097–1100.
algorithm within an evolutionary algorithm for coloring [24] J. Peem€ oller, A correction to Br
elazÕs modification of
problems in graphs, Journal of Heuristics 1 (1995) 105– BrownÕs coloring algorithm, Communications of ACM 26
128. (1983) 593–597.
[7] J.C. Culberson, Exploring the k-colorable landscape with [25] D. de Werra, Heuristics for graph coloring, Computing 7
Iterated Greedy, in [21], 1996, pp. 245–284. (1990) 191–208.