Previous Up Next

7.2  Implementations of Domains and Constraints

7.2.1  Suspended Goals: suspend

The constraint solvers of ECLiPSe are all implemented using suspended goals. The simplest implementation of any constraint is to suspend it until all its variables are sufficiently instantiated, and then test it.

The suspend solver implements this behaviour for all the mathematical constraints of ECLiPSe, >=, >, =:=, =\=, =< and <.

7.2.2  Interval Solver: ic

The standard constraint solver offered by most constraint programming systems is the finite domain solver, which applies constraint propagation techniques developed in the AI community [27]. ECLiPSe supports finite domain constraints via the ic library1. The library implements finite domains of integers, together with a basic set of constraints.

In addition, ic also allows continuous domains (in the form of numeric intervals), and constraints (equations and inequations) between expressions involving variables with continuous domains. These expressions can contain non-linear functions such as sin and built-in constants such as pi. Integrality is treated as a constraint, and it is possible to mix continuous and integral variables in the same constraint. Specialised search techniques (splitting [26] and squashing [15]) support the solving of problems with continuous variables.

Most constraints are also available in reified form, providing a convenient way of combining several primitive constraints.

Note that the ic library itself implements only a standard, basic set of arithmetic constraints. Many more finite domain constraints can be defined, which have uses in specific applications. The behaviour of these constraints is to prune the finite domains of their variables, in just the same way as the standard constraints. ECLiPSe offers several further libraries which implement such constraints using the underlying domain of the ic library.

7.2.3  Global Constraints: ic_global

One such library is ic_global. It supports a variety of constraints, each of which takes as an argument a list of finite domain variables, of unspecified length. Such constraints are called “global” constraints [2]. Examples of such constraints, available from the ic_global library are alldifferent/1, maxlist/2, occurrences/3 and sorted/2. For more details see section 8.5 in chapter 8.

7.2.4  Scheduling Constraints: ic_cumulative, ic_edge_finder

There are several ECLiPSe libraries implementing global constraints for scheduling applications. The constraints take a list of tasks (start times, durations and resource needs), and a maximum resource level. They reduce the finite domains of the task start times by reasoning on resource bottlenecks [13]. Three ECLiPSe libraries implementing scheduling constraints are ic_cumulative, ic_edge_finder and ic_edge_finder3. They implement the same constraints declaratively, but with different time complexity and strength of propagation. For more details see the library documentation in the Reference Manual.

7.2.5  Finite Integer Sets: ic_sets

The ic_sets library implements constraints over the domain of finite sets of integers2. The constraints are the usual relations over sets, e.g. membership, inclusion, intersection, union, disjointness. In addition, there are constraints between sets and integers, e.g. cardinality and weight constraints. For those, the ic_sets library cooperates with the ic library. For more details see chapter 10.

7.2.6  Linear Constraints: eplex

eplex supports a tight integration [4] between an external linear programming (LP) / mixed integer programming (MIP) solver (XPRESS [20] or CPLEX [11]) and ECLiPSe. Constraints as well as variables can be handled by the external LP/MIP solver, by a propagation solver like ic, or by both. Optimal solutions and other solution porperties can be returned to ECLiPSe as required. Search can be carried out either in ECLiPSe or in the external solver. For more details see chapter 16.

7.2.7  Constraints over symbols: ic_symbolic

The ic_symbolic library supports variables ranging over ordered symbolic domains (e.g. the names of products, the names of the weekdays), and constraints over such variables. It is implemented by mapping such variables and constraints to variables over integers and ic-constraints.


Previous Up Next