Given an infeasible set of linear constraints, finding the maximum cardinality feasible subsystem is known as the maximum feasible subsystem problem. This problem is known to be NP-hard, but has many practical applications. This paper presents improved heuristics for solving the maximum feasible subsystem problem that are significantly faster than the original, but still highly accurate.

Additional Metadata
Keywords Analysis of Algorithms, Artificial intelligence, Heuristic, Linear programming
Journal INFORMS Journal on Computing
Chinneck, J. (2001). Fast Heuristics for the Maximum Feasible Subsystem Problem. INFORMS Journal on Computing, 13(3), 210–223.