Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does there exist a way to check if a linear programming problem is unbounded without solving it directly? In other words, How the unboundedness of an LP can be realized from its structure. Assume the corresponding feasible area is nonempty.

share|improve this question

migrated from scicomp.stackexchange.com Jul 25 '12 at 17:16

This question came from our site for scientists using computers to solve scientific problems.

1  
I recommend asking on Math.SE. Hopefully you already know basics like the weak duality theorem. –  David Ketcheson Jul 20 '12 at 13:42

1 Answer 1

Claim: Let ${\cal P}$ be the set of solutions of $$A x \leq b, $$ and suppose ${\cal P}$ is feasible. Then ${\cal P}$ is unbounded if and only if the set of solutions of $$Ax \leq 0$$ contains a nonzero point.

The ''if'' part is obvious. The only if part may be proved roughly as follows. Take $x$ to be some point in ${\cal P}$ and take $y_t$ to be a sequence in ${\cal P}$ whose norm approaches infinity. Let $d_t$ be the normalized direction vector $d_t=(y-x)/||y-x||_2$. Pick a convergent subsequence of the $d_t$ and argue that $A d_t \leq 0$.

What this means is that checking whether an LP is unbounded is not much easier that checking whether the solution set of an LP is feasible; in turn, that is not much easier than solving the LP itself.

Edit: If what is being asked about is whether the minimum of $c^T x$ over ${\cal P}$ is $-\infty$, then this has a similar answer: it is true if and only if there is a $d$ with $c^T d < 0, Ad \leq 0$. The argument is more or less the same.

share|improve this answer
    
But unboundedness with an LP doesn't refer to the feasible set; it refers to the objective function. You can have an unbounded feasible region without the LP itself being unbounded. –  Mike Spivey Jul 25 '12 at 20:31
    
I added an edit in case that is what was meant. If I'm still misunderstanding the question, presumably the OP can state it in precise language for those of us not familiar with what unboundendess of an LP refers to. –  alexx Jul 25 '12 at 20:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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