User Tools

Site Tools


solver:sensitivity_analysis_parameter_ranges_for_lp

Sensitivity analysis (parameter ranges) for LP

How can I get sensitivity information (i.e. “parameter ranges”) for the rhs and objective function coefficients in a linear program?

There are two types of sensitivity information that one can extract from a solved GAMS model, information available within GAMS and information available only within the LP solver.

Upon solving an LP model, all GAMS solvers return 4 sets of values to GAMS: level and marginal values for the primal variables, and level and marginal values for the constraints. (N.B. The rhs term is not included in the level values for the constraints.) From this information, it is possible to compute, within the GAMS model, a range of parameter values for which the current solution (both primal and dual variables) will not change. Such a range of parameter values can be computed for all rhs coefficients having a zero marginal value, where the range of parameter values depends on the current level value for the constraint and the sense of the inequality in question.

Similarly, the set of obj. coefficients that can change without changing the primal or dual level values coincides with the set of primal variables currently at their bound. These coefficients can move an infinite amount in one direction, and a finite amount (determined by the marginal value or reduced cost) in the other. A simple example helps to demonstrate how this is below:

$offsymlist offsymxref offuellist offuelxref
option limrow=0, limcol=0;
sets
 I / 1 * 3 /,
 J / 1 * 4 /;

table A(I,J)
	1	2	3	4
1	1		1	
2	1	1	1	1
3		1			;

parameters
c(J) /
1	4,
2	1,
3	3,
4	1
/,
b(I) /
1	2,
2	4,
3	2
/;

free variable z;

positive variables
x(J);

equations
obj,
f(I);

obj ..	z =e= sum(J, c(J)*x(J) );

f(I) ..	sum(J, A(I,J)*x(J) ) =l= b(I);

model testlp / obj, f /;

solve testlp using lp maximizing z;

* here, we have all constraints active
* however, since the dual f.m("3") is 0, we know b("3") can be
* increased without bound, giving a "range" of [0 .. inf] for this solution

b("3") = b("3") + 8;

solve testlp using lp maximizing z;

* this demonstrates that the solution need not change from that above.
* in a LP of this form, we can decrease the c(j)'s for which x(j) = 0

c(J)$(x.l(J) eq x.lo(J)) = c(J) - 5;

solve testlp using lp maximizing z;

* now, note that since the duals (reduced costs)
* for c("3") and c("4") are negative,
* we know we can increase these c's by the negative of their reduced
* cost and decrease them without bound,
* while keeping the same solution
* this will introduce some degeneracy!!
c(J) = c(J) - x.m(J);

solve testlp using lp maximizing z;

************************************************************
* The complementarity slackness conditions for the LP can
* be written down and solved for explicitly using an LCP
************************************************************

positive variables
y(I);

equations
delx(J),
dely(I);

delx(J) ..	sum(I, y(I)*A(I,J) ) =g= c(J);
dely(I) ..	b(I) =g= sum(J, A(I,J)*x(J) );

model testlcp / delx.x, dely.y /;

* avoid repeating work already done
y.l(I) = f.m(I);
solve testlcp using mcp;

Note that we cannot address the issue of changing level values within the same basis in the GAMS model, since the GAMS model itself does not store the current basis matrix.

To determine the range of values a particular parameter can take without forcing a change in the current basis, but while allowing the level values to change, one must have a representation of the current basis. Since GAMS does not keep this information, these ranges must be produced by the LP solver. Documentation on how this is done using GAMS/CPLEX or GAMS/GUROBIis given here

solver/sensitivity_analysis_parameter_ranges_for_lp.txt · Last modified: 2010/03/29 13:36 by support