A Constraint Programming Framework for Local Search Methods.
We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm.
Introduction
Local search methods in Operations Research (or) date back to over thirty years
ago [13]. Applied to difficult combinatorial optimization problems, this heuristic
approach yields high-quality solutions by iteratively considering small modifications
(called local moves) of a good solution in the hope of finding a better one. Embedded
in meta-heuristics designed to escape local optima such as simulated annealing and
tabu search, it has been very successful in achieving near-optimal (and sometimes
optimal) solutions to a variety of hard problems [8][23][1].
Constraint Programming (cp) features very flexible modeling capabilities to easily
and closely reflect the various constraints of a problem. In solving real-life combinatorial
optimization problems, it has to date almost invariably adopted the branch-
and-bound strategy, a global and therefore complete search method. 1 When an
exact algorithm proves too costly, simple approximate algorithms are often devised
by heuristically discarding the least-promising branches in the branch-and-bound
search tree (a form of beam search).
* A preliminary version of this paper appeared as [18].
What can constraint programming bring to local search methods? The fact that
heuristics tend to be specialized for a particular context can become a drawback
when faced with an even just slightly different context, such as side constraints:
adapting them may demand considerable time and effort. It is therefore tempting
to gain both the efficiency of local search methods and the flexibility of constraint
programming. In this paper we argue that local search is not so foreign to branch-
and-bound search and that constraints can be more actively involved in the exploration
of these local search spaces. We propose a clean integration of local search
in constraint programming by keeping on doing what comes naturally, i.e. branch-
and-bound, but on a different search space, though related to the original one. In
contrast with or practice, the resulting framework maintains a clear separation
between the constraints of the problem and the actual search procedure. For both
or and cp, the potential pruning capabilities open the door to more elaborate local
moves, which could lead to even better approximate results.
This adaptation of local search to the constraint programming paradigm stems
from its perception as a generalization of conventional cp branch-and-bound search.
In the latter case, we branch on the variables of the model and the neighborhood
degenerates into the whole solution space for which a single iteration becomes sufficient
since the optimal solution will necessarily be found. In order to lift this
approach to local search, the art then consists of choosing a representation for a
particular neighborhood structure which cp branch-and-bound search can exploit.
Each iteration of local search will simply be a branch-and-bound search, but on a
different search space. The active role of modeling constraints (discarding infeasible
neighbors) together with lower bounds on the cost of partial solutions (discarding
unattractive neighbors) will help prune the tree and thus reduce the search effort
over the whole neighborhood.
The rest of the paper is organized as follows. Section 1 first gives an overview of
local search methods and constraint programming. Our general framework for local
search in cp is presented in section 2. The implementation of that framework is then
illustrated on personnel scheduling (section 3) and single-vehicle routing (section
problems. An empirical study is included for this latter type of application. Finally
we address the flexibility offered by our framework in section 5.
1. Background
1.1. Local Search Methods in Operations Research
Local search methods involve repeatedly going from one solution to another through
a local move. What constitutes a valid local move varies according to the problem
and even within it (see for example section 4.1). The set of all solutions reachable
from a solution s through a local move is termed the neighborhood of s. The set of
all feasible solutions in this neighborhood will be called its feasible neighborhood.
Given this framework, a simple strategy called iterative improvement moves to
the best feasible neighbor (i.e. of lowest cost) every time until it does not improve
on the current solution, reaching a local optimum. Several ways of alleviating
the obvious drawback of this strategy have been proposed. Multi-start iterative
improvement achieves local optima from a pool of solutions and returns the best one.
Genetic local search builds upon the previous by recombining the local optima (in
the fashion of genetic algorithms [10]), applying iterative improvement, discarding
the least-promising solutions and repeating the process until some stopping criterion
is satisfied.
Two very successful strategies try to escape local optima by allowing moves which
temporarily increase the cost of the solution. Tabu search [7] moves to the best
neighbor at each iteration, regardless of whether or not it improves on the current
solution. To avoid cycling, a dynamic list of tabu solution attributes is kept. Typi-
cally, such a list covers recently examined solutions, which will remain forbidden for
a certain number of iterations. Simulated annealing [12] randomly selects a neighbor
at each iteration. If it improves on the current solution, the move is performed;
otherwise, it will be performed with a certain probability which depends on the
cost difference and which also decreases over time according to a cooling schedule.
Both strategies iterate until some stopping criterion is satisfied.
One crucial aspect in all of these local search methods is obviously the choice of
the neighborhood structure (see for example [9]). Ambitious neighborhoods increase
the chances of success but are more expensive to explore for methods which need
to do so. Small neighborhoods are both simple and fast to explore but may prevent
us from ever reaching a particularly good solution: it could require a sequence of
local moves (as opposed to a single one in a larger neighborhood), and every such
move would have to be the one selected in its iteration. A neighborhood which
strictly includes another induces a search which encounters fewer local optima and
thus facilitates their avoidance.
Because of the above, large neighborhoods are attractive. Several techniques have
been developed to speed up their exploration. The size of the neighborhood can
be somewhat reduced either by ignoring parts of it which are unlikely to produce
good solutions or, in a more exact fashion, by interrupting a carefully engineered
exploration when the remainder can only lead to worse (or infeasible) solutions.
In addition, the feasibility of neighbors must be assessed. As an early example in
routing problems, [24] describes a way to verify time-window constraints in constant
time per neighbor, though assumptions about the neighborhood structure must
be made. Others may perform approximate tests of feasibility to quickly identify
promising neighbors which are then thoroughly investigated, with the potential risk
of missing the best one.
So, the challenge of expressive neighborhoods has been met with specialized techniques
embedded in the local search and sometimes with compromises.
1.2. Constraint Programming
Constraint programming solves combinatorial problems by actively using the constraints
of the problem to implicitly eliminate infeasible regions of the solution
space. The algorithm at the heart of this approach implements complex logical
reasoning over the set of constraints.
To every variable of a cp model is associated a domain: each value in that domain
represents a possible value for the variable. Constraints on the variables forbid
certain combinations of values. Picturing the model as a network whose vertices
are the variables and whose (hyper)edges are the constraints provides insight into
the basic algorithm used in cp. A vertex is labeled with the set of values in the
domain of the corresponding variable and an edge is incident to those vertices
representing the variables appearing in the associated constraint. Looking locally
at a particular edge (constraint), the algorithm attempts to modify the label (reduce
the domain) of the incident vertices (variables) by removing values which cannot
be part of any solution because they would violate that individual constraint; this
local consistency step can be performed efficiently. The modification of a vertex's
label triggers the inspection of all incident edges, which in turn may modify other
labels. This recursive process stops when either all label modifications have been
dealt with or the empty label is obtained, in which case no solution exists. The
overall behavior is called constraint propagation.
Since constraint propagation may stop with indeterminate variables (i.e. whose
domain still contains several values), the solution process requires search and its
potentially exponential cost. It usually takes the form of a tree search in which
branching corresponds to fixing a variable to a value in its domain, thus triggering
more constraint propagation. We call variable-selection heuristic and value-
selection heuristic the way one decides which variable to branch on and which
value to try first, respectively. For combinatorial optimization problems, the tree
search evolves into a branch-and-bound search in which one branches in the same
way and lower bounds at tree nodes are obtained by looking at the smallest value
left in the domain of a cost variable.
1.3. Local Search in Constraint Programming
As we just saw, branch-and-bound search is by far the most popular (and natural)
solution strategy in constraint programming to handle combinatorial optimization
problems. A few exceptions are nevertheless found in the literature. A recent survey
on applications of constraint programming [28] describes applications in which local
search and cp are "loosely connected": the latter is used as a preprocessing step for
the particular heuristic employed. Others offer a tighter connection but essentially
consider individually each of the possible moves in a neighborhood to then assess
their feasibility and cost [22][3][2] 2 . This can be a costly endeavor when the nature
of the local moves is such that a great number of possibilities must be considered.
To solve constraint satisfaction problems, which abound in Artificial Intelligence,
repair-based methods (e.g. [25][15]) have had a good share of success. They can be
viewed as local search methods which typically consider a very small neighborhood
(changing the value of one variable) and use iterative improvement in order to
minimize the number of violated constraints.
2. A New Combination of Local Search and CP
As mentioned in the introduction, we will view local search as a sequence of cp
branch-and-bound searches. Given a combinatorial optimization problem P , which
we call the master problem, and some initial solution to it, we will solve a sequence
of auxiliary problems using standard constraint programming techniques. P is described
by a constraint programming model whose role is to ensure the feasibility
of our solutions. Each auxiliary problem is described by another constraint programming
model, called the neighborhood model, which describes the local search
space. The two types of models are related by interface constraints.
Definition 1. Neighborhood model. Let N denote some neighborhood structure
for solutions to a combinatorial optimization problem P . A set of finite-domain
variables usually distinct from the variables appearing in the model
for P , together with a (possibly empty) set of constraints on f- is a neighborhood
model for N if there is a one-to-one mapping between the set of feasible
combinations of values for f- and the neighbors in N .
Example: Let P be the traveling salesman problem on m cities and consider
the exchange of two cities in a solution as our neighborhood structure N . We
introduce variables I and J , both ranging over the interval [2; m], and the constraint
I ! J between them. If a solution is represented as the sequence
of cities forming the tour, a particular (feasible) combination of values for fI ; Jg is
interpreted as exchanging entries c I and c J in that solution to obtain a neighbor.
One easily verifies that this constitutes a neighborhood model.
The requirement of a one-to-one mapping could be relaxed to a surjective mapping
though this would mean that a neighbor may be examined more than once: without
the constraint I ! J in the example above, symmetry would lead to identical
solutions. However, surjectivity is crucial since otherwise we would miss some of
the neighbors.
The solution space defined by the neighborhood model can be explored by standard
cp branch-and-bound search. We branch on f- and also bound the
cost of partially constructed neighbors. As we saw in section 1.1, some heuristic
algorithms based on local search, such as tabu search and variations on iterative
improvement, are interested in acquiring the best solution in the neighborhood
and hence do not require to manipulate the whole of it per se. We can therefore
record the cost of the best neighbor found so far and derive lower bounds for partial
neighbors to reduce the portion of the neighborhood that has to be explored,
as in conventional branch-and-bound. Note that we do not prescribe the order in
which we select variables for branching: in accordance with common practice in the
constraint programming community, dynamic variable-selection and value-selection
heuristics may be used to increase the efficiency of the search.
Initially, the model for the master problem is stated and the variables of that
model are only constrained to that extent - in other words, they are not bound to
the current solution. Then the local search takes place in the form of a complete
NEIGHBORHOOD MODEL
local move
restricting neighbors
fixing main
constraint checking interface constraints

Figure

1. The interaction between the master and neighborhood models.
branch-and-bound search on the neighborhood model. At different stages of the
branch-and-bound search, valuable information can be exploited in order to restrict
the set of allowable values for the neighborhood-model variables on which that
search is performed and, more importantly, constrain as well the principal modeling
variables of the master problem which may independently prune our search tree by
propagating these changes through modeling constraints we need not know anything
about (see figure 1). We automate this behavior by introducing a set of conditional
constraints 3 called the interface constraints.
Definition 2. Interface constraints. An interface constraint has the form
stands for a subset of the variables in the model for P . It adds constraint
once each of - fixed. The set of interface constraints
establishes the link between the model for P and the neighborhood model:
as variables of the latter model are fixed during the branch-and-bound search, constraints
are generated on some variables of the neighborhood model and some of
the master problem, reflecting the fact that we narrowed the search.
We see two main advantages for such a framework:
Flexibility, genericity. The modeling constraints for P (and often some of the
are kept separate from the neighborhood model. This provides a flexible
way to state instance-specific constraints, independently of the local search.
It is especially useful when lots of different side constraints are present in the
problem: they will not clutter the local search with explicit feasibility tests as
is often the case in operations research heuristics. They will rather be indirectly
involved when some of the modeling variables will be further constrained
through the interface constraints as a result of branching on - . The end
result is a generic neighborhood exploration method parameterized by the type
of neighborhood structure but not by the nature of the modeling constraints for
the master problem.
Table

1. Availability of physicians
A,B,C,D,E. (a=am, p=pm, n=night).
Mon Tue Wed Thu Fri
A p/n a/p n a/p/n p
C p/n a a/p/n a/n n
Search Economy. There is a strong relationship between the savings brought
about by this branch-and-bound approach and how ambitious the neighborhood
is. Typically, enlarging the neighborhood means increasing the degrees of
freedom and so requires a greater number of variables to encode its structure.
This translates into a greater depth of the neighborhood search tree and a potentially
larger gain with every branch pruned 4 , either from the lower bound at
the particular node or the modeling constraints. This constitutes an asset in
view of the current trend toward more ambitious neighborhood structures. The
freedom of choosing the order in which variables are fixed and values tried also
contributes to that gain.
On the other hand, there is of course a price to pay for that flexibility, namely
the cost of constraint propagation and of built-in backtracking. We will attempt to
empirically evaluate the overall efficiency of the approach in sections 4.4 and 4.5.
3. An Introductory Application: Physician Scheduling
Here is a first illustration of this general framework. On a hospital ward, there
must be a physician on duty at all time. Consequently, a ward schedule has to be
established for the staff of physicians. As can be expected, the rules governing the
construction of a valid schedule vary from one hospital to the next. We describe
but one such context.
Each day is divided into three shifts: am, pm and night. (For the night shift, the
physician is simply on call.) The planning horizon is typically a few months. There
are several rules about the frequency of shifts covered by the same physician:
1. no more than one shift per day;
2. no two consecutive shifts (for example, Monday-night then Tuesday-am);
3. no two consecutive night shifts.
Physicians also have other duties elsewhere, especially the ones who have a part-time
status. They hand in a form specifying the shifts for which they are available
(table 1 gives a small example for five physicians over an horizon of five days).
If two physicians share a responsibility outside the ward on a certain day, they
may ask that at least one of them be off daytime duty on that day. Finally, a
target workload (in number of shifts) is assigned to each physician, which may vary
according to her status. A good schedule should remain close to the targets.
Let the planning horizon range from day 1 to n and let
be the set of shifts to assign in the schedule. Let MD represent the set of physicians
on staff, A k , the set of pairs hi; ji such that physician k is available for the j shift
on day i and R, the set of pairs hfk; k 0 g; ii such that physicians k and k 0 cannot
be both on daytime duty on day i. A natural model for this problem associates a
distinct variable to every shift being assigned:
The constraints listed above can be expressed as follows, in the same order:
stand for the target workload of physician k whereas ff k stands for her
actual workload in the schedule. We adopt a least-squares objective function to be
A local move will consist of changing the value of one slot in the schedule. Let
oe represent the current schedule and oe(hi; ji) the physician currently covering the
j shift on day i. A neighboring schedule of oe can be encoded through a variable
S representing the slot to be modified and a variable V representing the new value
for that slot. Our neighborhood model is then:
The cost of a local move replacing physician k 0 by k in some slot is
which simplifies to
If the target workload is the same for all physicians, evaluating the relative merit
of a move simply amounts to looking at ff k \Gamma ff k 0 .
Table

2. A feasible schedule (left) and an optimal schedule (right).
Mon Tue Wed Thu Fri
Mon Tue Wed Thu Fri

Table

3. The partial schedule after choosing one possible completion (right).
Mon Tue Wed Thu Fri
Mon Tue Wed Thu Fri
Let ffXgg denote the current domain of finite-domain variable X . We introduce
the following interface constraints:
When S is fixed to some slot ha; bi:
conditional constraint (7) fills all the other slots with the value in the current
schedule since they will not change;
conditional constraint (8) binds V to S a;b , thus restricting V to the possible
values for that slot and forbidding the current value for S a;b , through constraint
of the neighborhood model.
When V is fixed to some physician k:
conditional constraints (9) and (10) maintain the value of all the slots which
cannot possibly change: those whose value is k already and those which cannot
take that value;
conditional constraint (11) restricts S to the slots which may admit value k.
Example: Consider a simple instance with five physicians, a scheduling horizon of
five days, physician availabilities as given in table 1 and a uniform target workload
of three shifts per physician. In addition, physicians A and D cannot be both on
daytime duty on Thursday and neither can B and C on Wednesday. Table 2 gives
a feasible schedule in which A works four shifts and D only two, yielding a score of
2 on the objective function. We will investigate the possible local moves from that
schedule.
In a cp branch-and-bound search on our neighborhood model, a popular variable-
selection heuristic would have us branch on the variable with smallest domain first.
In our case that would be V . As far as trying the different values for V , it makes
sense to order them according to a lower bound on the relative merit of the possible
local moves introducing that value, and starting with the smallest bound. For value
A, we look at (ff A \Gamma ff x similarly, for the other values we get
\Gamma1; \Gamma1; \Gamma2; \Gamma1, in that order. We will therefore start by examining D, as illustrated
in the search tree on the left in figure 2.
This triggers constraints (9)-(11), the first two partially filling the schedule as
illustrated on the left in table 3. Entries shown in bold result from more elaborate
reasoning than a mere initial unavailability of D for that shift, and are achieved
through constraint propagation. For example, once shift h3; nighti has been filled
by D (constraint (9)), constraint (3) tells us that shift h4; ami cannot be filled by D
as well and so should take its current value A (constraint (10)). Now then, because
A and D cannot be both on daytime duty on Thursday (constraint (5)), shift h4; pmi
should also take its current value E. The domain of S is made to correspond to the
unassigned shifts in the partial schedule, fh1; nighti; h2; pmig through the combined
effect of constraints (11) and V 6= oe(S).
Branching now on S, we can again order the two branches according to the
lower bound, though here they have identical value. The leftmost branch brings
us to a terminal node, changing the value of slot h1; nighti to D, with a relative
merit of \Gamma1. Conditional constraint (7) fills the rest of the schedule. Since that
relative merit score is as good as any lower bound on unexplored branches in the
search tree, the rest of the tree can be pruned and we are done (see figure 2(left)),
yielding the schedule on the right in table 3. The actual cost of that move is
which keeps the objective function at 2.
A further iteration using the same strategy would produce the search tree on the
right in figure 2 and a local move of cost \Gamma2, bringing the objective function down
to 0. We would therefore have an optimal schedule, shown on the right in table 2
with the overall modifications in bold.
This small example is already sufficient to bring forth the two advantages stressed
at the end of section 2. Exploring the neighborhood by first fixing V then S runs
contrary to what would naturally come to mind, that is, first choose a slot to modify
and then pick a new value for it. Nevertheless, it is probably the better strategy of
the two since the search trees generated tend to be more sparse. The combination
of this variable-selection heuristic with a value-selection heuristic, constraint propagation
and lower-bound pruning yields a neighborhood exploration which is very
efficient in terms of the number of neighbors (terminal nodes) actually considered.
The other advantage was a generic local search with the flexibility to handle
instance-specific constraints. As we mentioned before, in this type of personnel
scheduling problem the rules of the game depend on where you are. With this
"C" "E"
"A" "D"
"A"

Figure

2. Neighborhood search trees: first (left) and second (right) iterations. Branch labels are
"value"/"lower bound". Terminal nodes are labeled with the relative merit of the move.
approach, the different hospital contexts will be reflected and handled in the master
model and not in the local search itself.
4. A Routing Application Using Tabu Search
This section provides another instance of the general framework described in section
2. It addresses a well-known problem on which several local search heuristics have
been applied in the past. The traveling salesman problem with time windows
(tsptw) consists of finding a minimum cost (usually the total travel distance or
total schedule time) tour of a set of cities where each city is visited exactly once
and which starts and ends at a unique depot. In addition, each city must be visited
within its own time window. Early arrival is allowed but implies a waiting time until
the beginning of the window. [24] showed that simply deciding whether there exists
a feasible solution to an instance of the tsptw is NP-complete. Nevertheless, the
full problem has important applications in bank and postal deliveries, school-bus
routing and scheduling, disjunctive scheduling with sequence-dependent processing
times, automated manufacturing environments and as a subproblem of the vehicle
routing problem with time windows (vrptw).
A constraint programming model for our master problem, the tsptw, was presented
in [19]. We sketch it below, emphasizing the main variables which will be
referred to later on. Let ng represent the set of cities to visit and duplicate
the unique depot into an origin-depot and a destination-depot, identified as 0 and
tour thus becomes a Hamiltonian path starting at 0 and
ending at n+ 1. At the heart of the model are variables S i associated
to each of the cities (and the origin-depot) and which represent their successor in
the tour. Their domain will therefore be an integer in the range
valid tour assigns a distinct successor to each city and avoids sub-tours. We also
define predecessor variables
counterpart of the S i 's (S To account for the scheduling component
of the problem, variables T i are introduced to represent the time at which we
visit each city. These must take a value within their respective time window while
being coherent with the order in which cities appear on the tour and taking into
consideration the travel time between cities. Several redundant constraints are also
present to increase the amount of propagation.
4.1. Some Neighborhoods for Routing Problems
Given the inherent difficulty of the problem, several or heuristic algorithms have
been designed and among them some based on local search. We briefly describe
the most popular neighborhoods in the context of routing problems, which include
the tsptw but may allow solutions consisting of a set of routes and involve other
restrictions such as capacity constraints.
Neighborhoods generated by modifications at the level of vertices include re-inserting
a vertex or exchanging two vertices. GENI, a generalized insertion procedure
[5], directs the re-insertion between some of its p (from 2 to 7) nearest
neighbors. In the -interchange [17], subsets of vertices
are selected each from a different route and then swapped. The possibility
of an empty subset allows simply re-inserting vertices. For efficiency reasons, -
rarely exceeds 2.
At the level of edges, a k-interchange [13] replaces k edges in the solution by k
others that reconnect the route(s). Lin-Kernighan moves [14] for the tsp increase
k until a gain criterion fails and only consider nearest neighbors of vertices for the
exchanges. An Or-opt move [16] relocates a string of one, two or three consecutive
vertices. A 2-opt ? move [21] replaces two edges (v different routes
with edges (v This exchanges the end portion of one route with the
end of the other. The CROSS exchange [27] goes further by exchanging a middle
portion of one route with a middle portion of the other, replacing four edges, and
includes the two previous types of moves as special cases.
4.2. An Orientation-Preserving 3-Interchange Neighborhood
We consider the orientation-preserving 3-interchange neighborhood and provide a
neighborhood model for it. Let T be the current tour. If I represents a city on
this tour, then I its successor (respectively predecessor)
on T . We define the following binary relation on cities: I OE J holds if I appears
before J on T .
Without loss of generality, let I OE J OE K. A 3-interchange move from T deletes
the three edges reconnects the tour by introducing
three new ones on the vertices (cities) I , I
orientation-preserving 3-interchange move reconnects the tour in the only possible
way which does not reverse any of the original route segments, by adding edges
I I

Figure

3. The orientation-preserving 3-interchange.
3). This is desirable when a scheduling component
is present in the problem, such as time windows. Two segments of the original
route have been swapped but the ordering within a segment is kept.
The neighborhood defined by orientation-preserving 3-interchange moves can be
encoded through three finite-domain variables I ; J; K, ranging from 0 to n. Their
interpretation is the one given above. Because of constraint I OE J OE K, each
neighbor is in one-to-one correspondence with a 3-tuple of values describing it. We
therefore have a neighborhood model:
ng
I OE J OE K:
Associating a cost c ij to every edge (i; j), the cost of a local move is given by
the total cost of the arcs we add minus the total cost of the ones we remove. Its
smallest possible value will be used as our lower bound and will be refined automatically
through constraint propagation as the domains of I ; J; K shrink (ultimately
to a single value).
Here are the interface constraints used during the branch-and-bound search (refer
to figure 3 throughout):
Conditional constraints (12)-(15) deal with information traveling from the neighborhood
model (the box on the right in figure 1) to the master model (the box on
the left in the same figure): in (12) for example, as we try a value for I , say i, we
know that the initial tour segment up to i will remain in the new tour and so the
appropriate successor variables in the routing model can be fixed. (13)-(15) respectively
address tour segments hi which are unchanged
in the neighboring tour.
Conditional constraints (16) and (17) reflect the fact that having fixed I to i
allows us to constrain further J and K: J must appear, in the current tour, just
before the successor of i in the new tour (corresponding to the addition of edge
must be the predecessor of i + in the new tour (corresponding
to the addition of edge Similarly, (18) and (19) restrict I and K given a
value for J while (20) and (21) restrict I and J given a value for K. In turn, this
is information traveling from the master model to the neighborhood model: the
successor and predecessor variables, constrained by the master model, restrict the
possible values for I , J and K, which are used to identify the potential arcs to be
added and removed in a neighboring tour.
Suppose for example that the variable ordering in our search tree is I ; J; K
throughout. Then at depth 1, with I fixed, conditional constraints (12), (16) and
(17) will be triggered; at depth 2, with both I and J fixed, (13), (19) and (18)
will be triggered but only the first two will be useful since the value of I is already
known; finally at depth 3, with all the variables fixed, only (14) and (15) will be
worth triggering.
As we saw, only the S i 's and P j 's in the master model and the I ; J; K variables
for the neighborhood model were involved in the interface. Note for instance that
the time variables T i were not directly involved.
Example: Consider the following example in which we wish to find a good tour
of cities fb; c; d; e; f; gg starting at a and ending at h, the two copies of the depot.
Aside from the usual constraints in the master model, we add two others, c OE g
(in any feasible tour) and S d 6= g, to show how instance-specific constraints are
taken into account when examining neighbors. We shall concentrate here on the
implicit pruning of infeasible neighbors through the constraints and leave out that
of unattractive neighbors through the lower bounds. We therefore ignore the cost
of individual arcs in our exploration. Our variable-selection heuristic will again be
the common "smallest-domain-first", with lexicographic order as a tie breaker.
Let the current tour be ha; b; c; d; e; f; Initially, branching variables I , J and
K have domains as indicated in figure 4-i; they are of equal size and so we first
branch on I . At the root of our search tree we have five possible values for I : a, b, c,
d or e. They should be tried in turn for a complete exploration of the neighborhood
but let us jump to when b is considered (figure 4-ii). Several things happen:
{ c, d, e, f, g }
{ a, b, c, d, e }
{ b, c, d, e, f }
c
f
d
e
a
{ c, d, e, f, g }
{ a, b, c, d, e }
{ b, c, d, e, f }
c
f
d
e
a
I
c d e
I
b c d
e
a
I
d
e
I
d
e
c
f
d
e
a
{ d, e, f }
{ c, d, e }
I b
c
f
d
e
a
e
d
-i-ii-iii-iv-
Figure

4. Exploring a neighborhood.
ffl The neighborhood-model constraint I OE J OE K triggers the removal of value b
from the domain of J and then c from the domain of K.
ffl Conditional constraint (12) sets S a to b as the initial tour segment.
ffl Conditional constraint (16) enforces could reduce the domain
of J depending on what the possible values for S b are.
ffl Conditional constraint (17) enforces . The combined action
of instance-specific constraint c OE g removes g from K's domain, since g is
certainly not part of the domain of P c . In addition, f is removed from J's
domain, through J OE K.
We are left with three possible values in each of J and K's domain and so move on
to fix J . Suppose we try d (figure 4-iii):
ffl The neighborhood-model constraint J OE K triggers the removal of value d from
the domain of K.
ffl Conditional constraint (13) sets S c to d as the current tour segment from i + to
j.
ffl Conditional constraint (19) enforces Now since S d 6= g was given
as an instance-specific constraint, (S d so f is removed from
K's domain.
Finally we fix K to the only possible value, e (figure 4-iv):
ffl Conditional constraint (14) does not result in any variable assignment since
tour segment consists of the single city e.
ffl Conditional constraint (15) sets S f to g and S g to h as the remaining tour
segment.
4.3. A Tabu Search Algorithm
In order to evaluate some of the efficiency issues related to this approach, we used
the previous neighborhood structure within a tabu search algorithm. Our aim is
twofold: to evaluate the efficiency of the branch-and-bound search in terms of the
proportion of the neighborhood explicitly visited; to compare its execution time
with that of a conventional, specialized tabu search algorithm with the objective of
measuring the cost of constraint propagation and backtracking. We will therefore
leave out ad hoc constraints and remain strictly within the reach of that specialized
algorithm for the tsptw. This section describes the specifics of the algorithms.
A random tabu tag is associated with each pair of cities (each arc) and initially set
to zero. When a move is performed at iteration i, the three arcs being replaced in
the tour are only allowed to be brought back into the tour after iteration i+', where
' is an integer randomly drawn from the interval [5; 10] (a ' is drawn separately
for each arc): their tabu tag is thus updated to i '. The tabu status of a move
is determined by examining the tabu tags of the three arcs it would bring into the
tour: unless each tag is less than the index of the current iteration, the move is
declared tabu. However, an aspiration criterion is included according to which the
move will be performed anyway if its cost improves on the cost of the best tour
met so far. To obtain our initial feasible solution, we use a "near-sighted" version
(with of the generalized insertion heuristic geni-tw [6]. We then run
100 iterations of tabu search on it (this fixed number of iterations serves as our
stopping criterion and simplifies comparisons in the next section).
Two versions of the cp tabu search algorithm were implemented, coined "full" and
"light". They differ in the extent of the master model used. Neither includes the
structural tsp constraints (distinct successors; sub-tour avoidance) since the nature
of a move guarantees a valid tour (ignoring time windows). The "full" version uses
the rest of the model outlined at the beginning of section 4 while the "light" version
omits the redundant constraints, keeping only what is necessary to ensure time-window
compliance. A non-cp, specialized version only departs from the other
two in the way the neighborhood exploration is carried out: three nested loops
iterate over the whole neighborhood and the feasibility of each neighbor is explicitly
assessed without resorting to constraint propagation. Finally, a "passive" cp version
also proceeds by nested loops but uses constraint propagation (through the "light"
model) to verify the feasibility of neighbors. It represents a popular approach to
combining cp and local search (as indicated in section 1.3) and does not actively use
the constraints to restrict the part of the neighborhood which must be explored.
All four implementations are written in C++ (the cp versions use ilog Solver,
a C++ library implementing constraint programming for combinatorial problems
[11]) and even share some of the code. The seed for the generation of random tabu
tags is the same so that all four executions follow identical sequences of moves on
a given instance. Neighborhood exploration is therefore the only variable.
As in the example at the end of the previous section, our variable-selection
heuristic for the branch-and-bound search was "smallest-domain-first". When a
tie-breaker was frequently needed (i.e. for the "light" version without lower-bound
pruning, which reduces little the domain of branching variables), we found that
the ordering I ; K; J performed significantly better than lexicographic ordering. It
has the advantage of identifying early on the only backward arc introduced by the
move, (K; I + ), which is most likely to cause a time-window violation. For the value-
selection heuristic, we considered several strategies. Our first attempt was to imitate
what we had done in the physician scheduling example and order values according
to some measure of the cost of the related moves. For each value v in the domain,
an inexpensive measure such as "\Gammac vv + ", the cost of one of the arcs being replaced,
or refinements such as "minfc vSv
proved no better and even worse than a simple lexicographic ordering, on our bench-
marks. A possible explanation is that whereas in the physician scheduling example
it seemed likely that the selected branch of the search tree could be extended to a
feasible move, here such likelihood is doubtful as hinted in the next section by the
constrainedness indicator. As a result, we may not find a feasible neighbor for a
while and thus miss opportunities to prune unattractive subtrees. An orientation-preserving
3-interchange should more likely be feasible if it swaps two short tour
segments, i.e. when I , J and K are close on the tour. Lexicographic order was
successful because our initial solutions happened to almost follow that ordering and
so lexicographic proximity was synonymous to proximity on the tour. Accordingly,
we implemented a simple value-selection heuristic, favoring the earliest v on the
tour, which outperformed on average all the previous strategies.
4.4. Experimental Results
For our experiments, we considered a set of Euclidean problems with travel times
between cities taken as the distance separating them. They are in fact subproblems
of a well-known vrptw testbed from [26]. The original problem instances feature
100 cities distributed on the [0; 100] \Theta [0; 100] grid and require several vehicles to
service them while obeying the side constraints. Some partition of the cities such
that each group may be visited by a single vehicle yields our subproblems, 25 in
all. We used the instances from the RC2 class which features a mixture of clustered
and uniformly distributed cities and requires few vehicles, yielding larger routes.
Their resulting size varies from 20 to 42 cities.
In addition to execution time, we introduce two indicators to analyze the results:
jfeasible neighborhoodj
jneighborhoodj \Theta 100

Table

4. Constrainedness (fl) and search effort (ffl) for several tree-search strategies.
problem fl ffl-full ffl-light
pruning pruning pruning pruning
rc203 3.4 36.4 12.9 40.2 77.1 20.8 74.0
rc204 10.1 54.5 11.6 72.2 94.3 12.7 88.4
rc206 1.1 17.9 8.3 17.1 31.4 14.1 34.7
rc207 2.5 36.4 11.1 37.1 61.6 13.3 58.9
rc208 4.1 64.3 18.8 79.7 100.0 17.3 93.4
will indicate how constrained a problem instance is by evaluating for a given solution
the proportion of neighbors which are feasible;
jsearch-tree leavesj
jneighborhoodj \Theta 100
will measure the effort put into our neighborhood exploration by comparing the size
of the search tree with the size of the neighborhood. Both fl and ffl are expressed as
percentages.

Table

4 evaluates fl and ffl on the benchmark problems for the versions which
explore the neighborhood by tree search. Instances are aggregated according to the
original vrptw instances (rc201 to rc208) since they tend to have similar time-window
characteristics. Each entry thus represents the average of 2 to 4 tsptw
instances, each averaged over 100 iterations of tabu search. The second column gives
the percentage of feasible neighbors; the following two groups of three columns, the
search effort for the "full" and "light" version, respectively. Within each group,
the column on the left reports on a plain tree search, whose pruning comes from
constraint propagation only and not from lower bounds on the cost at tree nodes;
the middle column reflects the addition of lower-bound pruning to the tree search
to obtain branch-and-bound; we leave out the column on the right for now.
Our first observation is that practically all these instances exhibit very constrained
neighborhoods for the solutions considered: fl averages 3.3%. Even rc204, with very
few meaningful time windows, has an average fl of 10.1%. Avoiding the systematic
exploration of the whole neighborhood therefore appears advantageous. Looking at
the search effort for plain tree search, the "full" version performs much better than
the "light" one in examining roughly half the number of leaves: as can be expected,
more powerful propagation ends up producing smaller ffl's but also slows down the
exploration as we will see in table 5. The gap in the search effort narrows for branch-
and-bound search where the lower-bound pruning common to both versions has a
significant impact. That impact is striking when we look at the difference between
plain tree search and branch-and-bound search within each version, particularly
the "light" one. The variation in the search effort between the eight groups of
instances, especially visible in column six where we only rely on the time windows for

Table

5. Computation times (in cpu seconds on a sun Sparc 10) for several tree-search strategies.
problem full light
pruning pruning pruning pruning
rc206 4065.2 3488.4 4538.0 282.0 1767.9 323.4
rc207 8532.2 5103.5 8933.6 524.4 2936.7 686.3
rc208 40444.4 9454.2 28542.6 964.3 3475.7 1663.9
pruning, reflects the variation in typical time-window width between those groups
of instances.
The aspiration criterion included in our tabu search algorithm prevents missing
out on the best solution found so far simply because the move leading to it is
tabu. On the other hand, it requires evaluating every tabu move. In a tree-search
setting such as ours, knowing at an internal node that a tabu arc is involved implies
that every move through that node is necessarily tabu. Disregarding the aspiration
criterion could allow pruning whole subtrees of tabu moves. We investigated what
we call tabu pruning. Each time one of the branching variables is fixed to some
value v, thus identifying a break in the current tour, tabu pruning eliminates tabu
arcs from the two sets of candidates, f(v; w)
to reconnect that break. This translates into removing some of the possible
values for the remaining branching variables. Columns five and eight of table 4
report the result of adding tabu pruning to plain tree search (without lower-bound
pruning). This often lowers the search effort though not necessarily (for example,
rc208 in column five or rc206 in the last column) since it affects the variable-selection
heuristic and so the topology of the search tree.

Table

5 is organized as the previous table and gives the computation times. Turning
first to the "full" version, we see that the addition of lower-bound pruning does
significantly reduce the computation time, as hinted by the reduction in search effort
in the previous table. The usefulness of tabu pruning is not proven here: it
may decrease or increase the computation time, depending on the instance. Tabu
pruning can also change the best solution found by the tabu search algorithm. Six
of our 25 benchmark problems showed an increase of the solution cost ranging from
0.1% to 1.5%. On the other hand, one problem showed a decrease of 1.9%.
It is not at all clear that a large and powerful constraint model with several
redundant constraints, designed with a standard branch-and-bound exact (global
search) algorithm in mind, is appropriate for local search. Indeed, the figures for
the "light" version show a marked improvement over the other one. For plain
tree search, this translates into a decrease in the area of one order of magnitude.
What comes as a surprise is that the addition of lower-bound pruning significantly
hampers the efficiency despite its great contribution in reducing the search effort.

Table

6. Computation times (in cpu seconds on a sun Sparc 10) for four implementations of tabu
search on benchmark problems and comparative ratios.
problem non-cp passive cp ratio light ratio light ratio
passive plain plain
rc204 30.4 2615.4 86.0 1412.7 46.5 160.1 5.3
rc206 48.6 1458.7 30.0 282.0 5.8 108.8 2.2
rc207 52.2 2595.3 49.7 524.4 10.0 103.8 2.0
rc208 60.9 1993.2 32.7 964.3 15.8 134.7 2.2
average: 40.5 16.2 4.0
Runtime statistics reveal that the amount of backtracking information maintained
for the branch-and-bound is about 10 times the amount for plain tree search. The
sharp drop in efficiency is apparently due to the repeated storage and retrieval
of all that information. It was not a major factor in the "full" version because
that extra amount of backtracking information was added to an already significant
amount associated to the full constraint model. Tabu pruning generally increases
the computation time and is not attractive for this light-weight version.
This setback for lower-bound pruning prompted us to implement the explicit computation
of lower bounds at tree nodes instead of relying on constraint propagation
to a cost variable. We subsequently refer to this implementation as lower-bound
pruning ? . The improvement in speed was astonishing, as we will see in the next
table.

Table

6 compares the computation time of four tabu search implementations.
Column two represents the specialized version, which is faster as expected. Next
comes the computation time for the passive cp version followed by a comparison
with the specialized version (passive cp / non-cp). That ratio reflects the sole
cost of constraint propagation, here averaging 40:5. The other two groups of two
columns represent the light-plain and light-plain with lower-bound pruning ? versions
and the ratios are all taken with respect to the non-cp version. The ratios
for the light-plain combination indicate how profitable it can be to proceed by
tree search instead of systematically considering every neighbor as in passive cp:
tempering the cost of constraint propagation with the elimination of subtrees of
neighbors yields the average ratio of 16:2. The light-plain combination is thus 2:5
times faster than passive cp. It even outperforms the latter on rc208 for which there
was no elimination of neighbors to speak of (see table 4): the triggering of interface
constraints at various levels of the tree corresponds to factoring out common
constraint propagation fragments among subsets of neighbors. The lower-bound
pruning ? implementation now brings out the savings observed in search effort. It is
on average four times faster than plain tree search and ten times faster than passive
cp. It also comes within a factor of four of the specialized version.
Figure

5. Performance ratio for larger neighborhood search trees.1357
CPU
time
ratio
nb of cities
3-interchange
4-interchange
These experimental results clearly indicate the superiority of our approach over a
more passive use of constraint propagation in local search. Unfortunately, the cost
of constraint propagation and built-in backtracking still prevented us from being
competitive with the specialized version on these instances. We therefore decided to
investigate larger neighborhood search trees in order to increase the natural payoff
of branch-and-bound pruning. This was done in two ways: increasing the size of the
instances (number of cities), which affects the breadth of the neighborhood search
tree; and considering 4-interchanges instead of 3-interchanges, which increases the
depth of the search tree by one. As our previous instances fell in the range 20-40
cities, we considered 20-, 40-, 60-, and 80-city instances taken from [4]. These additional
results are summarized in figure 5 which plots the ratio of the execution time
for our final approach (light lower-bound pruning ? ) over that for the specialized
version, for both 3- and 4- interchange neighborhood structures and for increasing
problem size. Each point is the average of over a dozen instances of varying time
window width.
As expected, our relative performance improves with the growth of the search
tree, especially between 20 and 40 cities. (Note that these results are consistent
with the average value and variability of the ratios previously reported in table 6
on different instances.) For 3-interchanges, the average ratio falls to 1.5 at 80 cities.
Note in particular that for 4-interchanges it drops below one starting at 60 cities: we
thus perform better than the specialized version from that point on. Even though
a 4-interchange is seldom used in practice, a neighborhood search tree of depth
four would not be uncommon: we have already mentioned the cross exchange for
routing; for our physician scheduling application in section 3, changing the value of
two slots at a time instead of one, a very plausible neighborhood structure, would
also correspond to a depth of four.
4.5. Applying the Framework to the GENIUS heuristic
The combination of a well-known tsp heuristic, genius [5], with the constraint
programming routing model sketched at the beginning of the section is described
in [20]. Though this heuristic, composed of a tour construction phase and a post-optimization
phase, is not strictly speaking a local search algorithm, each of its two
phases involves the exploration of a neighborhood very similar to what was used
earlier. It was therefore a good candidate for our framework.
The resulting algorithm, genius-cp, was able to solve variations on the tsp (with
single or multiple time windows, precedence constraints, sequencing constraints,
pick-up and delivery problems) by simply adding the appropriate constraints to
the master model without any modification to the algorithmic part (genius). In
contrast, a subsequent version of the original heuristic to handle single time win-
dows, genius-tw [6], had required major changes: the addition of backtracking
capabilities, special-purpose code to verify feasibility and adjustments of algorithmic
control to reflect the temporal flavor of the problem.
A comparison of genius-cp and genius-tw on benchmark problems with single
time windows revealed that the flexibility of our approach cost us about a factor of
four in speed 5 , but the former more often found the best solution whenever their
solutions differed. As for the other variations on the tsp, no specialized heuristic
based on genius existed and so we compared with a close relative on the other side
of the family, an exact cp algorithm using the same routing model. It confirmed
that genius-cp was more robust and several orders of magnitude faster. The
heuristic solutions obtained were also often optimal and generally very good.
5. Addressing Flexibility
The previous section provided evidence of the search economy achieved by our
framework; the report on genius-cp also displayed some of its flexibility. We
would now like to briefly return to that latter advantage.
Again, the root of that flexibility is the separation of the constraints of a problem
(the declarative part) from the heuristic search strategy (the algorithmic part).
Because of this, a particular heuristic search strategy can serve in different contexts
without any modification of its implementation. Such an approach presents clear
advantages from a software engineering point of view: since one only needs to adapt
the model to the problem, it makes it much easier and faster to tailor a piece of
software to real-life situations while reusing the algorithmic component as is.
It also has an impact on the maintainability of the code, especially if additional
constraints suddenly arise. In such a situation, a non-cp approach would either
have to modify the way valid neighbors are generated or add feasibility tests, to
reflect the additional constraints. Both solutions alter the algorithmic component.
In contrast, a cp approach will add the required constraints to the declarative
component (the model), which often simply amounts to expressing them using
variables already present in the model and standard constraints. For example, we
give below some constraints and their expression in the context of section 4:
sequencing constraints:
city j must be visited last:
must immediately follow city i: S
precedence constraints:
city j must be visited after city i:
multiple time windows:
city i may be visited from 9am to 5pm but not between noon and 1pm:
The adaptation of the program would thus consist of one additional line of code
per new constraint, leaving the rest of it unchanged.
Conclusion
We have proposed a novel framework for local search algorithms in constraint pro-
gramming. By maintaining branch-and-bound search at their core, we believe that
a cleaner and more natural integration is achieved. In addition, the familiar pruning
which can take place yields substantial savings on the number of neighbors that
actually need to be considered. A major advantage of bringing constraint programming
into local search methods is the flexibility and ease with which additional
constraints can be handled.
Two examples of this framework were given: physician scheduling and single-vehicle
routing. Computational experiments on the latter provided an estimate of
the price of constraint programming in this setting: it showed that such a framework
outperforms the simpler, more passive use of constraint propagation in local search
and that it is competitive with a specialized, non-cp local search algorithm. It also
stressed that a light-weight master model may be preferable and that the standard
branch-and-bound approach comes with a computational cost which may outweigh
its benefit: in our case, the explicit computation of lower bounds proved much more
efficient.
A tabu algorithm which is tailored and optimized for a particular context is expected
to perform better. Our experimentation suggests that, given a large enough
neighborhood (and not inordinately large), an implementation of our framework
may run faster. The initial cost of using constraint propagation can turn up a profit
when combined with a branch-and-bound exploration of the neighborhood search
space. The small percentage of feasible neighbors which we encountered, even when
the proportion of truly constraining time windows was very small, indicates that
it is worth investing in the elimination of infeasible subsets of the neighborhood.
A more ambitious study of different and especially larger neighborhoods as well as
different combinatorial problems could serve to strengthen the previous claim and
also to identify possible settings in which the "full" version or tabu pruning may
be advantageous.

Acknowledgments

Financial support for this research was provided by the Natural Sciences and Engineering
Research Council of Canada (NSERC).
Notes
1. Though incomplete search methods have been successfully introduced in the constraint satisfaction
community.
2. The neighborhood for the "shuffle" moves of [2] is explored through a tree search guided by
constraint propagation. This lies one step closer to our approach.
3. A conditional constraint p ) q enforces the consequent q once the antecedent p is verified. We
use the syntax "Var = value" for an antecedent to mean that it is verified when variable Var is
fixed to some value.
4. Granted, such a tree remains relatively shallow but potentially very bushy.
5. This is for a version of genius-cp equipped with lower-bound pruning ? , an improvement over
what is described in [20]



--R

Local Search in Combinatorial Optimization.
Disjunctive Scheduling with Task Intervals.
A Constraint Logic Programming Approach to the Vehicle-Fleet Scheduling Problem
New Insertion and Postoptimization Procedures for the Traveling Salesman Problem.
A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows.
Heuristic for Integer Programming Using Surrogate Constraints.

' E. Taillard, and D. de Werra. A User's Guide to Tabu Search.
Adaptation in Natural and Artificial Systems.


Computer Solutions of the Traveling Salesman Problem.
An Effective Heuristic Algorithm for the Traveling Salesman Problem.
Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method
Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking
Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.
A View of Local Search in Constraint Programming.

An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows.
GENIUS-CP: a Generic Vehicle Routing Algorithm.
An Exchange Heuristic for Routing Problems with Time Windows.

Modern Heuristic Techniques for Combinatorial Problems.
Local Search in Routing Problems with Time Windows.
A New Method for Solving Hard Satisfiability Problems.
Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints.

Practical Applications of Constraint Programming.
--TR

--CTR
Michel Gendreau, Constraint Programming and Operations Research: Comments from an Operations Researcher, Journal of Heuristics, v.8 n.1, p.19-24, January 2002
Louis-Martin Rousseau , Michel Gendreau , Gilles Pesant, Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows, Journal of Heuristics, v.8 n.1, p.43-58, January 2002
Simon de Givry , Laurent Jeannin, A unified framework for partial and hybrid search methods in constraint programming, Computers and Operations Research, v.33 n.10, p.2805-2833, October 2006
Samir Loudni , Patrice Boizumault , Philippe David, On-line resources allocation for ATM networks with rerouting, Computers and Operations Research, v.33 n.10, p.2891-2917, October 2006
Christian Blum , Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Computing Surveys (CSUR), v.35 n.3, p.268-308, September
Lucas Bordeaux , Youssef Hamadi , Lintao Zhang, Propositional Satisfiability and Constraint Programming: A comparative survey, ACM Computing Surveys (CSUR), v.38 n.4, p.12-es, 2006
personnel scheduling problem;interface constraints;constraint programming;traveling salesman problem with time windows;neighborhood model;local search;tabu search