Localizer.
Local search is a traditional technique to solve combinatorial search problems which has raised much interest in recent years. The design and implementation of local search algorithms is not an easy task in general and may require considerable experimentation and programming effort. However, contrary to global search, little support is available to assist the design and implementation of local search algorithms. This paper describes the design and implementation of Localizer, a modeling language for implementing local search algorithms. Localizer makes it possible to express local search algorithms in a notation close to their informal descriptions in scientific papers. Experimental results on Boolean satisfiability, graph coloring, graph partitioning, and job-shop scheduling show the feasibility of the approach.
Introduction
Most combinatorial search problems are solved through global or local search. In global
search, a problem is divided into subproblems until the subproblems are simple enough to
be solved directly. In local search, an initial configuration is generated and the algorithm
moves from the current configuration to a neighborhood configuration until a solution (deci-
sion problems) or a good solution (optimization problems) has been found or the resources
available are exhausted. The two approaches have complementary strengths, weaknesses,
and application areas. The design of global search algorithms is now supported by a variety
of tools, ranging from modeling languages such as AMPL [2] and Numerica [10] to constraint
programming languages such CHIP, Ilog Solver, CLP(!), Prolog-IV, and Oz
to name only a few. In contrast, little attention has been devoted to the support of local
search, despite the increasing interest in these algorithms in recent years. (Note however
there are various efforts to integrate local search in CLP languages, e.g., [9]). The design
of local search algorithms is not an easy task however. The same problem can be modeled
in many different ways (see for instance [4]), making the design process an inherently
experimental enterprise. In addition, efficient implementations of local search algorithms
often require maintaining complex data structures incrementally, which is a tedious and
error-prone activity.
Localizer [5] is a domain-specific language for the implementation of local search al-
gorithms, combining aspects of declarative and imperative programming, since both are
important in local search algorithms. Localizer makes it possible to write local search
algorithms in a notation close to the informal presentation found in scientific publications,
while inducing a reasonable overhead over special-purpose implementations. Localizer
offers support for defining traditional concepts like neighborhoods, acceptance criteria, and
restarting states. In addition, Localizer also introduces the declarative concept of invariants
in order to automate the most tedious and error-prone aspect of local search procedures:
incremental data structures. Invariants provide a declarative way to specify what needs to
be maintained to define the neighborhood and the objective function.
This paper is a progress report describing the status of Localizer as of February 1998.
Its main focus is on the language and its implementation. 1 It is not intended as a final
word on the language, since new, higher-level, extensions are currently under evaluation.
The paper however describes the core of Localizer which will probably not evolve in
significant ways. The paper is organized in four main parts. Section 2 gives readers a quick
tour of Localizer. Section 3 describes the language in more detail. Section 4 describes the
implementation of invariants which are the cornerstone of Localizer. Section 5 summarizes
some experimental results from several applications. Finally, Section 6 concludes the paper.
A Tour of Localizer
This section gives an overview of the main features of Localizer. It starts by reviewing
the computational model of Localizer and the general form of Localizer statements. It
then considers the two main contributions of Localizer: invariants and neighborhoods.
2.1 The Computation Model
To understand statements in Localizer, it is best to consider the underlying computational
model first. Figure 1 depicts the computational model of Localizer for decision problems.
The model captures the essence of most local search algorithms. The algorithm performs
a number of local searches (up to MaxSearches and while a global condition is satisfied).
Each local search consists of a number of iterations (up to MaxTrials and while a local
condition is satisfied). For each iteration, the algorithm first tests if the state is satisfiable,
in which case a solution has been found. Otherwise, it selects a candidate move in the
neighborhood and moves to this new state if this is acceptable. If no solution is found after
MaxTrials or when the local condition is false, the algorithm restarts a new local iteration
in the state restartState(s). The computation model for optimization problems is similar,
except that line 5 needs to update the best solution so far if necessary, e.g. in the case of a
minimization,
5.1 bestBound := value(s);
5.2 best := s;
companion paper for the Operations Research community is oriented around applications and modeling aspects.
The optimization algorithm of course should initialize f   properly and return the best
solution found at the end of the computation.
procedure Localizer
begin
2 for search := 1 to MaxSearches while Global Condition do
3 for trial := 1 to MaxTrials while Local Condition do
5 return s;
6 select n in neighborhood(s);
7 if acceptable(n) then
9 s := restartState(s);

Figure

1: The Computation Model of Localizer
2.2 The Structure of Localizer Statements
The purpose of a Localizer statement is to specify, for the problem at hand, the instance
data, the state, and the generic parts of the computation model (e.g., the neighborhood
and the acceptance criterion). A Localizer statement consists of a number of sections
as depicted in Figure 2. The instance data is defined by the Type, Constant, and Init
sections, using traditional data structures from programming languages. The state is defined
as the values of the variables. The neighborhood is defined in the Neighborhood section,
using objects from previous sections. The acceptance criterion is part of the definition of
the neighborhood. The initial state is defined in section Start. The restarting states are
defined in section Restart, the parameters (e.g. MaxTrials) are given in the Parameter
section, and the global and local conditions are given in sections Global Condition and
Local Condition. Note that all the identifiers in boldface in the description of computation
model (e.g., search and trial), are in fact keywords of Localizer.
As mentioned previously, the most original aspects of Localizer are in the specifications
of the neighborhood and the acceptance criterion. Of course, some of the notations are
reminiscent of languages such as AMPL and Claire at the syntactical level but the underlying
concepts are fundamentally different. In the rest of this section, we describe the most
original aspects of Localizer without trying to be comprehensive.
2.3 The Running Example
This overview mostly uses Boolean satisfiability to illustrate the concepts of Localizer.
A Boolean satisfiability problem amounts to finding a truth assignment for a first-order
boolean formula expressed in disjunctive normal form. The input is given as a set of clauses,
Model i ::= [solve j optimize]
hObjective Functioni]

Figure

2: The Structure of Localizer Statements
each clause consisting of a number of positive and negative literals. As is traditional, a literal
is simply an atom (positive atom) or the negation of an atom (negative atom). A clause is
satisfied as soon as at least one of its positive atoms is true or at least one of its negative
atoms is false. The local search model considered for Boolean satisfiability is based on the
GSAT algorithm by Selman et al. in [8], where the local search moves consist of flipping
the truth value of an atom.
A local improvement model for Boolean satisfiability is described in Figure 3. In the
model, atoms are represented by integers 1 to n and a clause is represented by two sets:
the set of its positive atoms p and the set of its negative atoms n. This data representation
is specified in the Type section. A problem instance is specified by an array of m clauses
over n variables. The instance data is declared in the Constant section and initialized in
the Init section which is not shown. The state is specified by the truth values of the atoms
and is captured in the array a of variables in the Variable section. Variable a[i] represents
the truth value of atom i. The Invariant section is the key component of all Localizer
statements: it describes, in a declarative way, the data structures which must be maintained
incrementally. Invariants are reviewed in detail in Section 2.4. In the model depicted in

Figure

3, they maintain the number of true literals nbtl[c] in each clause c and the number
of satisfied clauses nbClauseSat. The Satisfiable section describes when the state is a
solution (all clauses are satisfied), while the Objective Function section describes the
objective function (maximize the number of satisfied clauses) used to drive the search. The
Neighborhood section describes the actual neighborhood and the acceptance criterion.
The neighborhood consists of all the states which can be obtained by flipping the truth
value of an atom and a move is accepted if it improves the value of the objective function.
The Neighborhood section is another important part of Localizer and is reviewed in
Solve
Type:
Constant:
cl: array[1.m] of clause = .;
Variable:
a: array[1.n] of boolean;
Invariant:
in 1.m] of int = sum(i in cl[i].p) a[j] + sum(j in cl[i]:n) !a[j];
Satisfiable:
Objective Function:
maximize nbClauseSat;
Neighborhood:
move a[i] := !a[i]
where i from f1.ng
accept when improvement;
Start:
forall(i in 1.n) a[i] := random(ftrue,falseg);
Restart:
forall(i in 1.n) a[i] := random(ftrue,falseg);

Figure

3: A Local Improvement Model for Boolean Satisfiability
more detail in Section 2.5. The Start and Restart sections describe how to generate an
initial state and a new state when restarting a search. They both use a simple random
generation in the model.
It is interesting at this point to stress the simplicity of the model, since it is difficult to
imagine a more concise formal statement of the algorithm.
2.4 Invariants
Invariants are probably the most important tool offered by Localizer to support the design
of local search algorithms. They make it possible to specify what needs to be maintained
incrementally without considering how to do so. Informally speaking, an invariant is an
expression of the guarantees that, at any time during the
computation, the value of variable v of type t is the value of the expression exp (also of type
t of course). For instance, the invariant
in 1.m] of int = sum(i in cl[i].p) a[j] + sum(j in cl[i]:n) !a[j];
in the Boolean satisfiablity model specifies that nbtl[c] is equal to the sum of all true
positive atoms and all false negative atoms in clause c, for all clauses in 1::n. Localizer
uses efficient incremental algorithms to maintain these invariants during the computation,
automating one of the tedious and time-consuming tasks of local search algorithms. For
instance, whenever a value a[k] is changed, nbtl[c] is updated in constant time.
Localizer allows a wide variety of invariants over complex data structures. The invariant
(also from the Boolean satisfiability model)
illustrates the use of relations inside an invariant. A relation, when used inside an expression,
is considered a 0-1 integer, i.e., the relation evaluated to 1 when true and 0 otherwise. The
excerpt
C: array[1.n] of int = distribute(x,1::n,1.n);
select i from 1.n where
select i from 1.n where size(C[i]) ? 0g;
unused
Candidates
B: array[k in 1.n] of
select i from C[k] & select j from C[k] where A[i; j]
is taken from a graph-coloring model implementing an algorithm in [4]. The graph-coloring
problem amounts to finding the smallest number of colors to label a graph such that that
adjacent vertices have different colors. For a graph with n vertices, the algorithm considers
n colors which are the integers between 1 and n. Color class C i is the set of all vertices
colored with i and the bad edges of C i , denoted by B i , are the edges whose vertices are
both colored with i. The main idea of the algorithm is to minimize the objective function
whose local minima are valid colorings. To minimize the function,
the algorithm chooses a vertex and chooses a color whose color class is non-empty or one of
the unused colors. It is important to consider only one of the unused colors to avoid a bias
towards unused colors. The invariant
B: array[k in 1.n] of
select i from C[k] & select j from C[k] where Adj[i; j]
that B[k] is the set of edges obtained by selecting two adjacent vertices in color
class k. It illustrates that Localizer can maintain queries over sets varying in time (since
evolves during the local search). The invariant
C: array[1.n] of int = distribute(x,1::n,1.n);
is equivalent to, but more efficient than,
C: array[i in 1.n] of int select i from 1.n where
This primitive function is provided, since it is useful in a large variety of applications. The
invariant
select i from 1.n where size(C[i]) ? 0g;
defines the non-empty classes. Note that here the set 1.n does not vary but the condition
Once again, it is important to emphasize the significant support provided by Localizer
with invariants. These invariants maintain complex data structures incrementally, but users
only have to specify them in a declarative way.
2.5 The Neighborhood
Many strategies such as local improvement, simulated annealing, and tabu search have been
proposed in the last decades for local search algorithms. This section reviews how they are
modeled in the neighborhood section, which is the other fundamental tool provided by
Localizer.
2.5.1 Local Improvement and Local Nondegradation
The model depicted in Figure 3 uses a stochastic local improvement approach. The neighborhood
section
Neighborhood:
move a[i] := !a[i]
where i from f1.ng
accept when improvement;
specifies the following strategy: select a value i in 1::n (i.e., select an atom), flip a[i], and, if
the resulting state improves the value of the objective function, take the move. If the state
does not improve the value of the objective function, the move is not taken and Localizer
proceeds to the next iteration of the innermost loop in the computational model. This
strategy illustrates the structure of the neighborhood definition in Localizer. The move
part specifies a state transformation: it uses traditional imperative constructs to show how
to transform a state into another state. The where part specifies the set of objects used to
specify the state transformation. The accept part describes when to accept the move.
The local improvement strategy can be made greedy by adding the keyword best in
front of the move instruction, as in
Neighborhood:
best move a[i] := !a[i]
where i from f1.ng
accept when improvement;
Solve
Type:
Constant:
cl: array[1.m] of clause = .;
Variable:
a: array[1.n] of boolean;
Invariant:
in 1.m] of int = sum(i in cl[i].p) a[j] + sum(j in cl[i]:n) !a[j];
Satisfiable:
Objective Function:
maximize nbClauseSat;
Neighborhood:
best move a[i] := !a[i]
where i from f1.ng
accept when noDecrease;
Start:
forall(i in 1.n) a[i] := random(ftrue,falseg);
Restart:
forall(i in 1.n) a[i] := random(ftrue,falseg);

Figure

4: A GSAT-based Model for Boolean Satisfiability
This excerpt specifies the following strategy: consider each value i in 1::n which, when
flipped, produces an improvement and select the one with the best improvement. Note that
this strategy explores the neighborhood in a systematic way, while the previous strategy
was selecting a random move and testing it for improvement. The neighborhood section
Neighborhood:
first move a[i] := !a[i]
where i from f1.ng
accept when improvement;
is another approach that explores the neighborhood systematically until a move improving
the value of the objective function is found. It should be contrasted with the random walk
strategy presented previously.
Sometimes it is important to allow more flexibility in the local search and to allow moves
which may not improve the objective function. The neighborhood
Neighborhood:
best move a[i] := !a[i]
where i from f1.ng
accept when noDecrease;
accepts the best move which does not decrease the value of the objective function. The
resulting model, depicted in Figure 4, captures the essence of the GSAT algorithm.
2.5.2 Simulated Annealing
Simulated annealing is a well-known stochastic strategy to enhance a local improvement
search. It is easily expressed by the Localizer neighborhood
Neighborhood:
move a[i] := !a[i]
where i from f1.ng
accept
when improvement ! ch++;
cor noDecrease;
The key novelty here is that the accept statement may have a number of acceptance conditions
which are tried in sequence until one succeeds or all fail. In addition, each acceptance
condition can be associated with an action. The simulated annealing neighborhood specifies
that a move is accepted when it improves the objective function, when it does not decrease
the objective function, or with the standard probability of simulated annealing, which depends
on a temperature parameter and the variation delta of the objective function. Note
that the variable ch is incremented when there is an improvement or a decrease in the
objective function. The complete model is given in Figure 5.
The model illustrates also several new features of Localizer. The Operator section
describes two procedures which are used subsequently in the Start and Restart sections.
Operators in Localizer uses traditional constructs from imperative programming languages
(e.g., loops and conditions) as well as some new primitives for randomization. These
features are once again described in more detail in Section 3. Note also the variables t (the
temperature) and ch (the change counter) which are used in various places in the model.
2.5.3 Tabu Search
Tabu search is another strategy to escape local optima which, in contrast to simulated
annealing, does not resort to stochastic moves. The neighborhood
Neighborhood:
best move a[i] := !a[i]
where i from f1.ng such that !tabu(i)
accept when always ! t[v] := trial;
Solve
Type:
Constant:
cl: array[1.m] of clause = .;
Variable:
a: array[1.n] of boolean;
t: real;
Invariant:
in 1.m] of int = sum(i in cl[i].p) a[j] + sum(j in cl[i]:n) !a[j];
Operator:
void
forall(i in 1.n) x[i] := random(ftrue,falseg);
ch := 0;
void lowTemp() f
ch := 0;
Satisfiable:
Objective Function:
maximize nbClauseSat;
Neighborhood:
move a[i] := !a[i]
where i from f1.ng
accept
when improvement ! ch++;
cor noDecrease
Start:
Restart:
lowTemp();

Figure

5: A Simulated Annealing Model for SAT
indicates how a simple tabu search can be expressed in Localizer. The key idea here is to
select an atom which is not tabu. The where clause is generalized to include this condition.
All the moves so-defined are accepted and the model also keeps track of when an atom was
last flipped by using the keyword trial. An atom is then tabu if it has been flipped recently,
which can be expressed as
f
return
where tl is a parameter specifying the time an atom stays on the tabu list. The complete
model is described in Figure 6. Of course, more complicated tabu search algorithms (e.g.,
using aspiration criteria to overwrite the tabu status or a tabu list whose size varies over
time) can be implemented easily.
2.5.4 Composing Neighborhoods
Localizer makes it also possible to compose neighborhoods. For instance, the following
neighborhood
try
move
where
i from OccurInUnsatClause
accept when
default:
best move
where
i from f1.ng
accept when noDecrease;
implements the random walk/noise strategy of GSAT. Here, Localizer flips an arbitrary
variable in an unsatisfied clause with a probability of 0.1 and applies the standard strategy
with a probability of 0.9. Note that Localizer simply goes to the next iteration if the
selected neighborhood is empty, since other neighborhoods may be non-empty.
2.5.5 Incrementality Issues
In the models presented so far, Localizer needs to simulate the move to find out how
the objective function evolves. This simulation can become very expensive when few moves
are accepted. In practice, local search implementations often try to evaluate the impact
Solve
Type:
Constant:
cl: array[1.m] of clause = .;
Variable:
a: array[1.n] of boolean;
t: array[1.n] of int;
tl: int;
Invariant:
in 1.m] of int = sum(i in cl[i].p) a[j] + sum(j in cl[i]:n) !a[j];
Operator:
void
tl := 10;
forall(i in 1.n) x[i] := random(ftrue,falseg);
forall(i in 1.n) t[i] := -tl;
return
Satisfiable:
Objective Function:
maximize nbClauseSat;
Neighborhood:
best move a[i] := !a[i]
where i from f1.ng such that !tabu(i)
accept when always ! t[v] := trial;
Start:
Restart:

Figure

Model for Boolean Satisfiability
of the move in the current state. Localizer supports this practice by allowing to specify
acceptance criteria which are evaluated in the current state. For instance, the neighborhood
definition
Neighborhood:
first move a[i] := !a[i]
where i from f1.ng
accept when in current state
evaluates the condition gain[i] ?= 0 in the current state to determine whether to take the
move. Of course, this requires to generalize the invariants to maintain gain[i] incrementally.
The invariants now become
Invariant:
nbtl: array[ i in 1.m ] of int = sum(i in cl[i]:p) a[j] + sum(j in cl[i]:n) !a[j];
The informal meaning of the new invariants are the following. g01[i] represents the change
in the number of satisfied clauses when changing the value of atom i from false to true,
assuming that atom i is currently false. Obviously, the flip produces a gain for all unsatisfied
clauses where atom i appears positively. It also produces a loss for all clauses where i
appears negatively and is the only atom responsible for the satisfaction of the clause. g10[i]
represents the change in satisfied clauses when changing the value of atom i from true
to false, assuming that atom i is currently true. It is computed in a way similar to g01.
gain[i] represents the change in satisfied clauses when changing the value of atom i. It is
implemented using a conditional expression in terms of g01[i], g10[i], and the current value
of atom i. No simulation is necessary in the resulting model.
The GSAT model can be made even more incremental. Since GSAT only selects the move
with the best objective value, it is possible to maintain these candidate moves incrementally.
The only change is to add the two invariants
Candidates
select i from 1.n where
Here maxGain is simply the maximum of all gains and Candidates describes the set of
candidates for flipping as the set of atoms whose gain is positive and maximal. Once the
invariants have been described, the neighborhood is defined by flipping one of the candidates.
There is no need to use the keyword best or a noDecrease acceptance criteria, since they
are already enforced by the invariants. The complete model is depicted in Figure 7. Of
course, the same transformation can be performed for the tabu search model.
Solve
Data Type:
Constant:
cl: array[1.m] of clause = .;
po: array[ i in 1.n] of fintg :=
select c from 1.m where i in cl[c]:p
no: array[ i in 1.n] of fintg :=
select c from 1.m where i in cl[c]:n
Variable:
a: array[1.n] of boolean;
Invariant:
nbtl: array[ i in 1.m ] of int = sum(i in cl[i]:p) a[j] + sum(j in cl[i]:n) !a[j];
gain: array[ i in 1.n ] of int = if a[i] then g10[i] else g01[i];
Candidates
select i from 1.n where
Satisfiable:
Neighborhood:
move a[i] := !a[i]
where i from Candidates;
Start:
forall(i in 1.n)
Restart:
forall(i in 1.n)

Figure

7: A More Incremental Model of GSAT
3 The Language
As mentioned previously, Localizer is an hybrid language embedding aspects of declarative
programming within an imperative language. The main declarative tool is, of course,
the concept of invariants which specify expressions whose values must be maintained in-
crementally. Imperative constructs are mostly used to specify state transformations and
the starting and restarting states. This section reviews Localizer in more detail and is
essentially organized along the textual ordering of Localizer statements.
3.1 The Type Section
The Type section of Localizer is used to define record types. Records within Localizer
are identical to records found in conventional imperative languages like Pascal or C. They
aggregate a number of named fields, possibly of different types. For instance, the excerpt
declares a record type Edge consisting of two integers (the origin and destination nodes),
while the excerpt
declares a record type clause with the two fields pl and nl of type "sets of integers".
3.2 Constants
The Constant section declares the input data and, possibly, some derived data which are
useful in stating the model. All constants are typed, read only (i.e., they cannot be modified
by assignments), and are initialized. As shown later on, there are various ways to initialize
data in Localizer.
3.2.1 Data Types
Basic Data Types The basic data types supported by Localizer are integers, booleans
and floats. The excerpt
declares an integer n whose value is 10, a float whose value is 3:14, and a Boolean. Integers
can range from \Gamma2 floats are double-precision floating-point numbers.
Arrays Localizer supports multi-dimensional arrays of arbitrary types. The declara-
tion
defines a one-dimensional array a of integers which is initialized by the vector [6,1,4,5,7].
The declaration
declares a matrix of integers.
Records As mentioned previously, records can be used in Localizer to cluster together
related data. For instance, the declaration
of Edge := [!
defines p as an array of 3 edges. Each edge is initialized with a tuple. A tuple is compatible
with a record type if it has the same number of fields and the type of each field is compatible
with the type of the corresponding field.
Sets Finally, Localizer supports sets of arbitrary types. For instance, the declaration
declares and initializes a set of edges.
3.2.2 Inline and Offline Initializations
Constants can be initialized inline as in all previous examples. They can also be initialized
offline in the Init section to separate the model from the instance data, which is usually a
good practice. The excerpt
declares a float f whose initialization is given in the Init section. The Init section consists
of a set of pairs (identifier,value) and, of course, the type of the initializationmust match the
type of the declaration. Offline initializations can be used for arbitrary types. For instance,
the Boolean satisfiability models may contain an initialization section of the form
Init:
cl
Here, cl is initialized with a vector of 11 tuples. Each tuple is a pair of sets. The first set
of each pair is associated with the first field of the record of type clause and denotes the
set of positive literals in that clause. The second set is matched with the second field of the
record and denotes the negative atoms of the clause.
3.2.3 Generic Data
Localizer also supports the concepts of generic data which was introduced in Numerica
[10]. The basic idea here is to initialize the data using an expression which may depend
on parameters of the declaration. Genericity is especially attractive to define derived data
which are then used to simplify the model. In the case of the fully incremental version of
GSAT (see Figure 7, it is important to know the clauses where an atom i appears positively
(and negatively). This information is derived from the data cl using the generic declarations
Constant:
po: array[i in 1.n] of fintg select c from 1.m where i in cl[c]:pg;
no: array[i in 1.n] of fintg select c from 1.m where i in cl[c]:ng;
There are a couple of important points to stress here. First, the declarations use parameters
which range over the index sets of the array. For instance, parameter i ranges over 1::n, the
set of atoms. Second, these parameters are used in the expression defined on the right-hand
side of := to specify the value of the array at the given position. In the GSAT example, po[i]
is defined as the set of clauses where atom i appears positively. The expressions allowed for
the right-hand side are very general and their syntax is given in Figure 8. Figure 9 describes
the signature of the primitive functions which have the obvious meanings.
3.3 Variables
Variables are of course fundamental in Localizer, since they define the state of the com-
putation. Variables are declared in the same ways as constants, except that they are not
initialized. They are generally given an initial value in the Start section and modified in the
Neighborhood and Restart sections. As should be clear from the examples, Localizer
has an assignment operator, whose right-hand side is an expression.
3.4 Invariants
Invariants are the key concept provided by Localizer to support the design of local search
algorithms. Syntactically, invariants are simply generic data. However, invariants are not
static since they may contain variables and/or other invariants. As a consequence, the
values of invariants are state-dependent and Localizer is responsible to update them after
each state transition. The following excerpt illustrates invariants from a graph-coloring
model where C[i] refers to another invariant whose type is fintg (set of integers).
constant literal
::= hexpri . hidentifieri
hSet Bodyi ::= hexpri . hexpri j hexpri
::= hexpri . hexpri
select hidentifieri from hrangei [ where hexpri
select hidentifieri from hexpri [ where hexpri
hrangei ::= hexpri . hexpri

Figure

8: Expression syntax
Arithmetic Set related Output
min2(int,int)!int size(fTg)!int print(.)!void
max2(int,int)!int random(fTg)!T println(.)!void
floor(float)!int minof(fTg)!T
ceil(float)!int insert(fTg,T)!void
round(float)!int remove(fTg,T)!void
exp(float)!float
time()!int

Figure

9: Primitive Functions
select i from 1.n where size(C[i])=0g;
in 1.n] of fEdgeg select i from C[k]
select j from C[k]
In addition to the standard expressions, invariants can also be defined in terms of distribute
and dcount. They take as input a one-dimensional array of integers A and two sets I and
O. I must be a subset of the index set of A. The result type of a distribute expression is
one-dimensional array of set of integers B whose index set is O. fintg.
The result type of a dcount expression is one-dimensional array of integers whose index
set is O. Their meanings are given by the following equivalences:
These expressions were introduced because of their ubiquity in practical applications. It is
important to stress that the data declared by invariants cannot appear in left-hand sides of
assignment statements.
Operators
The Operator section contains function definitions. Functions in Localizer are essentially
similar to functions in C and use traditional assignment, conditional, and iterative
statements, as well as recursion. In addition, Localizer provides some constructs which
are useful for local search algorithms. The syntax of statements in Localizer is sketched in

Figure

10. The forall instruction provides a convenient way of iterating over the elements
of a set. The choose instruction can be used to select an element from a set, in a (don't
care) nondeterministic way. It is possible to filter elements of the given set or to select
an element optimizing a function. The following examples illustrate the various forms of
choose statements:
choose i from A;
choose i from A minimizing D[i];
choose i from A such that gain[i] ? 0;
choose i from A such that gain[i] ? 0 maximizing D[i];
The entire state, including constants, variables, and invariants, are accessible to functions.
However, only variables and locals can be modified by assignments. Note that functions and
imperative constructs can be used in the Start and restart sections, in the specification
of the state transformation of the neighborhood, in the actions associated with specific
acceptance criteria, and in the from instructions that appear in the where clause of the
move instruction. Typical examples of functions were introduced in the models of Figures
5 and 6.
while hexpri do hstatementi
return hexpri
choose hidentifieri from hexpri [ hoptClausei
hoptClausei ::= minimizing hexpri
maximizing hexpri
::= such that hexpri [minimizing hexpri [with hletBlocki
::= such that hexpri [maximizing hexpri [with hletBlocki

Figure

10: The Syntax of Statements
3.6 Neighborhood
The neighborhood is specified in Localizer with a move instruction of the form:
move
where
from
xn from Sn
This instruction uses both declarative and procedural components. The first part of the
statement specifies, with the imperative code the transformation of the current
state into one of its neighbors. The second part starting with the where keyword
specifies the objects used in the imperative code. The modeling effort is primarily devoted
to the definition of the sets S i
and the invariants they are based on. The syntax of move
instructions is depicted in Figure 11.
Once an element of the neighborhood has been selected, Localizer determines if it is
an appropriate move. The acceptance criterion lists boolean conditions that are to be tried
in sequence. As soon as the state satisfies one of the conditions, it is accepted and the state
transformation is performed. The criterion is build according to the syntax
where
::= hidentifieri from f hexpr 1
::= hidentifieri from f hidentifieri : htypei j hselect 1
::= hidentifieri from hlvaluei [ hoptClausei

Figure

11: The Syntax of move Instructions
::= in resulting state hAcceptanceStatementi
::= in current state hAcceptanceStatementi
improvement
noDecrease
::= hAcceptanceConditioni and hAcceptanceConditioni
::= hAcceptanceConditioni or hAcceptanceConditioni
::= not hAcceptanceConditioni
Acceptance criteria are, by default, evaluated in the new state. This new state must be
constructed, which induces the update of all invariants. It is also possible to specify that
the acceptance criterion should be evaluated in the current state by using the keywords
in current state. Using the current state to evaluate moves may produce significant
improvements in efficiency.
3.7 The Objective Function
The objective function is stated in a separate section and is used to assess the "quality"
of a given state. The objective function can in fact be viewed as an invariant which is
maintained by Localizer and used to evaluate moves. Note that the objective function is
optional and is only used when the acceptance criteria are evaluated in the resulting state.
3.8 Termination Criteria
Termination is handled via several sections and depends on the nature of the problem. Each
model starts with a keyword that is either solve or optimize to specify either a decision
or an optimization problem.
The Satisfiable Section The (optional) satisfiable section is used to specify whether
a state is a solution. In decision problems, Localizer terminates whenever this is the
case. In optimization problems, Localizer updates the best solution whenever the state
is a solution which improves the best bound found so far. When the section is omitted,
Localizer assumes that every state is a solution.
The Local and Global Conditions These sections, which are optional, specify Boolean
predicates which are used to control the innermost and outermost loops of the computation
model. For instance, a simulated annealing model can use the local condition to implement
a cutOff strategy that terminates the innermost loop and drops the temperature whenever
the evaluation function has been updated sufficiently many times.
The Parameter Section This section, also optional, is used to override the default values
of some parameters of the system. Typical uses redefine the maxSearches and maxTrials
parameters of the computation model.
Implementation
This section reviews the implementation of invariants which are the cornerstone of Local-
izer. Informally speaking, invariants are implemented using a planning/execution model.
The planning phase generates a specific order for propagating the invariants, while the execution
phase actually performs the propagation. This model makes it possible to propagate
only differences between two states and mimics, to a certain extent, the way specific local
search algorithms are implemented.
The planning/execution model imposes some restrictions on the invariants. These restrictions
intuitively, makes sure that there is an order in which the invariants can be
propagated so that a pair (variable,invariant) is considered at most once. Various such
restrictions can be imposed. Static invariants can be ordered at compile time and are thus
especially efficient. However, static invariants rule out some interesting models for scheduling
and resource allocation problems. Dynamic invariants still make it possible to produce
an ordering so that a pair (variable,invariant) is considered at most once. However, dynamic
invariants require to interleave the planning and execution phases. Dynamic invariants seem
to be a good compromise between efficiency and expressiveness.
The rest of this section is organized as follows. The algorithms use normalized invariants
and Section 4.1 reviews the normalization process. Section 4.2 describes static invariants
and their implementation. This should give readers a preliminary understanding of the
implementation. Section 4.3 describes dynamic invariants and their implementation. This
section only considers arithmetic invariants but it is not difficult to generalize these results
to invariants over sets.
4.1 Normalization
The invariants of Localizer are rewritten into primitive invariants by flattening expressions
and arrays. The primitive invariants are of the form:
x := y \Phi z
where c is a constant, x; are variables, \Phi is an arithmetic operator such as
and   or an arithmetic relation such as -; ? and =, and Q is an aggregate operator such as
sum, prod, max, and min. Relations return 1 when true and 0 otherwise. An invariant
assigns to x the element in position e in the list [x last invariant is useful
for arrays which are indexed by expressions containing variables.
At any given time, Localizer maintains a set of invariants I over variables V . Given an
invariant I 2 I of the form x := e (where e is an expression), def(I) denotes x while exp(I)
denotes e. Given a set of invariants I over V and x 2 V , invariants(x; I) returns the subset
of invariants fI i
' I such that x occurs in exp(I i ). The set of variables V nfdef(I)jI ' Ig
are the variables which are the parameters of the system of invariants. These variables only
can be modified in the neighborhood definitions. Note also that a variable x can be defined
by at most one invariant. i.e. there exist at most one I ' I such that
4.2 Static Invariants
The basic assumption behind Localizer implementation is that invariants only change
marginally when moving from one state to one of its neighbors. Consequently, the goal of
the implementation is to run in time proportional to the amount of changes. More precisely,
the implementation makes sure that a pair (variable; invariant) is considered at most once,
i.e., when the variable is updated, the invariant is updated but it will never be reconsidered
because of that variable.
To achieve this goal, the implementation uses a planning/execution model where the
planning phase determines an ordering for the updates and the execution phase actually
performs them. The existence of a suitable ordering is guaranteed by the restrictions imposed
on the invariants by the system. Note also that planning/execution models are often
in graphical constraint systems (e.g., [1]).
This section describes static invariants which impose a static restriction. Although
this restriction may seem strong, it accommodates many models for applications such as
satisfiability and graph coloring to name a few. The main practical limitation is that
elements of arrays cannot depend on other elements in the same array. This restriction is
lifted by dynamic invariants. Note, however, that static invariants have the nice property
that the planning phase can be entirely performed at compile time.
4.2.1 The Planning Phase
The basic idea behind static invariants is to require the existence of a topological ordering
on the variables. This topological ordering is obtained by associating a topological number
t(x) with each variable x. The topological number of an invariant I is simply t(def(I)).
The topological numbers are obtained from constraints derived from the invariants.
1 The topological constraints of invariant I are defined as follows:
Definition 2 The topological constraints of a set of invariants I denoted by tc(I) is
I2I
tc(I).
Definition 3 A set of invariants I over t is static if there exists an assignment
such that t satisfies tc(I).
The planning phase for static invariants consists of finding the topological assignment. The
planning phase can be performed at compile time since the topological constraints do not
depend on the values of the variables in a given state.
4.2.2 The Execution Phase
The execution phase is given a set of variables M which have been updated and a topological
assignment t. It then propagates the changes according to the topological ordering. The
algorithm uses a queue which contains pairs of the form hx; Ii. Intuitively, such a pair
means that invariant I must be reconsidered because variable x has been updated. The
main step of the algorithm consists of popping the pair hx; Ii with the smallest t(I) and to
propagate the change, possibly adding new elements to the queue. The algorithm is shown
in

Figure

12.
procedure execute(I,M,t)
begin
while do
endwhile
function POP(Q,t)
pre: Q is not empty
post:

Figure

12: The Execution Phase for Static Invariants
4.2.3 Propagating the Invariants
To complete the description of the implementation of static invariants, it remains to describe
how to propagate the invariants themselves. The basic idea here is to associate two values
x with each variable x. The value x represents the value of variable x at the
beginning of the execution phase, while the value x c represents the current value of x. At
the beginning of the execution phase, x of course. By keeping these two values,
it is possible to compute how much a variable has changed and to update the invariants
accordingly. For instance, the propagation of the invariant
is performed by a procedure
procedure propagate(x i ,x := sum(x 1
begin
The procedure updates x c according to the change of x i . Note that, because of the topological
has reached its final value. Note also that x c is not necessarily final after
this update, because other pairs hx may need to be propagated.
4.3 Dynamic Invariants
Static invariants are attractive since the planning phase can be performed entirely at compile
time. However, there are interesting applications in the areas of scheduling and resource
allocation where sets of invariants are not static. This section introduces dynamic invariants
to broaden the class of invariants accepted by Localizer. Dynamic invariants are updated
by a series of planning/execution phases where the planning phase takes place at execution
time.
4.3.1 Motivation
The main restriction of static invariants comes from the invariant
The static topological constraint for this invariant is
and it prevents Localizer from accepting expressions where some elements of an array
may depend on some other elements of the same array. This constraint is strong, because
the value of e is not known at compile time. In fact, it may not even be known before the
start of the execution phase since some invariants may update it.
However, there are many applications in scheduling or resource allocation where such
invariants occur naturally. For instance, a scheduling application may be modeled in terms
of an invariant
start[3] := max(end[prec[3]]; end[disj[3]]);
where start[i] represents the starting date of task i, prec[i] the predecessor of the task in
the job and disj[i], the predecessor of task i in the disjunction. Variable disj[i] is typically
updated during the local search and the above invariant is normalized into a set of the form:
start 3 := max(p; d)
Of course, such an application has also invariants of the form
implying that the resulting set of invariants is not static.
4.3.2 Overview of the Approach
The basic idea behind dynamic invariants is to evaluate the invariants by levels. Each
invariant is associated with one level and, inside one level, the invariants are static. Once a
level is completed, planning of the next level can take place using the values of the previous
levels since lower levels are never reconsidered. With this computation model in mind, the
topological constraint associated with an invariant
can be reconsidered. The basic idea is to require that e be evaluated before x (i.e. the level
of x is the level of e Once e is updated, then it is easy to find a weaker topological
constraint since the value of e is known. The invariant can be simplified to
The planning phase is thus divided in two steps. A first step, which can be carried out
at compile time, partitions the invariants in levels. The second step, which is executed at
runtime, topologically sorts the invariants within each level whenever the invariants at the
lower level have been propagated.
4.3.3 Formalization
The basic intuition is formalized in terms of two assignments l
of two sets of constraints.
Definition 4 The level constraints associated with an invariant I and denoted by lc(I) are
defined as follows:
))g
The level constraints are not strong except for the invariant element where the level of x
is strictly greater than the level of e. Informally, it means that e must be evaluated in an
earlier phase than x.
Definition 5 The level constraints associated with a set of invariants I and denoted by
l(I) is simply S
I2I
Definition 6 A set of invariants I is serializable if there exists an assignment l
satisfying lc(I).
A serializable set of invariants can be partitioned into a sequence ! I
the invariants in I i have level i. This serialization can be performed at compile-time. The
second step consists of ordering the invariants inside each partition. This ordering can only
take place at runtime, since it is necessary to know the values of some invariants to simplify
the element invariants.
Definition 7 Let S be a computation state and let S(x) denote the value of x in S. The
static constraints associated with an invariant I wrt to S, denoted sd(I ; S) is defined as
follows:
Definition 8 The static constraints associated with a set of invariants I wrt to a state S,
denoted by sd(I; S) is simply S
I2I
Definition 9 A set of invariants I is static wrt to a state S if there exists an assignment
The main novelty of course is in the invariant element where the topological constraint
can ignore e since its value is known. In addition, since the final value of e is known, the
topological constraints can be made precise since the element y e c that x depends upon is
known.
be a computation state. A set of invariants I is dynamic wrt S 0 if
1. I is serializable and can be partitioned into a sequence ! I
2. I i is static wrt S i where S i (i ? 0) is the state obtained by propagating the invariants
I i\Gamma1 in S i\Gamma1 .
Of course, dynamic invariants cannot be recognized at compile-time and may produce an
execution error at runtime when Localizer is planning a level.
4.3.4 The Execution Algorithm
The new execution algorithm is a simple generalization of the static algorithm and is shown
in

Figure

13. Note the planning step which is called for each level.
procedure execute(I,M)
begin
do
endfor

Figure

13: The Execution Algorithm for Dynamic Invariants
5 Experimental results
This section summarizes some preliminary results on the implementation of Localizer
(about 35,000 lines of C++). The goal is not to report the final word on the implementation
but rather to suggest that Localizer can be implemented with an efficiency comparable
to specific local search algorithms. To demonstrate practicability, we experimented with
Localizer on several problems: GSAT, graph coloring, graph partitioning, and job-shop
scheduling.
5.1 GSAT
GSAT is generally recognized as a fast and very well implemented system. The experimental
results were carried out as specified in [8]. Table 1 gives the number of variables (V ), the
number of clauses (C), and MaxTrials (I) for each size of benchmarks as well as the CPU
times in seconds of Localizer (L), the CPU times in seconds of GSAT (G) as reported
in [8], and the ratio L=G. The times of GSAT are given on a SGI Challenge with a 70
MHz MIPS R4400 processor. The times of Localizer were obtained on a SUN SPARC-
scaled by a factor 1.5 to account for the speed difference between the two
machines. Localizer times are for the incremental model presented in Section 2. Note
that this comparison is not perfect (e.g., the randomization may be different) but it is
sufficient for showing that Localizer can be implemented efficiently.
5.2 Graph Coloring
Graph coloring was the object of an extensive experimental evaluation in [4] and this section
reports on experimental results along the same lines. The experiments were conducted on
graphs of densities 10, 50, and 90 and of sizes 125, 250, and 500. They were also conducted on
so-called "cooked" graphs. Because of the nature of the experimental results reported in [4],
it is not easy to compare the efficiency of Localizer to the efficiency of their algorithm. As
a consequence, a very efficient C implementation of their algorithm was built from scratch
by a graduate student who was closely supervised to obtain a very efficient incremental
algorithm. As far as we can judge, the timings and the quality of this algorithm seem
5 200 860 2000 873.11 168.00 5.20
Av. 3.38

Table

1: GSAT: Experimental Results
consistent with those in [4]. In addition, this algorithm is the most efficient implementation
built by a graduate student in the combinatorial optimization class at Brown (CS-258)
in the last three years (for the given model of course). In the following, we discuss the
development time of the two implementations, the quality of the solutions obtained (to
make sure that the algorithms are comparable in quality), and the efficiency.
Development Time The C implementation of the algorithm is about 1500 lines long
and required a full week. The Localizer model is about one page long.
Quality of the Solutions Table 2 describes the quality of the coloring found by Lo-
calizer. These results agree with those of the C implementation and with those reported
in [4]. Each set of rows corresponds to a class of graphs and to 100 executions of Localizer
on graphs from this class. The rows in each set report on the various values found
by Localizer on these graphs and their frequencies. The columns report the number of
vertices, the density of the graph, the size factor sf used in the experiments, the number of
colors found by some solution, and the frequency of colorings of this quality. For instance,
the first set of rows reports that, on graphs of 125 vertices and density of 50%, 92% of the
executions led to a coloring with 19 colors and 8% of the executions led to a coloring with
colors. The results are given both for random and cooked graphs and the frequencies
are similar for both Localizer and the C implementation.
Efficiency Table 3 compares the efficiency of Localizer with the C implementation on
the same problems. Each row reports the average time of the two implementations for the
100 graphs in each class and computes the slowdown of Localizer. The experiments were
performed on a SUN Sparc Ultra-1 running Solaris 5.5.1 and the standard C++ compiler.
The average slowdown is 4.82, while minimum and maximum slowdowns are respectively
3.56 and 5.54. On these problems, the average slowdown is slightly higher than a machine
generation but it remains reasonable given the preliminary nature of the implementation.
This slowdown should also be contrasted with the substantial reduction in development
time.
Vertices Density Size Factor (sf) Colors Frequency
random 125 50 3 19 92
random 250 50 4
43
34 44
random 500 50 4
random 125 90 1 - 44 7
random
random 500 90 1 - 143
144 22
cooked 125 4 9 100
cooked
cooked 500 2 25 71

Table

2: Graph Coloring: Quality of the Solutions
Vertices Density Size Factor (sf) Localizer (L) C Implementation (C) L/C
random 125 50 3 78.3 18.9 4.50
random 250 50 4 82.8 18.4 4.50
random 500 50 4 633.7 123.4 5.10
random 125 90 1 16.18 4.53 3.56
random
random 500 90 1 162.7 29.6 4.88
cooked 125 4 22.09 4.18 5.28
cooked
cooked 500 2 240.3 49.9 4.80
average 4.82

Table

3: Graph Coloring: Efficiency of Localizer
5.3 Graph Partitioning
The problem has been studied experimentally in [3] and, once again, the experiments reported
here are based on a similar setting. Table 4 depicts the experimental results of
Localizer. The first row gives the setting of our parameters: T is the starting tempera-
ture, TF is the percentage of reduction of the temperature, SF is the size factor and the
remaining two were described previously.

Table

5 compares Localizer with the results reported in [3].
5.4 Job-Shop Scheduling
To conclude, we report some preliminary results on job-shop scheduling. Localizer has
been evaluated on a set of 28 classic benchmarks. The model used for these experiment
implements the neighborhood, commonly referred to as N1, which considers the reversal of
exactly one edge on the critical path. N1 has a number of nice properties: It preserves the
satisfiability of the solution and the transition graph induced by the neighorhood is such
that the optimal solution is reachable from all nodes of the graph. The experiments were
conducted in a fashion similar to what is reported in [6]. The parameters were defined as
ffl The maximal number of searches (maxSearches) is 1
ffl The maximal number of iterations for the inner loop (maxTrials) is 12000.
ffl The tabu list has a varying length constrained in between 5 and 30. Moreover, the
length is varied according to the rule of [6].
ffl Contrary to [6], the model does not use a restarting strategy.
Graph Results
Class V ertices Density SB F req: Localizer
random 124 2 11-13 14-16 17-19 33 38 29 2.22
random 4 55-59 60-65 66-77
random 8 159-174 175-190 191- 23 53 24 3.24
random
random
random 2 92-106 107-121 122-131 12 42 36 5.10
random 4 324-343 344-363 364-380 38 43 19 6.50
random 8 828-877 878-927 928- 37 40 23 9.98
random 500 0.5 48-54 55-59 60-66 15 43 42 10.08
random 4 1661-1701 1702-1741 1742-1824 22 58 20 20.67
random 1000 0.25 90-103 104-118 119-126 41 52 7 19.99
random 0.5 439-455 456-475 476-503 36 43 21 22.62
geom. 500 5 4-13 14-23 24-37 7 58
geom. 20 148-246 247-346 347-450 41 44 15 11.40
geom. 1000 5 24-43 44-63 64-78 37 57 6 18.70
geom. 20 196-399 400-599 600-816
28

Table

4: Graph Partitioning: Experimental Results
Graph Results
Class V ertices Density L:Best L:Time J:Best J:T ime Ratio
random 124 2 11 2.22 13 85.4 38.5
random
random 500 0.5 47 10.08 52 379.8 37.7
random 1000 0.25 90 19.99 102 729.9 36.5

Table

5: Graph Partitioning: Comparison Results

Table

6 reports the preliminary results. These results cannot be really compared with
the results of [6], since the neighborhood used in their experiment is (RN1 [ RN2) while
the model used here relies on N1 alone. The time reported correspond to the algorithm
termination (once the 12000 iterations are spent), not the time required to produce the
best or the optimal solution for the first time. Note also that the the value of the optimal
solution was not used as a stopping criterion. If this condition was to be used, the running
time would vary a lot more. For instance, LA01 usually produce the optimum solution in
about 0:5 seconds. Interestingly enough, even the simple neighborhood N1 does quite well
and finds the optimum solution for benchmarks (out of 28 benchmarks). The table also
reports a coarse histogram that summarizes the frequencies of apparition for the solutions.
These frequencies were obtained based on a serie of 100 experiment for each benchmark.
In summary, the results seem to indicate that Localizer will also compare well on
scheduling application.
6 Conclusion
The main contribution of this paper is to show that local search can be supported by modeling
languages to shorten the development time of these algorithms substantially, while
preserving the efficiency of special-purpose algorithms. To substantiate this claim, we presented
a progress report on the domain-specific language Localizer, introduced in [5].
Localizer statements are organized around the traditional concepts of local search and
may exploit the special structure of the problem at hand. The main conceptual tool underly-
Benchmark Results (MD=12000,MS=1,Neighborhood=N1)
Name Job M: Opt Ranges F req: Loc Avg:sol:

Table

ing Localizer is the concept of invariants which make it possible to specify complex data
structures declaratively. These data structures are maintained incrementally by Local-
izer, automating one of the most tedious and error-prone parts of local search algorithms.
Experimental results indicate that Localizer can be implemented to run with an efficiency
comparable to specific implementations.
Our current research focuses on building higher-level data structures to simplify the
design of invariants which are the cornerstone of the language. Extending the strategies to
accommodate dynamic k-opt [7], genetic algorithms, constraint techniques are also contem-
plated. Longer term research will explore how Localizer can be turned into a programming
language library to guarantee extensibility and wide applicability for expert users,
while preserving the right level of abstraction.

Acknowledgments

This paper is dedicated to the memory of Paris C. Kanellakis who
kept on gently pressuring us to pursue this topic. Thanks to D. McAllester and B. Selman for
many discussions on this research and to Costas Bush for implementing the graph-coloring
algorithm in C. This research was supported in part by an NSF NYI Award.



--R

The Programming Language Aspects of ThingLab
AMPL: A Modeling Language for Mathematical Programming.
Optimization by Simulated Annealing: An Experimental Evaluation
Optimization by Simulated Annealing: An Experimental Evaluation
Modeling Language for Local Search.
Marco Trubian Mauro Dell'Amico.
Combinatorial Optimization: Algorithms and Complexity.
A New Method for Solving Hard Satisfiability Problems.
Models for Using Stochastic Constraint Solvers in Constraint Logic Programming.
Numerica: a Modeling Language for Global Optimization.
--TR

--CTR
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
Pascal Hentenryck , Laurent Michel , Liyuan Liu, Contraint-Based Combinators for Local Search, Constraints, v.10 n.4, p.363-384, October   2005
Irit Katriel , Laurent Michel , Pascal Hentenryck, Maintaining Longest Paths Incrementally, Constraints, v.10 n.2, p.159-183, April     2005
Pascal Hentenryck , Laurent Michel, Control Abstractions for Local Search, Constraints, v.10 n.2, p.137-157, April     2005
Laurent Michel , Pascal Van Hentenryck, A constraint-based architecture for local search, ACM SIGPLAN Notices, v.37 n.11, November 2002
Marco Cadoli , Toni Mancini, Combining relational algebra, SQL, constraint modelling, and local search, Theory and Practice of Logic Programming, v.7 n.1-2, p.37-65, January 2007
Laurent Michel , Pascal Van Hentenryck, Comet in context, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.95-107, June 08-08, 2003, San Diego, California, USA
incremental algorithms;modeling language;local search