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.
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:
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:
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:
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.
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
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).
ampl: reset;
ampl: model multmip3.mod;
ampl: data multmip3.dat;
ampl: suffix priority IN, integer, >= 0, <= 9999;
ampl: suffix direction IN, integer, >= -1, <= 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: 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;
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: 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
;
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.
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
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:
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).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 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:
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 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 ;
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.)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 ;
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:
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.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\ ';
You can use display to look at the .iis values that have been returned:
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.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 . . ;
If dropping the bounds is not of interest, then you may want to list only the constraints that are in the IIS:
AMPL's expand command lets you look at these constraints: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 ;
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.)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;
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:
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: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];
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: 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;
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: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 ;
An attempt to use .unbdd in this context fails, however: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]; };
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 statementampl: 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; <<<
in the script before the loop, so that .unbdd is already defined at the time the loop is scanned.suffix unbdd OUT;
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:
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:
The optional inout keyword determines how suffix values interact
with the solver:
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.
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
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
where arith-expr is any valid AMPL arithmetic expression not
involving variables.
>= arith-expr
<= arith-expr
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.)
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\
';
INOUT is the default if no inout keyword is specified.
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
Comments or questions?
Write to info@ampl.com
or use our comment form.
Return to the AMPL update page.