General Algebraic Modeling System

Last updated
GAMS
Developer(s) GAMS Development Corporation
Stable release
40.3.0 / 16 September 2022(4 days ago) (2022-09-16) [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, CPLEX, DICOPT, MOSEK, SNOPT, SULUM, 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 force 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">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 criterion, from some set of available alternatives. Optimization problems of sorts 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.

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

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

Computational science, also known as scientific computing or scientific computation (SC), is a field in mathematics that uses advanced computing capabilities to understand and solve complex problems. It is an area of science that spans many disciplines, but at its core, it involves the development of models and simulations to understand natural systems.

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

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.

Advanced process monitor (APMonitor) is a modeling language for differential algebraic (DAE) equations. It is a free web-service or local server for solving representations of physical systems in the form of implicit DAE models. APMonitor is suited for large-scale problems and solves linear programming, integer programming, nonlinear programming, nonlinear mixed integer programming, dynamic simulation, moving horizon estimation, and nonlinear model predictive control. APMonitor does not solve the problems directly, but calls nonlinear programming solvers such as APOPT, BPOPT, IPOPT, MINOS, and SNOPT. The APMonitor API provides exact first and second derivatives of continuous functions to the solvers through automatic differentiation and in sparse matrix form.

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.

AIMMS is a prescriptive analytics software company with offices in the Netherlands, United States, China 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.

<span class="mw-page-title-main">HiGHS optimization solver</span> Numerical software

HiGHS is open-source software to solve linear programming (LP), mixed-integer programming (MIP), and convex quadratic programming (QP) models.

References

  1. ↑ "40 Distribution". gams.com. Retrieved 2022-09-16.
  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. ↑ https://www.gams.com/blog/article/news/phasing-out-of-32-bit-support-with-gams-30/?tx_news_pi1%5Bcontroller%5D=News&tx_news_pi1%5Baction%5D=detail&cHash=42ad8bd6cb83482b9820e0af6e263f03 [ dead link ]
  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–4. doi:10.1023/A:1008655831209.
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.