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?