# Complexity of determining whether a LP or MIP is infeasible

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.

• 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.
– T_O
May 14 '20 at 16:08
• 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.
– T_O
May 14 '20 at 16:16
• Thank you very much! You should post this as an answer. May 14 '20 at 19:13