# Is the solution set of a linear program always bounded?

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?

## 1 Answer

• 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.

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