Let $(P) \max\left\{c^T \cdot x \mid A \cdot x \leq b, x \geq 0\right\}$ be an arbitrary linear programming problem and $M$ its solution set. Is it possible to find out if $M$ is unbounded (in finite steps)?

I think the answer is yes because we have linear program here and that's why it's possible to tell in polynomial time if it has feasible solution or infeasible. So there must be an algorithm to do this in polynomial time e.g. in finite steps.

But I don't know any algorithm to do this. So far I've read about the simplex method in a book and if I understood correctly, if you run simplex method on the LP above, you will see in the table that the problem is unbounded because there will appear one or more variables where you can pivot these to $\infty$.

But this is only thought is it correct like that? Maybe it's possible with another way too?

  • 1
    $\begingroup$ Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$. $\endgroup$ – A.Γ. Nov 10 '18 at 11:14

$$\max c^Tx$$

subject to

$$Ax\le b$$

$$x \ge 0$$

Using the simplex algorithm, we can determine if there is a solution, $x^*$.

Now consider

$$\max e^Tx$$

subject to

$$Ax\le b$$ $$c^Tx=c^Tx^*$$ $$x \ge 0$$

where $e$ is the all-one vector.

We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.

  • $\begingroup$ Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")? $\endgroup$ – tenepolis Nov 10 '18 at 14:01
  • 1
    $\begingroup$ ah yes, it's my habit to use that notation. $\endgroup$ – Siong Thye Goh Nov 10 '18 at 14:06

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.