# Knowing that a feasible solution exists and has a finite optimal solution

I have the following linear programming problem:

constraints:

$$x_1,x_2,x_3\geq200$$

$$0.45x_1+0.41x_2+0.5x_3 \leq 960$$

$$x_1+x_2+x_3 \leq 2000$$

$$x_2+x_3 \leq x_1$$

objective functions:

max $$0.35 x_{1}+0.41 x_{2} + 0.37 x_3$$

min $$0.45x1+0.41x_2+0.5x_3$$

How can I tell without solving the problem numerically that there is a feasible solution for both objective functions and a finite optimal solution?

Any advice about the theorem or the intuition would be greatly helpful!

• This may be related: cs.stackexchange.com/questions/13370/… – NoChance May 23 at 15:49
• In general, detecting feasibility is just as hard as deciding if an LP is optimal, because adding the constraint $c^\top x \leq z_0$ to the system, and performing a binary search procedure to identify the largest $z_0$ such that the new system is feasible is equivalent to solving the original problem (i.e. there is a polynomial time reduction from optimization to feasibility checking). Consequently, there is typically no easy way of detecting feasibility unless solving the problem is easy. One exception: you can usually check whether "obvious" solutions (e.g. a vector of all 0s) are feasible. – Ryan Cory-Wright May 23 at 16:08

## 1 Answer

As pointed out in the comments: We can easily construct a feasible solution, e.g. $$x_1=400, x_2=x_3=200$$ is feasible. It means that the feasible set is nonempty. The feasible set is bounded since $$200 <= x_i <= 2000$$ holds for all variables. I.e. we want to maximize a linear function over a nonempty bounded set. From this it follows that the problem has a finite optimal solution.