General Algebraic Modeling System

GAMS
Developer(s) GAMS Development Corporation
Stable release 24.4.3 / April 2, 2015
Development status Active
Platform Cross-platform
Type Algebraic Modeling Language (AML)
License Proprietary
Website GAMS

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.

GAMS was the first algebraic modeling language (AML) 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, GUROBI, MOSEK, SNOPT, SULUM, and XPRESS.

GAMS allows the users to implement a sort of hybrid algorithms combining different solvers. Models are described in concise, human-readable algebraic statements. GAMS is among the most popular input formats for the NEOS Server for Optimization. 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 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 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 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 is used to provide a sample GAMS model.[1] 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.[2]

References

  1. R E Rosenthal (1988). "Chapter 2: A GAMS Tutorial". GAMS: A User's Guide. The Scientific Press, Redwood City, California.
  2. 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.

External links