1. Introduction Stub.nl files 2. Linear Problems Rowwise treatment Columnwise treatment Optional ASL components Example: linrc, a ``solver'' for rowwise printing Affine objectives: linear plus a constant Example: shell script as solver for the dual LP 3. Integer and Nonlinear Problems Ordering of variables and constraints Priorities for integer variables Reading nonlinear problems Evaluating nonlinear functions Example: nonlinear minimization subject to simple bounds Example: nonlinear least squares subject to simple bounds Partially separable structure Fortran variants Nonlinear test problems 4. Advanced Interface Topics Writing the stub.sol file Locating evaluation errors Userdefined functions Checking for quadratic programs: example of a DAG walk C or Fortran 77 for a problem instance Writing stub.nl files for debugging Use with MATLAB 5. Utility Routines and Interface Conventions AMPL flag Conveying solver options Printing and Stderr Formatting the optimal value and other numbers More examples Multiple problems and multiple threads Appendix A: Changes from Earlier Versions
The AMPL modeling system [5] lets you express constrained optimization problems in an algebraic notation close to conventional mathematics. AMPL's solve command causes AMPL to instantiate the current problem, send it to a solver, and attempt to read a solution computed by the solver (for use in subsequent commands, e.g., to print values computed from the solution). This technical report tells how to arrange for your own solver to work with AMPL's solve command. See the AMPL Web site at
http://www.ampl.com/ampl/
AMPL runs solvers as separate programs and communicates with them by writing and reading files. The files have names of the form stub.suffix; AMPL usually chooses the stub automatically, but one can specify the stub explicitly with AMPL's write command. Before invoking a solver, AMPL normally writes a file named stub.nl. This file contains a description of the problem to be solved. AMPL invokes the solver with two arguments, the stub and a string whose first five characters are AMPL, and expects the solver to write a file named stub.sol containing a termination message and the solution it has found.
Most linear programming solvers are prepared to read socalled MPS files, which are described, e.g., in chapter 9 of [14]; see also the linear programming FAQ at
http://www.mcs.anl.gov/home/otc/Guide/faq/
In the following, we assume you are familiar with C and that your solver is callable from C or C++. If your solver is written in some other language, it is probably callable from C, though the details are likely to be systemdependent. If your solver is written in Fortran 77, you can make the details systemindependent by running your Fortran source through the FortrantoC converter f2c [4]. For more information about f2c, including how to get Postscript for [4], send the electronicmail message
send readme from f2c
ftp://netlib.belllabs.com/netlib/f2c/readme.gz
Netlib's AMPL/solver interface directory,
http://netlib.belllabs.com/netlib/ampl/solvers/
Material for many of the examples discussed here is in solvers/examples; you will find it helpful to look at these files while reading this report. You can get both them and source for the solvers directory from netlib. For more details, send the electronicmail message
send readme from ampl/solvers
ftp://netlib.belllabs.com/netlib/ampl/solvers/readme.gz
http://netlib.belllabs.com/netlib/bib/compression.html
ftp://netlib.belllabs.com/netlib/ampl
binary get solvers.tar
http://netlib.belllabs.com/netlib/ampl/
In this report, we use ANSI/ISO C syntax and header files, but the interface source and header files are designed to allow use with C++ and K&R C compilers as well. (To activate the older syntax, compile with DKR_headers, i.e., with KR_headers #defined.)
For simplicity, we first consider linear programming (LP) problems.
Solvers can view an LP as the problem of finding
to
where
and
Again for simplicity, the initial examples of reading linear problems
simply print out the data
(A,
b,
c,
d,
l,
u)
and perhaps the primal and dual initial guesses.
The first example, solvers/examples/lin1.c, just prints the data. (On a Unix system, type
make lin1
#include "asl.h"
ASL *asl;
The main routine in lin1.c expects to see one commandline argument: the stub of file stub.nl written by AMPL, as explained above. After checking that it has a commandline argument, the main routine allocates an ASL via
asl = ASL_alloc(ASL_read_f);
FILE *jac0dim(char *stub, fint stub_len);
jac0dim(stub, stublen)
jac0dim_ASL(asl, stub, stublen) .
For use with Fortran programs,
jac0dim
assumes
stub
is
stublen
characters long and is not nullterminated. After trimming
any trailing blanks from
stub
(by allocating space for
ASL
field
filename,
i.e.,
asl>i.filename_,
and copying
stub
there as the
stub),
jac0dim
reads the first part of
stub.nl
and records some numbers in
*asl,
as summarized in Table 1. If
stub.nl
does not exist,
jac0dim
by default prints an error message and stops execution (but setting
return_nofile
to a nonzero value changes this behavior: see
Table 2
below).
To read the rest of stub.nl, lin1.c invokes f_read. As discussed more fully below and shown in Table 6, several routines are available for reading stub.nl, one for each possible argument to ASL_alloc; f_read just reads linear problems, complaining and aborting execution if it sees any nonlinearities. F_read allocates memory as necessary by calling Malloc, which appears in most of our examples; Malloc calls malloc and aborts execution if malloc returns 0. (The reason for breaking the reading of stub.nl into two steps will be seen in more detail below: sometimes it is convenient to modify the behavior of the stub.nl reader here f_read by allocating problemdependent arrays before calling it.)
AMPL may transmit several objectives. The linear part of each is contained in a list of ograd structures (declared in asl.h; note that asl.h declares
typedef struct ograd ograd;
c = (real *)Malloc(n_var*sizeof(real)); for(i = 0; i < n_var; i++) if (n_obj)
Among the arrays allocated in lin1.c's call on f_read are an array of alternating lower and upper variable bounds called LUv and an array of alternating lower and upper constraint bounds called LUrhs. For the present exercise, these arrays could have been declared to be arrays of
struct LU_bounds { real lower, upper; };
printf("\nVariable\tlower bound\tupper bound\tcost\n"); for(i = 0; i < n_var; i++)
For lin1.c, the linear part of each constraint is conveyed in the same way as the linear part of the objective, but by a list of cgrad structures. These structures have one more field,
int goff;
Most LP solvers expect a ``columnwise'' representation of the constraint matrix A of (LP). By allocating some arrays (and setting pointers to them in the ASL structure), you can make the stub.nl reader give you such a representation, with subscripts optionally adjusted for the convenience of Fortran. The next examples illustrate this. Their source files are lin2.c and lin3.c in solvers/examples, and you can say
make lin2 lin3
The beginning of lin2.c differs from that of lin1.c in that lin2.c executes
A_vals = (real *)Malloc(nzc*sizeof(real));
Table 2 lists some
ASL
(i.e., asl>i...._)
components that you can optionally set and summarizes their effects.
It is easy to extend the above examples to show the variable and constraint names used in an AMPL model. When writing stub.nl, AMPL optionally stores these names in files stub.col and stub.row, as described in §A13.6 (page 333) of the AMPL book [5]. As an illustration, example file linrc.c is a variant of lin1.c that shows these names if they are available and tells how to get them if they are not. Among other embellishments, linrc.c uses the value of environment variable display_width to decide when to break lines. (By the way, $display_width denotes this value, and other environmentvariable values are denoted analogously.) Say
make linrc
linrc '?'
ampl: option solver linrc, linrc_auxfiles rc; solve;
ampl: solve >foo;
http://www.ampl.com/ampl/NEW/examine.html
Adding a constant to a linear objective makes the problem no harder to solve. (The constant may be stated explicitly in the original model formulation, or may arise when AMPL's presolve phase deduces the values of some variables and removes them from the problem that the solver sees.) For algorithmic purposes, the solver can ignore the constant, but it should take the constant into account when reporting objective values. Some solvers, such as MINOS, make explicit provision for adding a constant to an otherwise linear objective. For other solvers, such as CPLEX^{®} and OSL, we must resort to introducing a new variable that is either fixed by its bounds (CPLEX) or by a new constraint (OSL). Function objconst, with apparent signature
real objconst(int objno)
Sometimes it is convenient for the solver AMPL invokes to be a shell script that runs several programs, e.g., to transform stub.nl to the form the underlying solver expects and to create the stub.sol that AMPL expects. As an illustration, solvers/examples contains a shell script called dminos that arranges for minos to solve the dual of an LP. Why is this interesting? Well, sometimes the dual of an LP is much easier to solve than the original (``primal'') LP. Because of this, several of the LP solvers whose interface source appears in subdirectories of ampl/solvers, such as cplex and osl, have provision for solving the dual LP. (This is not to be confused with using the dual simplex algorithm, which might be applied to either the primal or the dual problem.) Because minos is meant primarily for solving nonlinear problems (whose duals are more elaborate than the dual of an LP), minos currently lacks provision for solving dual LPs directly. At the cost of some extra overhead (over converting an LP to its dual within minos) and loss of flexibility (of deciding whether to solve the primal or the dual LP after looking at the problem), the dminos shell script provides an easy way to see how minos would behave on the dual of an LP. And one can use dminos to feed dual LPs to other LP solvers that understand stub.nl files: it's just a matter of setting the shell variable $dsolver (which is discussed below).
The dminos shell script relies on a program called dualconv whose source, dualconv.c, also appears in solvers/examples. Dualconv reads the stub.nl for an LP and writes a stub.nl (or stub.mps) for the dual of the LP. Dualconv also writes a stub.duw file that it can use in a subsequent invocation to translate the stub.sol file from solving the dual LP into the primal stub.sol that AMPL expects. Thus dualconv is really two programs packaged, for convenience, as one. (Type
make dualconv
dualconv '?'
Here is a simplified version of the dminos shell script (for Unix systems):
#!/bin/sh dualconv $1 minos $1 AMPL dualconv u $1 rm $1.duw
dualconv $1
minos $1 AMPL
dualconv u $1
rm $1.duw
The simplified dminos script above does not clean up properly if it is interrupted, e.g., if you turn off your terminal while it is running. Here is the more robust solvers/examples/dminos:
#!/bin/sh # Script that uses dualconv to feed a dual LP problem to $dsolver dsolver=${dsolverminos} trap "rm f $1.duw" 1 2 3 4 13 dualconv $1 case $? in 0) rc=$? rm f $1.duw exit $rc
dsolver=${dsolverminos}
trap "rm f $1.duw" 1 2 3 4 13
dualconv $1
case $? in 0)
rc=$?
rm f $1.duw
exit $rc
To write stub.sol files, dualconv calls write_sol, which appears in most of the subsequent examples and is documented below in the section on ``Writing the stub.sol file''.
When writing
stub.nl,
AMPL orders the variables as shown in Tables 3 and 4 and the constraints
as shown in Table 5. These tables also give expressions for
how many entities are in each category.
Table 4 applies to AMPL versions >= 19930630;
nlvb
= 1
signifies earlier versions.
For all versions, the first
nlvc
variables appear nonlinearly in at least one constraint.
If
nlvo
>
nlvc,
the first
nlvc
variables may or may not appear nonlinearly in an objective,
but the next
nlvo

nlvc
variables do appear nonlinearly
in at least one objective. Otherwise all of the first
nlvo
variables appear nonlinearly in an objective. ``Linear arcs''
are linear variables declared with an
arc
declaration in the AMPL model, and ``nonlinear network'' constraints are
nonlinear constraints introduced with a
node
declaration.
Some integer programming solvers let you assign branch priorities to the variables. Interface routine mip_pri provides a simple way to get branch priorities from $mip_priorities. It complains if stub.col is not available. Otherwise, it looks in $mip_priorities for variable names followed by integer priorities (separated by white space). See the comments in solvers/mip_pri.c for more details. For examples, see solvers/cplex/cplex.c and solvers/osl/osl.c.
It is convenient to build data structures for computing derivatives while reading a stub.nl file, and amplsolver.a provides several ways of doing this, to suit the needs of various solvers. Table 6 summarizes the available stub.nl readers and the kinds of nonlinear information they make available. They are to be used with ASL_alloc invocations of the form
asl = ASL_alloc(ASLtype);
int reader(FILE *nl, int flags);
Specific evaluation routines are associated with each stub.nl reader. For simplicity, the readers supply pointers to the specific routines in the ASL structure, and asl.h provides macros to simplify calling the specific routines. The macros provide the following apparent signatures and functionality; many of them appear in the examples that follow. Reader pfg_read is mainly for debugging and does not provide any evaluation routines; it is used in solver ``v8'', discussed below. Reader fgh_read is mainly for debugging of Hessianvector products, but does provide all of the routines described below except for the full Hessian computations (which would have to be done with n_var Hessianvector products). Reader pfgh_read generally provides more efficient Hessian computations and provides the full complement of evaluation routines. If you invoke an ``unavailable'' routine, an error message is printed and execution is aborted.
Many of the evaluation routines have final argument nerror of type fint*. This argument controls what happens if the routine detects an error. If nerror is null or points to a negative value, an error message is printed and, unless err_jmp1 (i.e., asl>i.err_jmp1_) is nonzero, execution is aborted. (You can set err_jmp1 much the same way that obj1val_ASL and obj1grd_ASL in file objval.c set err_jmp to gain control after the error message is printed.) If nerror points to a nonnegative value, *nerror is set to 0 if no error occurs and to a positive value otherwise.
real objval(int nobj, real *X, fint *nerror)
void objgrd(int nobj, real *X, real *G, fint *nerror)
void conval(real *X, real *R, fint *nerror)
void jacval(real *X, real *J, fint *nerror)
real conival(int ncon, real *X, fint *nerror)
void congrd(int ncon, real *X, real *G, fint *nerror)
void hvcomp(real *HV, real *P, int nobj, real *OW, real *Y)
void duthes(real *H, int nobj, real *OW, real *Y)
void fullhes(real *H, fint LH, int nobj, real *OW, real *Y)
integer LH double precision H(LH,*)
fint sphsetup(int nobj, int ow, int y, int uptri)
void sphes(real *H, int nobj, real *OW, real *Y)
void xknown(real *X)
void xunknown(void)
void conscale(int i, real s, fint *nerror)
void lagscale(real sigma, fint *nerror)
void varscale(int i, real s, fint *nerror)
Our first nonlinear example ignores any constraints other than bounds on the variables and assumes there is one objective to be minimized. This example involves the PORT solver dmngb, which amounts to subroutine SUMSL of [6] with added logic for bounds on the variables (as described in [7]). If need be, you can get (Fortran 77) source for dmngb by asking netlib to
send dmngb from port
Most of mng1.c is specific to dmngb. For example, dmngb expects subroutine parameters calcf and calcg for evaluating the objective function and its gradient. Interface routines objval and objgrd actually evaluate the objective and its gradient; the calcf and calcg defined in mng1.c simply adjust the calling sequences appropriately. The calling sequences for objval and objgrd were shown above.
Since dmngb is prepared to deal with evaluation errors (which it learns about when argument *NF to calcf and calcg is set to 0), calcf and calcg pass a pointer to 0 for nerror.
The main routine in mng1.c is called MAIN__ rather than main because it is meant to be used with an f2ccompatible Fortran library. (A C main appears in this Fortran library and arranges to catch certain signals and flush buffers. The main makes its arguments argc and argv available in the external cells xargc and xargv.)
Recall that when AMPL invokes a solver, it passes two arguments: the stub and an argument that starts with AMPL. Thus mng1.c gets the stub from the first commandline argument. Before passing it to jac0dim, mng1.c calls ASL_alloc(ASL_read_fg) to make an ASL structure available. ASL_alloc stores its return value in the global cell cur_ASL. Since mng1.c starts with
#include "asl.h" #define asl cur_ASL
The invocation of dmngb directly accesses two ASL pointers: X0 and LUv (i.e., asl>i.X0_ and asl>i.LUv_). X0 contains the initial guess (if any) specified in the AMPL model, and LUv is an array of lower and upper bounds on the variables. Before calling fg_read to read the rest of stub.nl, mng1.c asks fg_read to save X0 (if an initial guess is provided in the AMPL model or data, and otherwise to initialize X0 to zeros) by executing
X0 = (real *)Malloc(n_var*sizeof(real));
After invoking dmngb, mng1.c writes a termination message into the scratch array buf and passes it, along with the computed solution, to interface routine write_sol, discussed later, which writes the termination message and solution to file stub.sol in the form that AMPL expects to read them.
The use of Cextern in the declaration
typedef void (*U_fp)(void); Cextern int dmngb_(fint *n, real *d, real *x, real *b, U_fp calcf, U_fp calcg, fint *iv, fint *liv, fint *lv, real *v, fint *uiparm, real *urparm, U_fp ufparm);
The previous example dealt only with a nonlinear objective and bounds on the variables. The next example deals only with nonlinear equality constraints and bounds on the variables. It minimizes an implicit objective: the sum of squares of the errors in the constraints. The underlying solver, dn2gb, again comes from the PORT subroutine library; it is a variant of the unconstrained nonlinear leastsquares solver NL2SOL [2,3] that enforces simple bound constraints on the variables. If need be, you can get (Fortran) source for dn2gb by asking netlib to
send dn2gb from port
Source for this example is solvers/examples/nl21.c. Much like mng1.c, it starts with
#include "asl.h" #define asl cur_ASL
for(Re = R + *N; R < Re; UR += 2)
MAIN__ invokes the interface routine dense_j() to tell jacval that it wants a dense Jacobian matrix, i.e., a full matrix with explicit zeros for partial derivatives that are always zero. If necessary, dense_j adjusts the goff components of the cgrad structures and tells jacval to zero its J array before computing derivatives.
Many optimization problems involve a
partially separable
objective function, one that has the form
in which
is an
matrix with a small number
of rows [11,12].
Partially separable structure is of interest because it
permits better Hessian approximations or more efficient
Hessian computations. Many partially separable problems
exhibit a more detailed structure, which the authors of
LANCELOT
[1]
call ``group partially separable structure'':
where
is a unary operator.
Using techniques described in [10],
the
stub.nl
readers
pfg_read
and
pfgh_read
discern this latter structure automatically, and the
Hessian computations that
pfgh_read
makes available exploit it. Some solvers, such as
LANCELOT
and
VE08
[17],
want to see partially separable structure. Driving such solvers involves
a fair amount of solverspecific coding. Directory
solvers/examples
has drivers for two variants of
VE08:
ve08
ignores
whereas
v8
exploits
partially separable structure, using reader
pfg_read.
Directory
solvers/lancelot
contains source for
lancelot,
a solver based on
LANCELOT
that uses reader
pfgh_read.
Fortran variants fmng1.f and fnl21.f of mng1.c and nl21.c appear in solvers/examples; the makefile has rules to make programs fmng1 and fnl21 from them. Both invoke interface routines jacdim_ and jacinc_. The former allocates an ASL structure (with ASL_alloc(ASL_read_fg)) and reads a stub.nl file with fg_read, and the latter provides arrays of lower and upper constraint bounds, the initial guess, the Jacobian incidence matrix (which neither example uses), and (in the last variable passed to jacinc_) the value Infinity that represents oo. These routines have Fortran signatures
subroutine jacdim(stub, M, N, NO, NZ, MXROW, MXCOL) character*(*) stub integer M, N, NO, NZ, MXROW, MXCOL subroutine jacinc(M, N, NZ, JP, JI, X, L, U, Lrhs, Urhs, Inf) integer M, N, NZ, JP integer*2 JI double precision X(N), L(N), U(N), Lrhs(M), Urhs(M), Inf
The Fortran examples call Fortran variants of some of the nonlinear evaluation routines. Table 8 summarizes the currently available Fortran variants; others (e.g., for evaluating Hessian information) could be made available easily if demand were to warrant them. In Table 8, Fortran notation appears under ``Fortran variant''; the corresponding C routines have an underscore appended to their names and are declared in asl.h. The Fortran routines shown in Table 8 operate on the ASL structure at which cur_ASL points. Thus, without help from a C routine to adjust cur_ASL, they only deal with one problem at a time. After solving a problem and executing
call delprb
Some nonlinear AMPL models appear in directory
http://netlib.belllabs.com/netlib/ampl/models/nlmodels/
ftp://netlib.belllabs.com/netlib/ampl/models/nlmodels.tar
Interface routine write_sol returns the computed solution and a termination message to AMPL. This routine has apparent prototype
void write_sol(char *msg, real *x, real *y, Option_Info *oi);
If the routines in amplsolver.a detect an error during evaluation of a nonlinear expression, they look to see if stub.row (or, if evaluation of a ``defined variable'' was in progress, stub.fix) is available. If so, they use it to report the name of the constraint, objective, or defined variable that they were trying to evaluate. Otherwise they simply report the number of the constraint, objective, or variable in question (first one = 1). This is why the Student Edition of AMPL provides the default value RF for $minos_auxfiles. See the discussion of auxiliary files in §A13.6 of the AMPL book [5]; as documented in netlib's ``changes from ampl'', i.e.,
ftp://netlib.belllabs.com/netlib/ampl/changes.gz
An AMPL model may involve userdefined functions. If invocations of such functions involve variables, the solver must be able to evaluate the functions. You can tell your solver about the relevant functions by supplying a suitable funcadd function, rather than loading a dummy funcadd compiled from solvers/funcadd0.c. (To facilitate dynamic linking, which will be documented separately, this dummy funcadd no longer appears in amplsolver.a.) Include file funcadd.h gives funcadd's prototype:
void funcadd(AmplExports *ae);
void (*Addfunc)(char *name, real (*f)(Arglist*), int type,
AmplExports *ae
void addfunc(char *name, real (*f)(Arglist*), int type,
When a userdefined function is invoked,
it always has a single argument,
al,
which points to an
arglist
structure. This structure is designed so the same
userdefined function can be linked with AMPL (in case
AMPL needs to evaluate the function); the final
arglist
components are relevant only to AMPL. The function receives
al>n
arguments,
al>nr
of which are numeric; for 0 <= i < al>n,
If
al>derivs
is nonzero, the function must store its first partial derivative
with respect to
al>ra[i]
in
al>derivs[i],
and if
al>hes
is nonzero (which is possible only with
fgh_read
or
pfgh_read),
it must also store the upper triangle of its
Hessian matrix in
al>hes,
i.e., for
0 <=
i
<=
j
<
al>nr
it must store its second partial with respect to
al>ra[i]
and
al>ra[j]
in
If the function does any printing, it should initially say
AmplExports *ae = al>AE;
See solvers/funcadd.c for an example funcadd. The mng, mnh and nl2 examples mentioned below illustrate linking with this funcadd.
Some solvers make special provision for handling quadratic
programming problems, which have the form
in which
For example, CPLEX, LOQO, and OSL handle
general positivedefinite
Q
matrices, and the old KORBX
solver handled
positivedefinite diagonal
Q
matrices (``convex separable quadratic
programs''). These solvers assume the explicit ½ shown
above in the (QP) objective.
AMPL considers quadratic forms, such as the objective in (QP), to be nonlinear expressions. To determine whether a given objective function is a quadratic form, it is necessary to walk the directed acyclic graph (DAG) that represents the (possibly) nonlinear part of the objective. Function nqpcheck (in solvers/nqpcheck.c) illustrates such a walk. It is meant to be used with a variant of fg_read called qp_read, which has the same prototype as the other stub.nl readers, and which changes some function pointers to integers for the convenience of nqpcheck. After qp_read returns, you can invoke nqpcheck one or more times, but you may not call objval, conval, etc., until you have called qp_opify, with apparent prototype
void qp_opify(void)
fint nqpcheck(int co, fint **rowqp, fint **colqp, real **delsqp);
Usually it is most convenient to call qpcheck rather than nqpcheck; qpcheck has apparent prototype
fint qpcheck(fint **rowqp, fint **colqp, real **delsqp);
Drivers solvers/cplex/cplex.c and solvers/osl/osl.c call qp_read and qpcheck, and file solvers/examples/qtest.c illustrates invocations of nqpcheck and qp_opify.
More elaborate DAG walks are useful in other situations. For example, the nlc program discussed next does a more detailed DAG walk.
Occasionally it may be convenient to turn a stub.nl file into C or Fortran. This can lead to faster function and gradient computations but, because of the added compile and link times, many evaluations are usually necessary before any net time is saved. Program nlc converts stub.nl into C or Fortran code for evaluating objectives, constraints, and their derivatives. You can get source for nlc by asking netlib to
send all from ampl/solvers/nlc
ftp://netlib.belllabs.com/netlib/ampl/solvers/nlc.tar
real feval_(fint *nobj, fint *needfg, real *x, real *g); void ceval_(fint *needfg, real *x, real *c, real *J);
Bounds are conveyed in
boundc_
as follows:
boundc_[0]
is the value passed for oo;
boundc_ + 1
is an array of lower and upper bounds on the variables, and
boundc_ + 2*n_var + 1
is an array of lower and upper bounds on the constraint bodies.
The initial guess appears in
x0comn_.
The f commandline option causes nlc to emit Fortran 77 equivalents of feval_ and ceval_; they correspond to the Fortran signatures
double precision function feval(nobj, needfg, x, g) integer nobj,needfg double precision x(*), g(*)
subroutine ceval(needfg, x, c, J) integer needfg double precision x(*), c(*), J(*)
common /funcom/ nvar, nobj, ncon, nzc, densej, colrow integer nvar, nobj, ncon, nzc, densej, colrow(*) common /boundc/ bounds double precision bounds(*) common /x0comn/ x0 double precision x0(*)
Commandline option 1 causes nlc to emit variants feval0_ and ceval0_ of feval_ and ceval_ that omit gradient computations. They have signatures
real feval0_(fint *nobj, real *x); void ceval0_(real *x, real *c);
You can use AMPL's write command or its o commandline flag to get a stub.nl (and any other needed auxiliary files) for use in debugging. Normally AMPL writes a binaryformat stub.nl, which corresponds to a commandline obstub argument. Such files are faster to read and write, but slightly less convenient for debugging, in that write_sol notes the format of stub.nl (binary or ASCII by looking at binary_nl) and writes stub.sol in the same format. To get ASCII format files, either issue an AMPL write command of the form
write gstub;
With AMPL versions >= 19970214, binary stub.nl files written on one machine with binary IEEEarithmetic can be read on any other.
It is easy to use AMPL with MATLAB with the help of a mex file that reads stub.nl files, writes stub.sol files, and provides function, gradient, and Hessian values. Example file amplfunc.c is source for an amplfunc.mex that looks at its left and righthand sides to determine what it should do and works as follows:
[x,bl,bu,v,cl,cu] = amplfunc('stub')
x = primal initial guess, bl = lower bounds on the primal variables, bu = upper bounds on the primal variables, v = dual initial guess (often a vector of zeros), cl = lower bounds on constraint bodies, and cu = upper bounds on constraint bodies.
[f,c] = amplfunc(x,0)
f = value of first objective at x and c = values of constraint bodies at x.
[g,Jac] = amplfunc(x,1)
g = gradient of first objective at x and Jac = Jacobian matrix of constraints at x.
W = amplfunc(Y)
[] = amplfunc(msg,x,v)
msg = termination message (a string), x = optimal primal variables, and v = optimal dual variables.
It is often convenient to use
.m
files to massage problems to a desired form. To illustrate this, the
examples
directory offers the following files (which are simplified forms
of files used in joint work with Michael Overton and Margaret Wright):
init.m,
which expects variable
pname
to have been assigned a
stub
(a string value), reads
stub.nl,
and puts the problem into the form
For simplicity, the example
init.m
assumes that the initial
x
yields
d(x)
> 0. A more elaborate version of
init.m
is required in general.
evalf.m,
which provides
[f,c,d] = evalf(x).
evalg.m,
which provides
[g,A,B] = evalg(x),
where
A = c'(x)
and
B = d'(x)
are the Jacobian matrices of
c
and
d.
evalw.m,
which computes the Lagrangian Hessian,
W = evalw(y,z),
in which
y
and
z
are vectors of Lagrange multipliers for the constraints
and
respectively.
enewt.m,
which uses
evalf.m,
evalg.m
and
evalw.m
in a simple, nonrobust nonlinear interiorpoint iteration that is meant
mainly to illustrate setting up and solving an extended system involving
the constraint Jacobian and Lagrangian Hessian matrices.
savesol.m,
which writes file
stub.sol
to permit reading a computed solution into an AMPL session.
hs100.amp,
an AMPL model for test problem 100 of Hock and Schittkowski [13].
hs100.nl,
derived from
hs100.amp.
To solve this problem, start MATLAB and type
pname = 'hs100'; init enewt savesol
Amplfunc.c provides dense Jacobian matrices and Lagrangian Hessians; spamfunc.c is a variant that provides sparse Jacobian matrices and Lagrangian Hessians. To see an example of using spamfunc, change all occurrences of ``amplfunc'' to ``spamfunc'' in the .m files.
Sometimes it is convenient for a solver to behave differently when invoked by AMPL than when invoked ``standalone''. This is why AMPL passes a string that starts with AMPL as the second commandline argument when it invokes a solver. As a simple example, nl21.c turns dn2gb's default printing off when it sees AMPL, and it only invokes write_sol when this flag is present.
Most solvers have knobs (tolerances, switches, algorithmic options, etc.) that one might want to turn. An AMPL convention is that appending _options to the name of a solver gives the name of an environment variable (AMPL option) in which the solver looks for knob settings. Thus a solver named wondersol would take knob settings from $wondersol_options (the value of environment variable wondersol_options). For interactive use, it's usually a good idea for a solver to print its name and perhaps version number when it starts, and to echo nondefault knob settings to confirm that they've been seen and accepted. It's also conventional for the msg argument to write_sol to start with the solver's name and perhaps version number. Since AMPL echoes the write_sol's msg argument when it reads the solution, a minor problem arises: if there are no nondefault knob settings, an interactive user would see the solver's name printed twice in a row. To keep this from happening, you can set need_nl (i.e., asl>i.need_nl_) to a positive value; this causes write_sol to insert that many backspace characters at the beginning of stub.sol. Usually this is done as follows: initially you execute, e.g.,
need_nl = printf("wondersol 3.2: ");
Conventionally, $solver_options may contain keywords and namevalue pairs, separated by white space (spaces, tabs, newlines), with case ignored in names and keywords. For namevalue pairs, the usual practice is to allow white space or an = (equality) sign, optionally surrounded by white space, between the name and the value. For debugging, it is sometimes convenient to pass keywords and namevalue pairs on the solver's command line, rather than setting $solver_options appropriately. The usual practice is to look first in $solver_options, then at the commandline arguments, so the latter take precedence.
Interface routines getstub, getopts, and getstops facilitate the above conventions. They have apparent prototypes
char *getstub (char ***pargv, Option_Info *oi); int getopts (char **argv, Option_Info *oi); char *getstops(char ***pargv, Option_Info *oi);
include "getstub.h"
include "asl.h"
char *sname; /* invocation name of solver */ char *bsname; /* solver name in startup "banner" */ char *opname; /* name of solver_options environment var */ keyword *keywds; /* key words */ int n_keywds; /* number of key words */ int want_funcadd; /* whether funcadd will be called */ char *version; /* for v and Ver_key_ASL() */ char **usage; /* solverspecific usage message */ Solver_KW_func *kwf; /* solverspecific keyword function */ Fileeq_func *feq; /* for n=filename */ keyword *options; /* commandline options (with ) before stub */ int n_options; /* number of options */
static Option_Info Oinfo = { ... };
Function getstub looks in *pargv for the stub, possibly preceded by commandline options that start with ``''; getstub provides a small default set of commandline options, which may be augmented or overridden by names in oi>options. Among the default commandline options are '?', which requests a usage summary that reports oi>sname as the invocation name of the solver; '=', which summarizes possible keyword values; v, which reports the versions of the solver (supplied by oi>version) and of amplsolver.a (which is available in cell ASLdate_ASL, declared in asl.h); and, if oi>want_funcadd is nonzero, u, which lists the available userdefined functions; userdefined functions are discussed in their own section above. If it finds a stub, getstub checks whether the next argument begins with AMPL and sets amplflag accordingly; if so, it executes
if (oi>bsname) need_nl = printf("%s: ", oi>bsname);
Function getopts looks first in $solver_options, then at the command line for keywords and optional values; oi>opname provides the name of the solver_options environment variable. Getopts is separate from getstub because sometimes it is convenient to call jac0dim, do some storage allocation, or make other arrangements before processing the keywords. For cases where no such separation is useful, function getstops calls getstub and getopts and returns the stub, complaining and exiting if none is found.
Keywords are conveyed in keyword structures declared in getstub.h:
struct keyword { char *name; Kwfunc *kf; void *info; char *desc; };
oi>option_echo &= ~ASL_OI_echothis;
oi>option_echo &= ~ASL_OI_echo;
For convenience, amplsolver.a provides a variety of keywordprocessing functions. Table 9 summarizes these functions; their prototypes appear in getstub.h, which also provides a macro, nkeywds, for computing the n_keywds field of an Option_Info structure from a keyword declaration of the form
static keyword keywds[] = { ... };
static Option_Info Oinfo = { "tn", "TN", "tn_options", keywds, nkeywds, 1 };
Some solvers, such as minos and npsol, have their own routines for parsing keyword phrases. For such a solver you can initialize oi>kwf with a pointer to a function that invokes it; if getopts sees a keyword that does not appear in oi>keywds, it changes any underscore characters to blanks and passes the resulting phrase to oi>kwf. Some solvers, such as minos, also need a way to associate Fortran unit numbers with file names; oi>feq (if not null) points to a function for doing this. See ampl/solvers/minos/m55.c for an example that uses all 12 of the Option_Info fields shown above, including oi>kwf and oi>feq.
Many solvers allow
outlev
to appear in $solver_options. Generally,
outlev = 0
means ``no printed output'', and larger integers
cause the solver to print more information while they work.
Another common keyword is
maxit,
whose value bounds the number of iterations allowed.
For standalone invocations (those without
AMPL),
solvers commonly recognize
wantsol=n,
where
n
is the sum of
A special keyword function,
WS_val,
processes
wantsol
assignments, which are interpreted by
write_sol.
Strings
WS_desc_ASL
and
WSu_desc_ASL
provide descriptions of
wantsol
for constrained and unconstrained solvers, respectively,
and appear in many of the sample drivers available from
netlib.
To facilitate using AMPL and solvers in some contexts, such as Microsoft Windows (in various versions), it is best to route all printing through printf and fprintf; a separate report will provide more details. Because of this, and because some systems furnish a sprintf that does not give the return value specified by ANSI/ISO C, amplsolver.a provides suitable versions of printf, fprintf, sprintf, vfprintf and vsprintf that function as specified by ANSI/ISO C, except that they do not recognize the L qualifier (for long double), and, as in AMPL, they provide some extensions: they turn %.0g and %.0G into the shortest decimal string that rounds to the number being converted, and they allow negative precisions for %f. These provisions apply to systems with IEEE, VAX, or IBM mainframe arithmetic, and solvers/makefile explains how to use the system's printf routines on other systems.
On systems where it is convenient to redirect stderr, it is best to write error messages to stderr. Unfortunately, redirecting stderr is inconvenient on some systems (e.g., Microsoft systems with the usual Microsoft shells). To promote portability among systems, amplsolver.a provides access to
extern FILE *Stderr,
An AMPL convention is that solvers should report (in the msg argument to write_sol) the final objective value to $objective_precision significant figures. Interface routines g_fmtop and obj_prec facilitate this. They have apparent prototypes
int g_fmtop(char *buf, double v); int obj_prec(void);
Two relatives of g_fmtop that are also in amplsolver.a are
int g_fmt( char *buf, double v); int g_fmtp(char *buf, double v, int prec);
If they find an exponent field necessary, both g_fmtop and its relatives delimit it with the current value of
extern char g_fmt_E;
By default, g_fmtop and its relatives only supply a decimal point if it is followed by a digit, but if you set
extern int g_fmt_decpt;
Some examples illustrating the above points appear in solvers/examples. One such example is tnmain.c, a wrapper for Stephen Nash's LMQN and LMQNBC [16,15], which solve unconstrained and simply bounded minimization problems by a truncated Newton algorithm. Since tnmain.c calls getstub, the resulting solver, tn, explains its usage when invoked
tn '?'
tn '='
For another example, files mng.c and nl2.c are for solvers called mng and nl2, which are more elaborate variants of the mng1 and nl21 considered above (source files mng1.c and nl21.c). Both use auxiliary files keywds.c, rvmsg.c and rvmsg.h to turn the knobs summarized in [9] and pass a more elaborate msg to write_sol. Their linkage, in solvers/examples/makefile, also illustrates adding userdefined functions, which we will discuss shortly. Unlike mng1, mng checks to see if the objective is to be maximized and internally negates it if so.
File mnh.c is a variant of mng.c that supplies the analytic Hessian matrix computed by duthes to solver mnh, based on PORT routine dmnhb. For maximum likelihood problems, it is sometimes appropriate to use the Hessian at the solution as an estimate of the variancecovariance matrix; mnh offers the option of computing standarddeviation estimates for the optimal solution from this variancecovariance matrix estimate. Specify stddev=1 in $mnh_options or on the command line to exercise this option, or specify stddev_file=filename to have this information written to a file.
Various subdirectories of
http://netlib.belllabs.com/netlib/ampl/solvers/
ftp://netlib.belllabs.com/netlib/ampl/solvers/README.gz
It is possible to have several problems in memory at once, each with its own ASL pointer. To free the memory associated with a particular ASL pointer asl, execute
ASL_free(&asl);
Independent threads may operate on independent ASL structures when amplsolver.a is compiled with MULTIPLE_THREADS #defined. In this case, it is necessary to suitably #define ACQUIRE_DTOA_LOCK(n) and FREE_DTOA_LOCK(n) to provide exclusive access to a few short critical regions (with distinct values of n); the recommended procedure is first to create arith.h by saying ``make arith.h'', then to add
#define MULTIPLE_THREADS
Thanks go to Bob Fourer, Brian Kernighan, Bob Vanderbei, and Margaret Wright for helpful comments. REFERENCES
Some changes are cosmetic, such as updates to netlib addresses
to reflect the breakup of AT&T. Others are intended to make the
AMPL/solver interface library more flexible and useful. Changes
introduced in 1997 include:
New facilities for computing second derivatives
in nonlinear problems.
Facilities for addressing several problems independently.
Adjustments to the external name space: most names contributed
by the AMPL/solver interface library now end with
_ASL
(for AMPL/Solver Library).
New facilities for processing commandline arguments and
solver_options
environment variables, meant to unify behavior among solvers
and simplify writing solver interfaces.
Changes to the
#include
files:
jacdim.h
is gone, replaced for most purposes by
asl.h
or
getstub.h
(which includes
asl.h).
In the
stub.nl
readers, logic to recognize some of the ``suffix'' arrays that AMPL will
soon be able to write. Use of these arrays will be documented in
a revised version of this report.
Function
funcadd,
which one provides to make userdefined functions available,
now takes an argument, and the
addfunc
routine it calls has an additional argument; for more details,
see the section on
``Userdefined functions''
above.
To allow for dynamic linking of userdefined functions, the dummy
funcadd
routine in source file
funcadd0.c
no longer appears in amplsolver.a; if desired, it must be linked explicitly.
Header file asl.h provides #defines that permit older solver interface routines to be used with only a few changes. Often it suffices to change ``jacdim.h'' to ``asl.h'' and to add
#define asl cur_ASL