p.1 Constraint programming is one of the most exciting developments in programming languages of the last
decade. Based on a strong theoretical foundation, it is attracting widespread commercial interest and is now becoming the
method of choice for modelling many types of optimization problems, in particular, those involving heterogeneous constraints
and combinatorial search. Not surprisingly, therefore, constraint programming has recently been identified by the ACM (Association
for Computing Machinery) as one of the strategic directions in computing research.
p.1 traditional programming languages, including object oriented languages, provide little support for specifying
relationships or constraints among programmer-defined entities.
p.2 for many applications, the crux of the problem is to model the relationships and find objects that satisfy
them. For this reason, since the late 1960's, there has been interest in programming languages which allow the programmer
simply to state relationships between objects.
p.3-4 Constraint programming has allowed us to specify the problem very naturally, and at a high level,
in terms of arithmetic constraints.
p.4 The engineering disciplines are one area in which constraint programming has been applied with notable
success. Many engineering problems are extremely well suited to constraint programming since they often involve hierarchical
composition of complex systems, mathematical or Boolean models, and - especially in the case of diagnosis and design - deep
rule-based reasoning... Arguably, however, the most important application of the new constraint programming languages is for
tackling difficult multi-faceted combinatorial problems, such as those encountered in job scheduling, timetabling and routing.
These kinds of problems are very difficult to express and solve in conventional programming languages. This is because they
require searching through a possibly exponentially sized solution space in order to find a good or optimal solution to the
problem. To obtain reasonable efficiency, the constraints must be used to prune the search space.
p.6 A striking feature of constraint programming is its multi-disciplinary nature. It embraces facets of
mathematics, traditional computer science and artificial intelligence. Constraint programming draws on work in constraint
solving algorithms from operations research, numerical computing and on constraint solving techniques used in constraint
satisfaction problems, an important area of artificial intelligence.
p.11-12 Constraint programming is built upon constraints and constraint solving... The most important operation
is to determine if a constraint is satisfiable. The second operation, simplification, rewrites a constraint in a form which
makes its information more apparent. The third operation, optimization, finds a solution which is 'best' according to some
criterion... Constraints are a mathematical formalization of relationships which can hold between objects... Real world constraints
and objects can be modelled by these idealized mathematical constraints. Building such models is the job of the constraint
programmer... Constraints occur in all sorts of everyday reasoning.
p.41 Constraints are powerful tools for modelling many real-world problems.
p.118 Both of these algorithms for integer optimization are naive in the sense that they only use the objective
function to eliminate solutions which are not better than the best solution already discovered. In particular, they do not
use the objective function to direct the search to that part of the solution space in which it is likely to find better solutions.
This contrasts to optimization algorithms for the real numbers, such as the simplex algorithm (see Section 2.4), in which
the objective function is used to direct the search.
p.167 Modelling is at the heart of constraint programming... the programmer can simply state the constraints
and leave the constraint solving to the underlying system... The primary role of the constraint programmer is simply to model
the problem... Clearly, before starting to model the problem, the programmer needs to know what are the primitive constraints
available to them, since ultimately the problem must be described in terms of these primitives.
p.181 Modelling in a CLP language is quite different to programming in a traditional programming language
and requires an ability to reason about a problem in terms of constraints. At first, this may seem both difficult and unintuitive.
However, because the resulting program uses constraints rather than Boolean tests and assignments, it is considerably more
flexible than a program written in a conventional language, and may be used to answer a wide variety of questions... With
experience, a constraint programmer is able to immediately define their problem in constraint terms. The most important words
of advice are - practice, practice, and then practice some more.
p.193 Not only can we make use of data structures to store fixed values, we can also use them to store variables
to represent data that is presently unknown.
p.208 One of the most interesting features of CLP languages is that the same mechanism, constraints, provides
both control and data structures.
p.256-257 As this example demonstrates, constrain and generate is almost always preferable to generate and
test... When possible, the constraint programmer should make use of these complex primitive constraints. One reason is that
they often allow a succinct description of the problem. A second, more important reason, is that they will, usually, lead
to a more efficient program since the constraint solver provides specialized propagation rules for these constraints which
will be more effective at domain pruning than those for the equivalent 'simple' primitive constraints.
p.266,269 Ideally, the constraint programmer wishes to find a model which can be efficiently evaluated by
the solver in their CLP system. However, reasoning about efficiency is quite difficult... Determining the relative efficiency
of different models is a difficult problem and one which relies upon an understanding of the underlying constraint solver.
The best model will be the one in which information is propagated earliest. This often means that the more direct the mapping
from the problem into the primitive constraints in the program, the better the model. Another guideline is that the fewer
the variables the better, so long as propagation of information is similar.
p.270 Efficiency is not the only criteria by which to compare models. Flexibility is also an important issue.
It is unusual for an application to remain static. Often there will be a need to extend the program to model constraints which
were not part of the problem's original formulation. Flexibility measures how easy it is to express these additional constraints
in the model.
p.278 One of the more difficult tasks of the constraint programmer is to understand the tradeoff between
the cost of adding redundant constraints and the reduction in search space they cause.
