Solver Usage

For the novice GAMS user, solver usage can be very simple: one runs the model and inspects the listing file to see what the solution is. No knowledge of solver options or solver specific return codes is required. While this is enough for some users, most will quickly find they need some basic knowledge of how to control the solver and interpret the results. Section Controlling a Solver via GAMS Options describes how to set the GAMS options that control a solver. Further, most solvers allow the user to set additional, solver-specific options. These can be set via a solver specific options file, which will be discussed in Section The Solver Options File. However, use of generic GAMS options should be prefered, since a GAMS option setting applies to all solvers and is interpreted by the solvers in a consistent way.

A number of solvers can make use of an initialization of variable and equation values. This will be discussed in Starting Point and Initial Basis.

Further solver specific topics, which are more interesting for advanced users, are discussed in the Sections Solve trace and Branch-and-Cut-and-Heuristic Facility (BCH).

For some hints on how to select a solver, see Choosing an appropriate Solver.

Controlling a Solver via GAMS Options

GAMS options can be set on the GAMS command line, e.g.,

$ gams trnsport iterlim = 100

Additionally, they can be set by an option statement within a GAMS model, e.g.,

option iterlim = 100;

Finally, a model attribute can set a GAMS option for an individual model:

mymodel.iterlim = 100;

The model suffix takes precedence over the option statement, which takes precendence over the command line parameters. If none of these methods is used to set an option, default values apply.

Further, one can unset any model-specific option by assigning it the value NA:

mymodel.iterlim = NA;

Unfortunately, not every option can be via as command line parameter, option statement, and model attribute. We refer to

The Solver Options File

To specify solver-specific options, it is necessary to use a solver option file. Two things are required to do this: one must create an option file having a proper name, and one must tell the solver to read and use this option file.

To tell a solver to use an option file, one can set the optfile model attribute or the optfile option to a positive value. For example,

model mymodel /all/;
mymodel.optfile = 1;
solve mymodel using nlp maximizing dollars;

The option file takes its name from the solver being used: solvername.XYZ, where solvername is the name of the solver that is specified, and the suffix XYZ depends on the value to which optfile has been set. If its value is 1, the suffix is opt. For example, the option file when calling CONOPT would be called conopt.opt. See the documentation on optfile for more information.

The format of the options file can change marginally from solver to solver. The following illustrates some frequent features of the option file format. However, solvers may vary from this format. Thus, the solver-specific documentation should be checked before using an option file.

  • Blank lines in an option file are ignored.
  • A comment line might begin with an asterisk (*) in the first column, is not interpreted by either GAMS or the solver, and is used purely for documentation.
  • Each non-comment line contains only one option specification.
  • The format for specifying options is as follows:
      keyword(s) [modifier] [value]
    The keyword may consist of one or more words and is not case sensitive. The value might be an integer, a real, or a string. Real numbers can be expressed in scientific format, e.g., 1e-6. Note that not all options require modifiers or values.
  • Any errors in the spelling of keyword(s) or modifiers will lead to that option being misunderstood and therefore ignored. Errors in the value of an option can result in unpredictable behavior. When detected, errors are either ignored or pushed to a default or limiting value, but not all can or will be detected.

Consider the following CPLEX options file,

* CPLEX options file
barrier
crossover 2

The first line begins with an asterisk and therefore contains comments. The first option specifies the use of the barrier algorithm to solve the linear programming problem, while the second option specifies that the crossover option 2 is to be used. Details of these options can be found in Summary of CPLEX Options.

Consider the following MINOS options file,

* MINOS options file
scale option 2
completion partial

The first option sets the scale option to a value of 2. In this case, the keyword 'scale option' consists of two words. In the second line, the completion option is set to partial. Details of these options can be found in Summary of MINOS Options.

Dot Options

Dot options in a solver option file allow users to associate values to variables and equations using the GAMS name of the variables and equations. The general syntax of a dot option in the option file is as follows:

(variable/equation name).optionname (value)

Dot options can be specified for all, a block, a slice, and a single variable and equation. Please note that a specific dot option may only apply to variables or equations (e.g. the GAMS/Gurobi dot option prior applies to variables only). The following example makes the use of the dot option clear.

For example, suppose one has a GAMS declaration:

Set i /i1*i5/;
Set j /j2*j4/;
Variable v(i,j);
Equation e(i,j);

Consider the following lines in an option file with the imaginary option name dotopt:

Line in option file Explanation
variables.dotopt 1 Sets the value of all variables to 1
equations.dotopt 2 Sets the value of all equations to 2
v.dotopt 3 Sets the value of the variables in block v to 3
e.dotopt(*,*) 4 Sets the value of the equations in block e to 4
v.dotopt(*,’j2’) 5 Sets the value of the variables v that have j2 in the second index position (slice) to 5
e.dotopt(’i3’,*) 6 Sets the value of the equations e that have i3 in the first index position (slice) to 6
w.dotopt(’i2’) 7 Sets the value of the single variables v(’i2’) to 7
e.dotopt(’i3’,’j3’) 8 Sets the value of the single equations e(’i3’,’i3’) to 8

The values of the dot option are applied in correspondence to the sequence in which they appear in the option file. In the current example, the values of dotopt for the equation e would be as follows:

e.dotopt i1 i2 i3
j2 4 4 6
j3 4 4 8
j4 4 4 6

Starting Point and Initial Basis

Starting Point

NLP solvers that search for a locally optimal solution of a NLP require an initial point to start their search. Further, as closer this initial point is to a local optimum, the less effort the solver may have to spend. The latter can also be true for solvers that search for global optimal solutions, such as most LP or MIP solver or global MINLP solvers.

Because of this immense importance of a starting point, GAMS always passes a starting point to a solver. By default, the point passed on by GAMS is given by the level and marginal attributes of variables and equations. If these values have not been set yet, default values are used. This default value is zero, except for variables which bounds would forbid this value. In this case, the bound closest to zero is used.

Next to setting these values explicitly in a GAMS model, a user can also load them from a save file or a GDX point file via execute_loadpoint. The latter may have been generated by running a related model and using option savepoint. Further, in models with several solve statements, the solution from one solve, if any, is used to initialize the starting point for a succeeding solve. This happens automatically since solutions from a solve statements are also stored in the level and marginal values of variables and equations. Finally, note that model attribute defpoint can be used to force sending the default starting point to a solver.

For some solvers, in particular for MIP or MINLP, an option may have to be set to make use of the starting point. Further, some solvers offer the possibility to make use of a partial starting point or use the starting point as a guide for the search. For details, see the specific solver manuals and look for parameters like mipstart and the use of the GAMS parameter tryint.

Initial Basis

While for some solvers, the values of a starting point are sufficient to initialize the search, active-set based algorithms make use of a different form of starting information. An active-set based algorithms tries to identify which constraints are active (or binding) in a feasible or optimal solution, that is, which variable are at one of their bounds (if any) and for which equations the activity equals to the right-hand-side. For linear programs, the simplex algorithm is such an algorithm. The classifications of constraints into active and inactive ones is called a basis. Active constraints are called nonbasic and inactive constraint are called basic. A basis that specifies the active constraints in an optimal solution is called an optimal basis.

Active-set based algorithms may start by guessing an initial basis and then iteratively update this basis by switching the basic-status of constraints until an optimal basis is found. Therefore, solution time may be reduced substantially if one can identify a priori a good approximation of an optimal basis. Such a user-provided initial basis is also called an advanced basis. However, provision of an advanced basis does not always help. Especially presolving algorithms in a solver may cause that a user provided initial basis is ignored. Further, solvers may perform poorly when the given basis is "worse" than what the solver would otherwise have constructed with its own heuristics. Finally, it is needless to say that only active-set based algorithms are amenable to the use of an initial basis.

If sufficient information is available in the starting point, then GAMS uses these values to automatically form an initial basis for a solver. This basis is formed as follows:

  • Variables with a zero level value are suggested to be nonbasic, if and only if they have a non-zero marginal value.
  • Variables with a non-zero level value are suggested to be nonbasic, if and only if the level value equals to one of the variable bounds. As a variable at one of their bounds indicates that the bound may be binding, nonbasic variables should also have non-zero marginal.
  • Equations with non-zero marginal are suggested to be nonbasic. Otherwise, they are suggested to be basic.

Next, GAMS decides whether the so formed basis contains sufficiently many nonbasic entries. It does so by checking whether the number of nonbasic entries in the basis exceeds the number of equations times the value of GAMS option bratio. Thus in a problem with 1000 equations and with the default value of bratio (0.25), GAMS will not suggest a basis unless it could find at least 250 nonbasic constraints.

Note, that the default starting point is usually not sufficient for the construction of an initial basis. If the automatic transfer of a basis from one solve statement to the next leads to poor behavior in the solver, setting the option bratio to 1 or the model attribute defpoint to 1 can suppress the use of an initial basis.

A user can also attempt to explicitly provide an initial basis by setting a corresponding starting point. That is, one can set a guess for an initial basis by specifying

  • non-zero marginals for equations that are felt to be active in a solution
  • non-zero marginals for variables that are felt to be at their bound in a solution
  • non-zero levels for the variables that are felt to be non-zero in a solution

Solve trace

In order to do accurate performance evaluations it may be useful to obtain more detailed information about a solve than the "end data" that the trace file provides. E.g., for a branch-and-bound based solver, one may want to have intermediate information about the values of primal and dual bounds at the root node and subsequent nodes within the search.

The solve trace option that is implemented in some of the GAMS solver interfaces allows users to output solve information, e.g., primal and dual bounds, for every n nodes or at every time step. For example, the user may be interested in the objective value of the incumbent solution or the best dual bound on the optimal value every 50 nodes and every five seconds of the solve.

Note
The solve trace file format and options may change in a future GAMS release.

The solve trace option is invoked via a GAMS solver options file. Usually, options to specify a filename of the trace file to be created and options to specify time and node intervals are available. Please refer to the GAMS solver manuals for the exact names of these options (search for solvetrace or miptrace).

The solve trace file is written in comma-separated-value (CSV) format, where the entries in each line have the following meaning:

Column Name Meaning
lineNum a line index
seriesID indicator why the line was written: S = start of search, N = node frequency, T = time frequency, E = end of search
node number of enumerated branch-and-bound nodes
seconds time since the solving started
bestFound primal bound, i.e., objective value of incumbent solution
bestBound dual bound, i.e., bound on optimal value

A sample solve trace file is miptrace.mtr where the file includes statistics of a GAMS run using the MIP model blend2 from the Performance Library and the solver XPRESS. See also the slides for the presentation Advanced Use of GAMS Solver Links (2013) for some ideas on what to do with the solve trace functionality.

Branch-and-Cut-and-Heuristic Facility (BCH)

Global search algorithms can sometimes significantly benefit from user supplied routines that support the solution process of an hard optimization problem. For example, branch-and-cut solvers (e.g., CPLEX, Gurobi, SCIP, Xpress) can profit from user-supplied cutting planes or good feasible solutions. GAMS users could supply these as part of the model given to the solver, by adding a set of constraints representing likely to be violated cuts and an initial solution (possibly in combination with GAMS parameters like tryint and solver-specific options like mipstart in CPLEX). However, this does not allow a dynamic interaction between a running solver and user supplied routines that, for example, use a current relaxation solution to construct cutting planes or feasible solutions. The GAMS Branch-and-Cut-and-Heuristic (BCH) facility attempts to automate all major steps necessary to make callbacks that certain solvers provide for such usage available to the GAMS user. This allows GAMS users to apply complex solution strategies without having to have intimate knowledge about the inner workings of a specific solver.

Currently, only two solvers support the BCH facility: CPLEX and SBB. With GAMS/CPLEX, user supplied GAMS programs that implement primal heuristics and cut generation can be used. With SBB, only primal heuristics are possible.

As the name indicates, the BCH facility has been designed with the solving process of a branch-and-cut solver (e.g., CPLEX, Gurobi, SCIP, Xpress) in mind. Such solvers often allow to call a user supplied routine after a node in the branch-and-bound (B&B) tree has been processed. Within that routine, available information like the solution of a relaxation (often an LP or NLP) at that node and the current incumbent, if any, is exported by the BCH facility into a GDX file using the original GAMS namespace. Next, different user supplied GAMS programs can be called, e.g., for finding cuts which are violated by the relaxation solution (cut generator) or to find new incumbents (primal heuristic). These GAMS programs should import the information from the GDX file and do their computations. After termination, the BCH facility resumes control, reads the findings from the GAMS program and passes them to the solver.

A relaxation solution may be exported into a file bchout.gdx by the BCH facility. This GDX file does not only contain the variable values as level values (.l), but also variable bounds (.lo and .up). For a B&B solver, these are the local bounds at this node. Hence, they reflect branching decisions made in the B&B tree and bound tightenings that were deduced by the solver. In a similar way, the BCH facility may export an incumbent solution to the GDX file bchout_i.gdx. The bounds for the incumbent solution reflect global bounds, i.e., the original bounds, possibly tightened by the solver. GDX files can be imported by the GAMS program using the compile time $load or run time execute_load.

The BCH facility is activated and controlled by setting certain options in the solvers options file. The precise names and meanings of the options may vary from one solver to another. Therefore, also the corresponding GAMS solver manual should be checked. The options that come with the BCH facility can be used to define the calls of the users GAMS programs, to determine when they should be called, and to overwrite the filenames for the GDX files (to avoid name clashes). General BCH related options are the following:

Name Description Default
UserGDXIn The name of the GDX file read back into the solver. bchin.gdx
UserGDXName The name of the GDX file exported from the solver with the solution at the node. bchout.gdx
UserGDXNameInc The name of the GDX file exported from the solver with the incumbent solution. bchout_i.gdx
UserGDXPrefix Prefix to add to UserGDXIn, UserGDXName, and UserGDXNameInc empty
UserJobID Postfix to add to listing and log filenames and to UserGDXIn, UserGDXName, and UserGDXNameInc. Further, --UserJobID is added to calls to users GAMS programs. empty
UserKeep Calls users GAMS programs with gamskeep instead of gams. 0

In the following, the interface for the available callbacks are explained in more detail and corresponding options are listed.

Primal Heuristics

In the primal heuristic callback, the user can provide a GAMS program which tries to construct a feasible solution based on the information provided by the solver, e.g., a current relaxation solution and the current incumbent. Thus, the GAMS program could attempt to repair infeasibilities in the relaxation solution or try to improve the incumbent from the solver.

If the GAMS program finds a new solution, it should store it in the level values of variables that correspond to the original variables. For example, if the original model uses binary variable open(i,t), then at the end of the GAMS program open.l(i,t) should contain a 0 (zero) or a 1 (one). The BCH facility calls the GAMS program and instructs GAMS to store the results in a GDX file at termination. This GDX file is then read in again by the BCH facility and the solution is passed back to the solver. The solver checks this solution for infeasibilties and in case this check is passed and the solution is better than the best known solution, the solver updates it's incumbent.

If the GAMS program cannot find a feasible solution, it can terminate with an execution error triggered by an abort statement to prevent the BCH facility from reading the results from the heuristic run.

BCH parameters to control the primal heuristic call are typically the following:

Name Description Default
UserHeurFreq Determines the frequency of the heuristic call. 10
UserHeurMult Determines the multiplier for the frequency of the heuristic call. 2
UserHeurIntervalDetermines the interval when to apply the multiplier for the frequency of the heuristic call. For example, for the first 100 (UserHeurInterval) nodes, the solver calls the heuristic every 10th (UserHeurFreq) node. After 100 nodes, the frequency gets multiplied by 10 (UserHeurMult), so that for the next 100 nodes the solver calls the heuristic every 20th node. For nodes 200-300, the heuristic get called every 40th node, for nodes 300-400 every 80th node and after node 400 every 100th node. 100
UserHeurFirst For how many of the first nodes the heuristic should be called. 10
UserHeurObjFirst Similar to UserHeurFirst, but specifices for how many of the first nodes the heuristic should be called if the optimal value of the current nodes relaxation promises a significant improvement of the current incumbent, i.e., the optimal value of the relaxation at the node has to be closer to the current dual bound than the current primal bound. solver dependent
UserHeurNewIntWhether to calls the heuristic when the solver found a new feasible solution. no
UserHeurCall Arguments to the GAMS call to invoke the heuristic GAMS program. empty

As an example, for the Oil Pipeline Network Design problem, the BCH options to invoke the primal heuristic in the GAMS program bchoil_h.inc when using GAMS/CPLEX could be

userheurcall     bchoil_h.inc mip cplex optcr 0 reslim 10
userheurfirst    5
userheurfreq     20
userheurinterval 1000

Cutting Planes

In the cut generator callback, the user can provide a GAMS program which tries to find a linear cut (that is, a linear inequality) that is violated by the relaxation solution. The solver would then add these cuts to it's cut pool. Typically, it then resolves the relaxation at the node and calls the cut generator again. If no cutting planes are found, the solver will continue, e.g., by processing the next node. Please note that the solver cannot perform validity checks on the provided cuts. Hence, it is possible to cut off areas of the feasible region, including optimal solutions.

Exporting cuts is a little more complicated than a solution because next to the cut coefficients, also the sense and the right-hand-side of the cut inequality needs to be exported. Further, exporting several cuts with one call should be possible. For this purpose, the GAMS program has to define and fill a set cc and parameters numcuts, rhs_c(cc), and sense_c(cc) appropriately. The set cc is used as a cut index. It can be larger than the number of actually generated cuts. Parameter numcuts should specify the number of added cuts. rhs_c(cc) should store the right-hand-side of each cut. Finally, sense_c(cc) should store the sense of each cut, which must be 1 for lower-equal (≤), 2 for equal (=, rather unusual for cuts), and 3 for greater-equal (≥). The corresponding declaration in GAMS code may be

$set MaxCuts 100
Set        cc          'cuts'  / 1 * %MaxCuts% /;
Parameters numcuts     'number of cuts to be added' / 0 /
           rhs_c(cc)   'cut rhs'
           sense_c(cc) 'the sense of the cuts';

The only thing missing are the cut coefficients. As it should be possible to return more than one cut, using variable attributes like level values is not sufficient. Therefore, for each variable that is part of a cut, a new parameter must be added in the GAMS program. The name of the parameter must be the name of the corresponding variable with an additional _c at the end. Further, the parameter must be indexed like the variable, but with the cut index set cc added at the beginning. For example, assume variable open(i,t) should be part of a cut. Then the cut coefficients should be stored in a parameter open_c(cc,i,t), e.g.,

Parameter  open_c(cc,i,t) 'coefficients of variable open(i,t) in cut cc';

The BCH facility reads all parameters that end in _c, takes the base name and looks for a variable with that name and indicies and builds up the cut matrix. A cut cannot introduce a new variable into the model. All cuts added to the model are assumed to be global cuts, that is, they need to be valid for the entire problem, not just for the current node.

BCH parameters to control the cut generation call are typically the following:

Name Description Default
UserCutFreq Determines the frequency of the cut generator call. 10
UserCutMult Determines the multiplier for the frequency of the cut generator call. 2
UserCutIntervalDetermines the interval when to apply the multiplier for the frequency of the cut generator call. See UserHeurInterval for details. 100
UserCutFirst Calls the cut generator for the first n nodes. 10
UserCutNewInt Whether to call the cut generator if the solver found a new integer feasible solution. no
UserCutCall Arguments to the GAMS call to invoke the cut generator GAMS program. empty

As an example, for the Oil Pipeline Network Design problem, the BCH options to invoke the cut generator in the GAMS program bchoil_c.inc when using GAMS/CPLEX could be

usercutcall   bchoil_c.inc mip cplex
usercutfirst  0
usercutfreq   0
usercutnewint yes

Incumbent Callbacks

The incumbent callbacks can be used to execute a GAMS program when the solver found a new feasible solution that improves the incumbent. Additionally, the incumbent check callback UserIncbCall can be used to notify the solver whether the given feasible solution should be accepted by the solver. This allows to implement a filtering mechanism that forces a solver to search for additional solutions even though an optimal solution might have been found already.

The following parameters control the incumbent callbacks:

Name Description Default
UserIncbCall Arguments to the GAMS call to invoke the incumbent checking GAMS program. The incumbent is rejected if the GAMS program terminates normally. In case of a compilation or execution error, the incumbent is accepted. empty
UserIncbICall Arguments to the GAMS call to invoke the incumbent reporting GAMS program. empty

Examples

The GAMS model library contains a few examples to show to use the BCH facility:

Choosing an appropriate Solver

For any of the GAMS problem classes (LP, MCP, MINLP, ...), there is no solver that is best on every problem instance. Below, we provide some links to rules of thumb on choosing a solver or solver comparisons.

Relative Merits of MINOS and CONOPT

How to choose between MINOS and CONOPT

It is almost impossible to predict how difficult it is to solve a particular model. The best and most reliable way to find out which solver to use is to try out both. However, there are a few rules of thumb:

CONOPT is well suited for models with very non-linear constraints. If you experience that MINOS has problems achieving feasiblity during the optimization, you should try CONOPT. On the other hand, if your model has few nonlinearities outside the objective function, MINOS and QUADMINOS is probably the best solver.

CONOPT is has a fast method for finding a first feasible solution that is particularly well suited for models with few degrees of freedom (this means: the number of variables is approximately the same as the number of constraints - in other words, models that are almost square). In these cases CONOPT is likely to outperform MINOS while for models with many more variables than equations MINOS is probably more suited.

CONOPT has a preprocessing step in which recursive equations and variables are solved and removed from the model. If you have a model where many equations can be solved one by one, CONOPT will take advantage of this property. Similarly, intermediate variables only used to define objective function terms are eliminated from the model and the constraints are moved into the objective function.

CONOPT has many built-in tests (e.g. tests for detecting poor scaling). Many models that can be improved by the modeler are rejected with a constructive message. CONOPT is therefore a useful diagnostic tool during model development even if another solver is used for the production runs.

Why serious NLP modelers should have both MINOS and CONOPT

It is almost impossible to predict how difficult it is to solve a particular model. However, if you have two solvers, you can try both. The overall reliability is increased and the expected solution time will be reduced.

On a test set of 196 large and difficult models, many poorly scaled or without initial values, both MINOS and CONOPT failed on 14 models. However only 4 failed on both MINOS and CONOPT. So the reliability of the combined set of solvers is much better than any individual solver.

Many examples of poorly formulated models were observed on which MINOS failed. CONOPT rejected many of the models, but with diagnostic messages pinpointing the cause of the problem. After incorporating the changes suggested by CONOPT, both MINOS and CONOPT could solve the model. Switching between the two solvers during the initial model building and debugging phase can often provide useful information for improving the model formulation.

Special Offer for two NLP Solvers

In order to encourage modelers to have two NLP solvers, GAMS offers a 50% discount on the second solver when both MINOS and CONOPT are purchased together.

PATH versus MILES

This document describes some of the differences between the MCP solvers PATH 4.7 and MILES. MILES is a free solver, that comes with the GAMS/BASE module, while PATH is an optional solver, that is charged for separately.

PATH and MILES are two GAMS solvers capable of solving mixed nonlinear complementarity problems (MCP). Both solvers are based on the sequential linear complementarity algorithm, i.e., they both solve a sequence of linear mixed complementarity problems whose solutions typically converge to the solution of the MCP. To solve each of the linear subproblems (major iterations), both codes use a generalization of an algorithm due to Lemke that is based on a sequence of pivots (minor iterations) similar to those generated by the simplex method for linear programming. To do these pivots efficiently, both codes use the same sparse linear algebra package.

As a result of the above similarities, the performance of the two codes is comparable for many "easy" models. Viewed over a broad range of problems, however, PATH is typically faster and more robust than MILES. While both codes solve all the MCP and MPSGE models in GAMSLIB, PATH signicantly outperforms MILES on the MCPLIB test collection found at CPNET.

Most sophisticated MCP and MPSGE modelers prefer to use PATH over MILES. PATH has a crashing scheme that allows it to quickly improve the user given starting point before starting to solve the linear subproblems. This frequently speeds up solution time. PATH automatically attempts to fix "singular" models using a technique based on proximal perturbations. In many cases, this enables the linear subproblems to be solved, leading to a model solution. This typically helps modelers at model development time.

PATH has many more solution options to enable it solve difficult models. The code automatically tries useful options on difficult problems using a restart procedure. PATH has a much more sophisticated "globalization" procedure that typically improves speed and robustness. PATH implements a nonmonotone watchdog technique. Stalling is frequently circumvented by allowing larger steps to be taken toward solutions.

PATH has many more diagnostic features that help uncover problems in a model. In particular, singularities in the model, zero rows and columns and several measures of optimality are returned to the user. Theoretically, PATH has better convergence properties than MILES. In particular, new merit functions are known to allow more reliable and faster convergence.