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

[Gabor Retvari]

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?

thanks,
Gabor

--

http://qosip.tmit.bme.hu/~retvari/index.html