[Help-glpk] Re: sensitivity analysis

[Yingjie Lan]

> > 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?
> 
> Non-linear dependence leads to a non-linear program, so in
> this case
> the simplex method cannot be applied.
> 

No, I am not saying it is non-linear program, it is still
a linear program, but the parameters may be a non-linear
function of scaler t. In a more general case, t could be
a vector. A little bit like the confidence region in
statistic analysis, we could have a simultaneous region
of all the right-hand sides, for example. Such a region 
could be a polytope with the single parameter bounds as
its extreme points (a good paper could be produced on 
this, if not yet done), I think, but this is just an initial
conjecture. Then you could have a curve/shape parametrized
on t (t could be a vector). All you need is to find out the 
intersection of the curve/shape thing with the conjectured 
polytope thing. This is certainly a very difficult problem, 
I am not talking about analytical solution, I am only talking 
about numerical -- it is still very difficult.

> > 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,
> 
> Harder, but not extremely, because you have only one
> parameter, so
> some one-dimensional methods can be used, even a brute
> force technique.

True, even for one scaler t, but it is much harder than
solving for all the roots of a polynomial (for, even if all 
the parameters depend polynomially on t, you still have
a boundary region at least as complicated as a polytope). 

> 
> >  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.
> 
> Could you provide an example of the dependence?
> 

A simple form could be polynomial dependence on scaler t.