General algebraic modeling system

Last updated
GAMS
Developer(s) GAMS Development Corporation
Stable release
47.2.0 / 1 July 2024(2 months ago) (2024-07-01) [1]
Platform Cross-platform
Type Algebraic Modeling Language (AML)
License Proprietary
Website www.gams.com

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.

Contents

GAMS was the first algebraic modeling language (AML) [2] and is formally similar to commonly used fourth-generation programming languages. GAMS contains an integrated development environment (IDE) and is connected to a group of third-party optimization solvers. Among these solvers are BARON, COIN-OR solvers, CONOPT, COPT Cardinal Optimizer, CPLEX, DICOPT, IPOPT, MOSEK, SNOPT, and XPRESS.

GAMS allows the users to implement a sort of hybrid algorithm combining different solvers. Models are described in concise, human-readable algebraic statements. GAMS is among the most popular input formats for the NEOS Server.[ citation needed ] Although initially designed for applications related to economics and management science, it has a community of users from various backgrounds of engineering and science.

Timeline

Background

The driving forces behind the development of GAMS were the users of mathematical programming who believed in optimization as a powerful and elegant framework for solving real life problems in science and engineering. At the same time, these users were frustrated by high costs, skill requirements, and an overall low reliability of applying optimization tools. Most of the system's initiatives and support for new development arose in response to problems in the fields of economics, finance, and chemical engineering, since these disciplines view and understand the world as a mathematical program.

GAMS’s impetus for development arose from the frustrating experience of a large economic modeling group at the World Bank. In hindsight, one may call it a historic accident that in the 1970s mathematical economists and statisticians were assembled to address problems of development. They used the best techniques available at that time to solve multi-sector economy-wide models and large simulation and optimization models in agriculture, steel, fertilizer, power, water use, and other sectors. Although the group produced impressive research, initial success was difficult to reproduce outside their well functioning research environment. The existing techniques to construct, manipulate, and solve such models required several manual, time-consuming, and error-prone translations into different, problem-specific representations required by each solution method. During seminar presentations, modelers had to defend the existing versions of their models, sometimes quite irrationally, because of time and money considerations. Their models just could not be moved to other environments, because special programming knowledge was needed, and data formats and solution methods were not portable.

The idea of an algebraic approach to represent, manipulate, and solve large-scale mathematical models fused old and new paradigms into a consistent and computationally tractable system. Using generator matrices for linear programs revealed the importance of naming rows and columns in a consistent manner. The connection to the emerging relational data model became evident. Experience using traditional programming languages to manage those name spaces naturally lead one to think in terms of sets and tuples, and this led to the relational data model.

Combining multi-dimensional algebraic notation with the relational data model was the obvious answer. Compiler writing techniques were by now widespread, and languages like GAMS could be implemented relatively quickly. However, translating this rigorous mathematical representation into the algorithm-specific format required the computation of partial derivatives on very large systems. In the 1970s, TRW developed a system called PROSE that took the ideas of chemical engineers to compute point derivatives that were exact derivatives at a given point, and to embed them in a consistent, Fortran-style calculus modeling language. The resulting system allowed the user to use automatically generated exact first and second order derivatives. This was a pioneering system and an important demonstration of a concept. However, PROSE had a number of shortcomings: it could not handle large systems, problem representation was tied to an array-type data structure that required address calculations, and the system did not provide access to state-of-the art solution methods. From linear programming, GAMS learned that exploitation of sparsity was key to solving large problems. Thus, the final piece of the puzzle was the use of sparse data structures.

Lines starting with an * in column one are treated as comments. [5] : 32 

A sample model

A transportation problem from George Dantzig is used to provide a sample GAMS model. [6] This model is part of the model library which contains many more complete GAMS models. This problem finds a 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.

 Sets       i   canning plants   / seattle, san-diego /       j   markets          / new-york, Chicago, topeka / ;  Parameters       a(i)  capacity of plant i in cases         /    seattle     350              san-diego   600  /       b(j)  demand at market j in cases         /    new-york    325              Chicago     300              topeka      275  / ;  Table d(i,j)  distance in thousands of miles                    new-york       Chicago      topeka      seattle          2.5           1.7          1.8      san-diego        2.5           1.8          1.4  ;  Scalar f  freight in dollars per case per thousand miles  /90/ ;  Parameter c(i,j)  transport cost in thousands of dollars per case ;            c(i,j) = f * d(i,j) / 1000 ;  Variables       x(i,j)  shipment quantities in cases       z       total transportation costs in thousands of dollars ;  Positive Variable x ;  Equations       cost        define objective function       supply(i)   observe supply limit at plant i       demand(j)   satisfy demand at market j ;  cost ..        z  =e=  sum((i,j), c(i,j)*x(i,j)) ;  supply(i) ..   sum(j, x(i,j))  =l=  a(i) ;  demand(j) ..   sum(i, x(i,j))  =g=  b(j) ;  Model transport /all/ ;  Solve transport using lp minimizing z ;  Display x.l, x.m ;

Subsystems

The Mathematical Programming System for General Equilibrium analysis (MPSGE) is a language used for formulating and solving Arrow–Debreu economic equilibrium models and exists as a subsystem within GAMS. [7]

See also

Related Research Articles

<span class="mw-page-title-main">Numerical analysis</span> Study of algorithms using numerical approximation

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. It is the study of numerical methods that attempt to find approximate solutions of problems rather than the exact ones. Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences like economics, medicine, business and even the arts. Current growth in computing power has enabled the use of more complex numerical analysis, providing detailed and realistic mathematical models in science and engineering. Examples of numerical analysis include: ordinary differential equations as found in celestial mechanics, numerical linear algebra in data analysis, and stochastic differential equations and Markov chains for simulating living cells in medicine and biology.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Basic Linear Algebra Subprograms (BLAS) is a specification that prescribes a set of low-level routines for performing common linear algebra operations such as vector addition, scalar multiplication, dot products, linear combinations, and matrix multiplication. They are the de facto standard low-level routines for linear algebra libraries; the routines have bindings for both C and Fortran. Although the BLAS specification is general, BLAS implementations are often optimized for speed on a particular machine, so using them can bring substantial performance benefits. BLAS implementations will take advantage of special floating point hardware such as vector registers or SIMD instructions.

<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.

<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.

Algebraic modeling languages (AML) are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation. One particular advantage of some algebraic modeling languages like AIMMS, AMPL, GAMS, Gekko, MathProg, Mosel, 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.

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

ADMB or AD Model Builder is a free and open source software suite for non-linear statistical modeling. It was created by David Fournier and now being developed by the ADMB Project, a creation of the non-profit ADMB Foundation. The "AD" in AD Model Builder refers to the automatic differentiation capabilities that come from the AUTODIF Library, a C++ language extension also created by David Fournier, which implements reverse mode automatic differentiation. A related software package, ADMB-RE, provides additional support for modeling random effects.

OptimJ is an extension for Java with language support for writing optimization models and abstractions for bulk data processing. The extensions and the proprietary product implementing the extensions were developed by Ateji which went out of business in September 2011. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and application programming tools, and bringing software engineering techniques such as object-orientation and modern IDE support to optimization experts.

<span class="mw-page-title-main">Zuse Institute Berlin</span> Research institute for applied mathematics and computer science in Berlin, Germany

The Zuse Institute Berlin is a research institute for applied mathematics and computer science on the campus of Freie Universität Berlin in Dahlem, Berlin, Germany.

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.

PROSE was the mathematical 4GL virtual machine that established the holistic modeling paradigm known as Synthetic Calculus. A successor to the SLANG/CUE simulation and optimization language developed at TRW Systems, it was introduced in 1974 on Control Data supercomputers. It was the first commercial language to employ automatic differentiation (AD), which was optimized to loop in the instruction-stack of the CDC 6600 CPU.

MINOS is a Fortran software package for solving linear and nonlinear mathematical optimization problems. MINOS may be used for linear programming, quadratic programming, and more general objective functions and constraints, and for finding a feasible point for a set of linear or nonlinear equalities and inequalities.

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

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

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

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.

References

  1. ↑ "47 Distribution". gams.com. Retrieved 2024-07-03.
  2. ↑ Kallrath, Josef (2004). Modeling Languages in Mathematical Optimization (First ed.). Norwell, USA: Kluer Academic Publishers. p. 241. ISBN   978-1-4613-7945-4.
  3. ↑ Toward a General Algebraic Modelling System (PDF). IX. International Symposium on Mathematical Programming. Budapest, Hungary. 1976. p. 185.
  4. ↑ "Phasing out of 32-bit support with GAMS 30".
  5. ↑ Rosenthal, Richard E (2007). GAMS — A user's guide (PDF). Washington, DC, USA: GAMS Development Corporation. Retrieved 2020-12-20.
  6. ↑ R E Rosenthal (1988). "Chapter 2: A GAMS Tutorial". GAMS: A User's Guide. The Scientific Press, Redwood City, California.
  7. ↑ Rutherford, T. F. (1999). "Applied General Equilibrium Modeling with MPSGE as a GAMS Subsystem: An Overview of the Modeling Framework and Syntax". Computational Economics. 14 (1/2): 1–4. doi:10.1023/A:1008655831209. S2CID   60954697.


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.