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 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 # 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. 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: 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 # 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 Type Meaning GamsStep A GamsStep refers to a GAMS execution phase (there are potentially multiple phases of GAMS execution in a single GAMS Job). For example, a trace file created with traceopt=0 for the [TRNSPORT] model, which contains a single solve statement, will contain two GamsSteps, one referring top the GAMS execution phase before the solve statement, the other one referring to the execution phase after the solve statement. Note that this may change depending on the setting of solveLink. GamsExit GamsExit describes the final GamsStep. GamsSolve GamsSolve describes a trace record referring to a solve statement. If a file has multiple solve statements, the corresponding trace file can have multiple GamsSolve trace records. ### Trace Record Fields For every trace record, the trace file can contain multiple fields from the following list. Name of Field Meaning CNS CNS solver. ComputerName Computer name. Direction Direction of optimization: 0=min, 1=max. DNLP DNLP solver. EMP EMP solver. ETAlg Elapsed time it took to execute the solve algorithm (see corresponding model attribute etAlg). ETSolve Elapsed time it took to execute a solve statement in total (see corresponding model attribute etSolve). ETSolver Elapsed time taken by the solver only (see corresponding model attribute etSolver). GamsCloseDownTime The time it takes to close down GAMS (which partly depends on command line parameters) including the time to write the file summary, a GDX file, a (obfuscated) save file, a parameter file. GamsCompTime Time of the GAMS compilation phase. GamsElapsedTime Elapsed time since the start of a GAMS run in seconds. GamsElements Number of ref UG_GAMSPrograms_Labels "labels". GamsErrorCount Number of compilation and execution errors. GamsExecTime GAMS execution time. GamsLineNumber Number of lines. This corresponds to the number of lines in the echo print of the input file. GamsReturnCode GAMS return code. GamsStartupTime The time it takes to start up GAMS including the time to check and dump command line parameters, initialize certain internal data structures, loading a work file, reading a license file GamsSymbols Number of symbols (also called identifiers) including names of UG_Parameters_IntrinsicFunctions "intrinsic functions" and predefined symbols. GAMSTotalTime Total time of the corresponding trace record. Does only apply for trace records of type GamsStep and GamsExit. GamsVersionID String that contains a GAMS version ID, e.g. WEX282-282 for the Windows 64bit version of GAMS 28.2. InputFileName GAMS model filename. JobDate Day when the job started. JobTime Time when the Job started. JulianDate Julian date number with start day/time of job. LP LP solver. Marginals Indicates availability of marginals: 0=no, 1=yes MCP MCP solver. MINLP MINLP solver. MIP MIP solver. MIQCP MIQCP solver. ModelGenerationTime Model generation time. Refers to the last model in the part of the program that corresponds to the trace record. ModelName Model name. Refers to the last model in the part of the program that corresponds to the trace record. ModelStatus Model status. Refers to the last model in the part of the program that corresponds to the trace record. ModelType Model type. Refers to the last model in the part of the program that corresponds to the trace record. MPEC MPEC solver. NLP NLP solver. NumberOfDiscreteVariables Number of discrete variables. Refers to the last model in the part of the program that corresponds to the trace record. NumberOfDomainViolations Number of domain violations (see also model attribute domUsd ). NumberOfEquations Number of equations. Refers to the last model in the part of the program that corresponds to the trace record. NumberOfInstructions Length of non-linear code. NumberOfIterations Number of iterations. Refers to the solve of the last model in the part of the program that corresponds to the trace record. NumberOfNodes Number of nodes. Refers to the solve of the last model in the part of the program that corresponds to the trace record. Only relevant if some tree search algorithm (e.g. branch-and-bound was used). NumberOfNonlinearNonZeros Number of nonlinear non-zeroes. Refers to the last model in the part of the program that corresponds to the trace record. NumberOfNonZeros Number of non-zeroes. Refers to the last model in the part of the program that corresponds to the trace record. NumberOfVariables Number of variables. Refers to the last model in the part of the program that corresponds to the trace record. ObjectiveValue Objective value. Refers to the solve of the last model in the part of the program that corresponds to the trace record. ObjectiveValueEstimate Estimate of the best possible solution for a mixed-integer model (aka best bound). Refers to the solve of the last model in the part of the program that corresponds to the trace record. OptionFile Solver option file number. Refers to the solve of the last model in the part of the program that corresponds to the trace record. Platform Platform ID, e.g. WEX for the Windows 64bit. QCP QCP solver. RMINLP RMINLP solver. RMIP RMIP solver. RMIQCP RMIQCP solver. RMPEC RMPEC solver. SolveLine Line number of the last solve statement in the part of the program that corresponds to the trace record. This corresponds to the line number in the echo print of the input file. SolveNumber Number of solve statement for a particular model. For example, solve myModelA...; solve myModelB...; solve myModelA...; results in solve numbers 1, 1, 2. SolverCalcTime Time spent in function and derivative calculations (deprecated, see also model attribute resCalc). SolverID Solver ID number. SolverName Name of the solver. Refers to the solve of the last model in the part of the program that corresponds to the trace record. SolverElapsedTime Elapsed time taken by the solver when solveLink=0 is used (almost identical to model attribute etSolver). SolverReadTime Time to import model (deprecated, see also model attribute resIn). SolverRealTime Elapsed time taken by the solver when solveLink=0 is used (almost identical to model attribute etSolver). SolverSignature String containing a solver signature, e.g. IBM ILOG CPLEX 28.2.0 r750fa45 Released Aug 19, 2019 WEI x86 64bit/MS Window. Refers to the solver used to solve the last model in the part of the program that corresponds to the trace record. SolverStatus Solver Status. Refers to the solve of the last model in the part of the program that corresponds to the trace record. SolverTime Time used to solve the model in seconds reported by the solver (see also model attribute resUsd). SolverVersion Solver Version (see also model attribute sysVer). SolverWriteTime Time to export solution (deprecated, see also model attribute GAMSAOresout "resOut"). User1 Content of user1 string. User2 Content of user2 string. User3 Content of user3 string. User4 Content of user4 string. User5 Content of user5 string. UserName User name. ### 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: 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 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:

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

Name Description Default
UserHeurFreq Determines the frequency of the heuristic call. 10
UserHeurMult Determines the multiplier for the frequency of the heuristic call. 2
UserHeurInterval Determines 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
UserHeurNewInt Whether 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.

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:

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

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
UserLazyConCall Arguments to the GAMS call to invoke the lazy constraint adding GAMS program. Lazy constraints that cut off the incumbent are expected (in a format similar to UserCutCall) if the GAMS program terminates normally. In case of a compilation or execution error, the incumbent is accepted. 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 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 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 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.

GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170