General Algebraic Modeling System
Encyclopedia
The General Algebraic Modeling System (GAMS) is a high-level modeling system for mathematical 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....

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

GAMS was the first algebraic modeling language
Algebraic modeling language
Algebraic Modeling Languages are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation...

 (AML) and is formally similar to commonly used fourth-generation programming language
Fourth-generation programming language
A fourth-generation programming language is a programming language or programming environment designed with a specific purpose in mind, such as the development of commercial business software. In the history of computer science, the 4GL followed the 3GL in an upward trend toward higher...

s. GAMS contains an integrated development environment
Integrated development environment
An integrated development environment is a software application that provides comprehensive facilities to computer programmers for software development...

 (IDE) and is connected to a group of third-party optimization 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. Among these 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 are BARON, COIN solvers, CONOPT, CPLEX, DICOPT, GUROBI, MOSEK
MOSEK
MOSEK is a software package for the solution of linear, mixed-integer linear, quadratic, mixed-integer quadratic, quadratically constraint, conic and convex nonlinear mathematical optimization problems. The emphasize in MOSEK is on solving large scale sparse problems. Particularly the...

, SNOPT, and XPRESS.

GAMS facilitates the users to implement a sort of hybrid algorithms combining different solvers in a seamless way. Models are described in concise algebraic statements which are easy to read, both for humans and machines. GAMS is among the most popular input formats for the NEOS Server for Optimization. Although initially designed for applications related to economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

 and management science, it has a large community of users from various backgrounds of engineering
Engineering
Engineering is the discipline, art, skill and profession of acquiring and applying scientific, mathematical, economic, social, and practical knowledge, in order to design and build structures, machines, devices, systems, materials and processes that safely realize improvements to the lives of...

 and science
Science
Science is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...

.

History

Initial research and development of GAMS was funded by the International Bank for Reconstruction and Development
International Bank for Reconstruction and Development
The International Bank for Reconstruction and Development is one of five institutions that compose the World Bank Group. The IBRD is an international organization whose original mission was to finance the reconstruction of nations devastated by World War II. Now, its mission has expanded to fight...

, usually referred to as The World Bank, through the Bank’s Research Committee (RPO 671-58, RPO 673-06) and carried out at the Development Research Center in Washington, D.C. Since 1987, R&D has been funded by GAMS Development Corporation.

The system was developed in close cooperation between mathematical economists who are an important group of GAMS users. The synergy between economics, computer science and operations research was the most important factor of success mail in the development of the system. Mathematical programming
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...

 and economics theory are closely intertwined. The Nobel Prize in Economics awarded to Leonid Kantorovich
Leonid Kantorovich
Leonid Vitaliyevich Kantorovich was a Soviet mathematician and economist, known for his theory and development of techniques for the optimal allocation of resources...

 and Tjalling Koopmans
Tjalling Koopmans
Tjalling Charles Koopmans was the joint winner, with Leonid Kantorovich, of the 1975 Nobel Memorial Prize in Economic Sciences....

 in 1975 for their “contribution to the theory of optimal allocation of resources” was really a prize in mathematical programming. Other Nobel laureates like Kenneth Arrow
Kenneth Arrow
Kenneth Joseph Arrow is an American economist and joint winner of the Nobel Memorial Prize in Economics with John Hicks in 1972. To date, he is the youngest person to have received this award, at 51....

 in 1972, Wassily Leontief
Wassily Leontief
Wassily Wassilyovich Leontief , was a Russian-American economist notable for his research on how changes in one economic sector may have an effect on other sectors. Leontief won the Nobel Committee's Nobel Memorial Prize in Economic Sciences in 1973, and three of his doctoral students have also...

 in 1973, and Harry Markowitz
Harry Markowitz
Harry Max Markowitz is an American economist and a recipient of the John von Neumann Theory Prize and the Nobel Memorial Prize in Economic Sciences....

 in 1990 are well known names in math programming. Another early example of this synergy is the use of LP in refining operations, which was started by Alan Manne, an economist, with his book on Scheduling of Petroleum Refinery Operations in 1956.

The origins of linear programming
Linear programming
Linear 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...

 algorithms stem from George Dantzig
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....

’s early work in the 1940s and 1950s. Computing technology and algorithmic theory had developed at a rapid pace. Thirty years later, it was possible to solve problems of practical size and complexity that allowed the user to test the economic theory on real life problems. The World Bank's research agenda in the 1970s and 1980s created the perfect environment to bring different disciplines together in order to apply mathematical programming to research and operational questions in Economic Development.

The focus and technical constraints of the development of modeling systems have changed in the last 30 years. The dominant constraints in the first phase were the computational limits of algorithms. Problem representation had to abide by algorithmic convenience, centralized expert groups managed large, expensive and long lasting projects and end users were effectively left out.
The second phase focused the model. This volume is about languages and systems supporting this stage. Applications are limited by modeling skill, project groups are much smaller and decentralized, the computational cost are low and the users are involved in the design of the application. Applications are designed to be independent of computing platforms and frequently operate in a client-server environment. The next step was to ameliorate the application as well as the optimization model. These are just one of many analytic tools that help making better decisions. User interfaces are built with off-the-shelf components and frequently change to adjust to evolving environments and new computing technologies.

Timeline

  • 1976 GAMS idea is presented at the ISMP Budapest
  • 1978 Phase I: GAMS supports linear programming
    Linear programming
    Linear 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...

    . Supported platforms: Mainframes and Unix Workstations
  • 1979 Phase II: GAMS 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...

    .
  • 1987 GAMS becomes a commercial product
  • 1988 First PC System (16 bit)
  • 1988 Alex Meeraus, the initiator of GAMS and founder of GAMS Development Corporation, is awarded INFORMS Computing Society Prize
  • 1990 32 bit Dos Extender
  • 1990 GAMS moves to Georgetown, Washington, D.C.
    Georgetown, Washington, D.C.
    Georgetown is a neighborhood located in northwest Washington, D.C., situated along the Potomac River. Founded in 1751, the port of Georgetown predated the establishment of the federal district and the City of Washington by 40 years...

  • 1991 Mixed Integer Non-Linear Programs capability (DICOPT)
  • 1994 GAMS supports mixed complementarity problem
    Mixed complementarity problem
    Mixed Complementarity Problem is a problem formulation in mathematical programming. Many well-known problem types are special cases of, or may be reduced to MCP...

    s
  • 1995 MPSGE language is added for CGE modeling
  • 1996 European branch opens in Germany
  • 1998 32 bit native Windows
  • 1998 Stochastic programming
    Stochastic programming
    Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within...

     capability (OSL/SE, DECIS)
  • 1999 Introduction of the GAMS Integrated development environment
    Integrated development environment
    An integrated development environment is a software application that provides comprehensive facilities to computer programmers for software development...

     (IDE)
  • 2000 GAMS World initiative started
  • 2001 GAMS Data Exchange (GDX) is introduced
  • 2002 GAMS is listed in OR/MS 50th Anniversary list of milestones
  • 2003 Conic programming is added
  • 2003 Global optimization
    Global optimization
    Global 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...

     in GAMS
  • 2004 Quality assurance initiative starts
  • 2004 Support for Quadratic Constrained programs
  • 2005 Support for 64 bit PC Operating systems
  • 2006 GAMS supports parallel grid computing
    Grid computing
    Grid computing is a term referring to the combination of computer resources from multiple administrative domains to reach a common goal. The grid can be thought of as a distributed system with non-interactive workloads that involve a large number of files...

  • 2007 GAMS supports open-source 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 from COIN-OR
    COIN-OR
    COIN-OR, which stands for Computational Infrastructure for Operations Research, is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the OR community with a peer-review process and an archive...

  • 2008 Support for 32 and 64 bit 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...

  • 2009 GAMS supports extended mathematical programs (EMP)
  • 2010 GAMS is awarded the company award of the German Society of Operations Research (GOR)

Background

The driving force behind the development of GAMS were the users of mathematical programming
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...

 who believed in 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....

 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
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

, finance
Finance
"Finance" is often defined simply as the management of money or “funds” management Modern finance, however, is a family of business activity that includes the origination, marketing, and management of cash and money surrogates through a variety of capital accounts, instruments, and markets created...

, and chemical engineering
Chemical engineering
Chemical engineering is the branch of engineering that deals with physical science , and life sciences with mathematics and economics, to the process of converting raw materials or chemicals into more useful or valuable forms...

, 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
World Bank
The World Bank is an international financial institution that provides loans to developing countries for capital programmes.The World Bank's official goal is the reduction of poverty...

. 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 sectoral 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 time and money did not allow. 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 matrix generators 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
TRW
TRW Inc. was an American corporation involved in a variety of businesses, mainly aerospace, automotive, and credit reporting. It was a pioneer in multiple fields including electronic components, integrated circuits, computers, software and systems engineering. TRW built many spacecraft,...

 developed a system called PROSE
Prose
Prose is the most typical form of written language, applying ordinary grammatical structure and natural flow of speech rather than rhythmic structure...

 that took the ideas of chemical engineers to compute point derivatives that were exact derivative
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...

s at a given point, and to embed them in a consistent, Fortran-style calculus modeling language
Modeling language
A modeling language is any artificial language that can be used to express information or knowledge or systems in a structure that is defined by a consistent set of rules...

. 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
Prose
Prose is the most typical form of written language, applying ordinary grammatical structure and natural flow of speech rather than rhythmic structure...

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

, GAMS learned that exploitation of sparsity was the key to solve large problems. Thus, the final piece of the puzzle was the use of sparse data structures.

A sample model

A transportation problem from George Dantzig
George 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 GAMS model. 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
Dantzig
- People :* Tobias Dantzig , mathematician from Latvia, father of George Dantzig* George Dantzig , American mathematician who introduced the simplex algorithm* David van Dantzig , Dutch mathematician...

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

See also

  • AIMMS
    AIMMS
    AIMMS is a software system designed for modeling and solving large-scale optimization and scheduling-type problems....

  • Algebraic modeling language
    Algebraic modeling language
    Algebraic Modeling Languages are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation...

  • AMPL
    AMPL
    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 AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...

     - a popular modeling language for large-scale linear, mixed integer and nonlinear optimization
  • APMonitor
    APMonitor
    APMonitor, 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...

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

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

    - a Java-based modeling language for optimization

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK