AMPL
Encyclopedia
AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language
for describing and solving high-complexity problems for large-scale mathematical computation (i.e. large-scale optimization and scheduling-type problems).
It was developed by Robert Fourer
, David Gay and Brian Kernighan
at Bell Laboratories
.
AMPL supports dozens of solver
s, both open source and commercial, including CBC, CPLEX
, FortMP
, Gurobi
, MINOS, IPOPT
, SNOPT
and KNITRO
. Problems are passed to solvers as nl files
.
AMPL is used by more than a hundred corporate clients. It is also used by government agencies and academic institutions.
One particular advantage of AMPL is the similarity of its syntax to the mathematical notation of optimization
problems. This allows for a very concise and readable definition of problems in the domain of optimization
. Many modern solvers available on the NEOS server hosted at the Argonne National Laboratory
accept AMPL input. According to the NEOS statistics AMPL is the most popular format for representing mathematical programming problems.
and imperative
programming styles. Formulation of optimization models takes place through declarative language elements such as sets, scalar and multidimensional parameters, decision variables, objectives and constraints, which allow for a concise description of most problems in the domain of mathematical optimization.
Procedures and control flow
statements are available in AMPL for
To support re-use and simplify construction of large-scale optimization problems, AMPL allows separation of model and data.
AMPL supports a wide range of problem types, among them:
AMPL invokes a solver in a separate process which has the following advantages:
Interaction with the solver is done through a well-defined nl interface
.
, Mac OS X
and Windows.
The translator itself is a proprietary software currently maintained by AMPL Optimization LLC. However there exist several online services providing free modeling and solving facilities using AMPL. Also a free student version with limited functionality is available.
The AMPL Solver Library (ASL) which allows to read the nl files and provides the automatic differentiation functionality is open-source. It is used in many solvers to implement AMPL connection.
is used to provide a sample AMPL model. This problem finds the least cost shipping schedule that meets requirements at markets and supplies at factories.
Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.
set Plants;
set Markets;
# Capacity of plant p in cases
param Capacity{p in Plants};
# Demand at market m in cases
param Demand{m in Markets};
# Distance in thousands of miles
param Distance{Plants, Markets};
# Freight in dollars per case per thousand miles
param Freight;
# Transport cost in thousands of dollars per case
param TransportCost{p in Plants, m in Markets} =
Freight * Distance[p, m] / 1000;
# Shipment quantities in cases
var shipment{Plants, Markets} >= 0;
# Total transportation costs in thousands of dollars
minimize cost:
sum{p in Plants, m in Markets} TransportCost[p, m] * shipment[p, m];
# Observe supply limit at plant p
s.t. supply{p in Plants}: sum{m in Markets} shipment[p, m] <= Capacity[p];
# Satisfy demand at market m
s.t. demand{m in Markets}: sum{p in Plants} shipment[p, m] >= Demand[m];
data;
set Plants := seattle san-diego;
set Markets := new-york chicago topeka;
param Capacity :=
seattle 350
san-diego 600;
param Demand :=
new-york 325
chicago 300
topeka 275;
param Distance : new-york chicago topeka :=
seattle 2.5 1.7 1.8
san-diego 2.5 1.8 1.4;
param Freight := 90;
Algebraic modeling language
Algebraic Modeling Languages are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation...
for describing and solving high-complexity problems for large-scale mathematical computation (i.e. large-scale optimization and scheduling-type problems).
It was developed by Robert Fourer
Robert Fourer
Robert Fourer is a prominent scientist working in the area of operational research and management science. He is currently a professor at Industrial Engineering and Management Sciences Department of Northwestern University. Robert Fourer is recognized as being the designer of the popular modeling...
, David Gay and Brian Kernighan
Brian Kernighan
Brian Wilson Kernighan is a Canadian computer scientist who worked at Bell Labs alongside Unix creators Ken Thompson and Dennis Ritchie and contributed to the development of Unix. He is also coauthor of the AWK and AMPL programming languages. The 'K' of K&R C and the 'K' in AWK both stand for...
at Bell Laboratories
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
.
AMPL supports dozens of solver
Solver
A solver is a generic term indicating a piece of mathematical software, possibly in the form of a stand-alone computer program or as a software library, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculate their solution...
s, both open source and commercial, including CBC, CPLEX
CPLEX
IBM ILOG CPLEX Optimization Studio is an optimization software package. In 2004, the work on CPLEX earned the first ....
, FortMP
FortMP
FortMP is a software package for solving large-scale optimization problems. It solves linear programming problems, quadratic programming problems and mixed integer programming problems...
, Gurobi
Gurobi
Gurobi is a commercial software package for solving large-scale linear optimization, quadratic optimization, and mixed-integer optimization problems...
, MINOS, IPOPT
IPOPT
IPOPT, short for "Interior Point OPTimizer, pronounced I-P-Opt", is a software library for large scale nonlinear optimization of continuous systems. It is written in Fortran and C and is released under the EPL . IPOPT implements a primal-dual interior point method, and uses line searches based on...
, SNOPT
SNOPT
SNOPT is a software package for solving large-scale optimization problems written by Philip Gill, Walter Murray and Michael Saunders....
and KNITRO
KNITRO
KNITRO is a software package for solving large scale mathematical optimization problems. KNITRO is specialized for nonlinear optimization, but also solves linear programming problems, quadratic programming problems, and systems of nonlinear equations. The unknowns in these problems must be...
. Problems are passed to solvers as nl files
Nl (format)
nl is a file format for presenting and archiving mathematical programming problems. It supports linear and nonlinear optimization problems as well as complementarity problems , in discrete or continuous variables...
.
AMPL is used by more than a hundred corporate clients. It is also used by government agencies and academic institutions.
One particular advantage of AMPL is the similarity of its syntax to the mathematical notation of optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problems. This allows for a very concise and readable definition of problems in the domain of optimization
Mathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
. Many modern solvers available on the NEOS server hosted at the Argonne National Laboratory
Argonne National Laboratory
Argonne National Laboratory is the first science and engineering research national laboratory in the United States, receiving this designation on July 1, 1946. It is the largest national laboratory by size and scope in the Midwest...
accept AMPL input. According to the NEOS statistics AMPL is the most popular format for representing mathematical programming problems.
Features
AMPL features a mixture of declarativeDeclarative programming
In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
and imperative
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
programming styles. Formulation of optimization models takes place through declarative language elements such as sets, scalar and multidimensional parameters, decision variables, objectives and constraints, which allow for a concise description of most problems in the domain of mathematical optimization.
Procedures and control flow
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
statements are available in AMPL for
- the exchange of data with external data sources such as spreadsheetsSpreadsheetA spreadsheet is a computer application that simulates a paper accounting worksheet. It displays multiple cells usually in a two-dimensional matrix or grid consisting of rows and columns. Each cell contains alphanumeric text, numeric values or formulas...
, databasesDatabaseA database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
, XMLXMLExtensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....
and text files - data pre- and post-processing tasks around optimization models
- the construction of hybrid algorithms for problem types for which no direct efficient solvers are available.
To support re-use and simplify construction of large-scale optimization problems, AMPL allows separation of model and data.
AMPL supports a wide range of problem types, among them:
- Linear programmingLinear programmingLinear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
- Quadratic programmingQuadratic programmingQuadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....
- Nonlinear programmingNonlinear programmingIn mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
- Mixed-integer programming
- Mixed-integer quadratic programming with or without convexConvex functionIn mathematics, a real-valued function f defined on an interval is called convex if the graph of the function lies below the line segment joining any two points of the graph. Equivalently, a function is convex if its epigraph is a convex set...
quadratic constraints - Mixed-integer nonlinear programming
- Global optimizationGlobal optimizationGlobal optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.- General :The most common form is the minimization of one real-valued function...
- Semidefinite programmingSemidefinite programmingSemidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
problems with bilinear matrix inequalities - Complementarity problemsComplementarity theoryA complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing a function of two vector variables subject to certain requirements which include: that the inner product of the two variables must equal zero, i.e. = 0...
(MPECs) in discrete or continuous variables
AMPL invokes a solver in a separate process which has the following advantages:
- Solver crashes do not affect the interpreter
- 32-bit version of AMPL can be used with a 64-bit solver and vice versa
Interaction with the solver is done through a well-defined nl interface
Nl (format)
nl is a file format for presenting and archiving mathematical programming problems. It supports linear and nonlinear optimization problems as well as complementarity problems , in discrete or continuous variables...
.
Availability
AMPL is available for many popular 32- and 64-bit platforms including LinuxLinux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
and Windows.
The translator itself is a proprietary software currently maintained by AMPL Optimization LLC. However there exist several online services providing free modeling and solving facilities using AMPL. Also a free student version with limited functionality is available.
The AMPL Solver Library (ASL) which allows to read the nl files and provides the automatic differentiation functionality is open-source. It is used in many solvers to implement AMPL connection.
Status history
This table present significant steps in AMPL history.| Year | Highlights |
|---|---|
| 1985 | AMPL was designed and implemented |
| 1990 | Paper describing the AMPL modeling language was published in Management Science Management Science: A Journal of the Institute for Operations Research and the Management Sciences Management Science: A Journal of the Institute for Operations Research and the Management Sciences is a peer-reviewed academic journal covering the techniques of operations research and scientific approaches to problems of management, marketing, manufacturing, and related fields... |
| 1991 | AMPL supports nonlinear programming Nonlinear programming In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are... and automatic differentiation Automatic differentiation In mathematics and computer algebra, automatic differentiation , sometimes alternatively called algorithmic differentiation, is a set of techniques to numerically evaluate the derivative of a function specified by a computer program... |
| 1993 | Robert Fourer Robert Fourer Robert Fourer is a prominent scientist working in the area of operational research and management science. He is currently a professor at Industrial Engineering and Management Sciences Department of Northwestern University. Robert Fourer is recognized as being the designer of the popular modeling... , David Gay and Brian Kernighan Brian Kernighan Brian Wilson Kernighan is a Canadian computer scientist who worked at Bell Labs alongside Unix creators Ken Thompson and Dennis Ritchie and contributed to the development of Unix. He is also coauthor of the AWK and AMPL programming languages. The 'K' of K&R C and the 'K' in AWK both stand for... were awarded ORSA/CSTS Prize by the Operations Research Society of America, for writings on the design of mathematical programming systems and the AMPL modeling language |
| 1995 | Extensions for representing piecewise-linear and network structures |
| 1995 | Scripting constructs |
| 1997 | Enhanced support for nonlinear solvers |
| 1998 | AMPL supports complementarity problems Complementarity theory A complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing a function of two vector variables subject to certain requirements which include: that the inner product of the two variables must equal zero, i.e. = 0... |
| 2000 | Relational database and spreadsheet access |
| 2005 | AMPL Modeling Language Google group opened |
| 2008 | Kestrel: An AMPL Interface to the NEOS Server introduced |
A sample model
A transportation problem from George DantzigGeorge Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
is used to provide a sample AMPL model. This problem finds the least cost shipping schedule that meets requirements at markets and supplies at factories.
Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.
set Plants;
set Markets;
# Capacity of plant p in cases
param Capacity{p in Plants};
# Demand at market m in cases
param Demand{m in Markets};
# Distance in thousands of miles
param Distance{Plants, Markets};
# Freight in dollars per case per thousand miles
param Freight;
# Transport cost in thousands of dollars per case
param TransportCost{p in Plants, m in Markets} =
Freight * Distance[p, m] / 1000;
# Shipment quantities in cases
var shipment{Plants, Markets} >= 0;
# Total transportation costs in thousands of dollars
minimize cost:
sum{p in Plants, m in Markets} TransportCost[p, m] * shipment[p, m];
# Observe supply limit at plant p
s.t. supply{p in Plants}: sum{m in Markets} shipment[p, m] <= Capacity[p];
# Satisfy demand at market m
s.t. demand{m in Markets}: sum{p in Plants} shipment[p, m] >= Demand[m];
data;
set Plants := seattle san-diego;
set Markets := new-york chicago topeka;
param Capacity :=
seattle 350
san-diego 600;
param Demand :=
new-york 325
chicago 300
topeka 275;
param Distance : new-york chicago topeka :=
seattle 2.5 1.7 1.8
san-diego 2.5 1.8 1.4;
param Freight := 90;
See also
- AIMMSAIMMSAIMMS is a software system designed for modeling and solving large-scale optimization and scheduling-type problems....
- APMonitorAPMonitorAPMonitor, or "Advanced Process Monitor", is a modeling language for differential and algebraic equations. It is used for describing and solving representations of physical systems in the form of implicit DAE models. APMonitor is suited for large-scale problems and allows solutions of dynamic...
- GAMSGeneral Algebraic Modeling SystemThe General Algebraic Modeling System is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...
- General Algebraic Modeling System - GLPK - free open source system based on a subset of AMPL
- MPS (format)MPS (format)MPS is a file format for presenting and archiving linear programming and mixed integer programming problems.- Overview :...
- nl (format)Nl (format)nl is a file format for presenting and archiving mathematical programming problems. It supports linear and nonlinear optimization problems as well as complementarity problems , in discrete or continuous variables...
- OptimJOptimJOptimJ is an extension of the Java with language support for writing optimization models and abstractions for bulk data processing. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and...
- Java based modeling language - sol (format)Sol (format)sol is a file format for representing solutions of mathematical programming problems. It is often used in conjunction with the nl format to return solutions from the solvers...
External links
- AMPL home page
- Prof. Fourer's home page at Northwestern UniversityNorthwestern UniversityNorthwestern University is a private research university in Evanston and Chicago, Illinois, USA. Northwestern has eleven undergraduate, graduate, and professional schools offering 124 undergraduate degrees and 145 graduate and professional degrees....