Re: [Help-glpk] [Fwd: help on interpreting sensitivity analysis]

[Marco Correia]

On Tuesday 12 July 2011 23:43:14 Andrew Makhorin wrote:
> > I have just started learning LP and glpk so apologies if I'm missing
> > something important.
> > 
> > I setup a problem (using the c interface), composed of the three
> > following constraints, and no objective function:
> > 
> > 4.0*x0 - x1 <= 3.0
> > 3.0*x0 + x1 >= 8.0
> > 2.0*x0 + x1 <= 7.5
> > 
> > where x0 and x1 are unbounded, and correspond to column 1 and 2.
> > 
> > The pdf file in attachment shows the feasible region of this system (x0
> > is vertical axis). From the docs I understood that the column Activity
> > Range allows me to obtain (among other things) the ranges that each
> > variable may take in order for the problem to stay feasible and optimal.
> > Please see the output of the print_ranges function attached. It shows a
> > correct interval for x0, but the upper bound of x1 is not correct, it
> > should be almost 7 as shown in the chart.
> > 
> > I suppose I'm assuming something that I shouldn't. Could someone please
> > point me in the right direction?
> 
> You didn't assign names to rows and columns, so some information
> in the analysis report was lost.
> 
> I rewrote your instance in cplex lp format:
> 
> minimize
>    z: 0 x0
> subject to
>    r1: 4.0 x0 - x1 <= 3.0
>    r2: 3.0 x0 + x1 >= 8.0
>    r3: 2.0 x0 + x1 <= 7.5
> bounds
>    x0 free
>    x1 free
> End
> 
> and solved it with glpsol as follows:
> 
>    glpsol --lp test.lp --ranges test.txt -o test.sol
> 
> In particular, for column x1 the analysis report (test.txt) says:
> 
> Column name:         x1
> St:                  BS
> Activity:            3.28571
> Obj.coef:            0.00000
> Marginal:            0.00000
> Lower bound:         -Inf
> Upper bound:         +Inf
> 
> This means that in the current basis (which is optimal) x1 is basic, and
> its value is 3.28571.
> 
> If the objective coefficient at x1 is decreasing (first line):
> Activity range:      4.00000
> Obj.coef.range:      0.00000
> Obj.value at
> break point:         0.00000
> Limiting variable:   r2
> 
> This means that if we would make the objective coefficient at x1 a bit
> less than zero (Obj.coef.range), the limiting variable, which is
> auxiliary variable r2, would enter the basis (that is, constraint r2
> would become inactive), and in the new adjacent optimal basis x1 would
> take on value 4.0.
> 
> If the objective coefficient at x1 is increasing (second line):
> Activity range:      3.28571
> Obj.coef.range:      +Inf
> Obj.value at
> break point:         +Inf
> Limiting variable:   (none)
> 
> This means that the current basis remain optimal for any positive
> objective coefficient at x1.
> 
> Note that the analysis has different meaning for basic and non-basic
> rows/columns. For more details please see the glpk reference manual. And
> check your plot; it looks incorrect.

Hi Andrew,

Thanks a lot for the quick reply. If my plot is incorrect then maybe it would 
explain my doubts. However, I cannot see why it is incorrect. In your naming 
of variables and constraints the xx axis would represent x1 and yy axis x2. 
The blue line is c1, the red c2, and the yellow c3. The interior of the 
triangle thus marks the feasible region.

If this is correct (please apologise if I'm making some basic mistake here), 
then I don't understand how the current basis remain optimal for any positive
objective coefficient after x1>=3.28571, as you said, since for approximately 
x>6.5 there is no feasible region.

Thanks again!
Marco

-- 
Marco Correia <address@hidden>