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

• Solver-Related Options for the list of solve-related options that can be set via the command line,
• Options that Control Solver-Specific Parameters and Options that Control the Choice of Solver for the list of solve-related options that can be set via the option statement, and
• Model Attributes Mainly Used Before Solve for the list of solve-related model attributes.

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.
• Many solvers echo the content of the option file to the log. This echo can be supressed with the option line echo off. The echo is enabled again with the line echo on. This can be useful if the option file contains a large number of dot options or indicator constraints.
• 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.

Options can also be defined by generating an options file within the GAMS source code. Consider the following code fragment for using MINOS options file,

Model m /all/;
Option NLP = MINOS;
* MINOS options file
$onecho > minos.opt
scale option 2
completion partial
$offecho
m.OptFile = 1;
Solve m maximizing z using nlp ;

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:

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:

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, the 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 whose bounds would forbid this value. In this case, the bound closest to zero is used.

In addition 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 algorithms make use of a different form of starting information. An active-set algorithm tries to identify which constraints are active (or binding) in a feasible or optimal solution, that is, which variables are at one of their bounds and for which equations the activity equals the right-hand-side and the marginal is non-zero. For example, the simplex method for linear programs is an active-set algorithm. The classification of constraints as either active or inactive is closely linked to a basis. Active constraints are called nonbasic and inactive constraints are called basic. A basis that specifies the active and inactive constraints in an optimal solution is called an optimal basis.

Active-set algorithms may start by guessing an initial basis and then iteratively updating this basis until an optimal basis is found. Solution time may be reduced substantially if a good approximation of the optimal basis can be identified and passed on to the solver. Such a user-provided initial basis is called an advanced basis. However, provision of an advanced basis does not always help. For example, the presolving algorithms used in some solvers may cause the advanced basis to be ignored. Further, solvers may perform poorly when the advanced basis provided is worse than what the solver would otherwise have constructed with its own heuristics. Finally, not all algorithms benefit from the provision of an advanced basis: interior-point algorithms are a notable example.

GAMS provides a hint to the solver to suggest whether a basis can or should be extracted from the initial point. The hint is based on the number of rows (aka single equations) with nonzero marginals and the value of the bratio option and is computed internally as:

  hint := (0 == bRatio) or (rowsWithNonzeroMarg > nRows * bratio)

While the setting of the variable level and marginal values is important in specifying an advanced basis, only the marginal values for the rows are relevant in computing the basis hint and in choosing a value for bratio. For example, in a problem with 1000 rows and with the default value of bratio (0.25), GAMS would suggest a basis only if at least 250 nonbasic rows exist.

Note that the default starting point - all marginals zero - 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 will cause the basis hint to be false and suppress the use of an initial basis. Setting the model attribute defpoint to 1 or 2 will achieve the same result. Conversely, setting bratio to 0 will force the basis hint to be true.

Active-set solvers in GAMS typically use the basis hint value to decide whether to extract (and use) the advanced basis available in the starting point. Details can vary by solver, but typically it works 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 the level value is equal one of the variable bounds. The marginal values may also be used here: nonbasic variables correspond with non-zero marginal values.
• Equations with non-zero marginal are suggested to be nonbasic. Otherwise, they are suggested to be basic.

Thus, a user can 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 predicted to be active in a solution
• non-zero marginals for variables that are predicted to be at their bound in a solution
• non-zero levels for the variables that are predicted to be non-zero in a solution

Trace Features

Sometimes it might be useful to get certain information about a particular solve statement (or GAMS job) in a compact and customizable format.

• The Trace file facility allows to create files containing information about the "end data" of a GAMS job and the contained solve statements.
• The Solve trace facility can provide more detailed information about the solution progress of a particular solve statement (e.g. objective value of the incumbent solution or the best dual bound every five seconds)

Trace File

The trace file contains information about the "end data" of a GAMS job and the contained solve statements. Creation of a trace file can be activated via command line parameter trace (see example below). The trace feature supports several predefined formatting options, that is differently formatted trace files can be created, depending on what output information is desired. The trace file format option can be set via command line parameter traceOpt. The trace file header defines the contained trace records and the associated trace record fields.

Note

• Trace information is appended to existing trace files in the format of the existing trace file. That is, if a previous trace file of the same name already exists, then all new trace data will be appended in the initial format, no matter if the current traceopt value actually implies a different format.
• Trace file headers can be modified, i.e. the predefined formats can be customized and trace record fields can be added or removed as needed.

Trace Records

A trace file can contain different types of trace records:

Trace Record Fields

For every trace record, the trace file can contain multiple fields from the following list.

Trace Report

GAMS can create trace reports from trace files, if started with command line parameter action=gt. The following sequence of commands loads model [TRNSPORT] from the GAMS model library, runs trnsport.gms and creates a tracefile trc.txt, and produces a trace report plus a trace summary from the trace file.

$ gamslib trnsport
$ gams trnsport trace=trc.txt
$ gams trc.txt a=gt

The trace file trc.txt contains the default trace record fields for the GamsStep and GamsSolve trace records:

* Trace Record Definition
* GamsStep
* JobDate JobTime InputFileName GAMS GamsVersionID GamsReturnCode GamsErrorCount GamsStartupTime GamsCompTime GamsExecTime GamsCloseDownTime GamsTotalTime "User1"
* GamsSolve
* JobDate JobTime InputFileName ModelType SolverName SolverStatus ModelStatus SolveNumber SolveLine SolverID SolverVersion NumberOfEquations NumberOfVariables NumberOfNonZeros NumberOfNonlinearNonZeros NumberOfInstructions
*  NumberOfIterations ModelGenerationTime SolverReadTime SolverCalcTime SolverWriteTime ObjectiveValue "User1"
*
09/25/19 07:04:00 trnsport.gms GAMS WEX282-282 1 0 0.015 0 0 0.016 0.031 ""
09/25/19 07:04:00 trnsport.gms LP CPLEX 1 1 1 64 23 NA 6 7 19 0 0 4 0 NA NA NA 153.675 ""
09/25/19 07:04:00 trnsport.gms GAMS WEX282-282 0 0 0 0 0 0 0 ""

The trace summary trc.sum contains condensed information about the trace records:

Trace Summary with TL=0 for [...]\trc.txt
Trace Records = 3, Error Records = 0, First Date = 09/25/19 07:04:00

The trace report is created in trc.lst and contains detailed information about the trace records from the underlying trace file including a ModelSolveStat matrix that assigns a score from 0 to 9 to all potential combinations of model status and solver status:

[...]
Trace Report for File: [...]\trc.txt


Using ModelSolveStat for TL=0

      1  2  3  4  5  6  7  8  9 10 11 12 13
   1  9  .  .  .  .  .  .  .  .  .  .  .  .
   2  9  9  9  9  9  .  .  9  .  .  .  .  .
   3  9  .  .  .  .  .  .  .  .  .  .  .  .
   4  9  .  .  .  .  .  .  .  .  .  .  .  .
   5  9  .  .  .  .  .  .  .  .  .  .  .  .
   6  .  5  5  5  5  .  .  5  .  .  .  .  .
   7  9  9  9  9  9  .  .  9  .  .  .  .  .
   8  9  9  9  9  9  .  .  9  .  .  .  .  .
   9  .  5  5  5  5  .  .  5  .  .  .  .  .
  10  9  .  .  .  .  .  .  .  .  .  .  .  .
  11  .  .  .  .  .  .  5  .  .  .  .  .  .
  12  .  .  .  .  .  .  .  .  .  .  3  .  3
  13  .  .  .  .  .  .  .  .  3  3  .  3  .
  14  4  4  4  4  4  6  .  4  .  .  .  3  .
  15  9  .  .  .  .  .  .  .  .  .  .  .  .
  16  9  .  .  .  .  .  .  .  .  .  .  .  .
  17  9  .  .  .  .  .  .  .  .  .  .  .  .
  18  9  .  .  .  .  .  .  .  .  .  .  .  .
  19  9  .  .  .  .  .  .  .  .  .  .  .  .


Marked trace records are listed below:

Record  Date     Time     Filename        Type    Solver       Message
        * Trace Record Definition
        * GamsStep
        * JobDate JobTime InputFileName GAMS GamsVersionID GamsReturnCode GamsErrorCount GamsStartupTime GamsCompTime GamsExecTime GamsCloseDownTime GamsTotalTime "User1"
        * GamsSolve
        * JobDate JobTime InputFileName ModelType SolverName SolverStatus ModelStatus SolveNumber SolveLine SolverID SolverVersion NumberOfEquations NumberOfVariables NumberOfNonZeros NumberOfNonlinearNonZeros NumberOfInstructions
        *  NumberOfIterations ModelGenerationTime SolverReadTime SolverCalcTime SolverWriteTime ObjectiveValue "User1"
        *

First time stamp = 09/25/19 07:04:00
Last  time stamp = 09/25/19 07:04:00

Total trace records   =     3
Total comment records =     7



Total GAMS records  =     2  all return codes

                          1  RC= 0  Normal completion
                          1  RC= 1  Executing subsystem

Time (sec)             total        mean
   start                0.01        0.01
   compile              0.00        0.00
   execute              0.00        0.00
   closedown            0.02        0.01
   total                0.03        0.02



Total SOLVE records =     1  all return codes

      solvestatus         1  RC= 1  1 Normal Completion

      modelstatus         1  RC= 1  1 Optimal

Numbers                total        mean
   equations               6        6.00
   variables               7        7.00
   nonzeros               19       19.00
     nonlinear             0        0.00
   instruction             0        0.00
   equations               6        6.00
Time (sec)             total        mean
   generation           0.00        0.00
   input                0.00        0.00
   calculation          0.00        0.00
   output               0.00        0.00
   total solve          0.00        0.00


SOLVESTAT Cross Tabulation

             1    2    3    4    5    6    7    8    9   10   11   12   13    tot
     LP      1    .    .    .    .    .    .    .    .    .    .    .    .      1
  total      1    0    0    0    0    0    0    0    0    0    0    0    0      1


MODELSTAT Cross Tabulation

             1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19    tot
     LP      1    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .      1
  total      1    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0      1


GTRACE      TIME     =        0.000 SECONDS        VERID WEX282-282
[...]

The trace report may be particularly interesting, if the underlying trace file contains multiple trace records from different solve statements. In combination with command line parameter traceLevel, it is easy to filter for GamsSolve trace records with a low ModelSolveStat score, i.e. undesirable combinations of model status and solver status. If we run [TRNSPORT] again with an iteration limit of 0 (remember that the trace information will be appended to the trace file from the example above) and recreate the trace report as follows

$ gams trnsport trace=trc.txt iterlim=0
$ gams trc.txt a=gt

the trace report shows two solve records and the obtained statuses:

Total SOLVE records =     2  all return codes

      solvestatus         1  RC= 1  1 Normal Completion
      solvestatus         1  RC= 2  2 Iteration Interrupt

      modelstatus         1  RC= 1  1 Optimal
      modelstatus         1  RC= 6  6 Intermediate Infeasible

A look at the ModelSolveStat matrix from the initial example, tells us that a combination of model status 6 (Intermediate Infeasible) in combination with solve status 2 (Iteration Interrupt) results in a score of 5. If we increase the traceLevel to a value greater than or equal to 5 and recreate the trace report again, e.g. via

$ gams trc.txt a=gt tracelevel=5

the ModelSolveStat matrix at the beginning of the trace report changes such that only the scores greater than 5 for accepted combinations of model and solver status are shown

Using ModelSolveStat for TL=5

      1  2  3  4  5  6  7  8  9 10 11 12 13
   1  9  .  .  .  .  .  .  .  .  .  .  .  .
   2  9  9  9  9  9  .  .  9  .  .  .  .  .
   3  9  .  .  .  .  .  .  .  .  .  .  .  .
   4  9  .  .  .  .  .  .  .  .  .  .  .  .
   5  9  .  .  .  .  .  .  .  .  .  .  .  .
   6  .  .  .  .  .  .  .  .  .  .  .  .  .
   7  9  9  9  9  9  .  .  9  .  .  .  .  .
   8  9  9  9  9  9  .  .  9  .  .  .  .  .
   9  .  .  .  .  .  .  .  .  .  .  .  .  .
  10  9  .  .  .  .  .  .  .  .  .  .  .  .
  11  .  .  .  .  .  .  .  .  .  .  .  .  .
  12  .  .  .  .  .  .  .  .  .  .  .  .  .
  13  .  .  .  .  .  .  .  .  .  .  .  .  .
  14  .  .  .  .  .  6  .  .  .  .  .  .  .
  15  9  .  .  .  .  .  .  .  .  .  .  .  .
  16  9  .  .  .  .  .  .  .  .  .  .  .  .
  17  9  .  .  .  .  .  .  .  .  .  .  .  .
  18  9  .  .  .  .  .  .  .  .  .  .  .  .
  19  9  .  .  .  .  .  .  .  .  .  .  .  .

and GAMS throws an execution error

--- Starting trace report generation
*** Status: Execution error(s)

The trace file facility in combination with the trace report can be particularly useful for automated quality assurance tests where certain expected outcomes should be audited.

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:

A sample solve trace file including statistics of a GAMS run using the MIP model [DICE] and the solver XPRESS looks as follows:

* miptrace file miptrace.mtr: ID = XPRESS.1 Instance = dice
* fields are lineNum, seriesID, node, seconds, bestFound, bestBound
1, S, 1, 0.078, na, na
2, N, 101, 0.781, 21, 23.9369
3, N, 201, 0.875, 21, 23.5564
4, N, 304, 1.031, 21, 23.5564
5, E, 399, 1.094, 21, 21
* miptrace file miptrace.mtr closed

See also the slides for the presentation Advanced Use of GAMS Solver Links (2013) and the accompanying scripts 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:

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 infeasibilities 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:

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.

Note

The elements of the cut index set must form a series of integers starting at 1 (1, 2, 3,...).

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 indices 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:

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. Furthermore, the callback UserLazyConCall allows to add lazy constraints after an incumbent has been found.

The following parameters control the incumbent callbacks:

Examples

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

• bchtlbas.gms : Trim Loss Minimization with Heuristic using BCH Facility This model implements a very simple LP/MIP based primal heuristic for the trimloss minimization problem.
• bchfcnet.gms : Fixed Cost Network Flow Problem with Cuts using BCH Facility This model implements simple but difficult to separate cuts for a network design problem. The global solver BARON is used to find violated cuts by solving a non-convex MINLP.
• bchmknap.gms : Multi knapsack problem using BCH Facility This model implements simple cover inequalities for the multi-knapsack problem.
• bchoil.gms : Oil Pipeline Design Problem using BCH Facility This is the most complex example. It implements three different primal heuristics: an initial heuristic based on a simplified cost structure, a rounding heuristic, and a local branching heuristic. In addition, complex cuts are generated by solving regionalized versions of the original problem.
• dicegrid.gms : MIP Decomposition and Parallel Grid Submission - DICE Example This example uses many of the UserJobID option to rename files, since running multiple jobs in parallel requires the use of different filenames. This example also uses the incumbent reporting call UserIncbICall.
• solnpool.gms : Cplex Solution Pool for a Simple Facility Location Problem This example uses the incumbent checking call UserIncbCall as an advanced filter for accepting or rejecting solutions found by CPLEX.

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.

• GAMS Blog: An Overview of Math Programming Solvers
• T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R. Bixby, E. Danna, G. Gamrath, A. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D. Steffy, K. Wolter, MIPLIB 2010, Mathematical Programming Computations, 3:2 (2011) 103-163. preprint
• M. Bussieck and S. Vigerske, MINLP Solver Software (2014).
• SNOPT vs. IPOPT: P. Gill, M. Saunders, E. Wong, On the Performance of SQP Methods for Nonlinear Optimization, 2015
• H. Mittelmann: Decision Tree for Optimization Software and Benchmarks for Optimization Software

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 3 is well suited for models with very non-linear constraints. If you experience that MINOS has problems achieving feasibility 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 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 significantly 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.