GAMS [ Home | Downloads | Documentation | Solvers | APIs | Tools | Model Libraries | Resources | Sales | Support | Contact Us | Search ]

Advanced Solver Usage

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
UserHeurFreqDetermines the frequency of the heuristic model calls.10
UserHeurMult Determines the multiplier for the frequency of the heuristic model calls.2
UserHeurIntervalDetermines 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
UserHeurFirstCalls the heuristic for the first n nodes.10
UserHeurObjFirstSimilar 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)
UserHeurNewIntCalls the heuristic if the solver found a new integer feasible solution (yes/no).no
UserHeurCallThe GAMS command line (minus the GAMS executable name) to call the heuristic. no
UserHeurFreqDetermines the frequency of the cut generator model calls. 10
UserCutMultDetermines the multiplier for the frequency of the cut generator model calls. 2
UserCutIntervalDetermines the interval when to apply the multiplier for the frequency of the cut generator model calls. See UserHeurInterval for details. 100
UserCutFirstCalls the cut generator for the first n nodes.10
UserCutNewIntCalls the cut generator if the solver found a new integer feasible solution (yes/no). no
UserCutCallThe GAMS command line (minus the GAMS executable name) to call the cut generator.no
UserGDXInThe name of the GDX file read back into the solver.bchin.gdx
UserGDXNameThe name of the GDX file exported from the solver with the solution at the node.bchout.gdx
UserGDXNameIncThe name of the GDX file exported from the solver with the incumbent solution.bchout_i.gdx
UserGDXPrefixPrefixes UserGDXIn, UserGDXName, and UserGDXNameIncempty
UserIncbCcallThe 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
UserIncbICallThe GAMS command line to call the incumbent reporting program.empty
UserJobIDPostfixes listing and log file and adds –UserJobID to the User*Calls. Postfixes UserGDXIn, UserGDXName, and UserGDXNameIncempty
UserKeepCalls 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:

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:

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