[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: Sat, 16 Jan 2010 17:03:07 -0800 (PST)

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

reply via email to

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