| |
[ Home | Support | Sales | Solvers | Documentation | Model Library | Search | Contact Us ] |
|---|
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 document describes how to produce ranging information when solving models with GAMS/Cplex or GAMS/OSL (a.k.a. OSL2).
Printing ranging information in the listing file
To include ranging information in the listing file, two model suffix values must be specified in the GAMS source code:
Model transport /All/; transport.DictFile = 4; transport.OptFile=1; Solve transport Using LP Minimizing z;The DictFile suffix tells GAMS to write the GAMS names for the model's variables and equations to a dictionary file. That file is then read by the solver (GAMS/Cplex or GAMS/OSL). By default no dictionary file is written.
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. For GAMS/OSL2, the name is osl2.opt.
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 or leave the variable name off for GAMS/OSL.
To write right-hand-side ranging for a particular equation, put a line 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 or leave the equation name off for GAMS/OSL.
Example
Solving the model trnsport.gms (from the model library) with Cplex using
objrng all rhsrng allas 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.009 0 0 X(SEATTLE,CHICAGO) -0.153 0 0.009 X(SEATTLE,TOPEKA) -0.036 0 +INF X(SAN-DIEGO,NEW-YORK) 0 0 0.009 X(SAN-DIEGO,CHICAGO) -0.009 0 +INF X(SAN-DIEGO,TOPEKA) -0.126 0 0.036 Z 0 1 +INFNotice that the current values of the objective function coefficients are all zero, except for the objective variable! 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 +----------------+-+----------------------+Ranging information available inside GAMS
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 option 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.incwill 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 original names are 28 or fewer characters long (GAMS names must be 31 or fewer characters long).
Second, the domain list of the new parameter is the same as the domain list for for the corresponding equation plus one new domain on the end. The user is responsible for ensuring that the ranged equations have 9 or fewer domains (GAMS allows 10 or fewer domains per variable or equation).
The new file with the range parameters can be used as an include file -- thereby allowing use of the parameters for calculations or report writing. In the current example, the following lines could be added at the end of trnsport.gms:
Solve transport using lp minimizing z ; Set RngLim /lo, up/; $include ranges.inc Display supplyRNG;The file ranges.inc is written during the execution of the Solve statement and is available immediately afterward. The Display statement would produce the following segment of trnsport.lst:
---- 89 PARAMETER supplyRNG lo up seattle 300.000 625.000 san-diego 550.000 +INFInterpreting "basis change" in OSL
There are some subtle differences in the ranging information supplied by the GAMS LP solvers. For example, when solving the LP
scalar b1 / 12 /; positive variables x, y, u1; free variable z; equations obj, f1, f2; obj .. z =e= x + y; f1 .. 2 * x + y =l= b1; f2 .. x + 2 * y =l= 4; model foo / obj, f1, f2 /; solve foo maximizing z using lp;the CPLEX LP solver would give the range [8, infinity) for the parameter b1. This range treats the point where equation f1 becomes binding, the variable y becomes basic, and the shadow price (dual value) associated with f1 becomes positive as a breakpoint in the solution space for the optimal primal and dual values, expressed as a function of the parameter b1. This is what one would normally expect.
The OSL solver indicates that the range of values for the rhs of equation f1 is [2, infinity). The lower bound of two is the parameter value at which the variable x (basic at the solution when b1 is in (2, infinity) becomes non-basic. What this range information fails to catch is the parameter value b1 = 8, where the variable y becomes basic (it is nonbasic at the solution when b1 > 8). OSL chooses to ignore this basis change as "uninteresting", since the leaving column is one that is not included in the original problem formulation.
In order to get the same behavior with GAMS/OSL and GAMS/CPLEX, it is necessary to add an explicit slack variable to this equation when using OSL, as follows:
f1 .. 2 * x + y + u1 =e= b1;When this slack column is included, OSL respects the change in basis when equation f1 becomes binding, and these solvers give the same results. A similar slack could be added to equation f2 as well.
In the example above, both solvers give an upper bound of infinity for the parameter associated with the slack constraint. This will not always be the case with OSL, however. Consider the following model.
sets I / 1 * 3 /, J / 1 * 2 /; table A(I,J) 1 2 1 1 2 1 1 3 1 ; parameters c(J) / 1 2, 2 1 /, b(I) / 1 8, 2 3, 3 2 /; positive variables x(J); free variable z; equations f(I), obj; obj .. z =e= sum(J, c(J)*x(J) ); f(I) .. sum(J, A(I,J)*x(J) ) =l= b(I); model bar / f, obj /; option lp=cplex; bar.optfile=1; solve bar using lp maximizing z;The optimal solution to model bar occurs at x = (2, 1), so that f(2) and f(3) are the active constraints. It is easy to see that b(1) can range between 1 and infinity without causing f(1) to become binding. However, as observed above, OSL pushes the value of b(1) down to zero before it sees an "interesting" basis change (i.e., x(2) leaves the basis), so OSL will give a lower bound of zero for the parameter b(1). In addition, OSL gives an upper bound of 3 for the parameter b(1), a value lower than the current parameter value. To explain this, we note that instead of determining a range of parameter values for slack constraints, OSL tries to determine how far the activity level (i.e. level values for the constraint body) can be moved before an "interesting" change in the basis occurs. The definition of "interesting" is somewhat involved.
If the level value can be decreased somewhat without violating any constraints or variable bounds, then the lower bound for the range is the value at which another constraint or variable bound first becomes active. If the level value cannot be decreased, then the constraints and bounds blocking this decrease are ignored during the computation of the lower bound. The upper bound on the range is computed in a similar fashion. Those having programming experience with OSL will perhaps recognize that this type of behavior is achieved by passing the value respect=1 to the OSL routine ekksbnd.
Although the explanation of how OSL gives rhs range information for
slack constraints is less than clear, one should remember that the ranges
for the parameter values (as opposed to the activity levels)
can be gotten from the marginal and level values for the rows in question,
both of which are available inside the GAMS model.