| Article ID: | iaor20032986 |
| Country: | United States |
| Volume: | 13 |
| Issue: | 3 |
| Start Page Number: | 210 |
| End Page Number: | 223 |
| Publication Date: | Jul 2001 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Chinneck John W. |
| Keywords: | analysis of algorithms |
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.