GAMS Modeling Object Design

This document gives a brief introduction to GAMS' new model-solver API, including a description of its design goals and philosophy. This document is not intended to be used as a user's manual but rather to give a picture of what the new API can do and a description of some of the conceptual underpinnings for the new API.

Further material: Presentation at ICS 2011


Historically, there have been a number of different GAMS solver interface libraries, i.e. libraries that enabled a solver to get all required information from a GAMS model, compute the solution, and return the solution, status information, and other information (e.g. solver log messages, nonlinear function evaluation error messages, node counts, time used) to GAMS. Each library was unique in some way, e.g. in the computer language or subset of GAMS model types it supported. Each library had its own advantages and disadvantages, but all of them were feature-poor and supported a limited scheme of operation: GAMS/Base would write scratch files containing the model to be solved, the GAMS solver link executable would use one of the solver interface libraries to read the model from scratch file and write a solution file, and GAMS/Base would read this solution file. While this scheme worked for many years it was inconvenient for the library user, difficult to maintain, slow, and a barrier to further development.

To address these issues and others, GAMS developed a new model-solver interface library, called GMO (GAMS Model Object), and a companion library called GEV (GAMS Environment Object). The two libraries are distinct and help to separate the purely model-specific tasks and information handled by GMO from the computing and solver environment that the model will be solved in, handled by GEV. The two libraries are typically used together and we will sometimes refer to them as simply GMO. For legacy reasons the new libraries support the old file-based scheme to communicate a model through scratch files.

In what follows, we first describe the basic structure, organization, and usage of GMO (Basic organization). Client applications can be split into two types: those defining or updating the model (Modeler Access to GMO) and those passing the model to a solver (Solver Access to GMO). We next describe some ways to update a model in Updating a GMO instance.

Basic organization

In this section we outline the basic organization of GMO. GMO is implemented as a shared library that interfaces to different languages via language-specific header files and interface code. The header files and code are included in source form with the GAMS distribution. Since the interface code employs dynamic loading, each GMO session begins with a call to initialize the required shared library (i.e. load it and all its symbols) and return an empty model object.

The next step is to load a model into the model object. This is typically done with a single wrapper call, as in the case of loading a model from model scratch files prior to solving in one of the GAMS solver links. It is also possible build up a model from scratch with a sequence of calls to provide the model column-wise or row-wise. If the model is built up column-wise or row-wise, additional information (e.g. about nonlinearities) may be passed to the object after the basic structure is built up. Once the model is complete, a finalization routine is called. This routine prepares the model object for efficient access by the user. Typically the model does not change after this point. There are exceptions to this (see Updating a GMO instance), but they usually involve small modifications to the existing model (like adding alternative bounds) or the addition of constraints and variables that require the re-finalization of the model.

When a model is fully loaded, the GMO client can start accessing the model. Typically the GMO client doing this will be a solver, but other clients (e.g. the CONVERT solver, the Examiner utility, or a model structure browser) exist also. In addition to querying the model, the client can also request that the model be presented or viewed in various different ways. For example, GMO can be requested to use an objective function or an objective variable. Most types of information are available immediately when the model is loaded, but some type of queries (e.g. Hessians, alternative QP forms) are less common and relatively expensive in time and/or space: these require that an initialization routine be called before the information is requested. Once the client has completed its work it reports on the solution found, if any. Typically, the model object is destroyed at this point. Model access by a client, especially solvers, is an important topic that is discussed in Solver Access to GMO.

The variety of data that go into the interface library when a model is defined and that a solver can request during solution is large, but the data can be divided into two types - data defining the model (e.g. number of rows and columns, coefficients, nonlinear functions) and data defining the solver environment (e.g. available and default GAMS solvers, license info, algorithm tolerances and limits). It is sometimes useful to separate these two types of data, so that it is possible to define and work with a model without specifying anything about the environment it exists in. The environment can be specified separately, and multiple models can make use of the same basic environment. To facilitate this, the solver interface is in two parts: the GMO interface deals with model-specific information and the GEV interface with information about the environment. The two environments are linked, since they are typically used together, with one (or multiple) models existing in one environment, but the separation makes it possible to define a model without defining its environment, etc. Since the bulk of the information and the code lies with GMO, we usually speak of the two libraries as one, called GMO, but it is worth remembering that GEV is a separate object.

Solver Access to GMO

One of the primary purposes of GMO is to provide convenient, efficient access to the model. GAMS links to many solvers, each solver link using GMO to access the model in different ways, so there is a wide array of possible methods to access the model in GMO. We describe them in this section.

There are multiple but equivalent views possible for the same model. For example, the model can be formulated with an objective function or with an objective variable. Free rows can be removed or left in, and the rows and/or columns can be permuted. Prior to accessing the model, the solver link can choose what view it would like to use. The view can be changed later, but since this can obviate the data obtained previously, the choice of view is usually made early on and left unchanged. Moreover, a view can be stored and restored in case multiple users access the same model.

All solvers will need to get basic information about a model - simple things like row and column counts, nonzero counts, etc. These are available via simple access routines. Since the model is essentially fixed (assuming the view does not change), basic information is pre-computed when the model takes its final form and is available at essentially no cost. Information about the rows and columns (e.g. variable level values, marginal values, variable priorities, row types) is also available, either for single rows/cols or in an array for all rows/cols at once.

For linear models, the only information left to get is the matrix of coefficients. This is available in a number of different forms e.g. column-wise or row-wise, either as a complete matrix returned with one call or as separate rows or columns returned via many calls. For nonlinear models, there are more variants on this theme: calls to return the function value or the function value and derivatives, calls for constraints and calls for the objective function. You can request that the nonlinear model be treated as its linearization around a certain point. There are also routines to do interval evaluations of functions and gradients. The GMO library prepares the model object to handle all these calls efficiently when the model takes its final form.

Nonlinear models present several additional challenges. When NL functions are evaluated, mathematical errors can occur (e.g. sqrt(-1)). GMO supports different ways to log and handle these errors. Some algorithms will require or want 2nd-order information. Since this can be relatively expensive to compute, the solver must first call an initialization routine specifying what is desired (e.g. only Hessian-vector products, Lagrangian Hessian, single-row Hessians) and potentially a limit on the memory dedicated to computing Hessians. After this initialization, 2nd-order information is available.

Once the solver finishes, the solution (if any) and related status values must be reported back to GMO. There are a number of convenience routines included in GMO for this purpose.

A convenient interface was and is an important design goal for GMO, especially in the area of solver access to the model. Convenience takes many forms: a number of ways to get the same model data in order to support a variety of different solver libraries, self-contained calls with minimal requirements on previous setup for correct behavior,and a modern interface adhering to design principles like information hiding, encapsulation, and an object model. By keeping these goals at the fore when designing GMO we have made accessing the model convenient and efficient, which greatly simplifies the task of building a correctly-functioning solver link.

In addition to providing convenient access to the model, a solver link needs to expose a particular API to be recognized by the GAMS system. This is not directly connected to the GMO API itself but knowledge about the expected solver link library API is required so we include it here.

GAMS calls a solver through the GEV API function gevCallSolver which eventually results in a sequence of calls to functions in the solver link library. GAMS loads solver link libraries dynamically at run time. The name of the library is specified in the configuration file together with the three letter audit code, e.g., cpx for CPLEX. All functions in the solver link library are prefixed by this audit code (we use xyz in this example). The following functions are recognized:

  • void xyzInitialize(void) (optional): Function called when loading the solver link library.
  • void xyzFinalize(void) (optional): Function called when unloading the solver link library.
  • int xyzCreate(void** handle, char* msg, int sizeBuf): Function to create a solver link object. Returns 0 and stores a non-NULL pointer to the object in handle on success, otherwise an error message should be stored in msg.
  • void xyzFree(void** handle): Function to destroy a solver link object.

Depending on the solver interface type (again communicated as part of the configuration file) different functions need to be in the API. For solver interface type 1 we have:

  • int xyzReadyAPI(void* handle, void* gmoHandle): Function to set up the model instance in the solver space. Returns 0 on success.
  • int xyzCallSolver(void* handle): Function to do the actual solve and solution reporting. Returns 0 on success.
  • int xyzModifyProblem(void* handle) (optional): Function to modify the problem. Returns 0 on success.

For solver interface type 2 we only have a single call:

  • int xyzCallSolver(void* handle, void* gmoHandle): Function to setup and solve. Returns 0 on success.

Usually, a solve in GAMS triggers the following sequence of function: xyzCreate, xyzReadyAPI, xyzCallSolver, xyzFree (interface type 1) or xyzCreate, xyzCallSolver, xyzFree (interface type 2) and the separation of xyzReadyAPI and xyzCallSolver seems unnecessary.

With Gather-Update-Solve-Scatter (GUSS) and the GAMSModelInstance class in various APIs we repeatedly solve a model with the same rim but different data (bounds, rhs, matrix coefficients). In this case the sequence of solves results in a sequence of function calls. Without the presence of xyzModifyProblem the following sequences will be called: xyzCreate, xyzReadyAPI, xyzCallSolver, xyzReadyAPI, xyzCallSolver, xyzReadyAPI, xyzCallSolver, ..., xyzFree (interface type 1) or xyzCreate, xyzCallSolver, xyzCallSolver, xyzCallSolver, ..., xyzFree (interface type 2). So, again there is little point (but possible) to split the link work in xyzReadyAPI and xyzCallSolver without the presence of xyzModifyProblem. If xyzModifyProblem is present (only with flavor 1) the following sequences will be called: xyzCreate, xyzReadyAPI, xyzCallSolver, xyzModifyProblem, xyzCallSolver, xyzModifyProblem, xyzCallSolver, ..., xyzFree.

Modeler Access to GMO

In normal operation the modeler creates a model in GAMS source form and the GAMS/Base module handles all the details necessary to build up model instances in GMO. However, there are cases (e.g. solving a model many times over with different scenario data) where it is useful to access and modify a GMO instance outside of GAMS/Base. GMO provides routines to support this, specifically routines to update the model (see Updating a GMO instance), solve the model with one of the GAMS solvers available as part of the GAMS environment and GEV, and retrieve the solution.

Access to a GMO instance is usually done using integer indices, [1..m] for the rows and [1..n] for the columns. However, it is also possible to reference rows and columns using the notation from the original GAMS model, e.g. x('seattle','topeka') or demand('chicago'). This is more convenient when specifying what data should be updated to define a new scenario. In order to update a model instance in this case, it is useful to have a convenient, efficient way to translate row and column indices from one form to the other. This translation is done by the model dictionary interface DCT.

The DCT API provides information about the variables, equations, and sets used to define the GMO model instance. In addition, given a row or column index, it will translate this index into the equation or variable name and the list of set labels that correspond to this index. It will also do the inverse operation, translating an equation/variable name and list of labels into a row or column index. GAMS builds models in a way that makes this translation very efficient.

This organization is also useful when updating models to create new scenarios. Models are organized so that:

  • There is one ordered universe of all labels appearing in the variables and equations of a given model. The order for the labeling does not change from symbol to symbol within a model.
  • All of the columns in a model corresponding to a given variable are contiguous. (Ditto for rows and equations)
  • The columns corresponding to a given variable are sorted by their index labels, using the universal order, with the left-most index varying slowest. (Ditto for rows and equations)
  • GDX data is sorted in the same way: sorted by index label order, left-most index varying slowest. This can be very useful, provided the model and the GDX data use the same label ordering.

Using the various GAMS component libraries, it is possible to create a model updating interface that is both convenient for the user (by using the symbolic names referenced in the GAMS source) and efficient in updating the model data.

Updating a GMO instance

There are several possible ways to modify a model contained in a GMO instance. By updating, we mean an actual model change, rather than a change in the view that doesn't alter the set of solutions.

In perhaps the simplest case, the user can specify alternate variable bounds, as is useful when implementing a branch and bound code. The original bounds are retained in this case, so that the model can be reverted to the original bounds with a single call.

It is possible to linearize a model around a given point. This requires no information from the point to linearize around and can be undone easily. This is almost a change in view but since the solutions of the original and linearized models may be quite different we can also consider this a model update.

Many algorithms (e.g. outer approximation, Benders decomposition, Danzig-Wolfe decomposition) involve the addition of rows, and columns incident on these rows, to a core model. Such algorithms can be implemented effectively using GMO by taking advantage of GMO facilities to add rows and columns. There will be only a small amount of work required to prepare the GMO instance for use after each round of additional rows and columns. Note that all the changes to the model in this case are additions: the existing structure and data are left as is.

Finally, there are facilities in GMO to update variable bounds (as mentioned before), variable types (e.g. to relax single discrete variables), and the right-hand-side of constraints. The user cannot directly modify matrix coefficients. There is a much better way to safely update exogenous data in a model: GAMS can provide a model instance in which GAMS parameters are visible and can be updated. A reevaluation of the expressions in the models provides the updated matrix elements. The underlying concept is also used in Gather-Update-Solve-Scatter (GUSS) and described in more detail in this paper. This is a powerful tool to efficiently do e.g. Monte-Carlo simulation without the need for GAMS to regenerate the entire model over and over.