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

countof(k) {indexing} object-expr

The number of members of the indexing set such that the object-expr is equal to k.

ILOG Solver's analogue to AMPL's cardinality operators is the IlcCard function. IlcCard acts like card when called with one argument representing a set of integers (type IlcIntSetVar) or objects (type IlcAnySetVar). It acts like count when called with an index (type IlcIndex) and a constraint using that index (type IlcConstraint). The special case of the countof(k) operator is implemented efficiently through Solver's IlcDistribute function.

In the case where IlcCard is called with two arguments, an index is implicitly defined to run over the elements of one or more arrays of integers (type IlcIntVarArray) or objects (type IlcAnyVarArray). To get the effect of AMPL's count applied to an arbitrary indexed collection of constraints, Solver must introduce auxiliary binary variables via its metaconstraint feature. The association between constraints and these binary variables is maintained automatically, however, in contrast to the integer programming approach where it is necessary to form additional constraints (such as Multi and Min_Ship above) to enforce the definition of the binary variables.

Pairwise operators

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];

In AMPL, properties of indexed collections are defined by means of iterated operators such as sum and exists. Thus it would make sense to introduce an analogous operator for pairwise difference in an indexed collection of variables (assign2.mod):

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

alldiff {indexing} object-expr

Satisfied iff the object-expr takes different values for all pairs of different members of the indexing set.

A similar operator could be introduced for indexed collections of set expressions, to express the property of being pairwise disjoint:

alldisjoint {indexing} set-expr

Satisfied iff the set-expr evaluates to nonintersecting sets for all pairs of different members of the indexing set.

ILOG Solver provides functions that correspond closely to these iterated pairwise operators. Function IlcAllDiff specifies that the components of an array of integers (type IlcIntVarArray) or an array of objects (type IlcAnyVarArray) must be pairwise different. Function IlcAllNullIntersect specifies that the components of an array of integer sets (type IlcIntSetVarArray) or an array of object sets (type IlcAnySetVarArray) must be pairwise disjoint. Solver's search procedure handles these relationships directly in an efficient way.

Variables in subscripts

   minimize TotalCost:
      sum {j in JOBS, k in MACHINES} cost[j,k] * Assign[j,k];

   minimize TotalCost:
      sum {j in JOBS, k in MACHINES} 
         if MachineForJob[j] = k then cost[j,k];

   minimize TotalCost:
      sum {j in JOBS, k in MACHINES} cost[j,MachineForJob[j]];

There is also good reason to want to use variables within subscripts in the constraints, as may be seen by considering the related problem of sequencing. In a representative sequencing problem, we may want to assign a number of jobs to an equal number of "slots" so that each job is assigned to a different slot. The key difference between these slots and the machines of the assignment example is that the slots have a significant ordering. Setup costs and times between jobs are a function of this slot ordering, in ways that can be hard to express using current AMPL features.

To illustrate the difficulties and a prospective remedy, we define data for a simple sequencing problem as follows:

   param n integer >  0;

   set JOBS := 1..n;
   set SLOTS := 1..n;

   param procTime {JOBS} >  0;
   param dueTime {JOBS} >  0;
   param duePenalty {JOBS} >  0;

   set JOBPAIRS := {j1 in JOBS, j2 in JOBS: j1 != j2};
   set PREC within JOBPAIRS;

   param setupCost {JOBPAIRS} > = 0;
   param setupTime {JOBPAIRS} > = 0;

Adopting the approach introduced in the assignment example, we could define the variables as follows:

   var SlotForJob {JOBS} integer > = 1, < = n;
   var JobForSlot {SLOTS} integer > = 1, < = n;

   var FinishTime {{0} union JOBS};

What is the setup cost associated with the kth slot? It is the cost of going from JobForSlot[k-1] to JobForSlot[k], or

   setupCost[JobForSlot[k-1],JobForSlot[k]]

   FinishTime[JobForSlot[k]]

   FinishTime[JobForSlot[k-1]] 
      + setupTime[JobForSlot[k-1],JobForSlot[k]]
      + procTime[JobForSlot[k]] 
           < = FinishTime[JobForSlot[k]]

   SlotForJob[j1] <  SlotForJob[j2]

   JobForSlot[SlotForJob[j]] = j

In general, any subscript in a constraint might be an expression that contains variables. Unlike current AMPL subscripts, these could not simply be instantiated when AMPL generates constraints. Rather, for each such subscript, AMPL would have to provide the solver with instructions for evaluating the expression, in the form of an expression tree or (for linear expressions) a list of coefficients.

ILOG Solver's arrays of integers (type IlcIntArray) and integer variables (type IlcIntVarArray) have a subscripting operator that admits any integer expression (type IlcIntExp) as its argument. Since an integer expression may in general contain variables, subscripts containing variables could be implemented straightforwardly. This observation also extends to Solver's analogous arrays of floating-point numbers (types IlcFloatArray, IlcFloatVarArray) and of objects (types IlcAnyArray, IlcAnyVarArray).

Object-valued variables

var indexing_opt 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, in the preceding assignment model we artificially defined JOBS and MACHINES to be sets of the first n integers. If object-valued variables were allowed, however, these could be modeled as sets of objects to be read from the problem data, with a check that each contained the same number of objects:

   set JOBS;
   set MACHINES;
      check card (JOBS) = card (MACHINES);

   var MachineForJob {JOBS} in MACHINES; 

ILOG Solver provides constrained enumerated variables (types IlcAnyVar and IlcAnyVarArray) whose values may be arbitrary objects. 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). The IlcAllDiff operator required for our formulation is applicable to both object and integer arrays.

Set-valued variables

As an example, consider first a simple knapsack problem that 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;

   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;

   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 budgeted traveling salesman problem offers a somewhat different example. The problem 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;

   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;

The general forms for declarations of set-valued variables would be as follows:

var indexing_opt 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 indexing_opt 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 indexing_opt var-name circular within const-set-expr ;

The same as above, except the orderings are circular.

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 proposed new features page.

Return to the AMPL update page.

Return to the AMPL home page.