Let $$\max\left\{c^T \cdot x \mid A \cdot x \leq b, x \geq 0\right\}$$ be an arbitrary linear program and let $M$ be its solution set. Is $M$ always bounded?

I think the solution set of linear programming problem is not always bounded because let's say the linear programming problem is infeasible, so then $M$ is empty. Is that enough of reasoning? It can also be unbounded I think if the value of its objective function can be made arbitrarily large so in that case it would be unbounded since its optimum value is $+ \infty$. And if this is not the case then the LP is bounded but as we see this is not always the case. So the statement is false, right?

  • If $M$ is empty, it is bounded.

  • Also note that, $M$ is a solution set, not a linear programming problem.

  • The statement is indeed false, here is a way to make $M$ unbounded. We let $A=0$ and $x=0$ and $c=0$. Hence $M=\{ x \in \mathbb{R}^n|x \ge 0\}$. It is unbounded. To see it clearly note that $ke \in M$, where $k \ge 0$ can be made arbitrarily large and $e$ is the all ones vector.

  • $\begingroup$ Thank you very much for answer! Just one question, by "all ones vector" you mean a vector filled with only $1$'s, right? $\endgroup$ – tenepolis Nov 10 '18 at 10:37
  • 1
    $\begingroup$ yes, in $\mathbb{R}^2$, it is $(1,1)^T$. $\endgroup$ – Siong Thye Goh Nov 10 '18 at 10:40

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.