### Table of Contents

# The GAMS Branch-and-Cut-and-Heuristic Facility

## Introduction

It is a known fact that hard mixed-integer programming (MIP) problems can significantly benefit from user supplied routines that generate *cutting planes* and *good integer feasible solutions*. GAMS users could supply cutting planes and an integer feasible point as part of the model given to the solver, by adding a set of constraints representing likely to be violated cuts and a feasible solution in combination with the `TryInt`

parameter or solver specific options like `MipStart`

in GAMS/CPLEX. A true dynamic interaction between a running branch-and-cut (B&C) solver like CPLEX, GUROBI, and XPRESS and user supplied routines was not possible. The GAMS Branch-and-Cut-and-Heuristic (BCH) facility closes this gap. The GAMS BCH facility automates all major steps necessary to define, excite and control the use of user defined routines within the framework of general purpose MIP codes. This allows GAMS users to apply complex solution strategies without having to have intimate knowledge about the inner workings of a specific MIP system. BCH strategies can now be implemented rapidly and reliably within a matter of days rather than weeks.

For those of you who learn best by example, we have prepared a multi knapsack problem with cover cut generation in the Annex of this page.

A presentation about BCH with performance comparisons can be found on the GAMS presentation page.

## Design Overview

After a node in the branch-and-bound (B&B) tree is processed by the solver a user supplied routine can be called. All available information from this node, like the LP solution, and the B&B tree, like the current incumbent, is exported in the original name space to a GAMS database. After that the solver can call two different user supplied GAMS programs, one for finding violated cuts (cut generator) and one to find a better incumbent (heuristic). These GAMS programs must import the information from the solver, find cuts or an integer solution and export their findings to another GAMS database which is imported by the solver after the cut generator or heuristic GAMS program terminates. In case the heuristic GAMS program found a solution, the solver checks this solution for infeasibilties and in case this check is passed and the solution is better than the best known solution, the solver updates it's incumbent. In case violated cuts are found, the solver adds these cuts to it's *cut pool*, resolves the LP at the node and calls the user supplied cut generating GAMS model again. If no cutting planes are found, the solver will process the next node. Please note that the solver cannot perform any checks on the new cuts. Hence, it is possible to cut off areas of the feasible space and even the optimal solution with wrong cuts.

## The Interface

Since data flows between the B&C solver and the user supplied cut generator and heuristic, both ends need to comply to a data contract. The GAMS databases make use of the GAMS Data eXchange(GDX) facility that allows convenient import and export of data. The B&C solver exports the LP solution, i.e. level values (`.l`

) and the bounds (`.lo`

and `.up`

), to the GDX file `bchout.gdx`

. The bounds are the actual bounds in this node. Hence for discrete variables, they reflect branching decisions made in the B&B tree. In a similar way, the incumbent solution is exported to the GDX file `bchout_i.gdx`

. The bounds for the incumbent solution reflect global bounds, i.e. the original bounds or globally feasible bounds improved by the preprocessor of the B&C solver. The solution can be imported using the compile time `$load`

or run time `execute_load`

routines.

At the end of the heuristic model the newly found solution should be stored in the level values of the variables corresponding to the original variables. For example, if the original model uses binary variable `open(i,t)`

, then at the end of the heuristic `open.l(i,t)`

should contain a 0 (zero) or a 1. If the heuristic cannot find an integer feasible solution, the model can terminate with an execution error triggered by abort to prevent the B&C solver from reading the results from the heuristic run.

Exporting violated cuts is a little more complicated because we need the complete constraints of the cuts. The B&C solver needs to know how many cuts have been found by the cut generator, it has to read the constraint matrix, the sense (`=l=, =g=, or =e=`

), and the right hand side of these cuts. The cut generator model has to define and fill the following symbols appropriately.

$set MaxCuts 100 Set cc 'cuts' /1*%MaxCuts%/ Parameter numcuts 'number of cuts to be added' /0/ rhs_c(cc) 'cut rhs' sense_c(cc) 'the sense of the cuts 1 =L=, 2 =E=, 3 =G=';

The only thing missing is the constraint matrix. For each variable which is part of a cut, we need a parameter in the cut generator model. For example, variable `open(i,t)`

is part of a cut. We need to define

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

This parameter has an extra cut index in the first position. The values of this parameter should reflect the coefficients in the cut constraint matrix. The B&C solver reads all parameters that end `in _c`

, takes the base name and looks for a variable with that name and indicies and builds up the cut matrix. A cut cannot introduce a new variable into the model. All cuts added to the model are *global cuts*, they apply to the entire problem, not just to a subtree.

## Solvers Aware of BCH

With the current GAMS system only two solvers are aware of the BCH facility: GAMS/CPLEX and GAMS/SBB. GAMS/CPLEX implements the full interface described in this document, heuristic and cut generation. GAMS/SBB only uses the heuristic.

## Options

There are three different option types that come with the BCH facility. One set option helps to determine *when to* call the heuristic model and cut generator model. The second set allows to overwrite the filenames for the GDX files (to avoid name clashes) and the options to define the heuristic and cut generation GAMS calls. These options go like other options into the option file of the solver (e.g. `cplex.opt`

or `sbb.op9`

).

Name | Description | Default |
---|---|---|

`UserHeurFreq` | Determines the frequency of the heuristic model calls. | 10 |

`UserHeurMult` | Determines the multiplier for the frequency of the heuristic model calls. | 2 |

`UserHeurInterval` | Determines the interval when to apply the multiplier for the frequency of the heuristic model calls. For example, for the first 100 (`UserHeurInterval` ) nodes, the solver call every 10th (`UserHeurFreq` ) node the heuristic. After 100 nodes, the frequency gets multiplied by 10 (`UserHeurMult` ), so that for the next 100 node 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` | Calls the heuristic for the first n nodes. | 10 |

`UserHeurObjFirst` | Similar to `UserHeurFirst` but only calls the heuristic if the relaxed objective value promises a significant improvement of the current incumbent, i.e. the LP value of the node has to be closer to the best bound than the current incumbent. | 0 (Cplex), 50 (SBB) |

`UserHeurNewInt` | Calls the heuristic if the solver found a new integer feasible solution (yes/no). | no |

`UserHeurCall` | The GAMS command line (minus the GAMS executable name) to call the heuristic. | no |

`UserHeurFreq` | Determines the frequency of the cut generator model calls. | 10 |

`UserCutMult` | Determines the multiplier for the frequency of the cut generator model calls. | 2 |

`UserCutInterval` | Determines the interval when to apply the multiplier for the frequency of the cut generator model calls. See `UserHeurInterval` for details. | 100 |

`UserCutFirst` | Calls the cut generator for the first n nodes. | 10 |

`UserCutNewInt` | Calls the cut generator if the solver found a new integer feasible solution (yes/no). | no |

`UserCutCall` | The GAMS command line (minus the GAMS executable name) to call the cut generator. | no |

`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` | Prefixes `UserGDXIn` , `UserGDXName` , and `UserGDXNameInc` | empty |

`UserIncbCcall` | The GAMS command line (minus the GAMS executable name) to call the incumbent checking routine. The incumbent is rejected if the GAMS program terminates normally. In case of a compilation or execution error, the incumbent is accepted. | no |

`UserIncbICall` | The GAMS command line to call the incumbent reporting program. | empty |

`UserJobID` | Postfixes listing and log file and adds `–UserJobID` to the `User*Calls` . Postfixes `UserGDXIn` , `UserGDXName` , and `UserGDXNameInc` | empty |

`UserKeep` | Calls `gamskeep` instead of `gams` . | 0 |

For the Oil Pipeline Network Design problem a typical GAMS/CPLEX option file with BCH options could look like this:

userheurcall bchoil_h.inc mip cplex optcr 0 reslim 10 userheurfirst 5 userheurfreq 20 userheurinterval 1000 usercutcall bchoil_c.inc mip cplex usercutfirst 0 usercutfreq 0 usercutnewint yes

## Examples

We have gathered a few examples that show how to use the new BCH facility:

**Trimloss Optimization with SBB**This model implements a very simple LP/MIP based heuristic for the trimloss minimization problem.**Single Commodity Uncapacitated Fixed Charge Network Flow Problem**This model implements simple but difficult to separate cuts for a network design problem. The global solver BARON is used to find violated cuts by solving a non-convex MINLP.**Oil Pipeline Design Problem**This is the most complex example. It implements three different heuristics: An initial heuristic based on a simplified cost structure, a rounding heuristic, and local branching. In addition complex cuts are generated by solving regionalized versions of the original problem.**MIP Decomposition and Parallel Grid Submission - DICE Example**This example uses many of the renaming and`UserJobID`

options since we have multiple jobs running that need to work on different filenames. This example also uses the incumbent reporting call`UserIncbICall`

.**Cplex Solution Pool for a Simple Facility Location Problem**This example uses the incumbent checking call`UserIncbCall`

as an advanced filter for accepting/rejecting solutions found by Cplex.

## Annex

The simple multi knapsack problem will be used to illustrate how to implement user cuts in the BCH facility. The model can also be found in the model library under the name [bchmknap].

### Base Model

$Title Multi knapsack problem using BCH Facility (BCHMKNAP,SEQ=289) $ontext This multiknapsack problem illustrates the use of user supplied cutting planes in the GAMS BCH (branch-and-cut-and-heuristic) facility. Please note, that cover cuts used in this example, are already implemented in modern MIP solvers. Example taken from the OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html first example in mknap1. Beasley, J E, OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society 41 (11) (1990), 1069-1072. Petersen, C C, Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Science 13 (9) (1967), 736-750. Linderoth, J, IE418 Lecture Notes - Lecture #19, 2003. Lehigh University, http://www.lehigh.edu/~jtl3/teaching/ie418/lecture19.pdf $offtext set j columns /c1*c6/ i rows /r1*r10/ Parameters obj(j) / c1 100, c2 600, c3 1200, c4 2400, c5 500, c6 2000 / rhs(i) / r1 80, r2 96, r3 20, r4 36, r5 44, r6 48, r7 10, r8 18, r9 22, r10 24 /; Table a(i,j) c1 c2 c3 c4 c5 c6 r1 8 12 13 64 22 41 r2 8 12 13 75 22 41 r3 3 6 4 18 6 4 r4 5 10 8 32 6 12 r5 5 13 8 42 6 20 r6 5 13 8 48 6 20 r7 8 r8 3 4 8 r9 3 2 4 8 4 r10 3 2 4 8 8 4 Binary variables x(j) Positive variables slack(i) Variable z; Equations mk(i), defobj; defobj.. z =e= sum(j, obj(j)*x(j)); mk(i).. sum(j, a(i,j)*x(j)) + slack(i) =e= rhs(i); model m /all/; * Export base data execute_unload 'mkdata', j, i, a, rhs; $ifi %system.mip% == cplex $goto cont $abort 'BCH Facility not available for MIP solver %system.mip%.' $label cont m.optfile = 1; m.optcr = 0; * We activate the user supplied cut generator and turn all advanced CPLEX options off $onecho > cplex.opt usercutcall bchcover.inc mip=cplex cuts no preind 0 heurfreq -1 mipinterval 1 $offecho solve m max z using mip;

### Cover cut Generator

$Title Simple cover inequalities for the multi-knapsack problem with integer data * Declare and get selected data from base model Set j, i; Parameter a(i,j), rhs(i); $gdxin mkdata $load j i a rhs * Declare selected variables from base MIP model Binary variables x(j) Positive variable slack(i); * Get current values from MIP solver $gdxin bchout $load x slack * Define separation model Parameter ai(j), rhsi slice of the multi knapsack problem; Binary variable y(j) membership in the cover variable obj; Equations k, defobj; defobj.. obj =e= sum(j, (1-x.l(j))*y(j)); * rhsi+1 only works if all ai are integer k.. sum(j, ai(j)*y(j)) =g= rhsi+1; model kn /all/; * In order to communicate with the MIP solver we need certain conventions * 1. Cut matrix interface requirement with fixed names Set cut potential cuts / 1*5 / Parameters rhs_c(cut) cut rhs sense_c(cut) 'the sense of the cuts 1 =L=, 2 =E=, 3 =G=' numcuts number of cuts passed back * 2. Nonzeros in cut matrix using the original variable name plus _c x_c(cut,j) coefficient of the x variables in the cut * We solve one knapsack type MIP to solve the cover separation problem for each * row in the original problem that is binding * The actual cover cut is sum(cover(j), x(j)) =l= sum(cover(j),1)-1; option optcr=0, limrow=0, limcol=0; option solprint=off, solvelink=%solvelink.CallModule%; Set c(cut) current cut /1/; numcuts = 0; loop(i$(numcuts < card(cut) and slack.l(i) < 1e-6), ai(j) = a(i,j); rhsi = rhs(i); solve kn min obj using mip; if ((kn.modelstat = %modelstat.Optimal% or kn.modelstat = %modelstat.IntegerSolution%) and obj.l < 0.95, numcuts = numcuts + 1; x_c(c,j) = round(y.l(j)); rhs_c(c) = sum(j,round(y.l(j))) - 1; sense_c(c) = 1; c(cut) = c(cut-1); ) ); * One can debug the cut generator by solving the RMIP of the base model (change * mip to rmip) and creating a GDX file with the name bchout.gdx: * gams bchmknap rmip=cplex gdx=bchout * Start the cut generator and analyze the cuts generated * gams bchcover.inc mip=cplex display numcuts, x_c, rhs_c, sense_c;

### Solution log

--- Job bchmknap.gms Start 08/06/10 04:36:58 WEX-VS8 23.5.1 x86/MS Windows GAMS Rev 235 Copyright (C) 1987-2010 GAMS Development. All rights reserved Licensee: GAMS Development Corporation, Washington, DC G871201/0000CA-ANY Free Demo, 202-342-0180, sales@gams.com, www.gams.com DC0000 --- Starting compilation --- bchmknap.gms(77) 3 Mb --- Starting execution: elapsed 0:00:00.003 --- bchmknap.gms(64) 4 Mb --- Generating MIP model m --- bchmknap.gms(75) 4 Mb --- 11 rows 17 columns 68 non-zeroes --- 6 discrete-columns --- Executing CPLEX: elapsed 0:00:00.008 IBM ILOG CPLEX Jul 4, 2010 23.5.1 WIN 18414.18495 VS8 x86/MS Windows Cplex 12.2.0.0, GAMS Link 34 Reading parameter(s) from "C:\tmp\cplex.opt" >> usercutcall bchcover.inc mip=cplex >> cuts no >> preind 0 >> heurfreq -1 >> mipinterval 1 Finished reading from "C:\tmp\cplex.opt" Cplex MIP uses 1 of 8 parallel threads. Change default with option THREADS. Reading data... Starting Cplex... Warning: Control callbacks may disable some MIP features. Clique table members: 24. MIP emphasis: balance optimality and feasibility. MIP search method: traditional branch-and-cut. Parallel mode: none, using 1 thread. Initializing dual steep norms . . . Iteration Dual Objective In Variable Out Variable 1 4400.000000 x(c4) slack(r6) 2 4216.666667 slack(r7) slack(r1) 3 4134.074074 slack(r6) slack(r5) Root relaxation solution time = 0.00 sec. Nodes Cuts/ Node Left Objective IInf Best Integer Best Node ItCnt Gap 0 0 4134.0741 2 4134.0741 3 *** Calling cut generator. Added 2 cuts 0 0 4090.6542 2 User: 1 4 *** Calling cut generator. Added 2 cuts 0 0 4001.4270 4 User: 1 5 *** Calling cut generator. Added 2 cuts 0 0 3950.4202 4 User: 1 6 *** Calling cut generator. Added 1 cut 0 0 3871.4286 2 User: 1 7 *** Calling cut generator. Added 1 cut 0 0 3841.6244 6 User: 1 9 *** Calling cut generator. No cuts found *** Calling cut generator. No cuts found 0 2 3841.6244 6 3800.0000 9 Elapsed real time = 0.58 sec. (tree size = 0.00 MB, solutions = 0) *** Calling cut generator. Added 1 cut *** Calling cut generator. No cuts found 1 3 3800.0000 3 3800.0000 11 User: 1 *** Calling cut generator. No cuts found * 2 0 integral 0 3800.0000 3800.0000 12 0.00% User cuts applied: 6 MIP status(101): integer optimal solution Fixing integer variables, and solving final LP... Iteration Dual Objective In Variable Out Variable 1 sI 0.000000 z defobj artif 2 8000.000000 slack(r8) x(c3) 3 3938.461538 slack(r10) slack(r5) 4 3800.000000 slack(r5) x(c2) 5 3800.000000 slack(r9) mk(r9) artif Fixed MIP status(1): optimal Proven optimal solution. MIP Solution: 3800.000000 (12 iterations, 3 nodes) Final Solve: 3800.000000 (5 iterations) Best possible: 3800.000000 Absolute gap: 0.000000 Relative gap: 0.000000 --- Restarting execution --- bchmknap.gms(75) 0 Mb --- Reading solution for model m *** Status: Normal completion --- Job bchmknap.gms Stop 08/06/10 04:36:59 elapsed 0:00:00.758

### Selected Portion of the Listing File

MODEL STATISTICS BLOCKS OF EQUATIONS 2 SINGLE EQUATIONS 11 BLOCKS OF VARIABLES 3 SINGLE VARIABLES 17 NON ZERO ELEMENTS 68 DISCRETE VARIABLES 6 GENERATION TIME = 0.000 SECONDS 4 Mb WIN235-235 Jul 2, 2010 EXECUTION TIME = 0.000 SECONDS 4 Mb WIN235-235 Jul 2, 2010 GAMS Rev 235 WEX-VS8 23.5.1 x86/MS Windows 08/06/10 04:36:58 Page 5 Multi knapsack problem using BCH Facility (BCHMKNAP,SEQ=289) Solution Report SOLVE m Using MIP From line 75 S O L V E S U M M A R Y MODEL m OBJECTIVE z TYPE MIP DIRECTION MAXIMIZE SOLVER CPLEX FROM LINE 75 **** SOLVER STATUS 1 Normal Completion **** MODEL STATUS 1 Optimal **** OBJECTIVE VALUE 3800.0000 RESOURCE USAGE, LIMIT 0.712 1000.000 ITERATION COUNT, LIMIT 17 2000000000 IBM ILOG CPLEX Jul 4, 2010 23.5.1 WIN 18414.18495 VS8 x86/MS Windows Cplex 12.2.0.0, GAMS Link 34 Reading parameter(s) from "C:\tmp\cplex.opt" >> usercutcall bchcover.inc mip=cplex >> cuts no >> preind 0 >> heurfreq -1 >> mipinterval 1 Finished reading from "C:\tmp\cplex.opt" Cplex MIP uses 1 of 8 parallel threads. Change default with option THREADS. *** Calling cut generator. =2 Added 2 cuts *** Calling cut generator. =2 Added 2 cuts *** Calling cut generator. =2 Added 2 cuts *** Calling cut generator. =2 Added 1 cut *** Calling cut generator. =2 Added 1 cut *** Calling cut generator. =2 No cuts found *** Calling cut generator. =2 No cuts found *** Calling cut generator. =2 Added 1 cut *** Calling cut generator. =2 No cuts found *** Calling cut generator. =2 No cuts found MIP status(101): integer optimal solution Fixed MIP status(1): optimal Proven optimal solution. MIP Solution: 3800.000000 (12 iterations, 3 nodes) Final Solve: 3800.000000 (5 iterations) Best possible: 3800.000000 Absolute gap: 0.000000 Relative gap: 0.000000 ---- EQU mk LOWER LEVEL UPPER MARGINAL r1 80.000 80.000 80.000 EPS r2 96.000 96.000 96.000 EPS r3 20.000 20.000 20.000 EPS r4 36.000 36.000 36.000 EPS r5 44.000 44.000 44.000 EPS r6 48.000 48.000 48.000 EPS r7 10.000 10.000 10.000 EPS r8 18.000 18.000 18.000 EPS r9 22.000 22.000 22.000 EPS r10 24.000 24.000 24.000 EPS LOWER LEVEL UPPER MARGINAL ---- EQU defobj . . . 1.000 ---- VAR x LOWER LEVEL UPPER MARGINAL c1 . . 1.000 100.000 c2 . 1.000 1.000 600.000 c3 . 1.000 1.000 1200.000 c4 . . 1.000 2400.000 c5 . . 1.000 500.000 c6 . 1.000 1.000 2000.000 ---- VAR slack LOWER LEVEL UPPER MARGINAL r1 . 14.000 +INF . r2 . 30.000 +INF . r3 . 6.000 +INF . r4 . 6.000 +INF . r5 . 3.000 +INF . r6 . 7.000 +INF . r7 . 10.000 +INF . r8 . 14.000 +INF . r9 . 12.000 +INF . r10 . 14.000 +INF . LOWER LEVEL UPPER MARGINAL ---- VAR z -INF 3800.000 +INF . **** REPORT SUMMARY : 0 NONOPT 0 INFEASIBLE 0 UNBOUNDED

# Sensitivity Analysis with GAMS/CPLEX or GAMS/GUROBI

## Introduction

Sensitivity analysis (post-optimality analysis) in linear programming allows one to find out more about an optimal solution for a problem. In particular, objective ranging and right-hand-side ranging give information about how much an objective coefficient or a right-hand-side coefficient can change without changing the optimal basis. In other words, they give information about how sensitive the optimal basis is to a change in the objective function or a right-hand side.

Although not so much used in practical large scale modeling, and not available for mixed-integer models or non-linear models, ranging information can still be of use in some circumstances. This section describes how to produce ranging information when solving models with GAMS/CPLEX or GAMS/GUROBI.

## Printing Ranging Information in the Listing File

To include ranging information in the listing file requires an option file. To make use of that you either add the parameter `optfile=1`

to your command line or add the option to you model, i.e.:

... Model transport /All/; transport.OptFile=1; Solve transport Using LP Minimizing z; ...

The `OptFile`

suffix tells GAMS to tell the solver to look for an options file. For GAMS/Cplex, the name of the options file is `cplex.opt`

.

### GAMS/CPLEX

To write objective ranging information for a particular variable, put a line in the options file:

objrng "variable name"

where "variable name" represents an actual GAMS variable name.

The ObjRng option can be repeated to specify ranging for more than one variable. To specify ranging for all variables use keyword `all`

in GAMS/Cplex.

To write right-hand-side ranging for a particular equation, use a line with option RHSRng in the options file as follows:

rhsrng "equation name"

The option can be repeated just as with the ObjRng option. To specify ranging for all equations use keyword `all`

with GAMS/Cplex.

Example: Solving the model `trnsport.gms`

(from the model library) with GAMS/Cplex using

objrng all rhsrng all

as the contents of `cplex.opt`

, gives the following table in the listing file:

EQUATION NAME LOWER CURRENT UPPER ------------- ----- ------- ----- cost -INF 0 +INF supply(seattle) 300 350 625 supply(san-diego) 550 600 +INF demand(new-york) 50 325 375 demand(chicago) 25 300 350 demand(topeka) 0 275 325 VARIABLE NAME LOWER CURRENT UPPER ------------- ----- ------- ----- x(seattle, new-york) 0.216 0.225 0.225 x(seattle, chicago) 0 0.153 0.162 x(seattle, topeka) 0.126 0.162 +INF x(san-diego, new-york) 0.225 0.225 0.234 x(san-diego, chicago) 0.153 0.162 +INF x(san-diego, topeka) 0 0.126 0.162 z -INF 1 +INF

GAMS does not have the notion of an objective row, it only knows about an objective variable. GAMS/CPLEX therefore has added a dummy objective function only with a 1.0 in the position of the objective variable:

objective variable +----------------+-+----------------------+ | | | | | | | | original | | | | matrix | | | | | | | | |----------------+-+----------------------+ +----------------+-+----------------------+ dummy | 0 |1| 0 | objective row +----------------+-+----------------------+

### GAMS/GUROBI

To include ranging information in the listing file, put the option Sensitivity in a line in the options file:

sensitivity 1

If you run the `trnsport`

model with GAMS/GUROBI and this option file, your listing file will have theses additional lines:

LP status(2): Model was solved to optimality (subject to tolerances). Performing sensitivity analysis... Objective coefficient sensitivity VARIABLE NAME, LOWER, CURRENT, UPPER x(seattle,new-york), 0.225, 0.225, INF x(seattle,chicago), 0, 0.153, 0.162 x(seattle,topeka), 0.126, 0.162, INF x(san-diego,new-york), 0, 0.225, 0.225 x(san-diego,chicago), 0.153, 0.162, INF x(san-diego,topeka), 0, 0.126, 0.162 Variable lower bound sensitivity VARIABLE NAME, LOWER, CURRENT, UPPER x(seattle,new-york), 0, 0, 50 x(seattle,chicago), -INF, 0, 300 x(seattle,topeka), 0, 0, 50 x(san-diego,new-york), -INF, 0, 325 x(san-diego,chicago), -50, 0, 0 x(san-diego,topeka), -INF, 0, 275 Variable upper bound sensitivity VARIABLE NAME, LOWER, CURRENT, UPPER x(seattle,new-york), 0, INF, INF x(seattle,chicago), 300, INF, INF x(seattle,topeka), 0, INF, INF x(san-diego,new-york), 325, INF, INF x(san-diego,chicago), 0, INF, INF x(san-diego,topeka), 275, INF, INF Right-hand-side sensitivity EQUATION NAME, LOWER, CURRENT, UPPER supply(seattle), 300, 350, INF supply(san-diego), 600, 600, INF demand(new-york), 0, 325, 325 demand(chicago), 0, 300, 350 demand(topeka), 0, 275, 275

## Ranging Information Available Inside GAMS (GAMS/CPLEX only)

Printed information in the listing file is not always enough. The printed format cannot be changed and the numbers are not accessible for further computations. To address these problems, another CPLEX option RngRestart is available:

rngrestart "file name"

where "file name" represents an actual file name. For example, using an options file containing

rhsrng supply rhsrng demand rngrestart ranges.inc

will result in a file named `ranges.inc`

being written with the following contents:

* Include file with ranging information * The set RNGLIM /LO,UP/ is assumed to be * declared. PARAMETER supplyRNG(i,RNGLIM) / seattle.LO 300 seattle.UP 625 san-diego.LO 550 san-diego.UP +INF /; PARAMETER demandRNG(j,RNGLIM) / new-york.LO 50 new-york.UP 375 chicago.LO 25 chicago.UP 350 topeka.LO 0 topeka.UP 325 /;

For each equation specified, the ranging information is stored in a newly declared corresponding GAMS parameter. There are a couple of things to note about this parameter.

First, the name of the parameter is based on the name of the equation, but with `RNG`

appended. The user is responsible for ensuring that the new name does not exceed the maximum symbol name length of GAMS identifiers.

Second, the domain list of the new parameter is the same as the domain list for for the corresponding equation plus on new domain on the end. The user is responsible for ensuring that the new parameter does not exceed the maximum number of index positions.

# 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 the trace file gives. E.g., for a branch-and-bound based solver, we may want to have intermediate information about the solve for the rootnode, subnodes, and end results.

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.

## Usage

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`

).

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

## Solve trace file format

The column headers for solve trace files are as follows:

- lineNum: GAMS index to be able to read in the file as a table
- seriesID: S=start, N=Node, T=time information, E=end
- node: number of enumerated branch-and-bound nodes
- seconds: time after solve start
- bestFound: best integer solution at a given time or node
- bestBound: best bound at a given time or node