Draft of April 17, 1996

Proposed New AMPL Features

Solver Interface

Facilities would be added for two-way communication between AMPL and a solver. As a result, some of the following features would be supported:

Other aspects of an advanced user interface would be visible to users through changes to the AMPL language as described below. The main topics are:

To keep things simple, the following discussion assumes that information about an optimal solution is returned to AMPL by a solve command. If instead the solution command is used to restore a solution from a previously saved .sol file, then the discussion applies to the solve whose results are recorded in the file.

User-defined qualifiers. Users would be able to expand the variety of information associated with a variable, constraint, or objective, by defining new "qualifiers" or "suffixes" or "dot notation" -- the preferred term to be decided. If we use "suffix", for example, the we would have a suffix command to define new suffixes and would extend the current dot notation to read them:

suffix suffix-name type-phraseopt restriction-phraseopt ... ;

Defines a new suffix that may be used with variables, constraints, and objectives. (A further refinement could restrict use to only one or two component types.) The type-phrase and restriction-phrase limit the range of values that a suffixed entity can take; they have the same syntax and meaning as in parameter declarations.

variable-ref.suffix-name
constraint-ref.suffix-name
objective-ref.suffix-name

Refers to an auxiliary value associated with the named component and suffix. The suffix must be previously defined. A suffixed reference may be used in any way that a parameter may be used; the modeler may assign it a value through a let statement, may use its value in an expression or a display statement, and so forth.
A major purpose of these user-defined suffixes or qualifiers is to pass additional information to solvers. For instance, variable-ref.pri might denote the priorities of integer variables for use by a branch-and-bound code. Some mechanism would have to be supplied for insuring that these values were sent to MIP solvers, and preferably only to MIP solvers. Writing such values to the .nl file for all known suffixes could be very inefficient. Instead the user might indicate in a suffix's definition (or a later command) that the associated values should be sent with any solve. Possibly the most efficient arrangement, if two-way communication is available, would be for the solver to ask AMPL for the qualified values that it wants; under this arrangement the priorities would not be sent to an LP solver, because the solver wouldn't ask for them.

Solver-defined qualifiers. Solvers would also be able to define suffixes, for the purpose of passing additional information back to AMPL. Examples include the results of sensitivity and infeasibility analyses.

A suffix should be subject to the same rules regardless of whether the user or the solver has defined it. Thus, when a solver finds a qualifier to be already defined, it might simply overwrite the associated values with new ones -- without having to determine whether the qualifier was defined by the user or by a previous solve. This mode of operation would allow for status qualifiers (explained further below) that might be defined initially by the user or the solver, and that the solver would both read and write at every subsequent invocation.

Statuses for variables and constraints. The status of a variable or constraint in the basis is very important for some uses of the simplex method, particularly where a series of similar problems is solved by starting each problem at the optimal basis from the previous problem. This motivates a comprehensive scheme for representing such statuses in AMPL. The intention is to provide a standard way of handling most of the statuses recognized by current solvers, while being flexible enough to accommodate unanticipated status values that may be important to particular solvers or algorithms.

Three predefined suffixes are proposed for making reference to statuses of variables and constraints. Their use can be summarized as follows, where we denote by ref either a variable-ref or a constraint-ref:

ref.astatus

The "AMPL status" of a variable or constraint -- whether it is currently active, and why it was removed if not.

ref.sstatus

The "solver status" of a variable or constraint -- typically, its status in an optimal basis returned by the most recent solve.

ref.status

If ref.astatus is not '' (an empty string) then ref.astatus, otherwise ref.sstatus.

A component's .astatus can be regarded as being set by AMPL, while its .sstatus is set by the solver or user. The .astatus would distinguish which variables and constraints AMPL would send to the solver, whereas the .sstatus would be sent to the solver along with the variables and constraints and would be used to suggest a starting point for the optimizing algorithm. The .status suffix would provide an easy way to get a quick summary of the most relevant status information, by typing something as short as display Buy.status. (The same suffixes could apply also to objectives, though with somewhat different meanings -- objective and problem suffixes are discussed separately below.)

Values of .astatus supported by AMPL would be as follows:

.astatus Interpretation
Variables Constraints
'' '' Normal state (active in the current problem)
'fix' Fixed by a fix or problem command
'drop' Dropped by a drop or problem command
'pre' 'pre' Fixed or dropped by AMPL's presolve phase
'sub' 'sub' Eliminated by substitution, as the result of a defined variable or a constraint interpreted as a definition
'unused' Not appearing in any declared constraint or objective
A variable of type 'unused' does not appear in any constraint of any status -- even a dropped or presolved constraint. A variable that appears in no active constraint but that does appear in dropped or presolved constraints would have type 'pre'.

AMPL would also define the following standard values for .sstatus:

Index .sstatus Intended interpretation
0 'none' Not yet assigned any status
1 'bas' Basic
2 'sup' Superbasic
3 'low' Nonbasic <= (usually =) lower bound
4 'upp' Nonbasic >= (usually =) upper bound
5 'equ' Nonbasic at equal lower and upper bounds
6 'btw' Nonbasic between bounds
(including nonbasic "free" variables)
The .sstatus of a constraint would normally pertain to a slack or artificial variable that the solver associates with the constraint. The index number shown in the table is intended as a concise alternative to the .sstatus string, for use by AMPL in communicating with solvers; users would see the index number only in exceptional cases (discussed further below).

A new option sstatus_table would provide a concise summary of the .sstatus values in use. AMPL would initialize it to the following table in the form of a string:

	'\
	0   none   not assigned any status\
	1   bas    basic\
	2   sup    superbasic\
	3   low    nonbasic <= (normally =) lower bound\
	4   upp    nonbasic >= (normally =) upper bound\
	5   equ    nonbasic at equal lower and upper bounds\
	6   btw    nonbasic between bounds\
	'
To employ a different arrangement of statuses, a solver would overwrite this default sstatus_table with its own string representing a table; and it would return its own choice of integer index value (not necessarily limited to the range of 0-6) for each variable and constraint. (A user could do the same thing, though this would be less common.) The new sstatus_table would subsequently be used by AMPL to retrieve the status strings (like 'bas' and 'upp') that a command like display Buy.status would exhibit. The sstatus index values would thus normally continue to remain invisible to users. The only exception would occur if the solver were to return an index value that did not appear in the table.

For completeness a corresponding astatus_table would also be initialized. It would not be subject to change by the solver, however.

When creating a variable or constraint, AMPL would set its .astatus to '' and its .sstatus to 'none'. Statuses of 'none' would indicate to a solver that it should pick statuses on its own, such as by a built-in crash procedure. At each solve, AMPL's default action would be to send all statuses to any simplex-based solver, and to overwrite them with the (usually optimal) statuses returned by the solver. This behavior could be overridden by either of the following:

reset statuses;

Set all .astatus values back to '' and all .sstatus values back to 'none'.

option reset_initial_statuses i;

If i is 1 (the default), send all statuses to any simplex-based solver. If i is 0, do not send any statuses, forcing the solver to pick its own starting status values; but do not reset the existing status values immediately.

A variety of directives might also exist to tell the solver to ignore all statuses or to treat them in some special way. These would vary from one solver to the next.

Statuses for objectives and problems. For completeness and to handle certain special circumstances, both objective functions and named problems could be assigned statuses much like variables and constraints. The forms ref.astatus and ref.sstatus would be extended to let ref be a reference to an objective or problem, and the value of ref.status would be derived from them in the same way. (Routine checking of the outcome of a solver run would be handled by a few simple solver termination status parameters or options, as described in the next subsection below.)

Values of .astatus for objectives and problems would be much the same as the previously defined values for variables and constraints:

.astatus Interpretation
Objectives Problems
'' '' Current, by default or through the effects of a restore, objective or problem command
'drop' Not current, by default or through the effects of a drop or objective command
'non' Not current, by default or through the effects of a problem command
'pre' 'pre' Objective value determined by presolve
AMPL would also define the following standard .sstatus values, which are necessarily quite different from those for variables and constraints:

Index .sstatus Intended interpretation
0 'none' Not yet assigned any status
7 'min' Minimized by most recent solve
8 'max' Maximized by most recent solve
9 '+unbdd' Found to be unbounded above by most recent solve
10 '-unbdd' Found to be unbounded below by most recent solve
11 'infeas' Not optimized at most recent solve because no feasible solution could be found
Following a solve, the .sstatus of the current objective and of the current problem would be set the same. Although in principle one or the other would be redundant, in practice there are situations in which each each relates to the status much better than the other. Unboundedness has a strong relation to the objective, for instance, while infeasibility is not really an objective property at all and so might more naturally be treated as a problem status. As another example, if the named problems feature were not in use (so that only the default problem Initial were defined) it would make more sense to refer to the statuses of objectives; if there were several named problems having one objective each, on the other hand, it could be clearer to refer to the problem statuses. Finally, subsequent assignments or other commands would also have the power to change the objective or problem .sstatus that had been set by solve, so that the two might not always remain the same.

The sstatus_table option would be extended to work with objectives and problems. Index values and status strings for variables, constraints, objectives and problems would thus all come from the same "space" (and this is why index numbers 1 through 6 do not appear in the above table). The table could be changed as previously described to implement alternative status schemes for objectives. This is not expected to happen very often, but it might make sense for multi-objective methods such as parametric algorithms.

Solver termination statuses. In scripts that implement iterative schemes, it is often necessary to branch on the outcome of the most recent solve. For example, certain decomposition schemes update the master problem in one way when a subproblem has a finite optimum, but a different way when a subproblem is unbounded. This sort of solver "termination status" is different from the statuses of individual model components discussed above; it is simpler in routine use, but can be specialized to deal with a broader variety of termination states that vary considerably from one solver to the next. Our overall design goal is similar, however; we want to have a standard arrangement that works well with most solvers, while providing enough flexibility to accommodate the many different algorithms and implementations to which AMPL might be hooked.

Several predefined quantities would be provided to report the termination status associated with the most recent solve, in complementary ways:

solve_code

A numerical value representing the outcome of the most recent solve.

solve_status

A (preferably short) character string representing the outcome of the most recent solve.

solve_message

A (potentially long) character string describing the outcome of the most recent solve, such as
	'CPLEX 3.0: optimal integer solution; objective 235625\
	684 simplex iterations\
	126 branch-and-bound nodes'
show_solve_message

Number of lines of the solve_message string to be displayed. A value of zero suppresses the message entirely.

solve_status_table

A character string that provides a table relating solve_code values to solve_status strings.

These might be implemented as predefined parameters or as options (or as some combination of the two). As parameters they would be accessible globally; as options they might have different values for each named problem (or environment), a property which could conceivably be useful in an iterative scheme alternating between problems.

Before the first solve, solve_code would be -1; solve_status and solve_message would be empty strings. In cases where a solver terminates without returning solver status information -- because it is a version that predates this new feature, or has aborted without writing results -- solve_code would be set by AMPL to -1, and solve_status would be '?'.

The value of solve_status_table would be initialized to

	'\
	  0   solved\
	100   solved?\
	200   infeasible\
	300   unbounded\
	400   limit\
	500   failure'
In each line, the number would be the minimum solve_code to be associated with the indicated solve_status. The solve_code values 0 through 99 would be associated with a solve_status of 'solved', for instance, and 300-399 would be associated with 'unbounded'. Thus a script that needed to test for a finite optimum might use a simple and easily understood test like
	if solve_status = 'solved' then ...
The same thing could be achieved by testing solve_code < 100, but this is undesirably cryptic. Instead, the solve_code values are mainly intended to provide a finer distinction, if needed, between different situation covered by the same solve_status. For example, CPLEX's "optimal with unscaled infeasibilities" and "optimal integer solution within mipgap" would have separate nonzero solve_code values < 100. The initial value of solve_status_table shown above is intended to suggest an AMPL-standard framework for relating solve_code and solve_status; but solvers would have the option of returning an alternative table reflecting a different numbering scheme.

Exit codes. For use under operating systems like Unix that return an exit code from every process, AMPL would provide access to these values:

solve_exitcode

The operating system exit code returned by the most recent solve command.

shell_exitcode

The operating system exit code returned by the most recent shell command. (Unrelated to the solver's activity, but noted here for completeness.)

By Unix conventions, solve_exitcode will normally be 0, but will be nonzero if the solver faults or otherwise fails to terminate normally. If the solver returns exit code 0 but produces no .sol file, however, AMPL will invoke a special rule and reset solve_exitcode to 2^16; because the largest possible exit code returned from Unix is 2^16-1, this case can be distinguished from others.


Sets

Member extraction operators. All of the AMPL set operators and functions have sets as their return values. As a result, it is very hard to construct an expression for an individual member of a set that has a certain property. The following operators are intended to fill this gap:

arg min {indexing-expr} object-expr
arg max {indexing-expr} object-expr

Returns a member of the indexing-expr for which the minimum or maximum of the object-expr is achieved. In the case of ties, one arbitrarily selected member is returned. (Should there also be operators for determining the set of all members for which the min or max is achieved?)

member_of {indexing-expr}
unique_of {indexing-expr}

Returns a member of the specified set. If the specified set has more than one member, member_of chooses one arbitrarily, whereas unique_of signals an error. An empty specified set is an error for either operator.

True sets of sets. . . .



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 1 APRIL 1996 BY 4er.