How to prove that an integer linear program is infeasible?

588 Views Asked by At

I have an ILP which I would like to show as infeasible. The naive idea I had was to try to show that the relaxed LP is also infeasible. Unfortunately, I know that the LP is feasible.

I want to know if there are any generic methods or conditions I can check for proving that an ILP is infeasible.

I would really appreciate if you can point to some reference material. I tried to Google for this, but couldn't get something which I could work with.