AMPL: A Modeling Language for Mathematical Programming

Technical Details of AMPL’s ilogcp Interface

This document describes the Concert C++ features that have been used in implementing the various kinds of AMPL extensions for ILOG CP and for CPLEX. Also a summary table specifies the Concert counterparts for specific AMPL constraint programming constructs.

Logical operators. AMPL's logical constraint expressions involving and and not are converted into corresponding Concert C++ expressions that use overloaded operators && and !. The AMPL expression c1 or c2 where c1 and c2 are constraint expression is translated into IloIfThen(env, !cc1, cc2) where cc1 and cc2 are Concert counterparts of c1 and c2. (Some uses of the or operation can be translated into a Concert expression using an overloaded || operator, but IloIfThen is more flexible; it accepts more types of constraints on the right-hand side.) Iterated logical operators exists and forall are implemented using IloOr and IloAnd respectively.

Conditional operators. Constraints involving ==> or <== are converted into the Concert representation using IloIfThen. Where else is used, a pair if IloIfThen objects is generated. Constraints using <==> are translated into corresponding Concert C++ expressions that use the overloaded operator ==.

The CPLEX mixed-integer solver directly accepts special cases of the implication operator in which the "if" part has a special simple form involving the value of a binary (zero-one) variable:

   binary-var = 0/1 ==> constraint-expr1
   binary-var = 0/1 ==> constraint-expr1 else constraint-expr2

   constraint-expr1 <== binary-var = 0/1
   constraint-expr1 <== binary-var = 0/1 else constraint-expr2
Here 0/1 must be either a 0 or a 1. However more general cases must be sent to ILOG CP or else translated into linear MIPs though the introduction of binary variables.

Counting operators. In the Concert driver, the count operator is translated into a sum of constraint expressions that represent its arguments. This approach uses the fact that a constraint expression in Concert is evaluated to 1 if satisfied and 0 otherwise. The atmost (atleast, exactly) k operators are converted into the sum of constraint subexpressions <= (>=, ==) k.

If the ilogcp solver option usenumberof is set to 1 (the default), the any numberof operators that have k a constant and have the same expression lists are combined into a single Concert IloDistribute constraint. This formulation as one "global" constraint permits very powerful efficiencies within the ILOG CP solver. When usenumberof is set to 0 or k is not a constant, numberof expressions are implemented as a sum of constraints of the form object-expr == k.

Pairwise operators. The ilogcp interface uses Concert IloAllDiff constraints to implement alldiff constraints from AMPL models.

Table of Concert counterparts. This table lists the AMPL operators relevant to constraint programming, and the Concert C++ calls that implement them. Where the model specifies an indexed collection of expressions or constraints, we denote by N the number of individual expressions or constraints passed to the solver interface.

AMPL Concert
constraint-expr1 or
constraint-expr2
IloIfThen(env, !constraint-expr1, constraint-expr2)
constraint-expr1 and
constraint-expr2
constraint-expr1 && constraint-expr2
not constraint-expr !constraint-expr
exists {indexing} constraint-expr IloOr disjunction(env);
disjunction.add(constraint-expr1);
...
disjunction.add(constraint-exprN);
forall {indexing} constraint-expr IloAnd conjunction(env);
conjunction.add(constraint-expr1);
...
conjunction.add(constraint-exprN);
if logical-expr then object-expr1
else object-expr2
IloIfThen(env, logical-expr, object-expr1);
IloIfThen(env, !logical-expr, object-expr2);
logical-expr ==> constraint-expr IloIfThen(env, logical-expr, constraint-expr)
logical-expr ==> constraint-expr1
else constraint-expr2
IloIfThen(env, logical-expr, constraint-expr1) &&
IloIfThen(env, !logical-expr, constraint-expr2)
logical-expr <==> constraint-expr logical-expr == constraint-expr
count {indexing} constraint-expr constraint-expr1 + ... + constraint-exprN
atmost k {indexing} constraint-expr constraint-expr1 + ... + constraint-exprN <= k
atleast k {indexing} constraint-expr constraint-expr1 + ... + constraint-exprN >= k
exactly k {indexing} constraint-expr constraint-expr1 + ... + constraint-exprN == k
numberof k in ({indexing} object-expr) (object-expr1 == k) + ... + (object-exprN == k) [1]
numberof k1 in ({indexing} object-expr)
...
numberof kN in ({indexing} object-expr)
IloIntVarArray cards(env);
IloIntArray values(env);
IloIntVarArray vars(env);
cards.add(IloIntVar(env));
values.add(k1);
...
cards.add(IloIntVar(env));
values.add(kN);
IloIntVar x1(env);
x1 == object-expr1;
vars.add(x1);
...
IloIntVar xM(env);
xM == object-exprM;
vars.add(xM);
IloDistribute(env, cards, values, vars);
[2]
alldiff {indexing} object-expr IloIntVarArray vars(env);
IloIntVar x1(env);
x1 == object-expr1;
vars.add(x1);
...
IloIntVar xN(env);
xN == object-exprN;
vars.add(xN);
IloAllDiff(env, vars);

[1] If option usenumberof=0.

[2] If option usenumberof=1 (the default).



Comments or questions?
Write to
info@ampl.com or use our comment form.

Return to the AMPL's ILOG CP page.

Return to the AMPL home page.


LAST MODIFIED 25 FEBRUARY 2013 BY 4er.