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)



Comments or questions?
Write to or use our comment form.

 Return to the AMPL Papers & Reports page.

 Return to the AMPL home page.