5

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.

G Oliveira
  • 51
  • 1
  • 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
  • 5
    Thank you very much! You should post this as an answer. – G Oliveira May 14 '20 at 19:13

0 Answers0