TRY NOW!
AMPL > >Resources > >New in AMPL: Logic & Constraint Programming Extensions

“Logic” and Constraint Programming Extensions

For combinatorial or discrete optimization, AMPL has always provided the option of including integer-valued variables in algebraic objectives and constraints. This is sufficient to make good use of mixed-integer programming solvers that use a classical branch-and-bound procedure.

Optimization systems for constraint programming (CP) also use a branching or tree search, but are able to work with a much broader variety of combinatorial expressions. In exchange for this advantage, CP solvers typically forego the ability to generate the bounds and cuts that are used to great advantage to limit the search in integer programming. The CP approach thus tends to be advantageous for problems that are “highly” combinatorial, in the sense that their formulation in terms of integer variables is artificial and hard to work with, or requires a very large number of variables or constraints, or fails to yield strong bounds.

AMPL has been extended in a variety of ways to take better advantage of the strengths of constraint programming. In this document we provide a syntax and usage summary of the extended operators that are recognized by AMPL’s drivers for the following CP solvers:

Follow these links for instructions on obtaining and setting up versions of these solvers that provide AMPL interfaces.

Several kinds of constraints useful for CP are naturally expressed by allowing variables in certain operands or arguments where only constant expressions are normally permitted. Other typical CP constraints have been made possible by adding operators to AMPL. Four classes of additions and extensions are covered specifically in this document:

Follow these links for more information. To get started, see also our presentation slides from INFORMS Phoenix 2012, our collection of simple examples using some of the features described in this document.

IBM ILOG CP with CPLEX

To obtain a driver for the ILOG Concert Technology C++ interface to the IBM ILOG CP constraint programming optimizer and also IBM CPLEX mixed-integer programming optimizer, there are several possibilities:

  • If you have an IBM CPLEX license from us, log in to your account at the AMPL download site and click on an ilogcp link to get a bundle of the needed files.
  • If you have a AMPL academic license from us, join the IBM Academic Initiative and send info@ampl.com a request to add free 1-year licenses for the CPLEX and ILOG CP solvers.
  • Or request a free 30-day AMPL trial and request the CPLEX product as one of your solvers.

Once the files are installed in your AMPL or solver directory, invoke this interface by setting

option solver ilogcp;

This solver processes the problems sent to it according to the setting of the optimizer directive in the ilogcp_options string:

optimizer=ilogcp
All problems are sent to ILOG CP.
optimizer=cplex
All problems are sent to CPLEX.
optimizer=auto
Conventional mixed-integer linear programs are sent to CPLEX, and optimization problems using the features described below are sent to ILOG CP.

Problems incorporating certain of the features described in this document, although not conventional mixed-integer programs, may optionally be sent to CPLEX. In that case the Concert interface makes an automatic transformation to an equivalent problem of a kind that CPLEX is able to handle. An error message is generated however if Concert is asked to send a problem to a solver that has no way of handling it.

See also our listing of ILOG CP solver options. For those familiar with the Concert C++ interface, we also provide a summary of technical details including a table of correspondences between AMPL and Concert constructs.

Gecode

An AMPL-interfaced version of the Gecode constraint programming solver is freely available from our Google Code download site for Windows, Linux, and MacOS.

To install, download and unpack the gecode.exe (Windows) or gecode (Linux, MacOS) executable file and place it in your AMPL or solver directory. Then select the Gecode solver with the command:

option solver gecode;

All of the modeling features described in this document are supported by the Gecode interface, with the limitation that the variables much be integer or binary. See also our complete listing of Gecode solver options.

JaCoP

An AMPL-interfaced version of the JaCoP constraint programming solver is freely available from our Google Code download site for Windows, Linux, and MacOS.

To install, download and unpack the zipfile corresponding to your platform, and copy all of the contained files — jacop.exe (Windows) or jacop (Linux, MacOS), ampljacop.jar, and JaCoP-3.2.jar — into your AMPL or solver directory. Then select the JaCoP solver with the command:

option solver jacop;

Notes on Java: Since JaCoP is Java-based, a Java installation is required to run it. Most computers already have Java installed, but if you get a “Failed to load” message then you may need to download the Java SE runtime environment. A “Failed to load” message can also occur if you are trying to run 64-bit JaCoP on a 64-bit platform, but have 32-bit Java installed; in that case you should install 32-bit JaCoP instead.

All of the modeling features described in this document are supported by the JaCoP interface, with the limitation that the variables much be integer or binary. See also our complete listing of JaCoP solver options.

Logical operators

Basic AMPL constraints consist of numerical-valued expressions connected by <=, >= or =. These constraint expressions are now allowed to be connected by AMPL’s unary and binary logical operators,

constraint-expr1 or constraint-expr2
Satisfied iff at least one of the operands is satisfied.
constraint-expr1 and constraint-expr2
Satisfied iff both of the operands are satisfied.
not constraint-expr
Satisfied iff the operand is not satisfied.

and AMPL’s iterated forms of the binary logical operators:

exists {indexing} constraint-expr
Satisfied iff the operand is satisfied for at least one member of the indexing set (the iterated form of or).
forall {indexing} constraint-expr
Satisfied iff the operand is satisfied for all members of the indexing set (the iterated form of and).

Constraint expressions can also be grouped by by parentheses:

( constraint-expr )
Satisfied iff the constraint-expr is satisfied.

So an AMPL constraint can be any logical combination of equalities and inequalities.

The simplest useful application of this extension is to specify disjunctive constraints. For example, in
multmip3.mod
from the AMPL book, we require for every origin i and destination j that total shipments sum {p in PROD} Trans[i,j,p] lie either at zero or between minload and limit[i,j]. This is accomplished in an integer programming framework by introducing auxiliary binary variables Use[i,j],

var Trans {ORIG,DEST,PROD} >= 0;
var Use {ORIG,DEST} binary;

and forming the following constraints:

subject to Multi {i in ORIG, j in DEST}:
   sum {p in PROD} Trans[i,j,p] <= limit[i,j] * Use[i,j];
subject to Min_Ship {i in ORIG, j in DEST}:
   sum {p in PROD} Trans[i,j,p] >= minload * Use[i,j];

The same restrictions can be stated using the or operator in this way:

subject to Multi_Min_Ship {i in ORIG, j in DEST}:
   sum {p in PROD} Trans[i,j,p] = 0 or
   minload <= sum {p in PROD} Trans[i,j,p] <= limit[i,j];

Fewer variables and constraints are required, and the statement of the constraint is much closer to its original formulation.

In another example, variables Assign[i1,i2,j] have been defined to represent the number of people of type (i1,i2) assigned to location j. The following declarations define an additional restriction in integer programming terms:

param upperbnd {(i1,i2) in ISO, j in REST} :=
   min (ceil((number2[i1,i2]/card {PEOPLE}) * hiDine[j]) + give[i1,i2],
        hiTargetTitle[i1,j] + giveTitle[i1],
        hiTargetLoc[i2,j] + giveLoc[i2],
        number2[i1,i2]);
var Lone {(i1,i2) in ISO, j in REST} binary;
subj to Isolation1 {(i1,i2) in ISO, j in REST}:
   Assign2[i1,i2,j] <= upperbnd[i1,i2,j] * Lone[i1,i2,j];
subj to Isolation2a {(i1,i2) in ISO, j in REST}:
   Assign2[i1,i2,j] +
      sum {ii1 in ADJACENT[i1]: (ii1,i2) in TYPE2} Assign2[ii1,i2,j]
         >= 2 * Lone[i1,i2,j];
subj to Isolation2b {(i1,i2) in ISO, j in REST}:
   Assign2[i1,i2,j] >= Lone[i1,i2,j];

Using the or operator, the same thing can be said much more directly and concisely:

subj to Isolation {(i1,i2) in ISO, j in REST}:
   Assign2[i1,i2,j] = 0 or
   Assign2[i1,i2,j] +
      sum {ii1 in ADJACENT[i1]:
                    (ii1,i2) in TYPE2} Assign2[ii1,i2,j] >= 2;

As a further complication under the integer programming approach, there are many other ways that this either-or constraint can be transformed, through addition of binary variables, to inequalities suitable for integer programming. Other transformations differ in the computation of the upper bound parameter, in the details of the constraint expressions, and in the choice of “cuts” such as Isolation2b to tighten the formulation. The transformation exhibited above is not obviously superior to others, though it did prove to be superior — for the data of interest — in a series of empirical tests.

Using the not operator it is possible to specify a feasible region that isn’t closed, so that optimization problems using continuous variables may be meaningless. This is illustrated by a very simple problem:

var x;
minimize Obj: x;
subject to OpenCons: not (x <= 2);

The objective has an infimum of 2, but no minimum that satisfies the constraint. The same problem arises if one uses a strict inequality < or >, specifically the expresion x > 2 in this case. Because the CP solvers operate only on discrete variables, however, they freely allows expressions that have these forms.

Conditional operators

AMPL already provides an if-then-else operator that returns a value that can be used in expressions:

if logical-expr then object-expr1
if logical-expr then object-expr1 else object-expr2
Takes the value of object-expr1 when the logical-expr is true, and the value of object-expr2 (or 0 if omitted) when the logical-expr is false. Each object-expr may be any expression that evaluates to a legal set member — that is, either a number or a string.
if logical-expr then set-expr1 else set-expr2
Takes the value of set-expr1 when the logical-expr is true, and the value of set-expr2 when the logical-expr is false.

When this operator appears in a constraint, the logical-expr can contain variables, in which case AMPL handles the constraint like other nonlinear constraints, passing an expression tree to the solver. In particular, the logical-expr may be any valid constraint-expr.

AMPL also has a similar if-then form of indexing expression, which is used in the context of constraints as follows:

subject to name {if logical-expr}: constraint-expr;
Enforces the constraint specified by the constraint-expr if and only if the logical-expr is true.

Thus for example in section 8.4 of the AMPL book we have:

subject to Time {if avail > 0}:
   sum {p in PROD} (1/rate[p]) * Make[p] <= avail;

It is arguably more natural, however, to make the if condition part of the constraint expression. Since the if-then and if-then-else constructs are already heavily used in AMPL (for expressions and for script statements), we have introduced several operators for describing implications in constraints. For example:

subject to Time:
   avail > 0 ==> sum {p in PROD} (1/rate[p]) * Make[p] <= avail;

General forms of AMPL’s conditional operators are as follows:

logical-expr ==> constraint-expr1
Satisfied if the logical-expr is true and constraint-expr1 is satisfied, or if the logical-expr is false.
logical-expr ==> constraint-expr1 else constraint-expr2
Satisfied if the logical-expr is true and constraint-expr1 is satisfied, or if the logical-expr is false and constraint-expr2 is satisfied.
logical-expr <==> constraint-expr
Satisfied if the logical-expr is true and constraint-expr is satisfied, or if the logical-expr is false and constraint-expr is not satisfied.

Additionally <== has the same meaning as ==> except with the roles of constraint-expr1 and constraint-expr2 reversed.

By allowing variables on both sides of the implication operators, these forms considerably expand the variety of conditional constraints that AMPL can conveniently express. For example, the previously defined Multi_Min_Ship constraint can be written:

subject to Multi_Min_Ship {i in ORIG, j in DEST}:
   sum {p in PROD} Trans[i,j,p] > 0 ==>
      minload <= sum {p in PROD} Trans[i,j,p] <= limit[i,j];

Again, the logical-expr can be any constraint-expr.

Counting operators

AMPL’s count operator returns the number of times that a certain constraint is satisfied:

count {indexing} constraint-expr
The number of members of the indexing set such that the constraint-expr is satisfied.

As an example, consider the multmip3.mod model previously cited. It has the following constraint on the number of destinations served by any origin:

subject to Max_Serve {i in ORIG}:
   sum {j in DEST} Use[i,j] <= maxserve;

Using count, the same thing can be expressed in terms of the natural Trans[i,j,p] variables, without recourse to the auxiliary zero-one Use[i,j] variables:

subject to Max_Serve {i in ORIG}:
   count {j in DEST} (sum {p in PROD} Trans[i,j,p] >  0) <= maxserve;

The constraint-expr can be any valid AMPL constraint. The AMPL translator will instantiate it for each member of the indexing set, and will communicate all of the instantiated constraints to the solver interface.

Additional iterated logical operators are provided to simplify the descriptions of constraints in some common special cases:

atmost k {indexing} constraint-expr
Satisfied iff the constraint-expr holds for at most k members of the indexing set.
atleast k {indexing} constraint-expr
Satisfied iff the constraint-expr holds for at least k members of the indexing set.
exactly k {indexing} constraint-expr
Satisfied iff the constraint-expr holds for exactly k members of the indexing set.

k can be any constant arithmetic expression that evaluates to a nonnegative integer value.

Another particularly important special case occurs when counting the number of set members at which a given expression takes a particular value. As a simple example, consider the scheduling problem that assigns a number of jobs to a smaller number of machines, so that at most cap[k] jobs are assigned to machine k. The conventional formulation defines a binary (zero-one) variable Assign[j,k] for each job-machine pair, such that Assign[j,k] will be 1 if and only if job j is assigned to machine k:

param n integer >  0;
set JOBS := 1..n;
set MACHINES := 1..n;
param cap {MACHINES} integer >= 0;
var Assign {JOBS,MACHINES} binary;

The requirements of the assignment can then be specified by one algebraic constraint for each job and for each machine:

subj to OneMachinePerJob {j in JOBS}:
   sum {k in MACHINES} Assign[j,k] = 1;
subj to CapacityOfMachine {k in MACHINES}:
   sum {j in JOBS} Assign[j,k] <= cap[k];

As an alternative, we could associate with each job only one variable, whose value is taken from the set of machines:

var MachineForJob {JOBS} integer >= 1, <= n;

For each j in JOBS, the value of MachineForJob[j] would be the number of the machine that is assigned to do job j. This approach requires fewer variables by an order of magnitude, and automatically enforces the requirement that one machine be assigned to each job. To specify that at most cap[k] jobs are assigned to machine k, we could use the count operator:

subj to CapacityOfMachine {k in MACHINES}:
   count {j in JOBS} (MachineForJob[j] = k) <= cap[k];

This is not as readable a statement of the constraint as one might like, however, and it is likely to be inefficient. Because the count operator can be applied to any AMPL constraint-expr, its implementation in the AMPL translator would scan through the entire set JOBS for each constraint, testing MachineForJob[j] = k for every combination of job j and machine k — even though only one pass through the jobs is necessary to accumulate the counts for all machines. To address this AMPL offers a more specialized iterated operator for counting individual values assumed by an indexed expression:

subj to CapacityOfMachine {k in MACHINES}:
   numberof k in ({j in JOBS} MachineForJob[j]) <= cap[k];

The general form is:

numberof k in ({indexing} object-expr)
The number of members of the indexing set such that the object-expr is equal to k.

Although it would still be possible to implement this operator inefficiently, the presence of numberof can alert the AMPL translator to the possibility of a more efficient evaluation.

Pairwise operators

Various assignment and related combinatorial problems require that a collection of entities be pairwise different or disjoint. New iterated operators for these conditions make them easier to state and help to make the resulting problems easier to solve.

An example is given by the assignment problem that resembles the one defined above, but with equal numbers of jobs and machines. Each job is assigned to one machine, as before, but also each machine gets one job. In describing the constraints on the machines, we can dispense with the parameters cap[k] (which would all be 1) and can instead simply say that no two variables MachineForJob[j1] and MachineForJob[j2] have the same value. Such a restriction can be stated in AMPL as follows:

subj to OneJobPerMachine {j1 in JOBS, j2 in JOBS: j1 < j2}:
   MachineForJob[j1] != MachineForJob[j2];

Although a CP solver could in principle handle these disequalities, this is a cumbersome way to express the simple idea of being pairwise different, and it gives rise to an order of magnitude more constraints than the conventional assignment formulation. As an alternative, an operator for pairwise difference in an indexed collection of variables has been introduced:

subj to OneJobPerMachine: alldiff {j in JOBS} MachineForJob[j];

In general, this operator can be applied to any collection of expressions involving variables:

alldiff {indexing} var-expr
alldiff ( {indexing} var-expr1, {indexing} var-expr2, ... )

Satisfied iff all of the specified variables take different values.Each {indexing} may be any AMPL indexing-expression, or may be omitted to specify a single item in the list. (This is the same syntax as for other AMPL iterated operators such as min and max.) Using alldiff makes constraints easier to read, and also conveys more useful information to a solver than a large collection of individual inequalities.