Algebraic modeling language

Last updated

Algebraic modeling languages (AML) are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation (i.e. large scale optimization type problems). [1] One particular advantage of some algebraic modeling languages like AIMMS, [1] AMPL, [2] GAMS, [1] Gekko, MathProg, Mosel, [1] [3] and OPL is the similarity of their syntax to the mathematical notation of optimization problems. This allows for a very concise and readable definition of problems in the domain of optimization, which is supported by certain language elements like sets, indices, algebraic expressions, powerful sparse index and data handling variables, constraints with arbitrary names. The algebraic formulation of a model does not contain any hints how to process it.

Contents

An AML does not solve those problems directly; instead, it calls appropriate external algorithms to obtain a solution. These algorithms are called solvers and can handle certain kind of mathematical problems like:

Core elements

The core elements of an AML are:

Design principles

Most AML follow certain design principles:

Data driven model generation

Most modeling languages exploit the similarities between structured models and relational databases [4] by providing a database access layer, which enables the modelling system to directly access data from external data sources (e.g. these [5] table handlers for AMPL). With the refinement of analytic technologies applied to business processes, optimization models are becoming an integral part of decision support systems; optimization models can be structured and layered to represent and support complex business processes. In such applications, the multi-dimensional data structure typical of OLAP systems can be directly mapped to the optimization models and typical MDDB operations can be translated into aggregation and disaggregation operations on the underlying model [6]

History

Algebraic modelling languages find their roots in matrix-generator and report-writer programs (MGRW), developed in the late seventies. Some of these are MAGEN, MGRW (IBM), GAMMA.3, DATAFORM and MGG/RWG. These systems simplified the communication of problem instances to the solution algorithms and the generation of a readable report of the results.

An early matrix-generator for LP was developed around 1969 at the Mathematisch Centrum (now CWI), Amsterdam. [7] Its syntax was very close to the usual mathematical notation, using subscripts en sigmas. Input for the generator consisted of separate sections for the model and the data. It found users at universities and in industry. The main industrial user was the steel maker Hoogovens (now Tata Steel) where it was used for nearly 25 years.

A big step towards the modern modelling languages is found in UIMP, [8] where the structure of the mathematical programming models taken from real life is analyzed for the first time, to highlight the natural grouping of variables and constraints arising from such models. This led to data-structure features, which supported structured modelling; in this paradigm, all the input and output tables, together with the decision variables, are defined in terms of these structures, in a way comparable to the use of subscripts and sets. This is probably the single most notable feature common to all modern AMLs and enabled, in time, a separation between the model structure and its data, and a correspondence between the entities in an MP model and data in relational databases. So, a model could be finally instantiated and solved over different datasets, just by modifying its datasets.

The correspondence between modelling entities and relational data models, [4] made then possible to seamlessly generate model instances by fetching data from corporate databases. This feature accounts now for a lot of the usability of optimization in real life applications, and is supported by most well-known modelling languages.

While algebraic modelling languages were typically isolated, specialized and commercial languages, more recently algebraic modelling languages started to appear in the form of open-source, specialized libraries within a general-purpose language, like Gekko or Pyomo for Python or JuMP for the Julia language.

Notable AMLs

Specialized AMLs

AML Packages in Generic Programming Languages

Related Research Articles

<span class="mw-page-title-main">AMPL</span> Algebraic modeling language

AMPL is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing . It was developed by Robert Fourer, David Gay, and Brian Kernighan at Bell Laboratories. AMPL supports dozens of solvers, both open source and commercial software, including CBC, CPLEX, FortMP, MOSEK, MINOS, IPOPT, SNOPT, KNITRO, and LGO. Problems are passed to solvers as nl files. AMPL is used by more than 100 corporate clients, and by government agencies and academic institutions.

IBM ILOG CPLEX Optimization Studio is an optimization software package.

The general algebraic modeling system (GAMS) 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 build large maintainable models that can be adapted to new situations. The system is available for use on various computer platforms. Models are portable from one platform to another.

SNOPT, for Sparse Nonlinear OPTimizer, is a software package for solving large-scale nonlinear optimization problems written by Philip Gill, Walter Murray and Michael Saunders. SNOPT is mainly written in Fortran, but interfaces to C, C++, Python and MATLAB are available.

<span class="mw-page-title-main">COIN-OR</span>

Computational Infrastructure for Operations Research (COIN-OR), is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the operations research (OR) community with a peer-review process and an archive. Papers in operations research journals on mathematical theory often contain supporting numerical results from computational studies. The software implementations, models, and data used to produce the numerical results are typically not published. The status quo impeded researchers needing to reproduce computational results, make fair comparisons, and extend the state of the art.

The TOMLAB Optimization Environment is a modeling platform for solving applied optimization problems in MATLAB.

BARON is a computational system for solving non-convex optimization problems to global optimality. Purely continuous, purely integer, and mixed-integer nonlinear problems can be solved by the solver. Linear programming (LP), nonlinear programming (NLP), mixed integer programming (MIP), and mixed integer nonlinear programming (MINLP) are supported. In a comparison of different solvers, BARON solved the most benchmark problems and required the least amount of time per problem.

AIMMS is a prescriptive analytics software company with offices in the Netherlands, United States, and Singapore.

SAMPL, which stands for "Stochastic AMPL", is an algebraic modeling language resulting by expanding the well-known language AMPL with extended syntax and keywords. It is designed specifically for representing stochastic programming problems and, through recent extensions, problems with chance constraints, integrated chance constraints and robust optimization problems. It can generate the deterministic equivalent version of the instances, using all the solvers AMPL connects to, or generate an SMPS representation and use specialized decomposition based solvers, like FortSP.

The FICO Xpress optimizer is a commercial optimization solver for linear programming (LP), mixed integer linear programming (MILP), convex quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP) and their mixed integer counterparts. Xpress includes a general purpose non-linear solver, Xpress NonLinear, including a successive linear programming algorithm, and Artelys Knitro.

LINDO is a software package for linear programming, integer programming, nonlinear programming, stochastic programming and global optimization.

<span class="mw-page-title-main">Pyomo</span>

Pyomo is a collection of Python software packages for formulating optimization models.

<span class="mw-page-title-main">JuMP</span> Programming language

JuMP is an algebraic modeling language and a collection of supporting packages for mathematical optimization embedded in the Julia programming language. JuMP is used by companies, government agencies, academic institutions, software projects, and individuals to formulate and submit optimization problems to third‑party solvers. JuMP has been specifically applied to problems in the field of operations research.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

<span class="mw-page-title-main">NEOS Server</span>

The NEOS Server is an Internet-based client-server application that provides free access to a library of optimization solvers. Its library of solvers includes more than 60 commercial, free and open source solvers, which can be applied to mathematical optimization problems of more than 12 different types, including linear programming, integer programming and nonlinear optimization.

Algebraic modeling languages like AIMMS, AMPL, GAMS, MPL and others have been developed to facilitate the description of a problem in mathematical terms and to link the abstract formulation with data-management systems on the one hand and appropriate algorithms for solution on the other. Robust algorithms and modeling language interfaces have been developed for a large variety of mathematical programming problems such as linear programs (LPs), nonlinear programs (NPs), mixed integer programs (MIPs), mixed complementarity programs (MCPs) and others. Researchers are constantly updating the types of problems and algorithms that they wish to use to model in specific domain applications.

SolverStudio is a free Excel plug-in developed at the University of Auckland that supports optimization and simulation modelling in a spreadsheet using an algebraic modeling language. It is popular in education, the public sector and industry for optimization users because it uses industry-standard modelling languages and is faster than traditional Excel optimisation approaches.

The GEKKO Python package solves large-scale mixed-integer and differential algebraic equations with nonlinear programming solvers. Modes of operation include machine learning, data reconciliation, real-time optimization, dynamic simulation, and nonlinear model predictive control. In addition, the package solves Linear programming (LP), Quadratic programming (QP), Quadratically constrained quadratic program (QCQP), Nonlinear programming (NLP), Mixed integer programming (MIP), and Mixed integer linear programming (MILP). GEKKO is available in Python and installed with pip from PyPI of the Python Software Foundation.

References

  1. 1 2 3 4 Kallrath, Joseph (2004). Modeling Languages in Mathematical Optimization. Kluwer Academic Publishing. ISBN   978-1-4020-7547-6.
  2. ↑ Robert Fourer; David M. Gay; Brian W. Kernighan (1990). "A Modeling Language for Mathematical Programming". Management Science. 36 (5): 519–554–83. doi:10.1287/mnsc.36.5.519.
  3. ↑ Gueret, Christelle; Prins, Christian; Sevaux, Marc (2002). Applications of Optimization with Xpress-MP. Dash Optimization Limited. ISBN   0-9543503-0-8.
  4. 1 2 Gautam Mitra; Cormac Lucas; Shirley Moody; Bjarni Kristjansson (1995). "Sets and indices in linear programming modelling and their integration with relational data models". Computational Optimization and Applications. 4 (3): 262–283.
  5. ↑ Database and spreadsheet table handlers for AMPL
  6. ↑ Koutsoukis, N.; Mitra, G.; Lucas, C. (1999). "Adapting on-line analytical processing for decision modelling: the interaction of information and decision technologies". Decision Support Systems. 26 (1): 1–30. doi:10.1016/S0167-9236(99)00021-4 . Retrieved November 22, 2017.
  7. ↑ Jac. M. Anthonisse, An input system for linear programming problems, Statistica Neerlandica 24 (1970), 143-153.
  8. ↑ Francis D Ellison; Gautam Mitra (1982). "UIMP: user interface for mathematical programming" (PDF). ACM Transactions on Mathematical Software. 8 (3): 229–255. doi:10.1145/356004.356005. S2CID   3948431. Archived from the original (PDF) on 2014-01-18. Retrieved 2014-01-16.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.