Abstract
We consider the problem Max FS: For a given infeasible linear system, determine a largest feasible subsystem. This problem has interesting applications in linear programming as well as in fields such as machine learning and statistical discriminant analysis. Max FS is N P-hard and also difficult to approximate. In this paper we examine structural and algorithmic properties of Max FS and of irreducible infeasible subsystems (IISs), which are intrinsically related, since one must delete at least one constraint from each IIS to attain feasibility. In particular, we establish: (i) that finding a smallest cardinality IIS is N P-hard as well as very difficult to approximate; (ii) a new simplex decomposition characterization of IISs; (iii) that for a given clutter, realizability as the IIS family for an infeasible linear system subsumes the Steinitz problem for polytopes; (iv) some results on the feasible subsystem polytope whose vertices are incidence vectors of feasible subsystems of a given infeasible system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. C. Aggarwal, R. K. Ahuja, J. Hao, and J. B. Orlin, Diagnosing infeasibilities in network flow problems, Mathematical Programming, 81 (1998), pp. 263–280.
E. Amaldi, From finding maximum feasible subsystems of linear systems to feed-forward neural network design, PhD thesis, Dep. of Mathematics, EPF-Lausanne, 1994.
E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Comput. Sci., 147 (1995), pp. 181–210.
—, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Comput. Sci., 209 (1998), pp. 237–260.
S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. Syst. Sci., 54 (1997), pp. 317–331.
A. Bachem and M. Grötschel, New aspects of polyhedral theory, in Optimization and Operations Research, A. Bachem, ed., Modern Applied Mathematics, North Holland, 1982, ch. I.2, pp. 51–106.
E. Balas and S. M. Ng, On the set covering polytope: All the facets with coefficients in {0,1,2}, Mathematical Programming, 43 (1989), pp. 57–69.
L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-Verlag, 1997.
J. Bokowski and B. Sturmfels, Computational Synthetic Geometry, no. 1355 in Lecture Notes in Mathematics, Springer-Verlag, 1989.
N. Chakravarti, Some results concerning post-infeasibility analysis, Eur. J. Oper. Res., 73 (1994), pp. 139–143.
J. Chinneck, Computer codes for the analysis of infeasible linear programs, J. Oper. Res. Soc., 47 (1996), pp. 61–72.
—, An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 127–144.
—, Feasibility and viability, in Advances in Sensitivity Analysis and Parametric Programming, T. Gál and H. Greenberg, eds., Kluwer Academic Publishers, 1997.
J. Chinneck and E. Dravnieks, Locating minimal infeasible constraint sets in linear programs, ORSA Journal on Computing, 3 (1991), pp. 157–168.
M. Dell’amico, F. Maffioli, and S. Martello, Annotated Bibliographies in Combinatorial Optimization, John Wiley, 1997.
K. Fan, On systems of linear inequalities, in Linear Inequalities and Related Systems, H. W. KUHN and A. W. TUCKER, eds., no. 38 in Annals of Mathematical Studies, Princeton University Press, NJ, 1956, pp. 99–156.
J. Gleeson and J. Ryan, Identifying minimally infeasible subsystems of inequalities, ORSA Journal on Computing, 2 (1990), pp. 61–63.
H. J. Greenberg, Consistency, redundancy, and implied equalities in linear systems, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 37–83.
H. J. Greenberg and F. H. Murphy, Approaches to diagnosing infeasible linear programs, ORSA Journal on Computing, 3 (1991), pp. 253–261.
J. Håastad, Some optimal inapproximability results, in Proc. Twenty-ninth Ann. ACM Symp. Theory of Comp., ACM, 1997, pp. 1–10.
M. Laurent, A generalization of antiwebs to independence systems and their canonical facets, Mathematical Programming, 45 (1989), pp. 97–108.
O. L. Mangasarian, Misclassification minimization, J. of Global Optimization, 5 (1994), pp. 309–323.
B. Mishra, Computational real algebraic geometry, in Handbook of Discrete and Computational Geometry, J. Goodman and J. O’Rouke, eds., CRC Press, 1997, ch. 29.
N. E. Mnëv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in Topology and Geometry — Rohlin Seminar, O. Y. Viro, ed., no. 1346 in Lecture Notes in Mathematics, Springer-Verlag, 1988, pp. 527–543.
T. S. Motzkin, Beiträge zur Theorie der Linearen Ungleichungen, PhD thesis, Basel, 1933.
M. Parker, A set covering approach to infeasibility analysis of linear programming problems and related issues, PhD thesis, Dep. of Mathematics, University of Colorado at Denver, 1995.
M. Parker and J. Ryan, Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 107–126.
J. Richter-Gebert, Realization Spaces of Polytopes, no. 1643 in Lecture Notes in Mathematics, Springer-Verlag, 1996.
J. Ryan, Transversals of IIS-hypergraphs, Congressus Numerantium, 81 (1991), pp. 17–22.
—, IIS-hypergraphs, SIAM J. Disc. Math., 9 (1996), pp. 643–653.
G. M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amaldi, E., Pfetsch, M.E., Trotter, L.E. (1999). Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem. In: Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds) Integer Programming and Combinatorial Optimization. IPCO 1999. Lecture Notes in Computer Science, vol 1610. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48777-8_4
Download citation
DOI: https://doi.org/10.1007/3-540-48777-8_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66019-4
Online ISBN: 978-3-540-48777-7
eBook Packages: Springer Book Archive