1
$\begingroup$

Say I have a system of linear equalities and inequalities with integer coefficients in $n$ variables, and let $R^n$ be the space of all possible solutions. I know that $\vec{0}$ is a solution.

Is there any efficient algorithm to check if there are any other solutions but zero? In other words, given a linear optimization problem, is there a way to check if the feasible region is a point?

$\endgroup$
3
  • $\begingroup$ You can use some LP solver to find the $\min f$ and $\max f$ for some non zero linear function $f$.. $\min f=\max f=0$ if and only if 0 is the unique point in your feasible region $\endgroup$ – Juan Pablo Contreras Jun 17 '15 at 17:29
  • $\begingroup$ Well, probably not... Say $f(x) = v * x$, if for every $x$ in the feasible region $v * x = 0$ that would imply by your assumption that the feasible region is a point while it could be a hyperplane... see my answer, it depends on $f$. $\endgroup$ – unddoch Jun 30 '15 at 14:15
  • $\begingroup$ I undertand!, I'm sorry for the omission. $\endgroup$ – Juan Pablo Contreras Jul 1 '15 at 12:14
0
$\begingroup$

I think the following is pretty much it:

Bring the problem into canonical form (where all variables are greater than zero) and checking for maximum of the function $f(x) = (1, 1, ...,1) * x$ using any LP solver.

Since no variable can be negative, the maximum can only be greater than 0 iff there's no unique solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.