How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to render the problem feasible, but this seems rather different than the LP case)?
Finally, how hard is it to compute the minimum number of constraints that must be removed to render an LP (and/or IP) feasible?
Finding a minimum-cardinality MIS for a linear program is an NP-hard problem in general, see Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95(3):533–554, 2003. For this reason, commercial solvers such as CPLEX use heuristics to identify small IIS which are not necessarily of minimum cardinality. Notice that for a given LP, there may be multiple overlapping IISs. To achieve feasibility, one must delete at least one inequality from each IIS. The aforementioned paper therefore defines Min IIS Covers.
