XPRESS

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

1. iterlim (on the cumulative pivot count) or reslim (in seconds of CPU time),
2. optca & optcr (stopping criteria based on gap between best integer solution found and best possible) or
3. 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

Option Description Default
algorithm choose between simplex and barrier algorithm
This option is used to select the barrier method to solve LPs. By default the barrier method will do a crossover to find a basic solution.
barrier: Use the barrier algorithm
simplex: Use the simplex algorithm
simplex
basisOut directs optimizer to output an MPS basis file
In general this option is not used in a GAMS environment, as GAMS maintains basis information for you automatically.
none
crash control for basis crashing procedure
A crash procedure is used to quickly find a good basis. This option is only relevant when no advanced basis is available.
deterministic control for deterministic behavior of concurrent solves 1
extraPresolve initial number of extra elements to allow for in the presolve
The space required to store extra presolve elements is allocated dynamically, so it is not necessary to set this control. In some cases, the presolve may terminate early if this is not increased.
lpIterLimit set the iteration limit for simplex solves
For MIP models, this is a per-node iteration limit for the B&B tree. Overrides the iterlim option.
mpsNameLength maximum length of MPS names in characters
Maximum length of MPS names in characters. Internally it is rounded up to the smallest multiple of 8. MPS names are right padded with blanks. Maximum value is 64.
mpsOutputFile Name of MPS output file
If specified XPRESS-MP will generate an MPS file corresponding to the GAMS model: the argument is the file name to be used. You can prefix the file name with an absolute or relative path.
none
presolve sets presolve strategy
0: presolve not applied
1: presolve applied
2: presolve applied, but redundant bounds are not removed
3: presolve applied, and redundant bounds always removed
1
reform substitute out objective var and equ when possible 1
reRun rerun with primal simplex when not optimal/feasible
Applies only in cases where presolve is turned on and the model is diagnosed as infeasible or unbounded. If rerun is nonzero, we rerun the model using primal simplex with presolve turned off in hopes of getting better diagnostic information. If rerun is zero, no good diagnostic information exists, so we return no solution, only an indication of unboundedness/infeasibility.
0
reslim overrides GAMS reslim option
Sets the resource limit. When the solver has used more than this amount of CPU time (in seconds) the system will stop the search and report the best solution found so far.
scaling bitmap control for internal scaling algorithm
Bitmap to determine how internal scaling is done. If set to 0, no scaling will take place. The default of 35 implies row and column scaling done by the maximum element method.
bit 0 = 1: Row scaling
bit 1 = 2: Column scaling
bit 2 = 4: Row scaling again
bit 3 = 8: Maximin
bit 4 = 16: Curtis-Reid
bit 5 = 32: Off implies scale by geometric mean, on implies scale by maximum element. Not applicable for maximin and Curtis-Reid scaling.
Controls the number of threads to use. Positive values will be compared to the number of available cores detected and reduced if greater than this amount. Non-positive values are interpreted as the number of cores to leave free so setting threads to 0 uses all available cores while setting threads to -1 leaves one core free for other tasks.
Range: [-∞, ∞]
1
trace turns on output of infeasibility diagnosis during presolve
Control of the infeasibility diagnosis during presolve - if nonzero, infeasibility will be explained.
writePrtSol directs optimizer to output a "printsol" file

## LP Options

Option Description Default
bigM infeasibility penalty used in the "big M" method auto
bigMMethod controls use of "big M" method - 0=no, 1=yes
The alternative to using the big M method is to use a phase I / phase II simplex.
auto
concurrentThreads control for concurrent LP algorithm
If positive, determines the number of threads used to run the concurrent LP code. If -1, the threads control will determine the number of threads used for the LP solves. This control only affects the LP solves if the deterministic control is set to 0.
Range: [-1, ∞]
-1
defaultAlg sets the default LP algorithm
1: automatic
2: dual simplex
3: primal simplex
4: Newton barrier
1
If positive, determines the number of threads used to run the parallel dual simplex code. If -1, the threads control will be used.
Range: [-1, ∞]
-1
etaTol zero tolerance on eta elements
During each iteration, the basis inverse is premultiplied by an elementary matrix, which is the identity except for one column the eta vector. Elements of eta vectors whose absolute value is smaller than etatol are taken to be zero in this step.
feasTol zero tolerance for RHS and bound values
This is the zero tolerance on right hand side values, bounds and range values. If one of these is less than or equal to feastol in absolute value, it is treated as zero.
1e-06
invertFreq frequency of basis re-inversion
The frequency with which the basis will be inverted. A value of -1 implies automatic.
auto
invertMin minimum number of iterations between basis re-inversion
lpLog print control for LP log
Specifies the frequency at which the simplex iteration log is printed.
n < 0: detailed output every -n iterations
n = 0: log displayed at the end of the solution process
n > 0: summary output every n iterations
100
Range: [-1, ∞]
-1
matrixTol zero tolerance on matrix elements
If the value of a matrix element is less than or equal to matrixtol in absolute value, it is treated as zero.
optimalityTol zero tolerance on reduced costs
On each iteration, the simplex method searches for a variable to enter the basis which has a negative reduced cost. The candidates are only those variables which have reduced costs less than the negative value of optimalitytol.
penalty minimum absolute penalty variable coefficient used in the "big M" method auto
pivotTol zero tolerance on pivot elements in simplex method
On each iteration, the simplex method seeks a nonzero matrix element to pivot on. Any element with absolute value less than pivottol is treated as zero for this purpose.
pricingAlg determines the pricing method to use
At each iteration, the pricing method selects which variable enters the basis. In general DEVEX pricing requires more time on each iteration, but may reduce the total number of iterations, whereas partial pricing saves time on each iteration, although possibly results in more iterations.
-1: partial pricing
0: automatic
1: DEVEX pricing
relPivotTol minimum size of pivot element relative to largest element in column
At each iteration a pivot element is chosen within a given column of the matrix. The relative pivot tolerance, relpivottol, is the size of the element chosen relative to the largest possible pivot element in the same column.

## 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
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.
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
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
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.
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

Option Description Default
solnpool solution pool file name
If set, the integer feasible solutions generated during the global search will be saved to a solution pool. A GDX file whose name is given by this option will be created and will contain an index to separate GDX files containing the individual solutions in the solution pool.
none
solnpoolCapacity limit on number of solutions to store
Range: [1, ∞]
999999999
solnpoolCullDiversity cull N solutions based on solution diversity
When performing a round of culls due to a full solution pool, this control sets the maximum number to cull based on the diversity of the solutions in the pool.
Range: [-1, ∞]
-1
solnpoolCullObj cull N solutions based on objective values
When performing a round of culls due to a full solution pool, this control sets the maximum number to cull based on the MIP objective function.
Range: [-1, ∞]
-1
solnpoolCullRounds terminate solution generation after N culling rounds
Limits the rounds of culls performed due to a full solution pool.
999999999
solnpoolDupPolicy sets policy for detecting/storing duplicate solutions
Determines whether to check for duplicate solutions when adding to the MIP solution pool, and what method is used to check for duplicates.
0: keep all
1: compare all vars, exact matches discarded
2: compare rounded discrete, exact continuous
3: compare rounded discrete only
3
solnpoolmerge solution pool file name for merged solutions none
solnpoolnumsym maximum number of variable symbols when writing merged solutions
Range: [1, ∞]
10
solnpoolPop controls method used to populate the solution pool
By default the MIP solution pool merely stores the incumbent solutions that are found during the global search, without changing the behavior of the search itself. In constrast, the MIP solution enumerator makes it possible to enumerate all or many of the feasible solutions for the MIP, instead of searching for the best solution.
1: generate solutions using the normal search algorithm
2: invoke the solution enumerator to generate solutions
1
solnpoolPrefix file name prefix for GDX solution files soln
solnpoolVerbosity controls verbosity of solution pool routines
-1: no output
0: output only messages coming from the XPRESS libraries
1: add some messages logging the effect of solution pool options
2: debugging mode
0

## QP Options

Option Description Default
eigenvalueTol zero tolerance for negative eigenvalues of quadratic matrices
A quadratic matrix is considered not to be positive semi-definite if its smallest eigenvalue is smaller than the negative of this value.
1e-6
ifCheckConvexity controls convexity check for QP models - 0=no, 1=yes
Applies to quadratic, mixed integer quadratic and quadratically constrained problems. Checking convexity takes some time, thus for problems that are known to be convex it might be reasonable to switch the checking off.
1

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