AMPL Modeling Language
Papers and Reports:
Abstracts & Download Options
To view saved PDF files, download and install Adobe
Acrobat Reader.
To view the PDF files immediately, install in your browser the Acrobat
Reader Plug-In
that comes with the Acrobat Reader 3.0 download package.
More information is available from our download
guide.
David M. Gay, Hooking Your Solver to AMPL. Technical report,
Bell Laboratories, Murray Hill, NJ
(1993; revised 1994, 1997).
This report tells how to make solvers work with AMPL's solve
command. It describes an interface library, amplsolver.a,
whose source is available as individual
files or in a single gzipped tar file.
Examples include programs for listing LPs, automatic conversion to the
LP dual (shell-script as solver), solvers for various nonlinear
problems (with first and sometimes second derivatives computed by
automatic differentiation), and getting C or Fortran 77 for non-linear
constraints, objectives and their first derivatives. Drivers
for various well known linear, mixed-integer, and nonlinear solvers provide
more examples.
Robert Fourer and David M. Gay and Brian W. Kernighan, A Modeling
Language for Mathematical Programming. Management Science
36 (1990) 519-554.
Practical large-scale mathematical programming involves more than just
the application of an algorithm to minimize or maximize an objective function.
Before any optimizing routine can be invoked, considerable effort must
be expended to formulate the underlying model and to generate the requisite
computational data structures. AMPL is a new language designed to make
these steps easier and less error-prone. AMPL closely resembles the symbolic
algebraic notation that many modelers use to describe mathematical programs,
yet it is regular and formal enough to be processed by a computer system;
it is particularly notable for the generality of its syntax and for the
variety of its indexing operations. We have implemented a translator that
takes as input a linear AMPL model and associated data, and produces output
suitable for standard linear programming optimizers. Both the language
and the translator admit straightforward extensions to more general mathematical
programs that incorporate nonlinear expressions or discrete variables.
David M. Gay, Correctly Rounded Binary-Decimal and Decimal-Binary
Conversions. Numerical Analysis Manuscript 90-10, AT&T Bell Laboratories, Murray Hill,
NJ (1990).
This note discusses the main issues in performing correctly rounded
decimal-to-binary and binary-to-decimal conversions. It reviews recent
work by Clinger and by Steele and White on these conversions and describes
some efficiency enhancements. Computational experience with several kinds
of arithmetic suggests that the average computational cost for correct
rounding can be small for typical conversions. Source for conversion routines
that support this claim is available from netlib.
David M. Gay, Automatic Differentiation of Nonlinear AMPL
Models. In Automatic Differentiation of Algorithms:
Theory, Implementation, and Application, A. Griewank and G.
Corliss, eds., SIAM (Philadelphia, 1991) 61-73.
We describe favorable experience with automatic differentiation of mathematical
programming problems expressed in AMPL, a modeling language for mathematical
programming. Nonlinear expressions are translated to loop-free code, which
makes analytically correct gradients and Jacobians particularly easy to
compute -- static storage allocation suffices. The nonlinear expressions
may either be interpreted or, to gain some execution speed, converted to
Fortran or C.
Robert Fourer and David M. Gay, Experience with a Primal Presolve
Algorithm. In Large Scale
Optimization: State of the Art, W.W. Hager, D.W. Hearn and P.M.
Pardalos, eds., Kluwer Academic
Publishers (Dordrecht, 1994) 135-154.
Sometimes an optimization problem can be simplified to a form that is
faster to solve. Indeed, sometimes it is convenient to state a problem
in a way that admits some obvious simplifications, such as eliminating
fixed variables and removing constraints that become redundant after simple
bounds on the variables have been updated appropriately. Because of this
convenience, the AMPL modeling system includes a "presolver" that attempts
to simplify a problem before passing it to a solver. The current AMPL presolver
carries out all the primal simplifications described by Brearely et
al. in 1975. This paper describes AMPL's presolver, discusses reconstruction
of dual values for eliminated constraints, and presents some computational
results.
Robert Fourer and David M. Gay, Expressing Special Structures in
an Algebraic Modeling Language for Mathematical Programming.
ORSA Journal on Computing 7 (1995) 166-190.
A knowledge of the presence of certain special structures can be advantageous
in both the formulation and solution of linear programming problems. Thus
it is desirable that linear programming software offer the option of specifying
such structures explicitly. As a step in this direction, we describe extensions
to an algebraic modeling language that encompass piecewise-linear, network
and related structures. Our emphasis is on the modeling considerations
that motivate these extensions, and on the design issues that arise in
integrating these extensions with the general-purpose features of the language.
We observe that our extensions sometimes make models faster to translate
as well as to solve, and that they permit a "column-wise" formulation of
the constraints as an alternative to the "row-wise" formulation most often
associated with algebraic languages.
David M. Gay, More AD of Nonlinear AMPL Models: Computing Hessian
Information and
Exploiting Partial Separability.
In Computational Differentiation: Techniques, Applications, and
Tools, M. Berz, C. Bischof, G. Corliss and A. Griewank, eds., SIAM
(Philadelphia, 1996) 173-184.
We describe computational experience with automatic differentiation
of mathematical programming problems expressed in the modeling language
AMPL. Nonlinear expressions are translated to loop-free code, which makes
it easy to compute gradients and Jacobians by backward automatic differentiation.
The nonlinear expressions may be interpreted or, to gain some evaluation
speed at the cost of increased preparation time, converted to Fortran or
C. We have extended the interpretive scheme to evaluate Hessian (of Lagrangian)
times vector. Detecting partially separable structure (sums of terms, each
depending, perhaps after a linear transformation, on only a few variables)
is of independent interest, as some solvers exploit this structure. It
can be detected automatically by suitable "tree walks". Exploiting this
structure permits an AD computation of the entire Hessian matrix by accumulating
Hessian times vector computations for each term, and can lead to a much
faster computation of the Hessian than by computing the whole Hessian times
each unit vector.
David M. Gay, Automatically Finding and Exploiting Partially Separable
Structure in Nonlinear
Programming Problems. Bell Laboratories, Murray Hill,
NJ (1996).
Nonlinear programming problems often involve an objective and constraints
that are partially separable -- the sum of terms involving only a few variables
(perhaps after a linear change of variables). This paper discusses finding
and exploiting such structure in nonlinear programming problems expressed
symbolically in the AMPL modeling language. For some computations, such
as computing Hessians by backwards automatic differentiation, exploiting
partial separability can give significant speedups.
Robert Fourer, Extending a General-Purpose Algebraic Modeling Language
to Combinatorial
Optimization: A Logic Programming Approach. In D.L. Woodruff,
ed., Advances in Computational and
Stochastic Optimization, Logic Programming, and Heuristic Search:
Interfaces in Computer Science and Operations Research, Kluwer Academic
Publishers, Dordrecht, The Netherlands (1998) 31-74.
M.C. Ferris, R. Fourer and D.M. Gay, Expressing Complementarity Problems
in an Algebraic Modeling Language and Communicating Them to Solvers.
SIAM Journal on Optimization 9 (1999) 991-1009.
Diverse problems in optimization, engineering, and economics have natural
formulations in terms of complementarity conditions, which state (in their
simplest form) that either a certain nonnegative variable must be zero
or a corresponding inequality must hold with equality, or both. A variety
of algorithms have been devised for solving problems expressed in terms
of complementarity conditions. It is thus attractive to consider extending
algebraic modeling languages, which are widely used for sending ordinary
equations and inequality constraints to solvers, so that they can express
complementarity problems directly. We describe an extension to the AMPL
modeling language that can express the most common complementarity conditions
in a concise and flexible way, through the introduction of a single new
"complements" operator. We present details of an efficient implementation
that incorporates an augmented presolve phase to simplify complementarity
problems, and that converts complementarity conditions to a canonical form
convenient for solvers.
R. Fourer and D.M. Gay, Conveying Problem Structure from an Algebraic
Modeling Language to Optimization Algorithms. In Computing
Tools for Modeling, Optimization and Simulation: Interfaces in
Computer Science and Operations Research, M. Laguna and J.L.
González Velarde, eds., Kluwer Academic Publishers, Dordrecht,
The Netherlands (2000).
Optimization algorithms can exploit problem structures of various kinds,
such as sparsity of derivatives, complementarity conditions, block structure,
stochasticity, priorities for discrete variables, and information about
piecewise- linear terms. Moreover, some algorithms deduce additional structural
information that may help the modeler. We review and discuss some ways
of conveying structure, with examples from our designs for the AMPL modeling
language. We show in particular how "declared suffixes" provide a new and
useful way to express structure and acquire solution information.
David M. Gay, Symbolic-Algebraic Computations in a Modeling
Language for Mathematical Programming. Technical Report
00-3-02, Computing Sciences Research Center, Bell Laboratories, Murray
Hill, NJ (2000).
This paper was written for the proceedings of a seminar on
"Symbolic-Algebraic Methods and Verification Methods -- Theory and
Applications" held 21-26 November 1999 at Schloss Dagstuhl, Germany.
It gives an overview of symbolic and algebraic computations within the
AMPL processor and its associated solver interface library.
R. Fourer and D.M. Gay, Extending an Algebraic Modeling Language to Support
Constraint Programming. To appear in INFORMS Journal on Computing
14:4 (Fall 2002).
Although algebraic modeling languages are widely used in linear and
nonlinear programming applications, their use for combinatorial or
discrete optimization has largely been limited to developing integer
linear programming models for solution by general-purpose
branch-and-bound procedures. Yet much of a modeling language's
underlying structure for expressing integer programs is equally useful
for describing more general combinatorial optimization constructs.
Constraint programming solvers offer an alternative approach to
solving combinatorial optimization problems, in which natural
combinatorial constructs are addressed directly within the solution
procedure. Hence the growing popularity of constraint programming
motivates a variety of extensions to algebraic modeling languages for
the purpose of describing combinatorial problems and conveying them to
solvers.
We examine some of these language extensions along with the
significant changes in solver interface design that they require. In
particular, we describe how several useful combinatorial features have
been added to the AMPL modeling language and how AMPL's general-purpose
solver interface has been adapted accordingly. As an illustration of a
solver connection, we provide examples from an AMPL driver for ILOG
Solver.
Robert Fourer, David M. Gay and Brian W. Kernighan, Design Principles and
New Developments in the AMPL Modeling Language. In Modeling Languages in
Mathematical Optimization, J. Kallrath, ed., Kluwer Academic Publishers,
Dordrecht, The Netherlands (2003), chapter 7.
The design of the AMPL modeling language stresses naturalness of expressions,
generality of iterating over sets, separation of model and data, ease of data
manipulation, and automatic updating of derived values when fundamental
values change. We show how such principles have guided the addition of
database access, complementarity modeling, and other language features.
Robert Fourer and David M. Gay, Numerical Issues
and Influences in the Design of Algebraic Modeling Languages for
Optimization. In Proceedings of the 20th Biennial Conference on Numerical
Analysis, Dundee, Scotland, D.F. Griffiths and D.A. Watson, eds. Numerical
Analysis Report NA/217 (2003) 39-51.
Technical report in: PDF (93K)
Elizabeth D. Dolan, Robert Fourer, Jean-Pierre Goux, Todd S. Munson and Jason Sarich,
Kestrel: An Interface from Optimization Modeling Systems to the NEOS Server.
INFORMS Journal on Computing 20 (2008) 525-538.
The NEOS server provides access to a variety of optimization resources via the Internet. The new Kestrel
interface to the server enables local modeling environments to request NEOS optimization services and
retrieve the results for local visualization and analysis so that users have the same convenient access to remote
NEOS solvers as to those installed locally. Kestrel agents have been implemented for the AMPL and GAMS
modeling environments; these agents have been designed so that subproblems can be queued for execution and
later retrieval of results, making possible a rudimentary form of parallel processing.
Web version of published paper in:
PDF (1253K)
Using AMPL Under MS/DOS
Using AMPL Under Unix
ILOG AMPL CPLEX System Version 9.0
User's guide in: PDF (769K)
ILOG AMPL CPLEX System Version 10.0
User's guide in: PDF (823K)
ILOG AMPL CPLEX System Version 11.0
User's guide in: PDF (871K)
Using AMPL/MINOS
Using AMPL/OSL
Comments or questions?
Write to info@ampl.com
or use our comment form.
Return to the AMPL Papers & Reports
page.
Return to the AMPL home page.
LAST MODIFIED 2 JANUARY 2009 BY
4er.
|