[Help-glpk] Re: sensitivity analysis

[Andrew Makhorin]

> Thanks a lot for all this nice information on doing sensitivity
> analysis, I think I am learning a lot on GLPK API from your email. Now
> I have a more complicated situation: what if more than one parameters
> ( coeff. or rhs, or some thing in the matrix) change simultaneously,
> say as a function of time t. Now I want to know when would the optimal
> basis change. How would you suggest to do this in an efficient way?

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.)

> 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).