Coloration Neighbourhood Search With Forward Checking.
Two contrasting search paradigms for solving combinatorial problems are i>systematic backtracking and i>local search. The former is often effective on highly structured problems because of its ability to exploit consistency techniques, while the latter tends to scale better on very large problems. Neither approach is ideal for all problems, and a current trend in artificial intelligence is the hybridisation of search techniques. This paper describes a use of forward checking in local search: pruning coloration neighbourhoods for graph colouring. The approach is evaluated on standard benchmarks and compared with several other algorithms. Good results are obtained; in particular, one variant finds improved colourings on geometric graphs, while another is very effective on equipartite graphs. Its application to other combinatorial problems is discussed.
Introduction
Graph colouring is an NP-hard combinatorial optimisation problem with
real-world applications such as timetabling, scheduling, frequency assign-
ment, computer register allocation, printed circuit board testing and pattern
matching. A graph E) consists of a set V of vertices and a set E
of edges between vertices. Two vertices connected by an edge are said to be
adjacent . The aim is to assign a colour to each vertex in such a way that no
two adjacent vertices have the same colour. A graph colouring problem for a
graph G is the problem of nding a k-colouring with k as small as possible.
The chromatic number (G) of a graph is the minimum number of colours
required to colour it.
Many algorithms have been proposed for the graph colouring problem.
Systematic backtracking gives good results on small graphs but scales poorly
to large problems. Most colouring algorithms are stochastic in nature, searching
in a non-systematic way with a variety of heuristics. The simplest type of
stochastic search is local search: hill climbing, often augmented with heuristics
for escaping local minima. Local search explores the neighbourhood of
a point  in a space by making local moves. The neighbourhood consists of
the set of points  0 that can be reached by a single local move. The aim is
to minimise (or equivalently to maximise) some objective function f() on
the space. A local move  !  0 can be classied as backward , forward or
sideways, depending on whether f( 0 ) f() is positive, negative or zero.
Some algorithms choose a forward move that yields the greatest reduction
in value, a strategy sometimes called greedy or steepest descent . A draw-back
of local (and other stochastic) search is that it may converge on a local
minimum: a point that has lower value than all its neighbours but is not a
global minimum. The aim of backward moves is to escape from local minima
by providing noise, while sideways moves are often used to traverse function
plateaus.
We might classify colouring algorithms by the search spaces they explore.
The space of total colorations consists of the possible colour assignments to all
the vertices of a graph, using a xed number of colours. This approach is used
by the TABU algorithm, which tries to minimise the number of con
icts. A
con
ict is an adjacent pair of vertices with the same colour. TABU generates
a selection of possible single-vertex re-assignments and selects the best, even
if this leads to more con
icts. It also maintains a list of recent moves and
avoids reversing them, which helps it to escape local minima.
The consistent total colorations are the total colorations that contain no
con
icts. This space is explored by the Greedy (or sequential) algorithm,
which tries to colour each vertex with a colour already used for a previous
vertex; if this is not possible then a new colour is used. Heuristics control the
vertex order and colour selection. The Iterative Greedy algorithm iteratively
applies the Greedy algorithm, using vertex orderings that are guaranteed to
generate a sequence of colorations using a non-increasing number of colours.
Brelaz's DSATUR algorithm [2] explores a similar space. It orders vertices
dynamically by maximum saturation (number of distinct colours assigned
to adjacent vertices), breaking ties by choosing a vertex of greatest forward
degree. The degree of a vertex is the number of its adjacent vertices, and its
forward degree is the number of its uncoloured adjacent vertices. DSATUR
has also been extended by backtracking. Mehrotra & Trick's version [15] uses
full (exhaustive) search and begins by computing a clique which is never re-
coloured. Another version described by Culberson, Beacham and Papp [3]
uses limited backtracking.
The space of consistent partial colorations consists of consistent colorations
of subsets of the vertices that do not use more than a specied number of
colours. This space is explored by the IMPASSE colouring algorithms. The
objective function to be minimised is the sum of the forward degrees of
the uncoloured vertices. Two such algorithms are Morgenstern's distributed
IMPASSE [17] and Lewandowski & Condon's parallel IMPASSE [14]. Distributed
IMPASSE performs limited searches on a distributed architecture,
each search starting from previous good coloration, which are maintained in
a pool. Parallel IMPASSE is a hybrid of IMPASSE and systematic search;
the two execute in parallel and communicate colouring improvements to each
other.
Finally, the independent sets of a graph are the sets of pairwise non-adjacent
vertices. They exploit the fact that all the vertices of an independent
set can be assigned the same colour. The space of independent sets
is explored by algorithms such as Johnson et al.'s XRLF [10] and Culberson
using (exhaustive or restricted) backtracking and
iteration. Mehrotra & Trick's LPCOLOR [15] uses column generation and
branch-and-bound to explore this space.
The motivation for this classication is that we shall describe a local
search algorithm that explores a new space. This is a subspace of the consistent
partial colorations, reduced by applying the Constraint Programming
technique of forward checking . We describe the new algorithm in Section 2
and evaluate its performance in Section 3. The algorithm, results and related
work are discussed in Section 4. This paper is an extension of earlier
work [19], but the algorithm is described in greater detail and evaluated more
systematically.
FC-consistent partial coloration neighbourhood
search
We rst discuss a simple consistency technique from constraint programming:
forward checking (FC). FC is commonly used with systematic backtracking
[9], and this combination can be applied to graph colouring as follows. Each
vertex has an associated domain of possible colours, initialised to the full
set of available colours. On colouring a vertex with one of the colours in its
domain, that colour is deleted from the domains of the adjacent vertices. No
colour assignment is permitted if it causes the domain of some uncoloured
vertex to become empty. This domain wipe-out often occurs long before the
vertex in question is due to be coloured, greatly reducing the search space.
On backtracking, a vertex is uncoloured and its assigned colour restored to
the domains of adjacent vertices. An analogue to the Brelaz heuristic may
be used to select vertices for colouring: select a vertex with smallest domain,
breaking ties by selecting a vertex with greatest forward degree.
FC is a simple and inexpensive algorithm, and sometimes out-performs
theoretically more powerful techniques. FC with backtracking also has the
advantage of completeness. That is, all k-colourings will eventually be found,
and if there is no k-colouring then the algorithm will eventually prove this
by terminating without nding a solution. However, systematic backtracking
algorithms often suer from poor scalability. For example the FC algorithm
is eective on small N-queens problems, but cannot solve problems with
more than approximately 100 queens; in contrast, a local search algorithm
solves up to 10 6 queens in linear time [16]. Backtracking and local search
are complementary search techniques for solving colouring and other combinatorial
problems, and considerable research has been devoted to combining
advantages of the two.
We describe how to exploit FC within a local search algorithm for graph
colouring. The idea is to explore the subspace of the consistent partial col-
orations that are also consistent under forward checking. That is, for each
of the currently uncoloured vertices, there is at least one available colour
that can be consistently assigned to it; colorations causing vertex domain
wipe-out are avoided. We shall call this subspace the FC-consistent partial
colorations. Our reasoning is that by reducing the search space we may avoid
some local minima.
Before describing the particular algorithm used to explore this space, we
discuss a complication that arises when applying local search to it. In systematic
backtracking it is simple to maintain vertex domains: the order in which
colours are restored from domains on backtracking is the reverse of the order
in which they were deleted during assignment. It is su-cient to maintain a
boolean variable for each colour in each domain, denoting whether or not the
colour is currently in the domain. However, local search is non-systematic,
and from a given coloration we may wish to uncolour any vertex, not just
the most recently coloured one. To do this we need a new way of maintaining
domains. A number we shall call a con
ict count is maintained for each
vertex-colour pair (v,c) recording how many currently coloured vertices the
assignment would con
ict with; initially all con
ict counts are zero. A
colour is classed as deleted from a vertex domain if and only if its con
ict
count is greater than zero. A domain's size is the number of its non-deleted
colours. The memory requirement for con
ict counts is not excessive: for n
vertices and k colours k  n con
ict counts are needed, which is roughly the
amount of memory required to represent the problem. They may be updated
incrementally: on colouring/uncolouring a vertex, the con
ict count for that
colour in each adjacent vertex is incremented/decremented. However, they
cause a signicant runtime overhead compared to standard forward check-
ing, because they are updated for the domains of uncoloured and coloured
vertices.
We can now design a local search algorithm on FC-consistent partial col-
orations. The algorithm chosen is rather simple, starting exactly as standard
FC: it selects a vertex for colouring, nds a colour that can be used without
causing domain wipe-out, colours the vertex, updates the domains of adjacent
vertices, and repeats by selecting another vertex. The only dierence so
far is that domains are maintained by con
ict counts. However, on reaching
a dead-end , where the selected vertex cannot be coloured, the new algorithm
behaves dierently to standard FC. It heuristically selects a vertex to be un-
coloured, instead of selecting the most recently coloured vertex. No attempt
is made to backtrack systematically, so completeness is lost. Because there
is now no obvious criterion for deciding when to stop backtracking and start
colouring vertices again, we introduce a parameter B  1. On reaching a
dead-end B vertices are uncoloured, and colouring resumes. Note that the
vertices selected for colouring and uncolouring may follow dierent heuris-
tics, so that the set of coloured vertices may change rapidly during search.
B plays the part of a noise parameter (or the temperature in simulated an-
nealing), controlling the permitted disruption to the state on reaching a local
minimum.
It remains to ll in details by describing three heuristics: selecting B
coloured vertices for uncolouring (CVERTEX), selecting an uncoloured vertex
for colouring (UVERTEX), and selecting colours to try when colouring
a vertex (COLOUR). We consider two alternative UVERTEX rules:
select the vertex with smallest current domain; break ties by
selecting the vertex adjacent to the greatest number of uncoloured ver-
tices; break further ties randomly.
Nonsingleton: randomly select a vertex with more than one colour in
its current domain; if none exists then select a vertex randomly.
The Brelaz heuristic is an obvious choice. The idea behind the Nonsingleton
heuristic is to emulate the MAXIS algorithm, which constructs independent
sets of vertices, whereas DSATUR constructs cliques. By selecting vertices
using an inverse of the Brelaz heuristic, and thus focusing on vertices that
are as independent as possible from those currently coloured, we might expect
to obtain a forward-checking analogue to MAXIS. This was tested and,
perhaps surprisingly, performed rather well on random graphs, whereas the
Brelaz heuristic performed poorly. However, the weaker Nonsingleton heuristic
performs better, possibly because of its greater
exibility in selecting a
vertex. It is discussed further in Section 4.
Given a free choice of vertices for uncolouring, which should be selected?
An obvious idea is to use an inverse of Brelaz: uncolour a vertex with large
domain and small degree (note that because con
ict counts are updated irrespective
of whether a vertex is coloured, coloured vertices also have domain
sizes). In tests this often caused stagnation, but the weaker Nonsingleton
heuristic (applied to coloured vertices) works well. To further reduce stagna-
tion, with probability 1=n (where n is the number of vertices in the graph)
the CVERTEX rule selects a vertex randomly instead of by domain size.
A random ordering on domain values works well, but performance can
be improved by remembering the previous colour of each vertex (if it was
coloured earlier). The COLOUR rule
ips between two modes: initially it
prefers dierent colours to those remembered for each vertex; if a dierent
colour is successfully used, the rule
ips to preferring the remembered colour;
when CVERTEX is next invoked it
ips back to preferring a dierent colour.
The aim of this rule is to minimise disruption to colorations as the set of
coloured vertices changes, while avoiding null local moves.
function
for
while U 6= fg
let
let colouring u to d
does not cause domain wipe-outg
for i=1 to min(B; jCj)
uncolour c and update domains
else
colour u to COLOUR(D) and update domains
return coloration

Figure

1: FC partial coloration neighbourhood search for xed k
The new algorithm FCNS (FC-consistent partial coloration Neighbourhood
is shown in Figure 1. k  1 is the permitted number of colours
and B  1 is the noise parameter. C is the current set of coloured vertices,
initialised to fg. U is the current set of uncoloured vertices, initialised to the
full set of n vertices g. Each vertex has a domain of colours that
are FC-consistent with the current partial coloration, initialised to the full
set of colours kg. The algorithm proceeds by selecting uncoloured vertices
using the UVERTEX rule, and colours them using the COLOUR rule.
On reaching a dead-end (D = fg) it uncolours B vertices, each selected by
the CVERTEX rule. Termination is not guaranteed but occurs if all vertices
are coloured
The algorithm can be used to nd a near-optimal colouring by applying
it iteratively in an obvious way: start with large k (for example
and apply the algorithm; on nding a total coloration using k 0  k colours,
restart the algorithm with k 0 1 colours; repeat until reaching a target number
of colours or a specied time. Performance is improved by starting each
iteration with a coloration similar to the previous one: colour assignments
are stored between iterations, and until the rst dead-end occurs each vertex
is assigned its previous colour where possible. It is also possible to speculatively
reduce k further in the hope of nding better colourings more quickly.
However, this aspiration approach does not always speed up search, because
inadvertently choosing k less than the chromatic number of the graph runs
the risk of spending a long time in fruitless search. Aspiration is not used in
current FCNS implementations.
3 Experimental results
FCNS is now evaluated using published results for several other algorithms
on the well-known DIMACS [11] 1 benchmarks. They are Culberson &
Luo's Iterated Greedy (IG) [4], Morgenstern's distributed IMPASSE [17],
Wheel Optimization (SWO) [12] and Glover, Parker & Ryan's TABU [8].
The TABU algorithm combines the TABU meta-heuristic with branch-and-
bound. SWO operates in two search spaces: a solution space and a prioritisation
space. Both searches in
uence each other: each solution is analysed
and used to change the prioritisation, which guides the search strategy used
to nd the next solution, found by restarting the search.
We use a standard set of benchmarks taken from the DIMACS web site.
Geometric graphs Rx.y and DSJRx.y are generated by randomly placing
x vertices in a unit square, then assigning edges between any two vertices
with Euclidean distance less than y=10 between them; a graph denoted by
Gc is the complement of the graph G. The names R and DSJR re
ect
dierent sources, but are (we believe) the same type of graph. Random
graphs Cn.p and DSJCn.p have n vertices, an edge being assigned between
any two vertices with a xed probability p=10. The names C and DSJC again
re
ect dierent sources. Flat graphs contain colorations that are hidden in
such a way as to mislead Brelaz-style heuristics; a graph
atn c x contains
vertices and a known hidden (though not necessarily optimal) c-colouring.
Leighton graphs le450 15x are derived from scheduling, and
have 450 edges and known chromatic number 15. Graph colouring is closely
related to the timetabling problem and there are two timetabling graphs; the
school1 problem is derived from timetabling data from a real high school with
around 500 students; the school1 nsh problem is derived from the same data
but ignores study halls. Register allocation graphs are used in compilers
to assign variables to registers, with the aim of avoiding the placement of
two variables in the same register when both may be active; there is one
such graph, mulsol.i.1. The latin square graph latin sqr 10 is derived from a
standard problem in design theory.

Figure

reproduces published results for SWO, IG, d-IMP (distributed
IMPASSE), p-IMP (parallel IMPASSE) and TABU, and Figure 3 shows results
for FCNS with the Brelaz (FCNS-b) and Nonsingleton (fCNS-n) heuris-
tics. All times are normalised to our machine (a 300 MHz DEC Alphaserver
1000A 5/300 under Unix) using benchmark timings from [11]; the DIMACS
benchmark program dfmax r500.5 takes 46.2 seconds on our machine. The
times for parallel IMPASSE were not normalised because of its parallel platform
(a 32-processor CM-5). In both tables k is the number of colours used
and t is the time taken in seconds. In Figure 3 B is the value used for the
parameter. Its value was chosen after a few runs to nd an appropriate
setting. This ad hoc approach is unfortunately necessary with many local
search algorithms; TABU has a list length parameter, and some algorithms
have more than one parameter (for example several local search algorithms
for the satisability problem). The initial number of colours k 0
for FCNS was
set to the worst k found by the other algorithms in each case (except where
our algorithms were even worse, when higher values were used). FCNS was
halted on reaching the target k, which was selected after a few experimental
runs. Times shown for FCNS are mean times taken to reach k from k 0
averaged
runs (more for short times). Experimental details for the other
algorithms vary (for details see the cited papers). Brie
y, SWO was terminated
after 1000 iterations, IG after 1000 iterations without improvement,
TABU after an hour or sooner if a lack-of-progress condition was satised,
distributed IMPASSE used conditions depending on the problem but always
halted on reaching a specied target k, and parallel IMPASSE ran for 3 hours
then reported the time taken to nd the best solution. The use of a time
limit instead of a target number of colours explains the occasional fractional
values of k.
First we discuss FCNS-b, which is clearly the best algorithm on the geometric
graphs. On R1000.5 and DSJR500.5 it nds the best reported colour-
ings, and on most of the others it nds equally good colourings in shorter
times. The geometric graphs are randomly generated but closely related to
a real problem: frequency allocation [10]. FCNS-b is therefore a promising
algorithm for solving such problems, and this is an area for future research.
It also performs very well on the school and mulsol graphs, roughly matching
SWO IG d-IMP p-IMP TABU
problem
school1 nsh 14 3.9 14.1 4.8 14 <0.24 14 66.4 26 16.8
mulsol.i.1
at300 26 0 35.8 6.4 37.1 4.1 26 5.4 32.4 6637 41 1849
at300 28 0 35.7 6.4 37 5.2 31 1028 33 1914 41 1849

Figure

2: Previous results for DIMACS benchmarks
FCNS-b FCNS-n
problem

Figure

3: FNCS results for DIMACS benchmarks
the performance of distributed IMPASSE. We also tested Mehrotra & Trick's
implementation 2 on the geometric graphs because it is known to
perform well on such graphs. On those with edge probability 0.1 it found the
same colourings in a slightly shorted time than FCNS-b. On those with edge
probability 0.5 it quickly found good colourings but then made no further
progress for a long time. For R125.5 it found a 36-colouring in 63.4 seconds,
for R250.5 a 66-colouring in 2.9 seconds, for DSJR500.5 a 130-colouring in
17.6 seconds, and for R1000.5 a 246-colouring in 75.8 seconds; no further
progress was made after several minutes. FCNS-b clearly scales better than
DSATUR, nding better colourings on the larger graphs. However, it is
very poor on the random,
at and latin square graphs, and mediocre on the
Leighton graphs.
Next we discuss FCNS-n. On the geometric and school graphs it is poor,
sometimes the worst algorithm, and (like FCNS-b) mediocre on the Leighton
graphs, but on the random,
at and latin square graphs it is beaten only
by distributed IMPASSE. This is presumably due to the use by distributed
IMPASSE of the XRLF algorithm [10] to generate initial colorations: parallel
IMPASSE does not use XRLF and is beaten by FCNS-n on random and
at
graphs. However, other algorithms are also better than FCNS-n on random
graphs. For example on G 1000;0:5
graphs the best algorithms nd colourings
in the low- or mid-80s.
To further investigate FCNS-n we applied it to equipartite graphs, which
have been studied by several researchers. A k-colourable equipartite graph
is generated by partitioning its vertices into k subsets, which are as equally-sized
as possible, the smallest being no more than 1 vertex smaller than the
largest. Edges are assigned with probability p, disallowing edges between vertices
in the same subset. This guarantees a k-colouring but does not preclude
better colourings. Eiben, van der Hauw & van Hemert [5] apply evolutionary
algorithms to 3-colourable equipartite graphs with 200 vertices. They report
low success rates on graphs with low density, especially around
where a phase transition occurs. Minton et al. [16] also report that the Min-
Con
icts local search algorithm has di-culties with similar problems, but
that a backtracking version of DSATUR solves them easily for 3  n  180.
Yugami et al. [27] apply local search with constraint propagation to the same
problems and obtain improved results. FCNS-n solves these problems easily:
nds 3-colourings in approximately 3 seconds. Moving to larger
problems, Culberson et al. [4] show that IG can nd hidden k-colourings for
G 1000;0:5
equipartite graphs with k  60. FCNS-n is also able to do this
and can go a little further. The algorithm was quite insensitive to B until
k  55, after which it became more sensitive. The optimal value for
was approximately the problems rapidly became harder
and the optimal value of B fell. It found a hidden 67-colouring after several
hours computation with but failed to nd a hidden 68-colouring. So
far as we known 67 is the highest value of k solved for this class of graph. In
further experiments FCNS-n also managed to nd the hidden colourings in
at1000 f50,60g 0, by setting starting with the target colouring
(50 or 60) specied as the initial colouring. However, these results took much
trial and error to achieve, so they were not included in our table.
It is perhaps surprising that the Nonsingleton heuristic should be successful
at all, let alone competitive. In particular, if a vertex has domain size 1
(hence only one possible colour) then Brelaz will select it before a vertex with
larger domain (hence more than one possibility), but Nonsingleton will delay
colouring such vertices as long as possible. To investigate the eect of adding
\forced moves" another variant was tried: select a vertex with domain size
1 if one exists, otherwise select one with maximum domain size. However,
this variant was inferior to both Brelaz and Nonsingleton. We speculate that
Nonsingleton causes FCNS to behave in a similar way to independent set-based
algorithms such as MAXIS, by focusing search on low-degree vertices.
A better algorithm might be obtained by explicitly designing it to nd independent
sets, and applying forward checking. Another research direction
is the design of new vertex orderings, with the aim of improving FCNS's
performance on random, Leighton and latin square graphs.
The noise parameter B unfortunately requires tuning to each graph. As
with any noise parameter, the eect of setting B too low is stagnation: FCNS
will never nd a colouring because it becomes trapped in a local minimum.
The eect of setting B too high is less serious, simply increasing the time
taken to nd a solution, but the increase depends on the problem. The
performance of FCNS-n seems to be fairly insensitive to the value of B when
nding an 18-colouring for DSJC125.5, while on DSJC1000.5 increasing B
from 1 to 2 slows it down greatly | or equivalently, prevents it from nding
good colourings in the same time. FCNS-b seems less sensitive, but can
still be slowed down signicantly by too much noise. We experimented with
variable noise levels to try to reduce sensitivity to noise, but with inconclusive
results. A slightly surprising feature of B is that, on several graphs (for
example R250.5), best results were obtained for FCNS-b and FCNS-n using
dierent values of B. However, perhaps this should not be surprising, because
the two algorithms focus on dierent regions of the graphs and therefore
might be expected to encounter local minima of dierent depths.
The main dierence between FCNS and other stochastic colouring algorithms
is that it performs forward checking. It also has an additional advantage over
IG and SWO: incrementality . IG and SWO are not incremental because
restarting is an expensive move, whereas IMPASSE, TABU and FCNS make
small, cheap moves in the search space. This is pointed out as a source of
ine-ciency by Joslin & Clements [12], and they propose hybrids of SWO
with local search for future work.
Graph colouring is a binary constraint satisfaction problem (given xed
k), and the use of con
ict counts to perform forward checking in local search
is easily generalised to other such problems. It can be further generalised
to non-binary constraint problems, and this has been done for propositional
satisability (SAT). Experimental results are very promising: on some large,
structured SAT problems it out-performs current systematic and local search
algorithms [20]. In fact our colouring and SAT algorithms are instances
of a general-purpose approach to combinatorial optimisation and constraint
satisfaction, which we call Constrained Local Search (CLS). The aim of CLS
is to enhance local search with constraint programming techniques used in
systematic search. It has also given good results on other SAT problems [20],
maximum clique problems [22], Golomb rulers [22] and a hard optimisation
problem (the generation of low-autocorrelation binary sequences) [21]. The
general approach is to take an eective backtracking algorithm and replace
systematic by randomised backtracking, usually improving its scalability at
the expense of completeness.
It might be argued that FCNS (or more generally CLS) is not a local
search algorithm, but simply a randomised backtracker. It certainly is a randomised
backtracker and has much in common with Dynamic Backtracking
(DB), which also allows the removal of early assignments without aecting
the assignments made since. This increased
exibility of backtracking was a
stated aim in the design of DB, and a later hybrid algorithm called Partial
Order Dynamic Backtracking [7] achieved even greater
exibility. Is FCNS
simply an inferior version of DB, sacricing completeness to no good pur-
pose? A counter-example to this view is the random 3-SAT problem, on
which DB is slower than depth-rst search [1] while CLS scales precisely as
local search [21]. Our view is that FCNS stochastically explores a space of
FC-consistent partial colorations by local search; the objective function it
minimises is the number of uncoloured vertices. However, to some extent
the question is academic: even if FCNS is not local search, experimental
results show that it captures its essence, successfully solving problems that
are beyond the range of systematic backtracking.
There are several other hybrids of local search and constraint techniques.
The simplest hybrid is a parallel or distributed implementation of more than
one algorithm, as in the IMPASSE algorithms used for colouring. Schaerf's
timetabling algorithm [24], extended to constraint satisfaction problems,
searches the space of all partial assignments (not only the consistent ones)
using an objective function that includes a measure of constraint violation.
This is a dierent space again than those searched by current colouring algorithms
and FCNS. In graph colouring terms this space may be called the
partial colorations as opposed to the consistent partial colorations explored
by IMPASSE. Jussien & Lhomme's Path-Repair Algorithm [13] is described
as a generalisation of Schaerf's approach that includes learning (allowing
complete versions to be devised) and a TABU list. Yugami, Ohta & Hara's
EFLOP algorithm [27] uses constraint propagation to escape local minima,
while allowing some constraint violation. However, forward checking is not
maintained throughout the search, as it is in FCNS. Ginsberg & McAllester's
Partial-order Dynamic Backtracking [7] is a hybrid of the Dynamic Back-tracking
algorithm with a local search algorithm [6], enabling it to follow
local gradients in the search space. Pesant & Gendreau [18] apply systematic
branch-and-bound search to e-ciently explore local search neighbourhoods.
The two-phase algorithm of Zhang & Zhang [28] searches a space of partial
variable assignments, alternating backtracking search with stochastic local
search on the same data structure. It can be tuned to dierent problems
by spending more time in either phase. Yokoo's Weak Commitment Search
[26] (WCS) greedily constructs consistent partial assignments. On reaching
a dead-end it randomly restarts, and uses learning to maintain complete-
ness. Richards & Richards [23] describe a SAT algorithm called learn-SAT
based on WCS. Shaw [25] describes a vehicle routing algorithm called Large
Neighbourhood Search. It performs local search and uses backtracking with
constraint propagation to test the legality of moves.
Each of these algorithms either permits constraint violation or uses learn-
ing, or both. Constraint violation implies, in the view of this author, that
constraints are being under-used. This may be a drawback when solving
highly structured problems: the best graph colouring results for structured
problems are obtained by algorithms such as IMPASSE and FCNS, which
do not violate constraints. The use of learning is a drawback when solving
large problems. It can be restricted to use only polynomial memory, but
combinatorial problems may be very large. The FCNS approach combines
constraint handling and local search, making cheap local moves and avoiding
memory-intensive learning techniques. We believe that this combination of
features makes it ideal for large, highly constrained problems.



--R

The hazards of fancy backtracking


Exploring the k-colorable landscape with iterated greedy
Graph coloring with adaptive evolutionary algorithms
Journal of Arti
GSAT and dynamic backtracking
Coloring by tabu branch and bound
Increasing tree search e-ciency for constraint satisfaction problems
Optimization by simulated annealing: an experimental evaluation

Journal of Arti
The path-repair algorithm
Experiments with parallel graph coloring heuristics and applications of graph coloring
A column generation approach to graph colouring
Minimizing con- icts: a heuristic repair method for constraint satisfaction and scheduling problems
Distributed coloration neighborhood search
A view of local search in constraint pro- gramming
Using an incomplete version of dynamic backtracking for graph colouring
Stochastic local search in constrained spaces
A hybrid search architecture applied to hard random 3-SAT and low-autocorrelation binary sequences
Trading completeness for scalability: hybrid search for cliques and rulers

Combining local search and look-ahead for scheduling and constraint satisfaction problems
Using constraint programming and local search methods to solve vehicle routing problems

Improving repair-based constraint satisfaction methods by value propagation
Combining local search and backtracking techniques for constraint satisfaction
--TR

--CTR
Steven Prestwich, SAT problems with chains of dependent variables, Discrete Applied Mathematics, v.130 n.2, p.329-350, 15 August
Marco Chiarandini , Thomas Sttzle, Stochastic Local Search Algorithms for Graph Set T-colouring and Frequency Assignment, Constraints, v.12 n.3, p.371-403, September 2007
forward checking;graph colouring;coloration neighbourhood