5
$\begingroup$

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer programming (MIP) ? Note that I only would like to know whether the problem is infeasible.

So far, I believe the worst case scenario would be a NP-Hard problem modeled as either a LP or MIP and, determining whether our model is infeasible, would be NP-Hard as well, i. e. complexity of O(2n) where n is the number of variables in our model.

$\endgroup$
  • $\begingroup$ LP is in P, see e.g. here or here. IP feasibility is NP complete, seh here. I am not sure about MIP, but I guess, we could ask an oracle for the solution to the integer variables, fix them and solve the remaining LP in polynomial time, so MIP-feasibility should also be in NP and thus NP complete as IP is already NP complete. $\endgroup$ – T_O May 14 at 16:08
  • $\begingroup$ To clarify my last comment: Only IP-feasibility is NP-complete. IP-optimality is (to the best of our knowledge) harder as one has to show that there is no better solution. $\endgroup$ – T_O May 14 at 16:16
  • 5
    $\begingroup$ Thank you very much! You should post this as an answer. $\endgroup$ – G Oliveira May 14 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.