New in AMPL: 1 September 2013
“LOGIC” AND CONSTRAINT PROGRAMMING EXTENSIONS
For combinatorial or discrete optimization, AMPL has always
provided the option of including integervalued variables in algebraic
objectives and constraints. This is sufficient to make good use of
mixedinteger programming solvers that use a classical branchandbound
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:
 Logical operators: and,
or, not; iterated exists, forall
 Conditional operators:
ifthen, ifthenelse, ==>, ==> else,
<==, <==>
 Counting operators: iterated
count, atmost, atleast, exactly,
numberof
 Pairwise operators:
alldiff
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.
To obtain a driver for the ILOG Concert Technology
C++ interface to the IBM ILOG CP constraint programming optimizer and also IBM CPLEX mixedinteger 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 1year licenses for the CPLEX and ILOG CP solvers.
 Or request a free 30day 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 mixedinteger 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 mixedinteger 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.
An AMPLinterfaced 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.
An AMPLinterfaced 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 JaCoP3.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 Javabased, 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 64bit JaCoP on a 64bit platform, but have 32bit Java installed; in that case you should install 32bit 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.
Basic AMPL constraints consist of numericalvalued
expressions connected by <=, >= or =.
These constraint expressions are now allowed to be connected by AMPL's
unary and binary logical operators,
 constraintexpr1 or constraintexpr2
 Satisfied iff at least one of the operands is satisfied.
 constraintexpr1 and constraintexpr2
 Satisfied iff both of the operands are satisfied.
 not constraintexpr
 Satisfied iff the operand is not satisfied.
and AMPL's iterated forms of the binary logical operators:
 exists {indexing} constraintexpr
 Satisfied iff the operand is satisfied for at least one member
of the indexing set (the iterated form of or).
 forall {indexing} constraintexpr
 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:
 ( constraintexpr )
 Satisfied iff the constraintexpr 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 eitheror 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.
AMPL already provides an ifthenelse operator that
returns a value that can be used in expressions:
 if logicalexpr
then objectexpr1
 if logicalexpr
then objectexpr1
else objectexpr2
 Takes the value of objectexpr1 when the
logicalexpr is true, and the value of objectexpr2 (or
0 if omitted) when the logicalexpr is false. Each
objectexpr may be any expression that evaluates to a legal set
member  that is, either a number or a string.
 if logicalexpr
then setexpr1
else setexpr2
 Takes the value of setexpr1 when the logicalexpr
is true, and the value of setexpr2 when the
logicalexpr is false.
When this operator appears in a constraint, the logicalexpr
can contain variables, in which case AMPL handles the constraint like
other nonlinear constraints, passing an expression tree to the solver.
In particular, the logicalexpr may be any valid
constraintexpr.
AMPL also has a similar ifthen form of indexing expression,
which is used in the context of constraints as follows:
 subject to name {if logicalexpr}:
constraintexpr;
 Enforces the constraint specified by the constraintexpr
if and only if the logicalexpr 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 "ifthen" and "ifthenelse"
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:
 logicalexpr ==>
constraintexpr1
 Satisfied if the logicalexpr is true and
constraintexpr1 is satisfied, or if the logicalexpr is
false.
 logicalexpr ==>
constraintexpr1 else
constraintexpr2
 Satisfied if the logicalexpr is true and
constraintexpr1 is satisfied, or if the logicalexpr is
false and constraintexpr2 is satisfied.
 logicalexpr <==>
constraintexpr
 Satisfied if the logicalexpr is true and
constraintexpr is satisfied, or if the logicalexpr is
false and constraintexpr is not satisfied.
Additionally <== has the same meaning as ==> except
with the roles of constraintexpr1 and constraintexpr2
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 logicalexpr can be any constraintexpr.
AMPL's count operator returns the
number of times that a certain constraint is satisfied:
 count {indexing}
constraintexpr
 The number of members of the indexing set such that the
constraintexpr 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 zeroone 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 constraintexpr 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 proavided to simplify
the descriptions of constraints in some common special cases:
 atmost k {indexing}
constraintexpr
 Satisfied iff the constraintexpr holds for at most
k members of the indexing set.
 atleast k {indexing}
constraintexpr
 Satisfied iff the constraintexpr holds for at least
k members of the indexing set.
 exactly k {indexing}
constraintexpr
 Satisfied iff the constraintexpr 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 (zeroone) variable
Assign[j,k] for each jobmachine 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
constraintexpr, 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}
objectexpr)
 The number of members of the indexing set such that the
objectexpr 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.
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}
varexpr
 alldiff ( {indexing}
varexpr1, {indexing}
varexpr2, ... )>
 Satisfied iff all of the specified variables take different values.
Each {indexing} may be any AMPL indexingexpression,
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.
Comments or questions? Write to info@ampl.com or use our comment form.
Return to the AMPL home
page.
LAST MODIFIED 4 SEPTEMBER 2013 BY 4er.
