[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]