Constraint Programming Essentials

Variables

In constraint programming, models are built using variables and constraints, and as such is similar to integer programming. One fundamental difference is that, in integer programming, the range of a variable is specified and maintained as an interval, while in constraint programming, the variable range is maintained explicitly as a set of elements. Note that in the constraint programming literature, the range of a variable is commonly referred to as its domain.

Constraints

As a consequence of this explicit range representation, constraint programming can offer a wide variety of constraint types. Most constraint programming solvers allow constraints to be defined by arbitrary expressions that combine algebraic or logical operators. Moreover, meta-constraints can be formulated by interpreting the logical value of an expression as a boolean value in a logical relation, or as a binary value in an algebraic relation. For example, to express that every two distinct tasks \(i\) and \(j\), from a set of tasks \(T\) with respective starting times \(s_i,s_j\) and durations \(d_i, d_j\), should not overlap in time, we can use logical disjunctions:

(12)\[(s_i + d_i \leq s_j) \vee (s_j + d_j \leq s_i), \; \forall i,j \in T, i \neq j.\]

As another example, we can set a restriction such that no more than half the variables from \(x_1, \dots, x_n\) are assigned to a specific value \(v\) as \(\sum_{i=1}^n (x_i = v) \leq 0.5n\).

Global constraints

In addition, constraint programming offers special symbolic constraints that are called global constraints. These constraints can be defined over an arbitrary set of variables, and encapsulate a combinatorial structure that is exploited during the solving process. The constraint cp::AllDifferent\((x_1 \dots, x_n)\) is an example of such a global constraint. This global constraint requires the variables \(x_1 \dots, x_n\) to take distinct values.

Solving

The solving process underpinning constraint programming combines systematic search with inference techniques. The systematic search implicitly enumerates all possible variable-value combinations, thus defining a search tree in which the root represents the original problem to be solved. At each node in the search tree, an inference is made by means of domain filtering and constraint propagation. Each constraint in the model has an associated domain filtering algorithm that removes provably inconsistent values from the variable domains. Here, a domain value is inconsistent if it does not belong to any solution of the constraint. The updated domains are then communicated to the other constraints, whose domain filtering algorithms in turn become active; this is the constraint propagation process. In practice, the most effective filtering algorithms are those associated with global constraints. Therefore, most practical applications that are to be solved with constraint programming are formulated using global constraints.

Application domains

Constraint programming can be particularly effective with highly combinatorial problem domains, such as timetabling or resource-constrained scheduling. For such problems an integer programming model may be non-intuitive to express. Moreover, the associated continuous relaxation may be quite weak, which makes it much harder to find a provably optimal solution. For example, again consider two tasks \(A\) and \(B\) that must not overlap in time. In integer programming one can introduce two binary variables, \(y_{AB}\) and \(y_{BA}\), representing that task \(A\) must be processed either before or after, task \(B\). The non-overlapping constraint can then be expressed as \(y_{AB} + y_{BA} = 1\), for which a continuous linear relaxation may assign a solution \(y_{AB} = y_{BA} = 0.5\), which is not very informative. In contrast, the non-overlapping requirement can be handled very effectively using a specific ‘sequential resource’ scheduling constraint in constraint programming that effectively groups together all pairwise logical disjunctions in (12) above. Such a constraint is also referred to as a disjunctive or unary constraint in the constraint programming literature.

Designing models

The expressiveness of constraint programming offers a powerful modeling environment, albeit one that comes with a caveat. Namely, that different syntactically equivalent formulations may yield quite different solving times. For example, an alternative to the constraint cp::AllDifferent\((x_1, x_2, \dots, x_n)\) is its decomposition into pairwise not-equal constraints \(x_i \neq x_j\) for \(1 \leq i < j \leq n\). The domain filtering algorithm for cp::AllDifferent provably removes more inconsistent domain values than the individual not-equal constraints, which results in much smaller search trees and faster solution times. Therefore, when designing a constraint programming model, one should be aware of the effect that different formulations can have on the solving time. In most situations, it is advisable to apply global constraints to exploit their algorithmic power.

Variables in Constraint Programming

Variables of a constraint program

A constraint programming problem is made up of discrete variables and constraints over these discrete variables. A discrete variable is a variable that takes on a discrete value.

AIMMS supports two base types of discrete variables for constraint programming. The first type of variable is the integer variable; an ordinary variable with a range formulated such as {a..b} where a and b are numbers or references to parameters (see Variable and Constraint Declaration). Such variables can also be used in MIP problems. The second type of variable is the element variable, which will be further detailed in this section. This type of variable can only be used in a constraint programming problem. These two types of variable can be combined in a third type, called an integer element variable, which supports the operations that are defined for both the integer variable and the element variable.

ElementVariable Declaration and Attributes

An element variable is a variable that takes an element as its value. It can have the attributes specified in this table. The attributes IndexDomain, Priority, NonvarStatus, Text, Comment are the same as those for the variables introduced in Variable and Constraint Declaration.

Attribute	Value-type	See also
IndexDomain	index-domain	Index domain for variables
Range	named set
Default	constant-expression	The Parameter Default attribute, The Variable Default attribute
Priority	expression	The Variable Priority attribute
NonvarStatus	expression	The Variable NonVar attribute
Property	NoSave	The Set Property attribute
Text	string	The Text and Comment attribute
Comment	comment string	The Text and Comment attribute
Definition	expression	The Variable Definition attribute

The Range attribute

The range of an element variable is a one-dimensional set, similar to the range of an element parameter. This attribute must be a set identifier; and this permits the compiler to verify the semantics when element variables are used in expressions. This attribute is mandatory.

The Default attribute

The attribute default of an element variable is a quoted element. This attribute is not mandatory.

The Definition attribute

The Definition attribute of an element variable is similar to the definition attribute of a variable, see also page The Definition attribute, except that its value is an element and the resulting element must lie inside the range of the element variable. This attribute is not mandatory.

The Property attribute

The following properties are available to element variables:

Nosave

When set, this property indicates that the element variable is not to be saved in cases.

EmptyElementAllowed

‘ When set, this property indicates that in a feasible solution, the value of this variable can, but need not, be the empty element ". When the range of the element variable is a subset of the set Integers, this property is not available. In the following example, for the element variable eV, not selecting an element from S, is a valid choice, but this choice forces the integer variable X to 0.

ElementVariable eV {
    Range       :  S;
    Property    :  EmptyElementAllowed;
}
Constraint Force_X_to_zero_when_no_choice_for_eV {
   Definition   :  if eV = '' then X = 0 endif;
}

This attribute is not mandatory.

Element translation

Constraint programming solvers only use integer variables, and AIMMS translates an element variable, say eV with range the set S containing \(n\) elements into a integer variable, say v, with range \(\{ 0 .. n-1\}\). By design, this translation leaves no room for the empty element ", and subsequently, in a feasible solution, the empty element is no part of it. In order to permit the explicit consideration of the empty element as part of a solution, the property EmptyElementAllowed can be set for eV. In that case the range of v is \(\{ 0 .. n\}\) whereby the value 0 corresponds to the empty element.

Selecting a Variable Type

Choosing variable type

When there are multiple types of objects, such as integer variables and element variables in AIMMS, the following two questions naturally arise:

1. How to choose between the various types?

2. Can these types be combined?

The answers to these questions are as follows:

1. You may want to base the choice of types of variables on the operations that can be performed meaningfully on these types. Which operation is appropriate for which variable type is described below.

2. An identifier can have both the ‘integer variable’ and ‘element variable’ types and is then called an ‘integer element variable’. This is created as an element variable with a named subset of the predeclared set Integers as its range.

Operations on variables

The operations on variables that are interesting in constraint programming are:

• Numeric operations, such as multiplication, addition, and taking the absolute value. These operations are applicable to integer variables and to integer element variables.

• Index operations; selecting an element of an indexed parameter or variable. An element variable eV can be an argument of a parameter P or a variable X in expressions such as P(eV) or X(eV). These operations are applicable to all element variables. In the Constraint Programming literature, such operations are often implemented using so-called element constraints.

• Compare, subtract, min and max operations. These operations are applicable to all discrete variables, including element variables. For element variables, AIMMS uses the ordering of sets, see Set Declaration and Attributes.

All of the above operations are available with integer element variables.

Contiguous range

In order to limit an element variable to a contiguous subset of its named range, element valued suffixes .lower and .upper can be used. In the example below, the assignment to eV.Lower restricts the variable eV to the contiguous set {c..e}.

Set someLetters {
    Definition   : data { a, b, c, d, e };
}
ElementVariable eV {
    Range        : someLetters;
}
Procedure Restrict_eV {
    Body         : eV.lower := 'c';
}

The specification of non-contiguous ranges, informally known as ranges with holes, is detailed in the next subsection.

Constraints in Constraint Programming

Introduction

The constraints in constraint programming allow a rich variety of restrictions to be placed on the variables in a constraint program, ranging from direct domain restrictions on the variables to global constraints that come with powerful propagation algorithms.

Domain restrictions

A domain restriction restricts the domain of a single variable, or of multiple variables, and is specified using the IN operator. For example, we can restrict the domain of an element variable eV as follows:

Constraint DomRestr1 {
    Definition   :  eV in setA;
}

When we apply the IN operator to multiple variables, we can define a constraint by explicitly listing all tuples that are allowed. For example:

Constraint DomRestr2 {
    Definition   :  (eV1, eV2, eV3) in ThreeDimRelation;
    Comment      : "ThreeDimRelation contains all allowed tuples""}

Constraint DomRestr3 {
    Definition   :  not( (eV1, eV2, eV3) in ComplementRelation );
    Comment      : "ComplementRelation contains all forbidden tuples""}

In constraint DomRestr2 above, the three element variables are restricted to elements from the set of allowed tuples defined by ThreeDimRelation. Alternatively, we can define such a restriction using the complement, i.e., a list of forbidden tuples, as with constraint DomRestr3. In constraint programming, these constraints are also known as Table constraints; the data for these constraints resemble tables in a relational database.

Algebraic restrictions

The following operations are permitted on discrete variables, resulting in expressions that can be used in constraint programming constraints:

1. The binary min(a,b), max(a,b) and the iterative min(i,x(i)), max(i,x(i)) can both be used,

2. multiplication *, addition +, subtraction -, absolute value abs and square sqr,

3. integer division div(a,b), integer modulo mod(a,b),

4. floating point division /, and

5. indexing: an element variable is used as an argument of another parameter or variable, P(eV), V(eV),

Note that the operation must be meaningful for the variable type, see Operations on variables.

These expressions can be compared, using the operators <=, <, =, <>, >, and >= to create algebraic restrictions. Simple examples of algebraic constraints, taken from Einstein’s Logic Puzzle, are presented below.

Constraint Clue15 {
    Definition   :  abs( Smoke('Blends') - Drink('Water') ) = 1;
    Comment      :  "The man who smokes Blends has a neighbor who drinks water.""}
Constraint TheQuestion {
    Definition   :  National(eV)=Pet('Fish');
    Comment      :  "Who owns the pet fish? Result stored in element variable eV""}

Combining restrictions

The constraints above can be combined to create other constraints called meta-constraints. Meta-constraints can be formed by using the scalar operators AND, OR, XOR, NOT and IF-THEN-ELSE-ENDIF. For example:

Constraint OneTaskComesBeforeTheOther {
    Definition   : {
        ( StartA + DurA <= StartB ) or
        ( StartB + DurB <= StartA )
    }
}

In addition, restrictions can be combined into meta-constraints using the iterative operators FORALL and EXISTS. Moreover, restrictions can be counted using the iterative operator SUM and the result compared with another value. Finally, meta-constraints are restrictions themselves, they can be combined into even more complex meta-constraints. The following example is a variable definition, in which the collection of constraints (Finish(i) > Deadline(i)) is used to form a meta-constraint.

Variable TotalTardinessCost {
    Definition  :  Sum( i, TardinessCost(i) | ( Finish(i) > Deadline(i) ) );
}

In the following example, the binary variable y gets the value 1 if each X(i) is greater than P(i).

Constraint Ydef {
    Definition   :  y = FORALL( i, X(i) > P(i) );
}

From the Steel Mill example, we can model that we do not want more than two colors for each slab by the following nested usage of meta-constraints:

Constraint EnhancedColorCst {
    IndexDomain  :  (sl);
    Definition   :  sum( c, EXISTS (o in ColorOrders(c), SlabOfOrder(o)=sl)) <= 2;
}

Global constraints

AIMMS supports the global constraints presented in this table. These global constraints come with powerful filtering techniques that may significantly reduce the search tree and thus the time needed to solve a problem.

Table 56 Global constraints

Global constraint	Meaning
cp::AllDifferent (\(i\), \(x_i\))	The \(x_i\) must have distinct values. \(\forall i,j| i \neq j: x_i \neq x_j\)
cp::Count (\(i\), \(x_i\), \(c\), \(\otimes\), \(y\))	The number of \(x_i\) related to \(c\) is \(y\). \(\sum_i (x_i=c) \otimes y\) where \(\otimes \in \{\leq, \geq, =, >, <, \neq\}\)
cp::Cardinality (\(i\), \(x_i\), \(j\), \(c_j\), \(y_j\))	The number of \(x_i\) equal to \(c_j\) is \(y_j\). \(\forall j: \sum_i (x_i=c_j) = y_j\)
cp::Sequence (\(i\), \(x_i\), \(S\), \(q\), \(l\), \(u\))	The number of \(x_i\in S\) for each subsequence of length \(q\) is between \(l\) and \(u\). \(\forall i=1..n-q+1:\) \(l \leq \sum_{j=i}^{i+q-1} (x_j\in S) \leq u\)
cp::Channel (\(i\), \(x_i\), \(j\), \(y_j\))	Channel variable \(x_i\to J\) to \(y_j\to I\) \(\forall i,j: x_i=j \Leftrightarrow y_j=i\)
cp::Lexicographic (\(i\), \(x_i\), \(y_i\))	\(x\) is lexicographically before \(y\) \(\exists i: \forall j<i: x_j=y_j \wedge x_i<y_i\)
cp::BinPacking (\(i\), \(l_i\), \(j\), \(a_j\), \(s_j\))	Assign object \(j\) of known size \(s_j\) to bin \(a_j \to I\). Size of bin \(i \in I\) is \(l_i\). \(\forall i: \sum_{j \mid a_j = i} s_j \leq l_i\)

The example below illustrates the use of the global constraint cp::AllDifferent as used in the Latin square completion problem. A Latin square of order \(n\) is an \(n\times n\) matrix where the values are in the range \(\{1..n\}\) and distinct over each row and column.

Constraint RowsAllDifferent {
    IndexDomain  :  r;
    Definition   :  cp::AllDifferent( c, Entry(r, c) );
}
Constraint ColsAllDifferent {
    IndexDomain  :  c;
    Definition   :  cp::AllDifferent( r, Entry(r, c) );
}

Additional examples of global constraints are present in the AIMMS Function Reference. Unless stated otherwise in the function reference, global constraints can also be used outside of constraints definitions, for example in assignments or parameter definitions.

Global constraint vector arguments

These global constraints have vectors as arguments. The size of a vector is defined by a preceding index binding argument. Further information on index binding can be found in the Chapter on Index Index Binding. Such a vector can be a vector of elements, for example the fourth argument of cp::Cardinality. In a vector of elements, the empty element " is not allowed; comparison of an element variable against the empty element is not supported.

Basic scheduling constraints

AIMMS offers support for both basic scheduling and advanced scheduling. Advanced scheduling will be detailed in the next section but, for basic scheduling, AIMMS offers the following two global constraints:

1. The global constraint cp::SequentialSchedule(\(j\), \(s_j\), \(d_j\), \(e_j\)) ensures that two distinct jobs do not overlap where job \(j\) has start time \(s_j\), duration \(d_j\) and end time \(e_j\). This constraint is equivalent to:

   • \(\forall i,j,i \neq j:(s_i+d_i\leq s_j) \vee (s_j + d_j \leq s_i)\).

   • \(\forall j: s_j + d_j = e_j\)

   This and similar constraints are also known as unary or disjunctive constraints within the Constraint Programming literature.

2. The global constraint cp::ParallelSchedule(\(l\), \(u\), \(j\), \(s_j\), \(d_j\), \(e_j\), \(h_j\)) allows a single resource to handle multiple jobs, within limits \(l\) and \(u\), at the same time. Here job \(j\) has start time \(s_j\), duration \(d_j\), end time \(e_j\) and resource consumption (height) \(h_j\). This constraint is equivalent to:

   • \(\forall t: l\leq\sum_{j|s_j\leq{}t<e_j} h_j\leq u\).

   • \(\forall j: s_j + d_j = e_j\)

   This and similar constraints are also known as cumulative constraints within the Constraint Programming literature.