×

Consistency, redundancy, and implied equalities in linear systems. (English) Zbl 0887.90114

Summary: Systems of linear inequalities have been studied for more than a century, but many of the results were developed during the early years of linear programming (1950s). New developments in linear programming plus interests in artificial intelligence have recently produced new results. One question is that of consistency: Does there exist a solution to satisfy all linear relations simultaneously? If so, are some of the relations redundant – that is, implied by the others? Are there implied equalities – that is, does some (weak) inequality have to hold with equality in every feasible solution? This paper brings together the main theorems that address these questions, unifies the framework, and presents some new results.

MSC:

90C05 Linear programming
65F10 Iterative numerical methods for linear systems
15A39 Linear inequalities of matrices

Software:

MINOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler and R.D.C. Monteiro, A geometric view of parametric linear programming,Algorithmica 8 (1992) 161–176. · Zbl 0767.90042 · doi:10.1007/BF01758841
[2] E. Amaldi and V. Kann,The complexity and approximability of finding maximum feasible subsystems of linear relations, Technical Report ORWP 93/11, Département de Mathématiques, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland (1993).
[3] E. Amaldi and V. Kann,On the approximability of removing the smallest number of relations from linear systems to achieve feasibility, Technical Report ORWP 94/6, Département de Mathématiques, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland (1994). · Zbl 0941.90504
[4] A. Boneh, Identification of redundancy by set-covering equivalence,Operational Research, ed. J.P. Brans (Elsevier, Amsterdam, The Netherlands, 1984) pp. 407–422.
[5] A. Boneh, S. Boneh and R.J. Caron, Constraint classification in mathematical programming,Math. Program. 61 (1993) 61–73. · Zbl 0782.90104 · doi:10.1007/BF01582139
[6] A. Boneh, R.J. Caron, F.W. Lemire, J.F. McDonald, J. Telgen and T. Vorst, Note on prime representations of convex polyhedral sets,J. Optim. Theory and Appl. 61 (1989) 137–142. · Zbl 0643.90049 · doi:10.1007/BF00940849
[7] R.J. Caron, J.F. McDonald and C.M. Ponic, A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary,J. Optim. Theory and Appl. 62 (1989) 225–237. · Zbl 0651.90047 · doi:10.1007/BF00941055
[8] W.B. Carver, Systems of linear inequalities,Ann. Math. 23,Ser. 2 (1921) 212–220. · JFM 48.0118.06 · doi:10.2307/1967919
[9] N. Chakravarti, Some results concerning post-nfeasibility analysis,Eur. J. Oper. Res. 73 (1994) 139–143. · Zbl 0806.90082 · doi:10.1016/0377-2217(94)90152-X
[10] A. Charnes and W.W. Cooper, Management models and industrial applications of linear programming,Manag. Sci. 4 (1957) 38–91. · Zbl 0995.90552 · doi:10.1287/mnsc.4.1.38
[11] M.C. Cheng, General criteria for redundant and nonredundant/linear inequalities,J. Optim. Theory and Appl. 53 (1987) 37–42. · Zbl 0593.90048 · doi:10.1007/BF00938815
[12] J.W. Chinneck, Localizing and diagnosing infeasibilities in networks, Technical Report SCE-90-14, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (1990). · Zbl 0855.90130
[13] J.W. Chinneck, Formulating processing network models: Viability theory,Naval Res. Logistics 37 (1990) 245–261. · Zbl 0803.90054 · doi:10.1002/1520-6750(199004)37:2<245::AID-NAV3220370205>3.0.CO;2-D
[14] J.W. Chinneck, Viability analysis: A formulation aid for all classes of network models,Naval Res. Logistics 39 (1992) 531–543. · Zbl 0825.90373 · doi:10.1002/1520-6750(199206)39:4<531::AID-NAV3220390407>3.0.CO;2-K
[15] J.W. Chinneck, Finding minimal infeasible sets of constraints in infeasible mathematical programs, Technical Report SCE-93-01, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (1993).
[16] J.W. Chinneck, Finding the most useful subset of constraints for analysis in an infeasible linear program, Technical Report SCE-93-07, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (1993).
[17] J.W. Chinneck, MINOS(IIS): Infeasibility analysis using MINOS,Comp. and Oper. Res. 21 (1994) 1–9. · Zbl 0800.90688 · doi:10.1016/0305-0548(94)90057-4
[18] J.W. Chinneck, An effective polynomial-time heuristic for the minimum-cardinality IIS setcovering problem,Ann. of Math. and AI 17 (1996) 127–144, this issue. · Zbl 0887.90112
[19] J.W. Chinneck and E.W. Dravnieks, Locating minimal infeasible constraint sets in linear programs,ORSA J. Comput. 3 (1991) 157–168. · Zbl 0755.90055
[20] J.W. Chinneck and W. Michalowski,MOLP formulation assistance using LP infeasibility analysis, Technical Report SCE-94-17, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (1994). · Zbl 0857.90110
[21] V. Chvátal, A greedy heuristic for the set covering problem,Math. Oper. Res. 4 (1979) 568–581.
[22] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[23] C.J. Debrosse and A.W. Westerberg, A feasible-point algorithm for structured design systems in chemical engineering,AIChE J. 19 (1973) 251–258. · doi:10.1002/aic.690190208
[24] E.W. Dravnieks, Identifying minimal sets of inconsistent constraints in linear programs: Deletion, squeeze and sensitivity filtering, M.Sc. Thesis, Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada (1989).
[25] K. Fan, On systems of linear inequalities, in ref. [66] pp. 99–156. · Zbl 0072.37602
[26] J. Farkas, Theorie der Einfachen Ungleichungen,J. reine und angewandte Math. 124 (1902) 1–27. · doi:10.1515/crll.1902.124.1
[27] L.R. Ford, Jr. and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962). · Zbl 0106.34802
[28] J.B.J. Fourier, Solution d’une question particulière du calcul des inégalités, Nouveau Bulletin des Sciences par la Société Philomathique de Paris (1826) 99–100.
[29] R.M. Freund, R. Roundy and M.J. Todd,Identifying the set of always-active constraints in a system of linear inequalities by a single linear program, Working Paper No. 1674-85 (Rev.), Sloan School of Management, MIT, Cambridge, MA 02139 (1985).
[30] D.R. Fulkerson, A network flow feasibility theorem and combinatorial applications,Can. J. Math. 11 (1959) 440–551. · Zbl 0098.33604 · doi:10.4153/CJM-1959-045-1
[31] D.R. Fulkerson, Networks, frames, blocking systems, in:Mathematics of the Decision Sciences: Part 1, eds. G.B. Dantzig and A.F. Veinott, Jr., Lectures in Applied Mathematics 11 (American Mathematical Society, Providence, RI, 1968) pp. 303–334. · Zbl 0182.53402
[32] T. Gal,Postoptimal Analyses, Parametric Programming, and Related Topics (McGraw-Hill, New York, NY, 1979; 2nd ed.: Walter de Gruyter, Berlin, 1995).
[33] T. Gal, Weakly redundant constraints and their impact on postoptimal analysis,Euro. J. Oper. Res. 60 (1992) 315–326. · Zbl 0762.90049 · doi:10.1016/0377-2217(92)90083-L
[34] D. Gale, Convex polyhedral cones and linear inequalities, in:Activity Analysis of Production and Allocation, ed. T.C. Koopmans (Wiley, New York, NY, 1951) pp. 287–297.
[35] D. Gale, A theorem in networks,Pacific J. Math. 7 (1957) 1073–1082. · Zbl 0087.16303
[36] S. Ghannadan and S.W. Wallace,Feasibility in capacitated networks: The effect of individual arcs and nodes, Technical Report, Department of Managerial Economics and Operations Research, Norwegian Institute of Technology, University of Trondheim, Norway (1994);Ann. of Math. and AI 17 (1996) 145–153, this issue. · Zbl 0891.68074
[37] S. Ghannadan and S.W. Wallace, Feasibility in uncapacitated networks: The effect of individual arcs and nodes,Ann. Oper. Res., to appear. · Zbl 0854.90062
[38] J.D. Gleeson, Diagnosing redundancy in large-scale linear programs, in:Final Report of Mathematics Clinic: Elements of an Intelligent Mathematical Programming System, ed. H.J. Greenberg, Mathematics Department, University of Colorado at Denver, Denver, CO (1989).
[39] J. Gleeson and J. Ryan, Identifying minimally infeasible subsystems of inequalities,ORSA J. Comput. 2 (1990) 61–63. · Zbl 0752.90050
[40] F. Glover,Netform modeling, Draft Monograph, School of Business, University of Colorado, Boulder, CO (1983).
[41] F. Glover, D. Klingman and N.V. Phillips,Network Models in Optimization and Their Applications in Practice (Wiley-Interscience, New York, NY, 1992).
[42] A.J. Goldman and A.W. Tucker, Theory of linear programming, in ref. [66] pp. 53–97. · Zbl 0072.37601
[43] R.A. Good, Systems of linear relations,SIAM Rev. 1 (1959) 1–31. · Zbl 0231.15006 · doi:10.1137/1001001
[44] H.J. Greenberg, An analysis of degeneracy,Naval Logistics Res. Quarterly 33 (1986) 635–655. · Zbl 0644.90058 · doi:10.1002/nav.3800330409
[45] H.J. Greenberg, Computer-assisted analysis for diagnosing infeasible or unbounded linear programs.Math. Program. Stud. 31 (1987) 79–97. · Zbl 0634.90043
[46] H.J. Greenberg, Diagnosing infeasibility for min-cost network flow models, Part I: Dual Infeasibility,IMA J. Math. in Management 1 (1987) 99–110. · Zbl 0677.90029 · doi:10.1093/imaman/1.2.99
[47] H.J. Greenberg, ANALYZE rulebase,Proc. NATO ASI: Mathematical Models for Decision Support (Springer, Berlin, 1988) pp. 229–238.
[48] H.J. Greenberg, Diagnosing infeasibility for min-cost network flow models, Part II: Primal Infeasibility,IMA J. Math. in Business and Industry 4 (1988) 39–50. · Zbl 0692.90046
[49] H.J. Greenberg, Intelligent analysis support for linear programs,Comp. and Chem. Eng. 16 (1992) 659–674. · doi:10.1016/0098-1354(92)80015-2
[50] H.J. Greenberg. An empirical analysis of infeasibility diagnosis for instances of linear programming blending models,IMA J. Math. in Business and Industry 4 (1992) 163–210. · Zbl 0825.90786
[51] H.J. Greenberg, Rule-based intelligence to support linear programming analysis,Decision Support Syst. 9 (1993) 425–448. · doi:10.1016/0167-9236(93)90051-4
[52] H.J. Greenberg,A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User’s Guide for ANALYZE (Kluwer, Boston, MA, 1993). · Zbl 0819.68025
[53] H.J. Greenberg, How to analyze results of linear programs, Part 3: Infeasibility diagnosis,Interfaces 23(6) (1993) 120–139. · doi:10.1287/inte.23.6.120
[54] H.J. Greenberg, How to analyze results of linear programs, Part 4: Forcing substructures,Interfaces 24 (1994) 121–130. · doi:10.1287/inte.24.1.121
[55] H.J. Greenberg, The use of the optimal partition in a linear programming solution for postoptimal analysis,Oper. Res. Lett. 15 (1994) 179–182. · Zbl 0814.90077 · doi:10.1016/0167-6377(94)90075-2
[56] H.J. Greenberg and F.H. Murphy, Approaches to diagnosing infeasibility for linear programs,ORSA J. Comput. 3 (1991) 253–261. · Zbl 0753.90041
[57] O. Güler, C. Roos, T. Terlaky and J.-Ph. Vial,Interior point approach to the theory of linear programming, Technical Report 92-21, Faculty of Technical Mathematics and Informatics/Computer Science, Delft University of Technology, Delft, The Netherlands (1992).
[58] A.J. Hoffman, Some recent applications of the theory of linear inequalities to external combinatorial analysis,Proc. Symposia on Applied Mathematics 10 (1960). · Zbl 0096.00606
[59] T. Huynh, L. Joskowics, C. Lassez and J.-L. Lassez, Practical tools for reasoning about linear constraints,Fundamenta Informaticae XV (1991) 357–379. · Zbl 0764.68152
[60] T. Huynh, C. Lassez and J.-L. Lassez, Practical issues on the projection of polyhedral sets,Ann. of Math. and AI 6 (1992) 295–316. · Zbl 0875.68821
[61] J-L. Imbert and P. Van Hentenryck,A note on redundant linear constraints, Technical Report, Department of Computer Science, Brown University, Providence, RI (1992);Ann. of Math. and AI 17 (1996) 85–106, this issue. · Zbl 0887.90115
[62] B. Jansen, J.J. de Jong, C. Roos and T. Terlaky,Sensitivity analysis in linear programming: just be careful!, Shell Report AMER 93.022, Shell International Oil Company, Amsterdam, The Netherlands (1993).
[63] B. Jansen, C. Roos and T. Terlaky, The theory of linear programming: skew symmetric self-dual problems and the central path,Optimization 29 (1994) 225–233. · Zbl 0820.90067 · doi:10.1080/02331939408843952
[64] R.G. Jeroslow, R.K. Martin, R.L. Rardin and J. Wang, Gainfree Leontief substitution flow problems,Math. Program. 57 (1992) 375–414. · Zbl 0778.90080 · doi:10.1007/BF01581090
[65] M.H. Karwan, V. Lofti, J. Telgen and S. Zionts,Redundancy in Mathematical Programming (Springer, Berlin, 1983). · Zbl 0524.90058
[66] H.W. Kuhn and A.W. Tucker,Annals of Mathematical Studies No. 38: Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ, 1956). · Zbl 0072.37502
[67] J.-L. Lassere, Consistency of a linear system of inequalities,Optim. Theory and Appl. 49 (1986) 177–179. · Zbl 0571.65049 · doi:10.1007/BF00939253
[68] J.-L. Lassez, Querying constraints,Proc. ACM Conf. on Principles of Database Systems, Nashville, TN (1990).
[69] J.-L. Lassez,From LP to LP: Programming with constraints, Technical Report, IBM T.J. Watson Research Center, Yorktown Heights, NY (1991).
[70] J.-L. Lassez and K. McAloon, Independence of negative constraints,Proc. Int. Joint Conf. on Theory and Practice of Software Development, Vol. I, Barcelona (1989) pp. 19–27.
[71] J.-L. Lassez and K. McAloon, A canonical form for generalized linear constraints,J. Symb. Comp. 13 (1992) 1–24. · Zbl 0745.90046 · doi:10.1016/0747-7171(92)90002-L
[72] J.-L. Lassez, K. McAloon and T. Huynh, Simplification and elimination of redundant linear arithmetic constraints,Proc. North American Conf. on Logic Programming, Cleveland, OH (1989) pp. 37–51.
[73] T.S. Motzkin,Beiträge zur Theorie der Linearen Ungleichungen, Ph.D. Dissertation, Azriel, Jerusalem (1936), [English transl. in:Contributions to the Theory of Linear Inequalities, RAND Corporation Translation 22, Santa Monica, CA (1952)].
[74] H. Nagamochi,Studies on multicommodity flows in directed networks, Doctorate Thesis, Kyoto University, Kyoto, Japan (1988).
[75] W.T. Obuchowska and R.J. Caron, Minimal representation of quadratically constrained convex feasible regions,Math. Program. 68 (1995) 169–186. · Zbl 0834.90102
[76] G.R. Parija and W.E. Wilhelm,A new algorithm for detecting redundant inequalities, Working Paper INEN/OR/WP/6/8-93, Department of Industrial Engineering, Texas A&M University, College Station, TX (1993).
[77] M.R. Parker,A set covering approach to infeasibilty analysis of linear programming problems and related issues, Ph.D. Thesis, Mathematics Department, University of Colorado at Denver, Denver, CO (1995).
[78] M.R. Parker and J. Ryan, Finding the minimum weight IIS cover of an infeasible system of linear inequalities,Ann. of Math. and AI 17 (1996) 107–126, this issue. · Zbl 0889.90110
[79] G.M. Roodman, Post-infeasibility analysis in linear programming,Manag. Sci. 9 (1979) 916–922. · doi:10.1287/mnsc.25.9.916
[80] C. Roos, Interior point approach to linear programming: Theory, algorithms and parametric analysis, in:Topics in Engineering: Modeling and Methods, eds. A.H.P. van der Burgh and J. Simonis (Kluwer Academic Publ., Dordrech, The Netherlands, 1992).
[81] C. Roos, Interior point methods for linear programming: Theory, algorithms and senisitivity analysis,Proc. Symp. on Engineering Mathematics, ed. T.F. Bewley (Kluwer Academic Publ., Dordrecht, The Netherlands, 1995).
[82] C. Roos and J.-P. Vial, Interior point methods for linear programming, Technical Report 94-77, Faculty of Technical Mathematics and Informatics/Computer Science, Delft University of Technology, Delft, The Netherlands (1994). · Zbl 0860.90087
[83] J. Ryan, Transversals of IIS-hypergraphs,Congressus Numerantium 81 (1991) 17–22. · Zbl 0765.05075
[84] J. Ryan,IIS-hypergraphs, Working Paper, US West Technologies, Boulder, CO (1994).
[85] J.K. Sankaran, A note on resolving infeasibility in linear programs by constraint relaxation,Oper. Res. Let. 13 (1993) 19–20. · Zbl 0771.90068 · doi:10.1016/0167-6377(93)90079-V
[86] A. Schrijver,Theory of Linear and Integer Programming (Wiley-Interscience, New York, NY, 1986). · Zbl 0665.90063
[87] P.J. Stuckey, Incremental linear constraint solving and detection of implicit equalities,ORSA J. Comput. 3 (1991) 269–274. · Zbl 0755.90058
[88] M. Tamiz, S.J. Mardle and D.F. Jones,Detecting IIS in infeasible linear programmes using techniques from goal programming, Technical Report, School of Mathematical Studies, University of Portsmouth, UK (1994). · Zbl 0868.90080
[89] J. Telgen,Redundancy and linear programs, Ph.D. Thesis (1979); also, published as Mathematical Centre Tracts 137 (Mathematisch Centrum, Amsterdam, The Netherlands, 1979).
[90] J. Telgen, Minimal representation of convex polyhedral sets,J. Optim. Theory and Appl. 38 (1982) 1–24. · Zbl 0471.93017 · doi:10.1007/BF00934319
[91] J. Telgen, Identifying redundant constraints and implicit equalities in systems of linear constraints,Manag. Sci. 29 (1983) 1209–1222. · Zbl 0527.90066 · doi:10.1287/mnsc.29.10.1209
[92] G.L. Thompson, F.M. Tonge and S. Zionts, Techniques for removing nonbinding constraints and extraneous variables from linear programming problems,Manag. Sci. 12 (1966) 588–608. · Zbl 0135.19904 · doi:10.1287/mnsc.12.7.588
[93] J.A. Tomlin and J.S. Welch, A pathological case in the reduction of linear programs,Oper. Res. Lett. 2 (1983) 53–57. · Zbl 0506.90050 · doi:10.1016/0167-6377(83)90036-6
[94] J.A. Tomlin and J.S. Welch, Formal optimization of some reduced linear programming problems,Math. Program. 27 (1983) 232–240. · Zbl 0535.90059 · doi:10.1007/BF02591947
[95] A.W. Tucker, Dual systems of homogeneous linear relations, in ref. [66] pp. 3–18. · Zbl 0072.37503
[96] J.N.M. van Loon, Irreducibly inconsistent systems of linear inequalities,Eur. J. Oper. Res. 8 (1981) 283–288. · Zbl 0468.90041 · doi:10.1016/0377-2217(81)90177-6
[97] S.W. Wallace and R.J-B. Wets, Preprocessing in stochastic programming: The case of uncapacitated networks,ORSA J. Comp. 1 (1990) 252–270. · Zbl 0752.90052
[98] S.W. Wallace and R.J-B. Wets, Preprocessing in stochastic programming: The case of linear programs,ORSA J. Comput. 4 (1992) 45–59. · Zbl 0760.90074
[99] S.W. Wallace and R.J-B. Wets, The facets of the polyhedral set determined by the Gale-Hoffman inequalities,Math. Program. 62 (1993) 215–222. · Zbl 0802.90041 · doi:10.1007/BF01585167
[100] S.W. Wallace and R.J-B. Wets, Preprocessing in stochastic programming: The case of capacitated networks,ORSA J. Comput. 7 (1995) 44–62. · Zbl 0822.90106
[101] H. Weyl, Elementare Theorie der Konvexen Polyeder,Commentarii Mathematici Helvetici 7 (1935) 290–306, [English transl.: Elementary theory of convex polyhedra, in:Contributions to the Theory of Games, eds. H.W. Kuhn and A.W. Tucker (Princeton University Press, Princeton, NJ, 1950) pp. 3–18.] · Zbl 0011.41104 · doi:10.1007/BF01292722
[102] H. Zullo,Feasibile flows in multicommodity graphs, Ph.D. Thesis, Mathematics Department, University of Colorado at Denver, Denver, CO (1995).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.