Fast Heuristics for the Maximum Feasible Subsystem Problem
John W. Chinneck · INFORMS journal on computing · 2001
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.