11.1  Constraint Logic Programming

One of the main ambitions of Constraint Programming is the separation of Modelling, Algorithms and Search. This is best characterised by two pseudo-equations. The first one is paraphrased from Kowalski [12]

Solution = Logic + Control

and states that we intend to solve a problem by giving a logical, declarative description of the problem and adding control information that enables a computer to deduce a solution.

The second equation

Control = Reasoning + Search

is motivated by a fundamental difficulty we face when dealing with combinatorial problems: we do not have efficient algorithms for finding solutions, we have to resort to a combination of reasoning (via efficient algorithms) and (inefficient) search.

We can consider every constraint program as an exercise in combining the 3 ingredients:

• Logic - The design of a declarative Model of the problem.
• Reasoning - The choice of clever Constraint Propagation algorithms that reduce the need for search.
• Search - The choice of search strategies and heuristics for finding solutions quickly.

In this chapter we will focus on the first issue, Problem Modelling, and how it is supported by ECLⁱPS^e.