Model and Solve Statements

Introduction

This chapter brings together all the concepts discussed in previous chapters by explaining how to specify a model and solve it.

The Model Statement

The model statement is used to collect equations into groups and to label them so that they can be solved. The simplest form of the model statement uses the keyword all: the model consists of all equations declared before the model statement is entered. For most simple applications this is all the user needs to know about the model statement.

The Syntax

In general, the syntax for a model declaration in GAMS is as follows:

model[s] model_name [text] [/ all | eqn_name {, eqn_name} /]
       {,model_name [text] [/ all | eqn_name {, eqn_name} /]} ;

The keyword model[s] indicates that this is a model statement and model_name is the internal name of the model in GAMS, it is an identifier. The optional explanatory text is used to describe the model, all is a keyword as introduced above and eqn_name is the name of an equation that has been declared prior to the model statement. For advice on explanatory text and how to choose a model_name, see the tutorial Good Coding Practices.

Note
Model statements for Mixed Complementarity Problem (MCP) and Mathematical Program with Equilibrium Constraints (MPEC) models require a slightly different notation, since complementarity relationships need to be included. For details see subsections Mixed Complementarity Problem (MCP) and Mathematical Program with Equilibrium Constraints (MPEC).

An example of a model definition in GAMS is shown below.

Model transport "a transportation model" / all /;

The model is called transport and the keyword all is a shorthand for all known (declared) equations.

Several models may be declared (and defined) in one model statement. This is useful when experimenting with different ways of writing a model, or if one has different models that draw on the same data. Consider the following example, adapted from [PROLOG], in which different groups of the equations are used in alternative versions of the problem. Three versions are solved: the linear, nonlinear, and 'expenditure' versions. The model statement to define all three is:

Model  nortonl   "linear version"      / cb,rc,dfl,bc,obj /
       nortonn   "nolinear version"    / cb,rc,dfn,bc,obj /
       nortone   "expenditure version" / cb,rc,dfe,bc,obj /  ;

Here cb, rc, etc. are the names of the equations. We will describe below how to obtain the solution to each of the three models.

Note
If several models are declared and defined with one model statement, the models have to be separated by commas or linefeeds and a semicolon terminates the entire statement.

If several models are declared then it is possible to use one previously declared model in the declaration of another. The following examples illustrate this:

Model one   "first model"                             / tcost_eq, supply_eq, demand_eq /
      two   "second model that nests first"           / one, balance_eq /
      three "third model that nests first and second" / two, capacity_eq, configure_eq /;

Model one is declared and defined using the general syntax, model two contains all the equations of model one and the equation balance_eq, and model three contains all of model two and the equations capacity_eq and configure_eq.

In addition to nesting models as illustrated above, it is also possible to use the symbols + and - to augment or remove items relative to models that were previously defined. The following examples serve as illustration:

Model four "fourth model: model three minus model one"         / three-one /
      five "fifth model: model three without eqn configure_eq" / three-configure_eq /
      six  "sixth model: model four plus model two"            / four+two /;

Model four contains the equations from model three except for those that belong to model one. Model five contains all equationsfrom model three except for equation configure_eq. Model six contains the union of the equations in model four and two. Note that both model names and equation names may be used in association with the symbols + and -.

Classification of Models

Various types of problems can be solved with GAMS. Note that the type of the model must be known before it may be solved. The model types are briefly discussed in this section. GAMS checks that the model is in fact the type the user thinks it is, and issues explanatory error messages if it discovers a mismatch - for instance, that a supposedly linear model contains nonlinear terms. Some problems may be solved in more than one way, and the user has to choose which way to use. For instance, if there are binary or integer variables in the model, it can be solved either as a MIP or as a RMIP.

The model types and their identifiers, which are needed in the a solve statement, are given in Table 1. For details on the solve statement, see section The Solve Statement.

GAMS Model Type Model Type Description Requirements and Comments
LP Linear Program Model with no nonlinear terms or discrete (i.e. binary, integer, etc) variables.
NLP Nonlinear Program Model with general nonlinear terms involving only smooth functions, but no discrete variables. For a classification of functions as to smoothness, see section Functions.
QCP Quadratically Constrained Program Model with linear and quadratic terms, but no general nonlinear terms or discrete variables.
DNLP Discontinuous Nonlinear Program Model with non-smooth nonlinear terms with discontinuous derivatives, but no discrete variables. This is the same as NLP, except that non-smooth functions may appear as well. These models are more difficult to solve than normal NLP models and we strongly advise not to use this model type.
MIP Mixed Integer Program Model with binary, integer, SOS and/or semi variables, but no nonlinear terms.
RMIP Relaxed Mixed Integer Program Like MIP, except that the discrete variable requirement is relaxed. See the note below on relaxed model types.
RMINLP Relaxed Mixed Integer Nonlinear Program Like MINLP except that the discrete variable requirement is relaxed. See the note below on relaxed model types.
MINLPMixed Integer Nonlinear Program Model with both nonlinear terms and discrete variables.
MIQCPMixed Integer Quadratically Constrained Program Model with both quadratic terms and discrete variables, but no general nonlinear term.
RMIQCP Relaxed Mixed Integer Quadratically Constrained Program Like MIQCP except that the discrete variable requirement is relaxed. See the note below on relaxed model types.
MCP Mixed Complementarity Problem A square, possibly nonlinear, model that generalizes a system of equations. Rows and columns are matched in one-to-one complementary relationships.
CNS Constrained Nonlinear System Model solving a square, possibly nonlinear system of equations, with an equal number of variables and constraints.
MPECMathematical Programs with Equilibrium Constraints A difficult model type for which solvers and reformulations are currently being developed.
RMPEC Relaxed Mathematical Program with Equilibrium Constraints A difficult model type for which solvers and reformulations are currently being developed. See the note below on relaxed model types.
EMP Extended Mathematical Program A family of mathematical programming extensions.
MPSGE General Equilibrium Not actually a model type but mentioned for completeness, see MPSGE.

Table 1: GAMS Model Types

Note
  • The relaxed model types RMIP, RMINLP, RMIQCP, and RMPEC solve the problem as the corresponding model type (e.g. MIP for RMIP) but relax the discrete requirement of the discrete variables. This means that integer and binary variables may assume any values between their bounds. SemiInteger and SemiCont variables may assume any values between 0 and their upper bound. For SOS1 and SOS2 variables the restriction of the number of non-zero values is removed.
  • Many "LP" solvers like Cplex offer the functionality of solving convex quadratic models. So the Q matrices in the model need to be positive semidefinite. An extension to to this are the second-order cone programs (SOCP) with either symmetric or rotated cones. See the solver manuals (e.g. on MOSEK) for details.
  • Unlike other checks on the model algebra (e.g. existance of discrete variables or general non-linear terms), the GAMS compiler does not enforce a quadratic model to only consist of quadratic and linear terms. This requirement is enforced at runtime for a particular model instance.

Linear Programming (LP)

Mathematically, the Linear Programming (LP) problem looks like:

\begin{equation*} \begin{array}{ll} \textrm{Minimize or maximize} & cx \\ \textrm{subject to} & Ax \, \, \alpha \, \, b \\ & L \leq x \leq U, \\ \end{array} \end{equation*}

where \(x\) is a vector of variables that are continuous real numbers, \(cx\) is the objective function, and \(Ax \, \alpha \, b\) represents the set of constraints. For details on the equation types allowed in GAMS, see Equation Types. \(L\) and \(U\) are vectors of lower and upper bounds on the variables.

GAMS supports free (unrestricted) variables, positive variables, and negative variables. Note that users may customize lower and upper bounds, for details see section Bounds on Variables.

For information on LP solvers that can be used through GAMS see the Solver/Model type Matrix.

Nonlinear Programming (NLP)

Mathematically, the Nonlinear Programming (NLP) problem looks like:

\begin{equation*} \begin{array}{ll} \textrm{Minimize or Maximize} & f(x) \\ \textrm{subject to} & g(x) \, \, \alpha \, \, 0 \\ & L \leq x \leq U, \\ \end{array} \end{equation*}

where \(x\) is a vector of variables that are continuous real numbers, \(f(x)\) is the objective function, and \( g(x) \, \alpha \, 0\) represents the set of constraints. For details on the equation types allowed in GAMS, see Equation Types. Note that the functions \(f(x)\) and \(g(x) \) have to be differentiable. \(L\) and \(U\) are vectors of lower and upper bounds on the variables.

For information on NLP solvers that can be used through GAMS see the Solver/Model type Matrix. See also the tutorial Good NLP Formulations.

Note
NLP models may have the nonlinear terms inactive. In this case setting the model attribute TryLinear to 1 causes GAMS to check the model and use the default LP solver if possible. For details on model attributes, see subsection Model Attributes.

Quadratically Constrained Programs (QCP)

Mathematically, the Quadratically Constrained Programming (QCP) problem looks like:

\begin{equation*} \begin{array}{lll} \textrm{Maximize or Minimize} & cx + x'Q x & \\ \textrm{subject to} & Aix + x' Rix \,\, \alpha \,\, bi & \textrm{for all} \,\, i \\ & L \leq x \leq U, & \\ \end{array} \end{equation*}

where \(x\) denotes a vector of variables that are continuous real numbers, \(cx\) is the linear part of the objective function, \(x'Qx\) is the quadratic part of the objective function, \(Aix\) represents the linear part of the \(i\)th constraint, \(x' Rix\) represents the quadratic part of the \(i\)th constraint, \(bi\) is the right-hand side if the \(i\)th constraint, and \(\alpha\) is an equation operator. For details on the equation types allowed in GAMS, see Equation Types". Further, \(L\) and \(U\) are vectors of lower and upper bounds on the variables.

Note that a QCP is a special case of the NLP in which all the nonlinearities are required to be quadratic. As such, any QCP model can also be solved as an NLP. However, most "LP" vendors provide routines to solve LP models with a quadratic objective. Some allow quadratic constraints as well. Solving a model using the QCP model type allows these "LP" solvers to be used to solve quadratic models as well as linear ones. Some NLP solvers may also take advantage of the special (quadratic) form when solving QCP models.

Attention
In case a model with quadratic constraints is passed to a QCP solver that only allows a quadratic objective, a capability error will be returned (solver status 6 CAPABILITY PROBLEMS). Some solvers will fail when asked to solve a non-convex quadratic problems as decribed above.
Note
Using the model attribute TryLinear causes GAMS to see if the problem can be solved as an LP problem. For details on model attributes, see subsection Model Attributes.

For information on QCP solvers that can be used through GAMS see the Solver/Model type Matrix.

Nonlinear Programming with Discontinuous Derivatives (DNLP)

Mathematically, the Nonlinear Programming with Discontinuous Derivatives (DNLP) problem looks like:

\begin{equation*} \begin{array}{ll} \textrm{Minimize} & f(x)\\ \textrm{subject to} & g(x) \, \, \alpha \, \, 0 \\ & L \leq x \leq U, \\ \end{array} \end{equation*}

where \(x\) is a vector of variables that are continuous real numbers, \(f(x)\) is the objective function, \(g(x) \, \alpha \, 0\) represents the set of constraints, and \(L\) and \(U\) are vectors of lower and upper bounds on the variables. For details on the equation types allowed in GAMS, see Equation Types. Note that this is the same as NLP, except that non-smooth functions, like abs, min, max may appear in \(f(x)\) and \(g(x)\).

For information on DNLP solvers that can be used through GAMS see the Solver/Model type Matrix.

Attention
  • We strongly advise against using the model type DNLP. The best way to model discontinuous functions is with binary variables, which results in a model of the type MINLP. The model [ABSMIP] demonstrates this formulation technique for the functions abs, min, max and sign. See also section Reformulating DNLP Models.
  • Solvers may have difficulties when dealing with the discontinuities, since they are really NLP solvers and the optimality conditions and the reliance on derivatives may be problematic. Using the global solvers ANTIGONE, BARON, COUENNE, LINDO or SCIP may alleviate this problem.

Mixed Integer Programming (MIP)

Mathematically, the Mixed Integer Linear Programming (MIP) problem looks like:

\begin{equation*} \begin{array}{lrclll} \textrm{Maximize or Minimize} & c_1 t + c_2 u + c_3 v + c_4 w + c_5 x + c_6 y + c_7 z & & & & \\ \textrm{subject to} & A_1 t + A_2 u + A_3 v + A_4 w + A_5 x + A_6 y + A_7 z & \alpha & b & & \\ & t & \in & \mathbb R & &\\ & u & \geq & 0 & \textrm{and}\,\, u \leq L_2 & \textrm{and} \, \, u \in \mathbb Z \\ & v & \in & (0,1) & &\\ & w & \in & \textrm{SOS1} & &\\ & x & \in & \textrm{SOS2} & &\\ & y & = & 0 & \textrm{or} \, \, \, L_6 \leq y & \\ & z & = & 0 & \textrm{or} \,\, \, L_7 \leq z & \textrm{and} \,\, z \in \mathbb Z,\\ \end{array} \end{equation*}

where

  • \(c_1t + c_2u + c_3v + c_4w + c_5x + c_6y + c_7z\) is the objective function,
  • \( A_1t + A_2u + A_3v + A_4w + A_5x + A_6y + A_7z \,\, \alpha \,\, b\) represents the set of constraints of various equality and inequality forms,
  • \( t\) is a vector of variables that are continuous real numbers,
  • \( u\) is a vector of variables that can only take integer values smaller than \( L_2 \),
  • \( v \) is a vector of binary variables,
  • \( w \) is a vector of variables that belong to SOS1 sets; this means that at most one variable in the set is nonzero,
  • \( x \) is a vector of variables that belong to SOS2 sets; this means that at most two adjacent variables in the set are nonzero,
  • \( y \) is a vector of variables that are semi-continuous; they are either zero or larger than \( L_6 \),
  • \( z \) is a vector of variables that are semi-integer; they are integer and either zero or larger than \( L_7 \).

For details on the equation types allowed in GAMS, see Equation Types. For more details on MIPs in GAMS, especially the use of SOS and semi variables, see section Special Mixed Integer Programming (MIP) Features.

For information on MIP solvers that can be used through GAMS, see the Solver/Model type Matrix.

Attention
Not all MIP solvers cover all the cases associated with SOS and semi variables. Please consult the solver manuals for details on capabilities.

Mixed Integer Nonlinear Programming (MINLP)

Mathematically, the Mixed Integer Nonlinear Programming (MINLP) problem looks like:

\begin{equation*} \begin{array}{ll} \textrm{Maximize or Minimize} & f(x) + Dy \\ \textrm{subject to} & g(x) + Hy \, \, \alpha \, \, 0 \\ & L \leq x \leq U \\ & y = \{0,1,2,\cdots\}, \\ \end{array} \end{equation*}

where \(x\) is a vector of variables that are continuous real numbers, \(y\) denotes a vector of variables that can only take integer values, \(f(x)+ Dy\) is the objective function, \(g(x) + Hy\ \, \alpha \, 0\) represents the set of constraints, and \(L\) and \(U\) are vectors of lower and upper bounds on the variables. For details on the equation types allowed in GAMS, see Equation Types. Further, \( y = \{0,1,2,\cdots\} \) is the integrality restriction on \(y\).

For information on MINLP solvers that can be used through GAMS see the Solver/Model type Matrix.

Note
  • SOS and semi variables can also be accommodated by some solvers. Please consult the solver manuals for details on capabilities.
  • The model attribute TryLinear causes GAMS to examine whether the problem may be solved as a MIP problem. For details on model attributes, see subsection Model Attributes.

Mixed Integer Quadratically Constrained Programs (MIQCP)

A Mixed Integer Quadratically Constrained Program (MIQCP) is a special case of the MINLP in which all the nonlinearities are required to be quadratic. For details see the description of the QCP, a special case of the NLP.

For information on MIQCP solvers that can be used through GAMS, see the Solver/Model type Matrix.

Note
The model attribute TryLinear causes GAMS to examine whether the problem may be solved as a MIP problem. For details on model attributes, see subsection Model Attributes.

Mixed Complementarity Problem (MCP)

Unlike the other model types we have introduced so far, the Mixed Complementarity Problem (MCP) does not have an objective function. An MCP is specified by three pieces of data: a function \(F(z): \mathbb R^n \mapsto \mathbb R^n \), lower bounds \(l \in \{\mathbb R \cup \{-\infty\}\}^n \) and upper bounds \(u \in \{\mathbb R \cup \{\infty\}\}^n \). A solution is a vector \( z \in \mathbb R^n \) such that for each \( i \in \{1, \ldots, n\} \), one of the following three conditions hold:

\[ \begin{array}{rcl} F_i(z) = 0 & \mbox{ and } & \ell_i \leq z_i \leq u_i \, \, \, \mbox{ or} \\ F_i(z) > 0 & \mbox{ and } & z_i = \ell_i \, \, \, \mbox{ or} \\ F_i(z) < 0 & \mbox{ and } & z_i = u_i . \end{array} \]

This problem can be written compactly as

\begin{equation*} F(z) \, \perp \, L \leq z \leq U, \end{equation*}

where the symbol \( \perp \) (which means "perpendicular to", shortened to "perp to") indicates pair-wise complementarity between the function \(F \) and the variable \(z\) and its bounds.

The following special case is an important and illustrative example:

\begin{equation*} F(z) \perp z \geq 0. \end{equation*}

In this example, the unstated but implied upper bound \(u\) is infinity. Since \(z\) is finite, we cannot have \( z_i = u_i \) and the third condition above cannot hold: this implies \( F(z) >= 0 \). The remaining two conditions imply pair-wise complementarity between \(z >= 0\) and \(F(z) >= 0\). This is exactly the Nonlinear Complementarity Problem, often written as

\begin{equation*} F(z) \geq 0, \quad z \geq 0, \quad \langle{F(z)},{z}\rangle = 0. \end{equation*}

None of this rules out the degenerate case (i.e. \(F_i(z)\) and \( z_i \) both zero). In practice, these can be difficult models to solve.

Another special case arises when the bounds \( L \) and \( U \) are infinite. In this case, the second and third conditions above cannot hold, so we are left with \( F(z) = 0 \), a square system of nonlinear equations. And finally, we should mention a special case that occurs frequently in practice: if \( \ell_i = u_i \) (i.e. \( z_i \) is fixed) then we have a complementary pair: one of the three conditions will hold as long as \(F_i(z)\) is defined. Essentially, fixing a variable removes or obviates the matching equation. This is often useful when modeling with MCP.

The definition above describes the canonical MCP model as it exists when GAMS passes it to an MCP solver. Some models have exactly this form even in the GAMS code, but usually some processing is done by the GAMS system to arrive at a model in this form. Here we'll describe the steps of this process and illustrate with an example from the model library.

  1. The process starts with the list of rows (aka single equations) and columns (aka single variables) that make up the MCP model, and potentially some matching information.
    • The usual rules apply: rows are part of the model because their associated equations are included in the model statement, but columns only become part of the model by use: a column enters the model only if it is used in some row of the model. Therefore including a variable symbol as part of a match in the model statement will not influence the set of columns belonging to the model.
    • Matches (where they exist) are pointers from rows to columns.
    • Technically, the MCP is defined via a function \(F\) while a model contains constraints. Given a constraint, we define an associated function as LHS - RHS, so e.g. \(F_i \geq 0\) is consistent with a =G= constraint.
  2. The explicit matches are processed: each match creates a complementary pair. What remains after the explicit matches are consumed are the unmatched rows and unmatched columns.
    • It is an error for any column to be matched to multiple rows, so the row-column matching is one-to-one.
    • For each match some consistency checks between the column bounds and the row type are made. For details, see Table 2.
    • For example, matching an =N= row with any column is good, matching an =E= row with a free column is good, matching an =E= row with a lower-bounded column is allowed, and matching a =G= row with an upper-bounded column results in an error.
  3. Any fixed columns remaining are ignored: these columns can be treated like exogenous variables or parameters.
  4. If what remains is a set of =E= rows and an equal number of unbounded columns, these can be matched up in any order and we have a well-defined MCP. If this is not what remains, an error is triggered.

To illustrate how this works, consider the spatial equilibrium model [SPATEQU] with the following model statement:

Model  P2R3_MCP        / dem, sup, in_out.p, dom_trad.x /;
  1. The model P2R3_MCP includes the rows from equations dem, sup, in_out and dom_trad and exactly the columns used by these rows. Checking the listing file, we see columns for Qd, Qs, x, and p. In addition, the model statement specifies two matches: in_out.p and dom_trad.x. These matches always take the form of an equation.variable pair, with no indices or domains included.
  2. In this example, the rows corresponding to the equation in_out match up perfectly with the columns from the variable p: there are no holes in the set of rows or columns because of some dollar conditions in the equation definition. We have a one-to-one match so all the rows of in_out and columns of p are consumed by the match in the model statement. The same holds for the dom_trad.x pair, so what is left are the rows of dem and sup and the columns of Qd and Qs, all of which are unmatched.
  3. There are no fixed variables to remove.
  4. Since dem and sup are =E= constraints and Qd and Qs are free variables, we can match them in any order without changing the solution set for this model. The counts of these unmatched equality rows and unmatched free variables are equal, so we get a well-defined MCP.

When rows are matched explicitly to columns, some care must be taken to match them consistently. For example, consider a row-column match g.y. The row g can be of several types: =N=, =E=, =G=, or =L=. An =N= row can be matched to any sort of variable: the =N= doesn't imply any sort of relationship, which works perfectly with our definition of \( \perp \) above: the allowed sign or direction of g is determined completely by the bounds on the complementary variable y. If g is an =E= row, this is consistent with a free variable y, but what if y has an active lower bound? By definition we allow g to be positive at solution, but this violates the declaration as an =E= row. Such cases can be handled by marking the row with a redef. The total number of redefs for a given model is available via the NumRedef model attribute and is shown in the report summary. Note that the set of rows marked depends on the solution: in the example above, if g is zero at solution it will not be marked as a redef, regardless of what the bounds are on y. Finally, some combinations are simply not allowed: they will result in a model generation error. The table below lists the outcome for all possible combinations.

Table 2: MCP Matching

Column Bounds =N= =E= =G= =L=
lower OK redef OK ERROR
upper OK redef ERROR OK
free OK OK OK OK
double OK redef redef redef
fixed OK redef redef redef

The definition, process, and rules above have several implications for valid MCP models:

  • It is always acceptable to use the =N= notation when defining the equations in an MCP model, provided these equations are matched explicitly. In this case the bounds on F(z) are implied by the bounds on the matching columns, and redefs will never occur.
  • Variables that are known to be lower-bounded (no upper bound) will match consistently with =G= equations.
  • Variables that are known to be upper-bounded (no lower bound) will match consistently with =L= equations.
  • Variables that are known to be unbounded will match consistently with =E= equations.
  • Where the bound structure is not known in advance, or both upper and lower bounds exist, a match with an =N= equation will always be consistent. Other equation types will result in errors or redefs.
  • The model may initially have fewer rows than columns, as long as the "extra" columns are unmatched fixed columns that ultimately get removed from the MCP passed to the solver.
  • Any bounded-but-not-fixed column must be matched explicitly to a row.
  • The only rows that may be unmatched are =E= rows.
  • It is customary to re-use the constraints of an LP or NLP model when formulating the MCP corresponding to the Karush-Kuhn-Tucker (KKT) conditions. If the original model is a minimization, the LP/NLP marginals .m and the variables for these marginals in the MCP will use the same sign convention, and the orientation for the constraints will be consistent between the two models, making re-use easier.

As mentioned above, it is typical to use the same equations in both NLP and MCP models. Sometimes, it is not the original equation that is wanted for the MCP, but rather the reoriented (aka negated or flipped) equation. For example, the flipped version of x**1.5 =L= y is y =G= x**1.5, while sqr(u) - sqr(v) =E= 5 becomes - sqr(u) + sqr(v) =E= -5. Instead of re-implementing the equation in flipped form, the same result can be achieved by prefixing the equation name with a - in the model statement. See the [mcp10] model for an example of such usage. When equations are used in flipped form, they are marked with a redir in the listing file's solution listing.

An example of complementarity that should be familiar to many is the relationship between a constraint and its associated dual multiplier: if the constraint is non-binding, its dual multiplier must be zero (i.e. at bound) while if a dual multiplier is nonzero the associated constraint must be binding. In fact, the KKT or first-order optimality conditions for LP and NLP models can be expressed and solved as an MCP.

These complementarity relationships found in optimization problems are useful in understanding the marginal values assigned to rows and columns in the GAMS solution for MCP. With no objective function, the usual definition for marginal values and their interpretation isn't useful. Instead, the GAMS MCP convention for the marginal values of columns is to return the slack of the associated row (i.e. its value when interpreted and evaluated as a function). For the marginal values of rows, the level value (not the slack) of the associated column is returned. When we apply this convention to the NCP ( \(F(z) \geq 0, z \geq 0, \langle{F(z)},{z}\rangle = 0\)) we see pairwise complementarity between the levels and marginals returned for each of the rows and columns in the model. This is also the case if we take the KKT conditions of an LP in a suitable standard form: minimization, \(x \geq 0, Ax \geq b\).

MCPs arise in many application areas including applied economics, game theory, structural engineering and chemical engineering. For further details on this class of problems, see http://www.neos-guide.org/content/complementarity-problems.

For information on MCP solvers that can be used through GAMS, see Solver/Model type Matrix.

Constrained Nonlinear System (CNS)

The Constrained Nonlinear System (CNS) is the second GAMS model type that does not have an objective function. Mathematically, a CNS model looks like:

\begin{equation} \begin{array}{ll} \textrm{Find} & x \\ \textrm{subject to} & F(x) = 0 \\ & L \leq x \leq U \\ & G(x) \, \, \alpha \, \, b, \\ \end{array} \end{equation}

where \(x\) is a set of continuous variables and \(F\) is a set of nonlinear equations of the same dimension as \(x\). This is a key property of this model type: the number of equations equals the number of variables, so we have a square system. The (possibly empty) constraints \(L \leq x \leq U \) are not intended to be binding at the solution, but instead are included to constrain the solution to a particular domain, to avoid regions where \(F(x)\) is undefined, or perhaps just to give the solver a push in the right direction. The (possibly empty) constraints \(G(x) \, \, \alpha \, \, b\) are intended to serve the same purpose as the variable bounds and are silently converted to equations with bounded slacks.

Note that since there is no objective in a CNS model, there are no marginal values for variables and equations. Any marginal values already stored in the GAMS database will remain untouched. CNS models also make use of some model status values that allow a solver to indicate if the solution is unique (e.g. for a non-singular linear system) or if the linearization is singular at the solution. For singular models (solved or otherwise), the solver can mark one or more dependent rows with a depnd. The total number of rows so marked for a given model is available via the NumDepnd model attribute and is shown in the report summary.

The CNS model is a generalization of a square system of equations \(F(x) = 0\). Such a system could also be modeled as an NLP with a dummy objective. However, there are a number of advantages to using the CNS model type, including:

  • A check by GAMS that the model is really square,
  • solution/model diagnostics by the solver (e.g. singular at solution, (locally) unique solution),
  • CNS-specific warnings if the side constraints \(L \leq x \leq U \) or \(G(x) \, \, \alpha \, \, b\) are active at a solution,
  • and potential improvement in solution times, by taking better advantage of the model properties.

For information on CNS solvers that can be used through GAMS, see the Solver/Model type Matrix.

Mathematical Program with Equilibrium Constraints (MPEC)

Mathematically, the Mathematical Program with Equilibrium Constraints (MPEC) problem looks like:

\begin{equation*} \begin{array}{ll} \textrm{Maximize or Minimize} & f(x,y) \\ \textrm{subject to} & g(x,y) \, \, \alpha \, \, 0 \\ & L_x \leq x \leq U_x \\ & F(x,y) \perp L_y \leq y \leq U_y, \\ \end{array} \end{equation*}

where \(x\) and \(y\) are vectors of continuous real variables. The variables \(x\) are often called the control or upper-level variables, while the variables \(y\) are called the state or lower-level variables. \(f(x,y)\) is the objective function. \(g(x,y) \, \alpha \, 0\) represents the set of traditional (i.e. NLP-type) contraints; some solvers may require that these constraints only involve the control variables \(x\). The function \(F(x,y)\) and the bounds \(L_y\) and \(U_y\) define the equilibrium constraints. If \(x\) is fixed, then \(F(x,y)\) and the bounds \(L_y\) and \(U_y\) define an MCP; the discussion of the "perp to" symbol \( \perp \) in that section applies here as well. From this definition, we see that the MPEC model type contains NLP and MCP models as special cases of MPEC.

A simple example of an entire MPEC model is given below.

variable z, x1, x2, y1, y2;
positive variable y1;
y2.lo = -1;
y2.up =  1;

equations cost, g, h1, h2;

cost..  z =E= x1 + x2;
g..     sqr(x1) + sqr(x2) =L= 1;
h1..    x1 =G= y1 - y2 + 1;
h2..    x2 + y2 =N= 0;

model example / cost, g, h1.y1, h2.y2 /;
solve example using mpec min z;

Note that as in the MCP, the complementarity relationships in an MPEC are specified in the model statement via equation-variable pairs: the h1.y1 specifies that the equation h1 is perpendicular to the variable y1 and the h2.y2 specifies that the equation h2 is perpendicular to the variable y2. For details on the solve statement, see section The Solve Statement.

While the MPEC model formulation is very general, it also results in problems that can be very difficult to solve. The state-of-the-art for MPEC solvers is not nearly as advanced as that for other model types. As a result, you should expect the MPEC solvers to be more limited by problem size and/or robustness issues than solvers for other model types.

For information on MPEC solvers that can be used through GAMS, see the Solver/Model type Matrix. For more details on MPECs and solver development, see http://gamsworld.org/mpec/index.htm and http://www.neos-guide.org/content/complementarity-problems.

Extended Mathematical Programs (EMP)

Extended Mathematical Programming (EMP) is an (experimental) framework for automated mathematical programming reformulations. Using EMP, model formulations that GAMS cannot currently handle directly or for which no robust and mature solver technology exists can be automatically and reliably reformulated or transformed into models for which robust and mature solver technology does exist within the GAMS system. For more details, see the chapter on EMP. Currently EMP supports:

  • Equilibrium problems including variational inequalities, Nash games, and Multiple Optimization Problems with Equilibrium Constraints (MOPECs).
  • Hierarchical optimization problems such as bilevel programs.
  • Disjunctive programs for modeling discrete choices with binary variables.
  • Stochastic programs including two-stage and multi-stage stochastic programs, chance constraints and risk measures such as Variance at Risk (VaR) and Conditional Variance at Risk (CVaR).

Apart from the disjunctive and stochastic programming models mentioned above, EMP models are typically processed (aka solved) via the JAMS solver: this solver does the work of reformulation/transformation, calling GAMS to solve this reformulation, and post-processing the solution that results to bring it back in terms of the original EMP model.

Examples demonstrating how to use the EMP framework and the JAMS and DE solvers are available in the GAMS EMP Library. These solvers require no license of their own to run but can and do call subsolvers that do require a license.

Model Attributes

Models have attributes that hold a variety of information, including

  • information about the results of a solve performed, a solve statement, the solution of a model,
  • information about certain features to be used by GAMS or the solver,
  • information passed to GAMS or the solver specifying various settings that are also subject to option statements.

Model attributes are accessed in the following way:

model_name.attribute

Here model_name is the name of the model in GAMS and .attribute is the specific attribute that is to be accessed. Model attributes may be used on the left-hand side and the right-hand side of assignments. Consider the following example:

transport.resLim = 600;
x = transport.modelStat;

In the first line the attribute .resLim of the model transport is specified to be 600 (seconds). In the second line the value of the attribute .modelStat of the model transport is assigned to the scalar x. Note that model attributes may also be used in display statements".

Some of the attributes are mainly used before the solve statement to provide information to GAMS or the solver link. Others are set by GAMS or the solver link and hence are mainly used after a solve statement.

Moreover, some of the attributes used before the solve may also be set via an option statement or the command line. Consider the following example:

option ResLim=10;

This line is an option statement and applies to all models. One can set the model attribute .ResLim to overwrite the global ResLim option. In order to revert the individual .ResLim to the global ResLim option, one needs to set the model attribute to NA. For more on option statements, see chapter The Option Statement.

gams mymodel ResLim=10

This sets the global ResLim option when invoking the gams run (e.g. from the command line). For more on command line parameters, see chapter The GAMS Call and Command Line Parameters.

Note that a model-specific option takes precedence over the global setting specified with an option statement and that a setting via an option statement takes precedence over a setting via the command line parameter.

The complete list of model attributes is given below. Observe that each entry is linked to a detailed description of the respective attribute, including information of whether the attribute is also available as command line parameter or option statement. Note that detailed descriptions of all GAMS command line parameters, options and model attributes are given in section Detailed Descriptions of All Options.

Model Attributes Mainly Used Before Solve

Attribute Description
bRatioBasis acceptance threshold
cheatCheat value, i.e. minimum solution improvement threshold
cutOffCutoff value for branch and bound
defPointIndicator for passing on default point
dictFileForce writing of a dictionary file if dictfile > 0
domLimDomain violation limit solver default
fdDeltaStep size for finite differences
fdOptOptions for finite differences
holdFixedTreat fixed variables as constants
integer1..5Integer communication cells
iterLimIteration limit of solver
limColMaximum number of columns listed in one variable block
limRowMaximum number of rows listed in one equation block
MCPRHoldFxPrint list of rows that are perpendicular to variables removed due to the holdfixed setting
nodLimNode limit in branch and bound tree
optCAAbsolute Optimality criterion solver default
optCRRelative Optimality criterion solver default
optFileDefault option file
priorOptPriority option for variable attribute .prior
real1..5Real communication cells
reformReformulation level
resLimWall-clock time limit for solver
savePointSave solver point in GDX file
scaleOptEmploy user specified variable and equation scaling factors
solPrintSolution report print option
solveLinkSolver link option
solveOptMultiple solve management
sysOutSolver Status file reporting option
threadsNumber of threads to be used by a solver
tolInfeasInfeasibility tolerance for an empty row of the form a.. 0*x =e= 0.0001;
tolInfRepThis attribute sets the tolerance for marking infeasible in the equation listing
tolProjTolerance for setting a variable level to its bound and filtering marginals when reading a solution
tryIntWhether solver should make use of a partial integer-feasible solution
tryLinearExamine empirical NLP model to see if there are any NLP terms active. If there are none the default LP solver will be used
workFactorMemory Estimate multiplier for some solvers
workSpaceWork space for some solvers in MB

Model Attributes Mainly Used After Solve

Attribute Description
domUsdNumber of domain violations
etAlgElapsed time it took to execute the solve algorithm
etSolveElapsed time it took to execute a solve statement in total
etSolverElapsed time taken by the solver only
handleUnique handle number of SOLVE statement
iterUsdNumber of iterations used
lineLine number of last solve of the corresponding model
linkUsedInteger number that indicates the value of SolveLink used for the last solve
marginalsIndicator for marginals present
maxInfesMaximum of infeasibilities
meanInfesMean of infeasibilities
modelStatInteger number that indicates the model status
nodUsdNumber of nodes used by the MIP solver
numberModel instance serial number
numDepndNumber of dependencies in a CNS model
numDVarNumber of discrete variables
numEquNumber of equations
numInfesNumber of infeasibilities
numNLInsNumber of nonlinear instructions
numNLNZNumber of nonlinear nonzeros
numNOptNumber of nonoptimalities
numNZNumber of nonzero entries in the model coefficient matrix
numRedefNumber of MCP redefinitions
numVarNumber of variables
numVarProjNumber of bound projections during model generation
objEstEstimate of the best possible solution for a mixed-integer model
objValObjective function value
procUsedInteger number that indicates the used model type
resCalcTime spent in function and derivative calculations (deprecated)
resDerivTime spent in derivative calculations (deprecated)
resGenTime GAMS took to generate the model in CPU seconds(deprecated)
resInTime to import model (deprecated)
resOutTime to export solution (deprecated)
resUsdTime the solver used to solve the model in CPU seconds
rObjObjective function value from the relaxed solve of a mixed-integer model when the integer solver did not finish
solveStatIndicates the solver termination condition
sumInfesSum of infeasibilities
sysIdentSolver identification number
sysVerSolver version

The Solve Statement

Once a model has been defined using the model statement, the solve statement prompts GAMS to call one of the available solvers for the particular model type. This section introduces and discusses the solve statement in detail. For a list of GAMS model types, see Table 1. For information on how to specify desired solvers, see section Choosing a Solver.

Note
It is important to remember that GAMS does not solve the problem, but passes the problem definition to one of a number of separate solver programs that are integrated with the GAMS system.

The Syntax of the Solve Statement

In general, the syntax for a solve statement is as follows. Note that there are two alternatives that are equally valid:

solve model_name using model_type maximizing|minimizing var_name;
solve model_name maximizing|minimizing var_name using model_type ;

The keyword solve indicates that this is a solve statement. Model_name is the name of the model as defined by a model statement. Note that the model statement must be placed before the solve statement in the program. The keyword using is followed by model_type, which is one of the GAMS model types described above, see Table 1. The keywords maximizing or minimizing indicate the direction of the optimization. Var_name is the name of the objective variable that is being optimized. An example of a solve statement in GAMS is shown below.

Solve transport using lp minimizing cost ;

Solve and using are reserved words, transport is the name of the model, lp is the model type, minimizing is the direction of optimization, and cost is the objective variable. Note that an objective variable is used instead of an objective row or function.

Attention
The objective variable must be scalar and of type free, and must appear in at least one of the equations in the model.

Recall that some model types (e.g. the Constrained Nonlinear System (CNS) or the Mixed Complementarity Problem (MCP) do not have an objective variable. So their solve statement syntax is slightly different:

solve model_name using model_type;

As before, solve and using are keywords, model_name is the name of the model as defined by a model statement and model_type is the GAMS model type CNS or MCP. There is no objective variable and consequently no direction of optimization. An example from the spatial equilibrium model [SPATEQU] illustrates this solve statement:

Solve P2R3_MCP using mcp;

P2R3_MCP is the model name, the model type is MCP and as expected, there is no objective variable.

The EMP model type serves many purposes including some experimental ones. The solve statement with model type EMP can be with or without the objective variable and optimization direction.

Actions Triggered by the Solve Statement

When GAMS encounters a solve statement during compilation (the syntactic check of the input file) or execution (actual execution of the program), it initiates a number of special actions. The purpose is to prevent waste that would be caused by solving a model that has apparently been incorrectly specified. During compilation the following are verified:

  1. All symbolic equations have been defined and the objective variable is used in at least one of the equations.
  2. The objective variable is scalar and of type free (even though lower and upper bounds may have been specified)
  3. MCP models are checked for appropriate complementarity and squareness.
  4. Each equation fits into the specified problem class (linearity for LP, continuous derivatives for NLP, as outlined above).
  5. All sets and parameters in the equations have values assigned.
Note
GAMS issues explanatory error messages if it discovers that the model is not according to type; for example, the presence of nonlinear terms in a supposedly LP model. For details on error messages, see chapter GAMS Output.

At execution time the solve statement triggers the following sequence of steps:

  1. The model is translated into the representation required by the solution system to be used.
  2. Debugging and comprehension aids that the user wishes to see are produced and written to the output file (EQUATION LISTING, etc). For customizing options (e.g. LimRow and LimCol), see chapter The Option Statement.
  3. GAMS verifies that there are no inconsistent bounds or unacceptable values (for example, NA or UNDF) in the problem.
  4. Any errors detected at this stage cause termination with as much explanation as possible, using the GAMS names for the identifiers causing the trouble.
  5. GAMS designs a solution strategy based on the possible availability of level values or basis information from a previous solution: all available information is used to provide efficiency and robustness of operation. Any specifications provided by the user (Iteration limits etc.) are incorporated. A solver is chosen which is either the default solver for that problem type, the solver specified on the command line or the solver chosen by an option statement. For details see section Choosing a Solver.
  6. GAMS passes control to the solution subsystem and waits while the problem is being solved.
  7. GAMS reports on the status of the solution process and loads solution values back into the GAMS database. This causes new values to be assigned to the .l and .m fields for all individual equations and variables in the model. In addition, the post solution model attributes are assigned. The procedure for loading back the data associated with level and marginal values may be customized using the SolveOpt model attribute and option. A row by row and column by column listing of the solution is provided by default. It may be suppressed by the SolPrint model attribute or option. Any apparent difficulty with the solution process will cause explanatory messages to be displayed. Errors caused by forbidden nonlinear operations are reported at this stage.
Note
When the solver does not provide a dual solution (.m), then GAMS does not print the marginal column in the solution listing and set the marginal field in variables and equations to NA.

The outputs from these steps, including any possible error messages, are discussed in detail in chapter GAMS Output.

Programs with Several Solve Statements

Several solve statements can be processed in the same program. The next few subsections discuss various instances where several solve statements may be needed in the same file. If sequences of expensive or difficult models are to be solved, it might be useful to interrupt program execution and continue later. For details on this topic, see chapter The Save and Restart Feature.

Several Models

If there are different models then the solves may be sequential, as below. Each of the models in [PROLOG] consists of a different set of equations, but the data are identical, so the three solves appear in sequence with no intervening assignments:

Solve nortonl using nlp maximizing z;
Solve nortonn using nlp maximizing z;
Solve nortone using nlp maximizing z;

When there is more than one solve statement in the program, GAMS uses as much information as possible from the previous solution to provide a starting point or basis in the search for the next solution.

Loop: One Model, Different Data

Multiple solves may also occur as a result of a solve statement within a loop statement. Loop statements are introduced and discussed in detail in chapter Programming Flow Control Features; here we show that they may contain a solve statement and thus lead to multiple solves within one model. The example from [MEANVAR] computes the efficient frontier for return and variance for a portfolio selection problem at equidistance points.

loop(p(pp),
   v.fx = vmin + (vmax-vmin)/(card(pp)+1)*ord(pp) ;
   Solve var1 maximizing m using nlp ;
   xres(i,p)         = x.l(i);
   xres('mean',p)    = m.l;
   xres('var',p)     = v.l;
);

The set p is a set of point between the minimum and maximum variance, it is the driving set of the loop. A variance variable v is fixed at a equidistance points. With each iteration through the loop another variance level is used, the NLP model var1 is solved for each iteration and the outputs are stored in the parameter xres(*,pp), to be used later for reporting. As often for reporting purposes, the universal set * is used.

This example demonstrates how to solve the same model (in terms of variables and equations) multiple times with slightly different data. For such situations the Gather-Update-Solve-Scatter (GUSS) facility improves on the loop implementation by saving generation time and minimizing the communication with the solver. GUSS is activated by the additional keyword scenario in the solve statement followed by a set name that provides mapping information between parameters in the model and the scenario containers. A GUSS implementation of the loop would look as follows:

parameter vfx(p), px(p,i), pm(p);
set dict / p  .scenario.''
           v  .fixed   .vfx
           x  .level   .px
           m  .level   .pm /;
vfx(p(pp)) = vmin + (vmax-vmin)/(card(pp)+1)*ord(pp);          
Solve var1 maximizing m using nlp scenario dict;
xres(i,p)      = px(p,i);
xres('mean',p) = pm(p);
xres('var',p)  = vfx(p);

Customizing Solution Management: SolveOpt

It is important to consider how GAMS manages solutions if multiple models are solved. By default, GAMS merges subsequent solutions with prior solutions. This is not an issue if all models operate over the same set of variables. However, recursive procedures, different equation inclusions or logical conditions may cause only part of the variables or different variables to appear in the models to be solved. In such a case it might be useful to modify the solution management procedure using the model attribute or option SolveOpt.

Sensitivity or Scenario Analysis

Multiple solve statements can be used not only to solve different models, but also to conduct sensitivity tests, or to perform case (or scenario) analyses of models by changing data or bounds and then solving the same model again. While some commercial LP systems allow access to "sensitivity analysis" through GAMS it is possible to be far more general and not restrict the analysis to either solver or model type. This facility is even more useful for studying many scenarios since no commercial solver will provide this information.

An example of sensitivity testing is in the simple oil-refining model [MARCO]. Because of pollution control, one of the key parameters in oil refinery models is an upper bound on the sulfur content of the fuel oil produced by the refinery. In this example, the upper bound on the sulfur content of fuel oil was set to 3.5 percent in the original data for the problem. First, the model is solved with this value. Next, a slightly lower value of 3.4 percent is used and the model is solved again. Finally, the considerably higher value of 5 percent is used and the model is solved for the last time. Key solution values are saved for later reporting after each solve. This is necessary because a following solve replaces any existing values. The key solution values are the activity levels of the process level z, a variable that is defined over a set of processes p and a set of crude oils cr. The complete sequence is:

parameter report(*,*,*) "process level report";

qs('upper','fuel-oil','sulfur') = 3.5  ;
Solve oil using lp maximizing phi;
report(cr,p,'base')  =  z.l(cr,p) ;
report('sulfur','limit','base') = qs('upper','fuel-oil','sulfur');

qs ('upper','fuel-oil','sulfur') = 3.4  ;
Solve oil using lp maximizing phi ;
report(cr,p,'one') = z.l(cr,p) ;
report('sulfur','limit','one') = qs ('upper','fuel-oil','sulfur');

qs('upper','fuel-oil','sulfur') = 5.0  ;
Solve oil using lp maximizing phi ;
report(cr,p,'two') = z.l(cr,p) ;
report('sulfur','limit','two') = qs('upper','fuel-oil','sulfur');

Display report ;

Note that the parameter report is defined over the universal set or short universe. In general, the universe is useful when generating reports, otherwise it would be necessary to provide special sets containing the labels used in the report. Any mistakes made in spelling labels used only in the report should be immediately apparent, and their effects should be limited to the report. The parameter qs is used to set the upper bound on the sulfur content in the fuel-oil, and the value is retrieved for the report. Note that the display statement in the final line is introduced and discussed in detail in chapter The Display Statement. This example shows not only how simply sensitivity analysis can be done, but also how the associated multi-case reporting can be handled.

The output from the display statement is shown below. Observe that there is no production at all if the permissible sulfur content is lowered. The case attributes have been listed in the row SULFUR.LIMIT. Section Global Display Controls contains more details on how to arrange reports in a variety of ways.

----    225 PARAMETER report  process level report

                         base         one         two

mid-c .a-dist          89.718                  35.139
mid-c .n-reform        20.000                   6.772
mid-c .cc-dist          7.805                   3.057
w-tex .cc-gas-oil                               5.902
w-tex .a-dist                                  64.861
w-tex .n-reform                                12.713
w-tex .cc-dist                                  4.735
w-tex .hydro                                   28.733
sulfur.limit            3.500       3.400       5.000
Note
For other ways to do comparative analyses with GAMS, see the tutorial Comparative Analyses with GAMS.

Iterative Implementation of Non-Standard Algorithms

Another use of multiple solve statements is to permit iterative solution of different blocks of equations, most often using solution values from the first solve as data for the next solve. These decomposition methods are useful for certain classes of problems because the subproblems being solved are smaller, and therefore more tractable. One of the most common examples of such a method is the Dantzig-Wolfe decomposition.

An example of a problem that is solved in this way is a multi-commodity network flow problem in [DANWOLFE].

Choosing a Solver

After a model has been checked and prepared as described above, GAMS passes the model to a solver. When the GAMS system is installed default solvers for all model types are specified and these solvers are used if the user doesn't specify anything else. It is easy to switch to other appropriate solvers provided the user has the corresponding license. There are multiple ways to switch solvers:

  1. Using a command line parameter of the following form:
    gams mymodel model_type=solver name
    For example,
    gams mymodel lp=cbc
  2. With an option command of the following form that is placed before the solve statement:
    Option model_type=solver_name;
    Here option is a keyword, model_type is the same model type that is used in the solve statement and solver_name is the name of one of the available solvers. For example,
    Option LP=cbc, NLP=conopt, MIP=cbc, MINLP=default;
    The MINLP=default switches back to the default solver for the MINLP model type.
  3. Instead of providing a particular solver for a model type, the option Solver can be used to use a given solver for all model types this solver can handle.
    Option Solver=cbc;
  4. (Re)running gamsinst at any time and altering the choice of default solver as described in the installation notes.
Note
A list of all solvers and current default solvers may be generated in the listing file with Option SubSystems;.

Making New Solvers Available with GAMS

This short section is to encourage those of you who have a favorite solver not available through GAMS. Linking a solver program with GAMS requires some programming skills and the use of libraries provided by GAMS. There is a collection of open source solver links to GAMS at the COIN-OR project GAMSLinks. The benefits of a link with GAMS to the developer of a solver are several. They include:

  • Immediate access to a wide variety of test problems.
  • An easy way of making performance comparisons between solvers.
  • The guarantee that a user has not somehow provided an illegal input specification.
  • Elaborate documentation, particularly of input formats, is not needed.
  • Access to the existing community of GAMS users, for marketing or testing.

This completes the discussion of the model and solve statements.