AN EFFECTIVE POLYNOMIAL-TIME HEURISTIC FOR THE MINIMUM-CARDINALITY IIS SET-COVERING PROBLEM

The state-of-the-art methods for analyzing infeasible linear programs concentrate on isolating Irreducible Infeasible Sets (IISs) of constra ints. However, when there are numerous infeasibilities in the model, i t is also useful to identify a minimum-cardinality set of constraints which, if removed from the LP, renders it feasible. This set of constr aints covers the IISs. This paper presents a heuristic algorithm for f inding a small-cardinality set of constraints which covers the IISs in an infeasible LP. Empirical tests show that it finds a true minimum-c ardinality cover over all of the examples in a test set, though this p erformance cannot be guaranteed in general.