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.

  • $\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
    Commented May 14, 2020 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
    Commented May 14, 2020 at 16:16
  • 5
    $\begingroup$ Thank you very much! You should post this as an answer. $\endgroup$
    – G Oliveira
    Commented May 14, 2020 at 19:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.