Re: [Help-glpk] LP Modeling question: avoiding 'x' to be a scalar multiple of 'y'

[Michael Hennebry]

On Wed, 7 Nov 2007, Gabor Retvari wrote:

> On Wednesday 07 November 2007, Michael Hennebry wrote:
> > On Wed, 7 Nov 2007, Gabor Retvari wrote:
> > > I would like to ask your help regarding a strange linear feasiility
> > > problem I have: I am serching for some [x,y] vector in a (polyhedral) set
> > > 'P', so that 'x' is not a scalar multiple of 'y'. That is, I want to find
> > >
> > > [x,y] \in P = {[x,y]: Ax + By \le b, x \ge 0, y \ge 0}
> > >
> > > such that there is no scalar k > 0, for which k * x = y !
>
> > The bad news is that you can't.
> > The good news is that you don't need to.
> > With floating point, it's rather unlikely that a
> > multidimensional y would be a scalar multiple of x.
>
> My problem is that a trivial solution, where 'y' is a scalar multiple of 'x',
> always exists, however, I am not interested in such trivial solutions. I ask
> whether or not there exists a non-trivial solution. Now, if I happen to get a
> solution where 'y' is not a scalar multiple of 'x', I am fine. But if I get a
> solution where 'y' _is_ a scalar multiple of 'x', I can't decide, whether
> there exist a non-trivial solution (only I failed to compute it) or there
> does not exist a non-trivial solution at all (and this is why I get a trivial
> one).
>
> Does this mean that only the 'bad news' part apply?

It means that you misunderstood the good news.
Does the following satify your criterion:
y=(1, 1), x=(1, 1.000000000000000000001) ?

In any case, I just noticed that this is a feasibility question.
That makes it easier.
If P is full dimensional you have feasibility.
If for nonnull y1, y2, k1 and k2
    (y1*k1, y1), (y2*k2, y2) in P
    k1 != k2
then you have feasibility.
If x and y have dimension n and P has dimension > n, you have feasibility.
Once you have k, minimize up to n linearly
independant linear functions of x-ky.
If they all produce zero, you have infeasibility.

-- 
Mike   address@hidden
"Horse guts never lie."  -- Cherek Bear-Shoulders