I have the following linear programming problem:



$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!

  • $\begingroup$ This may be related: cs.stackexchange.com/questions/13370/… $\endgroup$ – NoChance May 23 at 15:49
  • $\begingroup$ 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. $\endgroup$ – Ryan Cory-Wright May 23 at 16:08

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.


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.