### Table of Contents

# Introduction

This document describes the GAMS/XPRESS linear and mixed-integer programming solver. The GAMS/XPRESS solver is based on the XPRESS Optimization Subroutine Library, and runs only in conjunction with the GAMS modeling system.

GAMS/XPRESS (also simply referred to as XPRESS) is a versatile, high-performance optimization system. The system integrates a powerful simplex-based LP solver, a MIP module with cut generation for integer programming problems and a barrier module implementing a state-of-the-art interior point algorithm for very large LP problems.

The GAMS/XPRESS solver is installed automatically with your GAMS system. Without a license, it will run in student or demonstration mode (i.e. it will solve small models only). If your GAMS license includes XPRESS, there is no size or algorithm restriction imposed by the license, nor is any separate licensing procedure required.

# Usage

To explicitly request that a model be solved with XPRESS, insert the statement

option LP = xpress; { or MIP, RMIP, QCP, MIQCP, or RMIQCP }

somewhere before the solve statement. If XPRESS has been selected as the default solver (e.g. during GAMS installation) for the model type in question, the above statement is not necessary.

The standard GAMS options (e.g. iterlim, optcr) can be used to control XPRESS. For more details, see section Controlling a Solver via GAMS Options.

In addition, XPRESS-specific options can be specified by using a solver option file. While the content of an option file is solver-specific, the details of how to create an option file and instruct the solver to use it are not. This topic is covered in section The Solver Options File.

An example of a valid XPRESS option file is:

* sample XPRESS options file algorithm simplex presolve 0 IterLim 50000

In general this is enough knowledge to solve your models. In some cases you may want to use some of the XPRESS options to gain further performance improvements or for other reasons.

## General

The options advBasis, algorithm, basisOut, mpsOutputFile, reform, reRun, and reslim control the behavior of the GAMS/XPRESS link. The options crash, extraPresolve, lpIterlimit, presolve, scaling, threads, and trace set XPRESS library control variables, and can be used to fine-tune XPRESS. See section General Options for more details of XPRESS general options.

## LP

See section LP Options for more details of XPRESS library control variables which can be used to fine-tune the XPRESS LP solver.

## MIP

In some cases, the branch-and-bound MIP algorithm will stop with a proven optimal solution or when unboundedness or (integer) infeasibility is detected. In most cases, however, the global search is stopped through one of the generic GAMS options:

- iterlim (on the cumulative pivot count) or reslim (in seconds of CPU time),
- optca & optcr (stopping criteria based on gap between best integer solution found and best possible) or
- nodlim (on the total number of nodes allowed in the B&B tree).

It is also possible to set the maxNode and maxMipSol options to stop the global search: see section MIP Options for XPRESS control variables for MIP. The options loadMipSol, mipCleanup, mipTrace, mipTraceNode, and mipTraceTime control the behavior of the GAMS/XPRESS link on MIP models. The other options in section MIP Options set XPRESS library control variables, and can be used to fine-tune the XPRESS MIP solver.

## MIP Solution Pool

Typically, XPRESS finds a number of integer feasible points during its global search, but only the final solution is available. The MIP solution pool capability makes it possible to store multiple integer feasible points (aka solutions) for later processing. The MIP solution pool operates in one of two modes: by default `(solnpoolPop = 1)`

the global search is not altered, but with `(solnpoolPop = 2)`

a selected set (potentially all) of the integer feasible solutions are enumerated.

The MIP enumeration proceeds until all MIP solutions are enumerated or cut off, or until a user-defined limit is reached. Whenever a new solution is generated by the enumerator, it is presented to the solution pool manager. If there is room in the pool, the new solution is added. If the pool is full, a * cull round * is performed to select a number of solutions to be thrown out - these solutions can be those stored in the pool and/or the new solution. Solutions can be selected for culling based on their MIP objective value and/or the overall diversity of the solutions in the pool. If neither is chosen, a default choice is made to throw out one solution based on objective values. Whenever a solution is thrown out based on its MIP objective, the enumeration space is pruned based on the cutoff defined by this objective value.

By default, the capacity of the pool is set very large, as is the number of cull rounds to perform, so selecting only `solnpoolPop = 2`

will result in full enumeration. However, many different strategies can be executed by setting the solution pool options. For example, to choose the \(N\)-best solutions, simply set the solution pool capacity to \(N\). When the pool is full, new solutions will force a cull round, and the default is to reject one solution based on its objective and update the cutoff accordingly. To generate all solutions with an objective as good as \(X\), leave the pool capacity set at a high level but set the cutoff to \(X\) using the `mipabscutoff`

option. To return the \(N\)-first solutions, set the solution pool capacity to \(N\) and `solnpoolCullRounds = 0`

: as soon as the pool is full the enumeration will stop on the cull round limit.

A number of other strategies for controlling the solution pool behavior are possible by combining different options. Several working examples are provided in the GAMS Test Library in models `xpress03.gms`

, `xpress04.gms`

, and `xpress05.gms`

.

See section MIP Solution Pool Options for XPRESS control variables for MIP Solution Pool.

## Newton-Barrier

The barrier method is invoked by default for quadratic problems, and can be selected for linear models by using one of the options

algorithm barrier defaultalg 4

The barrier method is likely to use more memory than the simplex method. No warm start is done, so if an advanced basis exists, you may not wish to use the barrier solver.

See section Newton-barrier Options for XPRESS control variables for the Newton-Barrier method.

# Options

The tables that follow contain the XPRESS options. They are organized by function (e.g. LP or MIP) and also by type: some options control the behavior of the GAMS/XPRESS link and will be new even to experienced XPRESS users, while other options exist merely to set control variables in the XPRESS library and may be familiar to XPRESS users.

## General Options

## LP Options

## MIP Options

Option | Description | Default |
---|---|---|

backTrack | determines selection of next node in case of a full backtrack`1` Unused`2` Select the node with the best estimated solution`3` Select the node with the best bound on the solution`4` Select the deepest node in the search tree (aka DFS)`5` Select the highest node in the search tree (aka BFS)`6` Select the earliest node created`7` Select the latest node created`8` Select a node randomly`9` Select the node whose LP relaxation contains the fewest number of infeasible global entities`10` Combination of 2 and 9`11` Combination of 2 and 4`12` Combination of 3 and 4 | `3` |

breadthFirst | determines number of nodes to include in a breadth-first search Used only if `nodeselection` = 4.Range: [ `1` , ∞] | `1` |

coverCuts | number of rounds of lifted cover inequalities at the top node A lifted cover inequality is an additional constraint that can be particularly effective at reducing the size of the feasible region without removing potential integral solutions. The process of generating these can be carried out a number of times, further reducing the feasible region, albeit incurring a time penalty. There is usually a good payoff from generating these at the top node, since these inequalities then apply to every subsequent node in the tree search. | |

cutDepth | maximum depth in search tree at which cuts will be generated Generating cuts can take a lot of time, and is often less important at deeper levels of the tree since tighter bounds on the variables have already reduced the feasible region. A value of 0 signifies that no cuts will be generated. | |

cutFreq | frequency at which cuts are generated in the tree search If the depth of the node modulo `cutfreq` is zero, then cuts will be generated. | |

cutStrategy | specifies the cut strategy An aggressive cut strategy, generating a greater number of cuts, will result in fewer nodes to be explored, but with an associated time cost in generating the cuts. The fewer cuts generated, the less time taken, but the greater subsequent number of nodes to be explored. `-1` automatic`0` no cuts`1` conservative cut strategy`2` moderate cut strategy`3` aggressive cut strategy | `-1` |

gomCuts | number of rounds of Gomery cuts at the top node Gomory cuts can always be generated if the current node does not yield an integral solution. However, they are usually not as effective as lifted cover inequalities in reducing the size of the feasible region. | |

heurThreads | number of threads for running parallel root node heuristics If positive, determines the number of root threads dedicated to running parallel heuristics. If 0, heuristics are run sequentially with the root LP solver and cutting. If -1, the threads control will be used as the default. Range: [ `-1` , ∞] | `0` |

loadMipSol | loads a MIP solution (the initial point) If true, the initial point provided by GAMS will be passed to the optimizer to be treated as an integer feasible point. The optimizer uses the values for the discrete variables only: the level values for the continuous variables are ignored and are calculated by fixing the integer variables and reoptimizing. In some cases, loading an initial MIP solution can improve performance. In addition, there will always be a feasible solution to return. | `0` |

maxMipSol | maximum number of integer solutions in MIP tree search This specifies a limit on the number of integer solutions to be found (the total number, not necessarily the number of distinct solutions). 0 means no limit. | |

maxNode | maximum number of nodes to explore in MIP tree search If the GAMS nodlim model suffix is set, that setting takes precedence. | `maxint` |

mipAbsCutoff | nodes with objective worse than this value are ignored If the user knows that they are interested only in values of the objective function which are better than some value, this can be assigned to `mipabscutoff` . This allows the Optimizer to ignore solving any nodes which may yield worse objective values, saving solution time. | |

mipAbsStop | stopping tolerance for gap: if met XPRESS returns proven optimal The global search is stopped if the gap is reduced to this value. This check is implemented in the Optimizer library, and if the search is stopped on this check the Optimizer returns a status of proven optimal. For this reason you should use the GAMS <modelname>.optca parameter instead of this option. | |

mipAddCutoff | amount to add to MIP incumbent to get the new cutoff Once an integer solution has been found whose objective function is equal to or better than `mipabscutoff` , improvements on this value may not be interesting unless they are better by at least a certain amount. If `mipaddcutoff` is nonzero, it will be added to `mipabscutoff` each time an integer solution is found which is better than this new value. This cuts off sections of the tree whose solutions would not represent substantial improvements in the objective function, saving processor time. Note that this should usually be set to a negative number for minimization problems, and positive for maximization problems. Notice further that the maximum of the absolute and relative cut is actually used. | `auto` |

mipCleanup | clean up the MIP solution (round-fix-solve) to get duals If nonzero, clean up the integer solution obtained, i.e. round and fix the discrete variables and re-solve as an LP to get some marginal values for the discrete vars. | `1` |

mipLog | print control for MIP log`0` no printout in global`1` only print out summary statement at the end`2` print out detailed log at all solutions found`3` print out detailed log at each node`n < 0` Print out summary log at each nth node, or when a new solution is found | `-100` |

mipPresolve | bitmap controlling the MIP presolve If set to 0, no presolve will be performed. `bit 0 = 1` reduced cost fixing will be performed at each node`bit 1 = 2` primal reductions will be performed at each node`bit 2 = 4` unused`bit 3 = 8` node preprocessing is allowed to change bounds on continuous columns`bit 4 = 16` dual reductions will be performed at each node | |

mipRelCutoff | relative difference between the MIP incumbent and the new cutoff Percentage of the LP solution value to be added to the value of the objective function when an integer solution is found, to give the new value of `mipabscutoff` . The effect is to cut off the search in parts of the tree whose best possible objective function would not be substantially better than the current solution. | `0` |

mipRelStop | stopping tolerance for relative gap: if met XPRESS returns proven optimal The global search is stopped if the relative gap is reduced to this value. This check is implemented in the Optimizer library, and if the search is stopped on this check the Optimizer returns a status of proven optimal. For this reason you should use the GAMS <modelname>.optcr parameter instead of this option. | `0` |

mipThreads | number of threads for parallel mip algorithm If positive, determines the number of threads used to run the parallel MIP code. If -1, the `threads` control will be used.Range: [ `-1` , ∞] | `-1` |

mipTol | integrality tolerance for discrete vars This is the tolerance within which a decision variables value is considered to be integral. | `5e-6` |

mipTrace | name of MIP trace file A miptrace file with the specified name will be created. This file records the best integer and best bound values every `miptracenode` nodes and at `miptracetime` -second intervals. | `none` |

mipTraceNode | node interval between MIP trace file entries | `100` |

mipTraceTime | time interval, in seconds, between MIP trace file entries | `5` |

nodeSelection | sets node selection strategy This determines which nodes will be considered for solution once the current node has been solved. `1` local first: choose between descendant and sibling nodes if available, o/w from all outstanding nodes`2` best first: choose from all outstanding nodes`3` local depth first: choose between descendant and sibling nodes if available, o/w from the deepest nodes`4` best first, then local first: best first for the first BREADTHFIRST nodes, then local first is used`5` pure depth first: choose from the deepest outstanding nodes | `1` |

objGoodEnough | stop once an objective this good is found | `none` |

preProbing | control probing done on binary variables during presolve This is done by fixing a binary to each of its values in turn and analyzing the implications. `-1` automatic`0` disabled`1` light probing - only few implications will be examined`2` full probing - all implications for all binaries will be examined`3` full probing and repeat as long as the problem is significantly reduced | `-1` |

pseudoCost | default pseudo-cost The default pseudo cost used in estimation of the degradation associated with an unexplored node in the tree search. A pseudo cost is associated with each integer decision variable and is an estimate of the amount by which the objective function will be worse if that variable is forced to an integral value. | |

sleepOnThreadWait | control behavior of waiting threads in a MIP solve | `0` |

symmetry | adjust overall amount of effort in symmetry detection`0` no symmetry detection`1` conservative effort`2` intensive symmetry search | `1` |

symSelect | adjust what is searched in symmetry detection`-1` automatic`0` search the whole matrix (otherwise the 0, 1, and -1 coefs only)`1` search all entities (otherwise binaries only) | `-1` |

treeCoverCuts | number of rounds of lifted cover inequalities at tree nodes The number of rounds of lifted cover inequalities generated at nodes other than the top node in the tree. Compare with the description for `covercuts` . A value of -1 indicates the number of rounds is determined automatically. | `auto` |

treeGomCuts | number of rounds of Gomery cuts at tree nodes The number of rounds of Gomory cuts generated at nodes other than the top node in the tree. Compare with the description for `gomcuts` . A value of -1 indicates the number of rounds is determined automatically. | `auto` |

treePresolve | amount of full presolving to apply at tree nodes`-1` automatic`0` disabled`1` cautious strategy - only when significant reductions possible`2` medium strategy`3` aggressive strategy - most frequently | `0` |

treePresolveKeepBasis | control use of existing basis when presolving at tree nodes`0` drop basis and resolve node from scratch`1` presolve/preserve the basis and warm-start`2` ignore the basis during presolve and attempt warm-start | `0` |

varSelection | determines how to use pseudo-costs This determines how to combine the pseudo costs associated with the integer variables to obtain an overall estimated degradation in the objective function that may be expected by branching on a given integer variable. The variable selected to be branched on is the one with the maximum estimate. `-1` automatic`0` unused`1` the minimum of the up and down pseudo costs`2` the up pseudo cost plus the down pseudo cost`3` the max of the up and down pseudo costs, plus twice the min of the up and down pseudo costs`4` the maximum of the up and down pseudo costs`5` the down pseudo cost`6` the up pseudo cost`7` a weighted combination of the up and down pseudo costs, where the weights depend on how fractional the variable is`8` the product of the up and down pseudo costs | `-1` |

## MIP Solution Pool Options

## QP Options

## Newton-barrier Options

Option | Description | Default |
---|---|---|

barAlg | determines which barrier algorithm to use`-1` automatic`0` unused`1` infeasible-start barrier alg`2` homogeneous self-dual barrier alg`3` start with 2 optionally switch to 1 | `-1` |

barCrash | determines the type of crash used for the crossover from barrier`0` Turn off all crash procedures`1-6` From 1-most conservative to 6-most aggressive | `4` |

barDualStop | stopping tolerance for dual infeasibilities in barrier: 0=auto The dual constraint residuals must be smaller than this value for the current point to be considered dual feasible. | `auto` |

barGapStop | stopping tolerance for relative duality gap in barrier: 0=auto The gap between the primal and dual solutions must be smaller than this value for the current point to be considered optimal. | `auto` |

barIndefLimit | limit consecutive indefinite barrier iterations that will be performed For QP models, once this limit is hit, the problem will be reported to be indefinite. Range: [ `1` , ∞] | `15` |

barIterLimit | maximum number of barrier iterations | `500` |

barOrder | controls the Cholesky factorization in barrier`0` automatic`1` Minimum degree method. This selects diagonal elements with the smallest number of nonzeros in their rows or columns.`2` Minimum local fill method. This considers the adjacency graph of nonzeros in the matrix and seeks to eliminate nodes that minimize the creation of new edges.`3` Nested dissection method. This considers the adjacency graph and recursively seeks to separate it into non-adjacent pieces. | `auto` |

barOutput | controls the level of solution output from barrier`0` No output`1` At each iteration | `1` |

barPrimalStop | stopping tolerance for primal infeasibilities in barrier: 0=auto The primal constraint residuals must be be smaller than this value for the current point to be considered primal feasible. | `auto` |

barStart | controls the computation of the barrier starting point`0` automatic`1` uses simple heuristics to compute the starting point based on the magnitudes of the matrix entries`2` uses the pseudoinverse of the constraint matrix to determine primal and dual initial solutions | `0` |

barStepStop | stopping tolerance on the step size of the barrier search direction If the step size is smaller, the current solution will be returned. | `1e-10` |

barThreads | number of threads for parallel barrier algorithm | |

cpuPlatform | selects vectorized instruction set to use for barrier method Generic code and SSE2 or AVX optimized code will result in a deterministic or reproducible solution path. AVX2 code may result in a nondeterministic solution path. `-2` Highest supported: generic, SSE2, AVX or AVX2`-1` Highest supported deterministic: generic, SSE2 or AVX`0` generic code compatible with all CPUs`1` SSE2 optimized code`2` AVX optimized code`3` AVX2 optimized code | `-1` |

crossover | crossover control for barrier method Determines whether and how the barrier method will cross over to the simplex method when an optimal solution has been found, in order to provide an end basis. `-1` automatic`0` no crossover`1` primal crossover first`2` dual crossover first | `auto` |

crossoverThreads | number of threads for parallel barrier algorithm If positive, determines the number of threads used to run the crossover code. If -1, the threads control will determine the number of threads used for the crossover. Range: [ `-1` , ∞] | `-1` |

denseColLimit | controls trigger point for special treatment of dense columns in Cholesky factorization | `0` |

# Helpful Hints

The comments below should help both novice and experienced GAMS users to better understand and make use of GAMS/XPRESS.

**Infeasible and unbounded models**The fact that a model is infeasible/unbounded can be detected at two stages: during the presolve and during the simplex or barrier algorithm. In the first case we cannot recover a solution, nor is any information regarding the infeasible/unbounded constraint or variable provided (at least in a way that can be returned to GAMS). In such a situation, the GAMS link will automatically rerun the model using primal simplex with presolve turned off (this can be avoided by setting the rerun option to 0). It is possible (but very unlikely) that the simplex method will solve a model to optimality while the presolve claims the model is infeasible/unbounded (due to feasibility tolerances in the simplex and barrier algorithms).- The barrier method does not make use of
`iterlim`

. Use`bariterlim`

in an options file instead. The number of barrier iterations is echoed to the log and listing file. If the barrier iteration limit is reached during the barrier algorithm, XPRESS continues with a simplex algorithm, which will obey the iterlim setting. - Semi-integer variables are not implemented in the link, nor are they supported by XPRESS; if present, they trigger an error message.
- SOS1 and SOS2 variables are required by XPRESS to have lower bounds of 0 and nonnegative upper bounds.