Proposed New AMPL Features Draft of June 30, 1996

Constraint Logic Programming Extensions

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

Optimization systems for constraint logic programming 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, logic programming solvers typically forego the ability to generate the strong bounds and cuts that are used to great advantage to limit the length of the search in integer programming. The logic programming 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, large, or simply very hard to solve.

AMPL could be extended in a variety of ways to take better advantage of the strengths of constraint logic programming solvers. Several kinds of constraints useful in logic programming are naturally expressed by allowing variables in certain operands or arguments where only constant expressions are currently permitted. The features of constraint logic programming systems also suggest some operators and functions that should be added to the AMPL language. Possibilities include:

Other extensions would permit a broader variety of expressions for defining a variable's domain: Each of these items corresponds to a section below, in which we propose a new feature and explains its usefulness. A final paragraph indicates how the feature could be handled by current built-in constructs of ILOG Solver. (There is also the possibility of defining new variable types, operators and constraints in ILOG Solver for purposes of implementing certain AMPL features.)


Logical operators

Current AMPL constraints consist of numerical-valued expressions connected by <=, >= or =. A "logical" extension is to allow these constraint expressions to be connected by logical (boolean) operators. These include the standard 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 the 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. This is the iterated form of or.

forall {indexing} constraint-expr

Satisfied iff the operand is satisfied for all members of the indexing set. This is the iterated form of and.

If we allow constraint-expr to be any valid expression for a constraint, and permit grouping of constraint expressions by parentheses,
( constraint-expr )

Satisfied iff the constraint-expr is satisfied.

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

The simplest useful application of this extension is in specifying disjunctive constraints. For example, in multmip3.mod from the AMPL book, we require that every nonzero sum {p in PROD} Trans[i,j,p] lie 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 could 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;
The above is moreover only one of many 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 use of "cuts" such as Isolation2b to tighten the formulation. The chosen transformation is not obviously superior to others, though it did prove to be superior -- for the data of interest -- in a series of empirical tests.

Although the use of or could be limited to simple cases like this, it would be desirable to allow the full generality of logical operations on constraint equalities and inequalities. There are thorny issues to be dealt with in the general case, however:

Solver drivers will have to detect and deal with these situations by analyzing the expression tree that they receive from AMPL. Probably AMPL can help by identifying common subexpressions and by identifying certain common special cases.

ILOG Solver provides analogues for AMPL's and (&&), or (||), and not (!) by overloading existing C++ operators. It also defines operators for exclusive or (!=), equivalence (==), and implication (<=). The effect of AMPL's iterated logical operators can be achieved by treating them as special cases of the count operator described next.


Cardinality operators

AMPL's card operator returns the number of members in its operand. When it is applied to a set defined in terms of variables, it can count the number of constraints of a given form that are satisfied. For instance, in the multmip3.mod example previously cited, there is 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 card, the same thing could 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}:
	   card {j in DEST: sum {p in PROD} Trans[i,j,p] > 0} 
              <= maxserve;
This form may be too general, however. The operand of card can be any set expression; so to implement the resulting constraint, the solver would have to receive sufficient information to allow it to evaluate that set expression given any values of the variables. To circumvent this difficulty, we could restrict the ways in which variables may appear in the argument to card, but we prefer to avoid complicating the language design with such restrictions. Instead, we could define a new operator that explicitly counts 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.

The above constraint would then be written:
	subject to Max_Serve {i in ORIG}:
	   count {j in DEST} (sum {p in PROD} Trans[i,j,p] > 0) 
              <= maxserve;
The constraint-expr could be any valid AMPL constraint, but no new conventions would be necessary in order to communicate it to a solver. The AMPL translator would instantiate it for each member of the indexing set, and would communicate it using the conventions already in place for passing constraints to solvers.

Additional iterated logical operators might be defined to simplify the descriptions of constraints in a few common special cases:

atmost1 {indexing} constraint-expr

Satisfied iff the constraint-expr holds for at most one member of the indexing set.

atleast1 {indexing} constraint-expr

Satisfied iff the constraint-expr holds for at least one member of the indexing set.

exactly1 {indexing} constraint-expr

Satisfied iff the constraint-expr holds for exactly one member of the indexing set.

The atleastone operator is a synonym for exists, but the other two are not currently available in AMPL.

To come: Generalization to iterated logical operators atmost(n), atleast(n), exactly(n) . . .

ILOG Solver's analogue to count is the IlcCard function. IlcCard works in the same way, its first argument being an index and its second a constraint using that index. Indexing is limited to all members of one or more arrays of integers (type IlcIntVarArray) or objects (type IlcAnyVarArray), however. To get the effect of count on an arbitrary collection of constraints that have been instantiated by AMPL, one could apply IlcCard to an array of integer variables that have been defined (using the IlcIntVar constructor) so that a variable is 1 iff its corresponding constraint is satisfied.


Conditional operators

To come: Several varieties of if-then and if-then-else . . .


Exclusion operators

To come: iterated operators alldifferent on numbers or objects, disjoint on sets . . .


Variables in subscripts

To come: Expressions like X[S[j]] or SC[S[j-1],S[j]] . . .


Object-valued variables

Currently a var declaration can use only the >= and <= operators to restrict the domain of a variable. If the in operator were also allowed in this context, then variables could be restricted to taking values from a given set:

var indexingopt var-name in const-set-expr ;

Restricts the defined variable(s) to values that lie within the set specified by the const-set-expr.

In the context of logic programming, the interesting case is where the const-set-expr specifies a set of objects denoted by character strings, or a finite set of numbers that stand for objects. The case where this expression is a union of numbers and/or numerical intervals is naturally handled in the more traditional context of numerical-valued variables and integer programming, as will be explained elsewhere . . .

As an example, an assignment of jobs to machines would be modeled in the integer programming context by defining a binary (zero-one) integer variable for each job-machine pair:

	set JOBS;
	set MACHINES;

	var Assign {JOBS,MACHINES} binary;
Instead we could declare only one variable for each job, whose value is taken from the set of machines:
	var Assign {JOBS} in MACHINES;
For each i in JOBS, the value of Assign[i] would be the machine to which job i is assigned. This approach requires fewer variables by an order of magnitude. There is not much that one can do with these variables in AMPL currently, because few operators or functions (only = and !=, in fact) accept variables as arguments. This limitation would be relaxed, however, by some of the extensions described above. Examples to come . . .

ILOG Solver provides constrained enumerated variables (types IlcAnyVar and IlcAnyVarArray) whose values may be arbitrary objects. ILOG Solver's integer-valued variables can also be used in contexts where each integer stands for an object (rather than for a numerical value that participates in arithmetic expressions).


Set-valued variables

A second extension to the var declaration's domain specification would give rise to variables that take on subsets as values:

var indexingopt var-name within const-set-expr ;

Defines set-valued variables whose domain consists of all unordered subsets of the set specified by the const-set-expr.

var indexingopt var-name ordered within const-set-expr ;

The same as above, except the const-set-expr must describe an ordered set, and induces an ordering on all of the subsets in the variable's domain. Ordered set functions such as first and next may thus be applied to the variable and its members.

var indexingopt var-name circular within const-set-expr ;

The same as above, except the orderings are circular.

The use of within in the domain specification is sufficient to distinguish declarations of set-valued variables. The distinction could be emphasized, however, by starting the declaration with a new keyword (such as var_set) or an extra keyword (as in var set).

Many kinds of combinatorial problems are more naturally described in terms of choosing an optimal subset, than in terms of any numerical decision variables. A simple knapsack problem, for example, concerns a set of objects having given values and weights, and an overall capacity:

	set OBJECTS;

	param value {OBJECTS} > 0;
	param weight {OBJECTS} > 0;

	param capacity > 0;
The problem can be stated concisely and naturally as follows: find a subset of some given set of objects, such that the total value of the subset is maximized, subject to the total weight of the subset being less than the capacity. This statement can be converted to a conventional algebraic formulation, by defining binary variable corresponding to each object:
	var In {OBJECTS} binary;

	maximize Total_Value: 
	   sum {i in OBJECTS} value[i] * In[i];

	subject to Weight_Limit:
	   sum {i in OBJECTS} weight[i] * In[i] <= capacity;
The concise and natural original description could be expressed directly in AMPL, however, by use of a set-valued variable:
	var Knapsack within OBJECTS;

	maximize Total_Value: 
	   sum {i in Knapsack} value[i];

	subject to Weight_Limit:
	   sum {i in Knapsack} weight[i] <= capacity;
The alternative objective and constraint superficially resemble the standard algebraic constraints, but they sum over the members of the set-valued variable Knapsack rather than over the set of objects.

A seemingly similar example is given by the budgeted traveling salesman problem, which is stated in terms of a set of cities, one designated the home city; a set of city pairs on which travel is possible, and travel costs between these pairs; and an overall budget:

	set CITIES; 
	param Home symbolic in CITIES; 

	set LINKS within {i in CITIES, j in CITIES: i <> j}; 
	param cost {LINKS}; 

	param budget > 0;
In one version of the problem, the goal is to plan a tour from the home city visiting as many cities as possible, using only available city-pair links, and subject to the total travel cost being within the budget. For this case we need a variable whose values are (circularly) ordered subsets of cities:
	var Tour circular within CITIES; 

	maximize Cities_Visited: card {Tour}; 

	subject to Budget_Limit: 
	   sum {c in Tour} cost[c,next(c)] <= budget; 

	subject to Leave_Home: first(Tour) = Home; 

	subject to Link_Exists {c in Tour}: (c,next(c)) in LINKS;
Unlike the knapsack problem, this one has no especially obvious equivalent as an integer program; the equivalent IPs that do exist, moreover, are generally too hard for general-purpose integer programming codes except in very small instances. It is safe to say that most combinatorial optimization problems of practical complexity share these properties.

ILOG Solver includes data types for sets of objects (IlcAnySet) and sets of integers (IlcIntSet). Set-valued variables are provided by corresponding constrained set variables of objects (types IlcAnySetVar and IlcAnySetVarArray) and integers (types IlcIntSetVar and IlcIntSetVarArray). Functions are provided for the standard set operations, including membership, containment, union, intersection, and cardinality.



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

Return to the AMPL/ILOG Solver links page.

Return to the AMPL update page.

Return to the AMPL home page.


LAST MODIFIED 1 APRIL 1996 BY 4er.