Draft Writeup of July 30, 1998

SUFFIXES

To represent values associated with a model component, AMPL employs various qualifiers or suffixes appended to component names. A suffix consists of a period or "dot" (.) followed by a (usually short) identifier, so that for example the reduced cost associated with a variable Buy[j] is written Buy[j].rc, and the reduced costs of all such variables can be viewed by giving the command display Buy.rc. There are numerous built-in suffixes of this kind, available for use in any AMPL session; see our table of built-in suffixes for details.

AMPL cannot anticipate all of the values that a solver might associate with model components, however. The values recognized (as input) or computed (as output) depend on the design of each solver and its algorithms. To provide for the representation of these values, the concept of a suffix has been extended to permit the definition of new suffixes for the duration of an AMPL session.

We first consider suffixes that are defined by the user, generally for the purpose of sending values to a solver. Then we describe how suffixes may be defined by a solver for the purpose of returning additional values.


User-defined suffixes

Most solvers recognize a variety of algorithmic choices or settings, each governed by a single value that applies to the entire problem being solved. Thus you can alter selected settings by setting up a single string of directives, as in this example applying the CPLEX solver to an integer program:

ampl: model multmip3.mod;
ampl: data multmip3.dat;

ampl: option solver cplex;
ampl: option cplex_options 'nodesel 3 varsel 2 backtrack 1.5';
ampl: solve;

CPLEX 5.0: nodesel 3
varsel 2
backtrack 1.5

CPLEX 5.0: optimal integer solution; objective 235625
611 simplex iterations
104 branch-and-bound nodes
A few kinds of solver settings are more complex, however, in that they require separate values to be set for individual model components. These settings are far too numerous to be accommodated in a directive string. Instead you can now specify them by means of user-defined suffixes that the solver interface has been set up to recognize.

As an example, for each variable in an integer program, CPLEX recognizes a separate branching priority and a separate preferred branching direction, represented by an integer in [0,9999] and in [-1,1] respectively. A new version of AMPL's CPLEX driver recognizes the suffixes .priority and .direction as giving these settings. To make use of these suffixes, you begin by entering a suffix command to define each one for the current AMPL session:

ampl: reset;
ampl: model multmip3.mod;
ampl: data multmip3.dat;

ampl: suffix priority IN, integer, >= 0, <= 9999;
ampl: suffix direction IN, integer, >= -1, <= 1;
The effect of these statements is to define expressions of the form name.priority and name.direction, where name denotes any variable, objective or constraint of the current model. The argument IN specifies that values corresponding to these suffixes are to be read in by the solver, and the subsequent phrases place restrictions on the values that will be accepted (much as in a param declaration).

The newly defined suffixed expressions may be assigned values by use of AMPL's let command. In particular, for our current example we want to use these suffixes to assign CPLEX priority and direction values corresponding to the binary variables Use[i,j]. Normally you will choose such values based on your knowledge of the problem and your past experience with similar problems. Here is one possibility:

ampl: let {i in ORIG, j in DEST} 
ampl?   Use[i,j].priority := sum {p in PROD} demand[j,p];

ampl: let Use["GARY","FRE"].direction := -1;
Variables not assigned a .priority or .direction value get a default value of zero (as do all constraints and objectives in this example), as you can check:

ampl: display Use.direction;
Use.direction [*,*] (tr)

:   CLEV GARY PITT    :=
DET   0     0   0
FRA   0     0   0
FRE   0    -1   0
LAF   0     0   0
LAN   0     0   0
STL   0     0   0
WIN   0     0   0
;
With the suffix values assigned as shown, CPLEX's search for a solution turns out to require fewer simplex iterations and fewer branch-and-bound nodes:

ampl: solve;

CPLEX 5.0: nodesel 3
varsel 2
backtrack 1.5

CPLEX 5.0: optimal integer solution; objective 235625
413 simplex iterations
64 branch-and-bound nodes
Further information about the suffixes recognized by CPLEX, and how to determine the corresponding settings, can be found in the CPLEX driver's README.cplex file. Other solver interfaces may recognize different suffixes for different purposes; you'll need to check separately for each solver you want to use.


Solver-defined suffixes

The most common use of AMPL suffixes is to represent solver result values that correspond to variables, constraints, and other model components. Yet only the most standard kinds of results, such as reduced costs and slacks, are covered by the built-in suffixes. To allow for other, more solver-specific results of optimization, AMPL permits solver drivers to define new suffixes and to associate solution result information with them.

To exhibit the possibilities, we give examples of solver-defined suffixes that are created by the revised CPLEX driver. Sensitivity analysis provides an example of numerical solver-defined suffixes, and infeasibility diagnosis shows how a symbolic (string-valued) suffix works.

Before a solver-defined suffix can be used in an AMPL script, it must be declared. The reporting of a direction of unboundedness gives an example of this situation.

For further information on all of these features, see the CPLEX driver's README.cplex file.

Sensitivity analysis. When the keyword sensitivity is included in CPLEX's list of directives, classical sensitivity ranges are computed and are returned in three new suffixes:

ampl: model steelT.mod;
ampl: data steelT.dat;

ampl: option solver cplex;
ampl: option cplex_options 'sensitivity';

ampl: solve;
CPLEX 5.0: sensitivity
CPLEX 5.0: optimal solution; objective 515033
18 iterations (1 in phase I)

suffix up OUT;
suffix down OUT;
suffix current OUT;
The three lines at the end show the suffix commands that are executed by AMPL in response to the results from the solver. These commands are invoked automatically; you do not need to type them. The argument OUT in each command says that these are suffixes whose values will be written out by the solver (in contrast to the previous example, where the argument IN indicated suffix values that the solver was to read in).

The sensitivity suffixes are interpreted as follows. For variables, suffix .current indicates the objective function coefficient in the current problem, while .down and .up give the smallest and largest values of the objective coefficient for which the current LP basis remains optimal:

ampl: display Sell.down, Sell.current, Sell.up;
:       Sell.down Sell.current    Sell.up      :=
bands 1   23.3          25       1e+20
bands 2   25.4          26       1e+20
bands 3   24.9          27          27.5
bands 4   10            27          29.1
coils 1   29.2857       30          30.8571
coils 2   33            35       1e+20
coils 3   35.2857       37       1e+20
coils 4   35.2857       39       1e+20
;
For constraints, the interpretation is similar except that it applies to a constraint's constant term (the so-called right-hand side value):

ampl: display time.down, time.current, time.up;
: time.down time.current   time.up    :=
1   37.8071       40       66.3786
2   37.8071       40       47.8571
3   25            32       45
4   30            40       62.5
;
You can use AMPL's generic synonyms to display a table of ranges for all variables or constraints, similar to the tables produced by the standalone version of CPLEX. (Values of -1e+20 in the .down column and 1e+20 in the .up column correspond to what CPLEX calls -infinity and +infinity in its tables.)

Infeasibility diagnosis. For a linear program that has no feasible solution, you can ask CPLEX to find an irreducible infeasible subset (or IIS) of the constraints and variable bounds, which may provide useful information on the source of the infeasibility. You turn on the IIS finder by changing the iisfind directive from its default value of 0 to either 1 (for a relatively fast version) or 2 (for a slower version that tends to find a smaller constraint subset).

The following example shows how IIS finding might be applied to the infeasible diet problem from chapter 2 of the AMPL book. After solve detects that there is no feasible solution, it is repeated with the 'iisfind 1' directive:

ampl: model diet.mod;
ampl: data diet2.dat;

ampl: option solver cplex;
ampl: solve;
CPLEX 5.0: infeasible problem
7 iterations (7 in phase I)

ampl: option cplex_options 'iisfind 1';
ampl: solve;
CPLEX 5.0: iisfind 1
CPLEX 5.0: infeasible problem
0 iterations

Returning iis of 7 variables and 2 constraints.

suffix iis symbolic OUT;

option iis_table '\
0	non	not in the iis\
1	low	at lower bound\
2	fix	fixed\
3	upp	at upper bound\
';
Again, AMPL shows the suffix statement that has been executed automatically. You can see that the new suffix is named .iis and that it is symbolic, or string-valued. An associated option iis_table, also set up by the solver driver and displayed automatically by solve, shows the strings that may be associated with .iis and gives brief descriptions of what they mean.

You can use display to look at the .iis values that have been returned:

ampl: display _varname, _var.iis, _conname, _con.iis;

:     _varname    _var.iis     _conname    _con.iis    :=
1   "Buy['BEEF']"   upp      "diet['A']"     non
2   "Buy['CHK']"    low      "diet['B1']"    non
3   "Buy['FISH']"   low      "diet['B2']"    low
4   "Buy['HAM']"    upp      "diet['C']"     non
5   "Buy['MCH']"    non      "diet['NA']"    upp
6   "Buy['MTL']"    upp      "diet['CAL']"   non
7   "Buy['SPG']"    low            .            .
8   "Buy['TUR']"    low            .            .
;
This information indicates that the IIS consists of four lower and three upper bounds on the variables, plus the constraints providing the lower bound on B2 and the upper bound on NA in the diet. Together these restrictions have no feasible solution, but dropping any one of them will permit a solution to be found to the remaining ones.

If dropping the bounds is not of interest, then you may want to list only the constraints that are in the IIS:

ampl: display {i in 1.._ncons: _con[i].iis <> "non"}
ampl?    (_conname[i], _con[i].iis);

:   _conname[i]  _con[i].iis    :=
3   "diet['B2']"   low
5   "diet['NA']"   upp
;
AMPL's expand command lets you look at these constraints:
ampl: expand {i in 1.._ncons: _con[i].iis <> "non"} _con[i];

s.t. diet['B2']:
	700 <= 15*Buy['BEEF'] + 20*Buy['CHK'] + 10*Buy['FISH'] + 10*Buy['HAM']
	 + 15*Buy['MCH'] + 15*Buy['MTL'] + 15*Buy['SPG'] + 10*Buy['TUR'] <= 
	20000;

s.t. diet['NA']:
	0 <= 938*Buy['BEEF'] + 2180*Buy['CHK'] + 945*Buy['FISH'] + 
	278*Buy['HAM'] + 1182*Buy['MCH'] + 896*Buy['MTL'] + 1329*Buy['SPG'] + 
	1397*Buy['TUR'] <= 40000;
You might conclude in this case that, if the bounds on purchases are to be met, then you need to allow either less vitamin B2 or more sodium in the diet. Further experimentation would be necessary to determine the amount less or more, however. (After you make adjustments that remove this IIS, the entire problem might become feasible, or CPLEX might find another IIS. The finder's algorithm detects only one IIS at a time.)

Direction of unboundedness. For an unbounded linear program -- one that has in effect a minimum of -Infinity or a maximum of +Infinity -- the "solution" is characterized by a feasible point together with a direction of unboundedness from that point. On return from CPLEX, the values of the variables define the feasible point. The direction of unboundedness is given by an additional value associated with each variable through the solver-defined suffix .unbdd.

An application of the direction of unboundedness can be found in our example of Benders decomposition applied to a transportation-location problem. One part of the decomposition scheme is a subproblem obtained by fixing the variables Build[i], which indicate the warehouses that are to be built, to trial values build[i]. In its dual form, this subproblem is:

var Supply_Price {ORIG} <= 0;
var Demand_Price {DEST};

maximize Dual_Ship_Cost:
   sum {i in ORIG} Supply_Price[i] * supply[i] * build[i] + 
   sum {j in DEST} Demand_Price[j] * demand[j];

subj to Dual_Ship {i in ORIG, j in DEST}:
   Supply_Price[i] + Demand_Price[j] <= var_cost[i,j];
When all values build[i] are set to zero, no warehouses are built, and the primal subproblem is infeasible. As a result, the dual formulation of the subproblem -- which always has a feasible solution -- must be unbounded. When this dual problem is solved from the AMPL command line, CPLEX returns the direction of unboundedness in the expected way:

ampl: model trnloc1d.mod;
ampl: data trnloc1.dat;

ampl: problem Sub: Supply_Price, Demand_Price, Dual_Ship_Cost, Dual_Ship;
ampl: let {i in ORIG} build[i] := 0;

ampl: option solver cplex, cplex_options 'presolve 0';
ampl: solve;
CPLEX 5.0: presolve 0
CPLEX 5.0: unbounded problem
30 iterations (0 in phase I)
variable.unbdd returned

suffix unbdd OUT;
The suffix message indicates that .unbdd has been created automatically. You can use this suffix to display the direction of unboundedness, which is quite simple in this case:

ampl: display Supply_Price.unbdd;
Supply_Price.unbdd [*] :=
 1 -1    4 -1    7 -1   10 -1   13 -1   16 -1   19 -1   22 -1   25 -1
 2 -1    5 -1    8 -1   11 -1   14 -1   17 -1   20 -1   23 -1
 3 -1    6 -1    9 -1   12 -1   15 -1   18 -1   21 -1   24 -1
;

ampl: display Demand_Price.unbdd;
Demand_Price.unbdd [*] :=
A3 1   A6 1   A8 1   A9 1   B2 1   B4 1
;
Our script for Benders decomposition (trnloc1d.mod) solves the subproblem repeatedly, with differing build[i] values generated from the master problem. After each solve, the result is tested for unboundedness and an extension of the master problem is constructed accordingly. The essentials of the main loop are as follows:

repeat {
   solve Sub;
   if Dual_Ship_Cost <= Max_Ship_Cost + 0.00001 then break;

   if Sub.result = "unbounded" then {
      let nCUT := nCUT + 1;
      let cut_type[nCUT] := "ray";
      let {i in ORIG} supply_price[i,nCUT] := Supply_Price[i].unbdd;
      let {j in DEST} demand_price[j,nCUT] := Demand_Price[j].unbdd;
      }
   else {
      let nCUT := nCUT + 1;
      let cut_type[nCUT] := "point";
      let {i in ORIG} supply_price[i,nCUT] := Supply_Price[i];
      let {j in DEST} demand_price[j,nCUT] := Demand_Price[j];
      }

   solve Master;
   let {i in ORIG} build[i] := Build[i];    
};
An attempt to use .unbdd in this context fails, however:
ampl: include /tmp/trnloc1d.run;

/tmp/trnloc1d.run, line 41 (offset 991):
	Bad suffix .unbdd for Supply_Price

context:  let {i in ORIG} supply_price[i,nCUT] := >>> Supply_Price[i].unbdd; <<< 
The difficulty here is that AMPL scans all commands in the repeat loop before beginning to execute any of them. As a result it encounters the use of .unbdd before any infeasible subproblem has had a chance to cause this suffix to be defined. To make this script run as intended, it is necessary to place the statement
suffix unbdd OUT;
in the script before the loop, so that .unbdd is already defined at the time the loop is scanned.


The suffix statement

A new AMPL suffix is defined by a statement of the following general form:

suffix suffix-name typeopt restriction-phraseopt inoutopt ... ;
This statement causes AMPL to recognize suffixed expressions of the form component-name.suffix-name, where component-name refers to any currently declared variable, constraint, objective, or problem. The definition of a suffix remains in effect until the next reset statement or the end of the current AMPL session.

The suffix-name is subject to the same rules as other names in AMPL. Suffixes have a separate name space, however, so that a suffix may have the same name as a parameter, variable, or other model component. The optional phrases of the suffix statement may appear in any order; their effects are described below.

A suffixed expression may be assigned (or reassigned) a value by use of AMPL's let statement. The optional type in the suffix statement indicates what values may be assigned, with all numerical values being the default:

type values allowed
none specified    any numerical value
integer integer numerical values
binary 0 or 1
symbolic character strings listed in option suffix-name_table
All numerical-valued suffixed expressions have an initial value of 0. Their permissible values may be further limited by a restriction-phrase having either of the forms

>= arith-expr
<= arith-expr
where arith-expr is any valid AMPL arithmetic expression not involving variables.

For each symbolic suffix, AMPL automatically defines an associated integer-valued suffix, suffix-name_num. An AMPL option suffix-name_table must then be created to define a relation between the .suffix-name and .suffix-name_num values, as in the following example:

suffix iis symbolic OUT;

option iis_table '\
0	non	not in the iis\
1	low	at lower bound\
2	fix	fixed\
3	upp	at upper bound\
';
Each line of the table consists of an integer value, a string value (without white space), and an optional comment. Every string value is associated with its adjacent integer value, and with any higher integer values that are less than the integer on the next line. Assigning a string value to a .suffix-name expression is equivalent to assigning the associated numerical value (or one of the associated numerical values) to a .suffix-name_num expression. The latter expressions are initially assigned the value 0, and are subject to any restriction-phrases as described above. (Normally the string values of symbolic suffixes are used in AMPL commands and scripts, while the numerical values are used in communication with solvers.)

The optional inout keyword determines how suffix values interact with the solver:

inout handling of suffix values
IN written by AMPL before invoking the solver, then read in by solver
OUT written out by solver, then read by AMPL after the solver is finished
INOUT      both read and written, as for IN and OUT above
LOCAL neither read nor written
INOUT is the default if no inout keyword is specified.



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

Return to the AMPL update page.

Return to the AMPL home page.


LAST MODIFIED 30 JULY 1998 BY 4er.