| Proposed New AMPL Features | Draft of June 30, 1996 |
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:
- 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.
- 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.
- ( constraint-expr )
- Satisfied iff the constraint-expr is satisfied.
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:
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 we allow < and > in the constraints.)
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.
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.
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.
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.
- 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.
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).
- 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.
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.
Return to the AMPL/ILOG Solver links page.
Return to the AMPL update page.