help-glpk
[Top][All Lists]

## [Help-glpk] Re: sensitivity analysis

 From: Yingjie Lan Subject: [Help-glpk] Re: sensitivity analysis Date: Fri, 15 Jan 2010 19:23:59 -0800 (PST)

```> 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 + t*c')*x + ... + (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.

```