[Help-glpk] Re: sensitivity analysis

[Yingjie Lan]

> That you need is another kind of post-optimal analysis, so
> called
> parametric analysis. You define the objective function or
> rhs vector
> to depend on some scalar parameter t, for example:
> 
>    z = (c[1] + t*c'[1])*x[1] + ... + (c[n] +
> t*c'[n])*x[n],
> 
> and then see how the optimal solution is changing on
> varying t.
> 
> There exist efficient methods to perform the parametric
> analysis,
> unfortunately, in glpk this feature is not implemented yet.
> (I have it
> in the to-do list.)

I'm looking forward to it. In the example you have given, the params are 
linearly dependent on t -- what if the dependence is non-linear?

> 
> > One possible way I am thinking is to do something like
> a binary
> > search, and test if the basis remains optimal a long
> the way.
> 
> This technique may work, however, it is inefficient (and
> non-elegant).
> 

When the params (not just rhs, coefs, but also any entry in the contraint 
matrix) depends nonlinearly on scaler t, I wonder if there are some efficient 
algorithms. This problem seems extremely hard, as the set of t that shares the 
same optimal basis might be many disjoint intervals. We might just be satisfied 
with identifying one particular interval of t that contains some initial t_0.