This paper presents a new dimension reduction strategy for medium and large-scale linear programming problems. The proposed method uses a subset of the original constraints and combines two algorithms: the weighted average and the cosine simplex algorithm. The first approach identifies binding constraints by using the weighted average of each constraint, whereas the second algorithm is based on the cosine similarity between the vector of the objective function and the constraints. These two approaches are complementary, and when used together, they locate the essential subset of initial constraints required for solving medium and large-scale linear programming problems. After reducing the dimension of the linear programming problem using the subset of the essential constraints, the solution method can be chosen from any suitable method for linear programming. The proposed approach was applied to a set of well-known benchmarks as well as more than 2000 random medium and large-scale linear programming problems. The results are promising, indicating that the new approach contributes to the reduction of both the size of the problems and the total number of iterations required. A tree-based classification model also confirmed the need for combining the two approaches. A detailed numerical example, the general numerical results, and the statistical analysis for the decision tree procedure are presented.
KeywordsLinear ProgrammingBinding ConstraintsDimension ReductionCosine SimilarityDecision AnalysisDecision Trees
Sergeant, C.R., Bazaraa, M.S. and Jarvis, J.J. (1978) Linear Programming and Network Flows. Journal of the Operational Research Society, 29, 510. https://doi.org/10.2307/3009778
Gal, T. (1992) Weakly Redundant Constraints and Their Impact on Post Optimal Analysis in LP. European Journal of Operational Research, 60, 315-326. https://doi.org/10.1016/0377-2217(92)90083-L
Karwan, M.H., Lotfi, V., Telgen, J. and Zionts, S. (1983) Redundancy in Mathematical Programming: A State-of-the-Art Survey. Springer-Verlag, Berlin. https://doi.org/10.1007/978-3-642-45535-3
Thompson, G.L., Tonge, F.M. and Zionts, S. (1966) Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems. Management Science, 12, 588-608. https://doi.org/10.1287/mnsc.12.7.588
Andersen, E.D. and Andersen, K.D. (1995) Presolving in Linear Programming. Mathematical Programming, 71, 221-245. https://doi.org/10.1007/BF01586000
Corley, H.W., Rosenberger, J., Yeh, W.C. and Sung, T.K. (2006) The Cosine Simplex Algorithm. International Journal of Advanced Manufacturing Technology, 27, 1047-1050. https://doi.org/10.1007/s00170-004-2278-1
Nikolopoulou, E.I., Manoussakis, G.E. and Androulakis, G.S. (2019) Locating Binding Constraints in LP Problems. American Journal of Operations Research, 9, 59-78. https://doi.org/10.4236/ajor.2019.92004
Dantzig, G.B. (1951) Maximization of a Linear Function of Variables Subject to Linear Inequalities. In: Koopmans, T.C., Ed., Activity Analysis of Production and Allocation, Wiley & Chapman-Hall, New York, 339-347.
Dantzig, G.B. (1955) Linear Programming under Uncertainty. Management Science, 1, 197-206. https://doi.org/10.1287/mnsc.1.3-4.197
Dantzig, G.B. (2016) Application of the Simplex Method to a Transportation Problem. In: Koopmans, T.C., Ed., Activity Analysis of Production and Allocation, John Wiley and Sons, New York, 359-373.
Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2011) Linear Programming and Network Flows. 4th Edition, Wiley, Hoboken.
Vanderbei, R.J. (2020) Linear Programming: Foundations and Extensions. International Series in Operations Research and Management Science, Vol. 285, Springer, Berlin. https://doi.org/10.1007/978-3-030-39415-8
Brown, G.W. and Koopmans, T.C. (1952) Computational Suggestions for Maximizing a Linear Function Subject to Linear Inequalities. In: Koopmans, T.C., Ed., Activity Analysis of Production and Allocation, Wiley, New York, 625-628. https://doi.org/10.2307/2226909
Khachiyan, L.G. (1980) Polynomial Algorithms in Linear Programming. USSR Computational Mathematics and Mathematical Physics, 20, 53-72. https://doi.org/10.1016/0041-5553(80)90061-0
Bland, R.G., Goldfarb, D. and Todd, M.J. (1981) Ellipsoid Method: A Survey. Operations Research, 29, 1039-1091. https://doi.org/10.1287/opre.29.6.1039
Karmarkar, N. (1984) A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, 4, 373-395. https://doi.org/10.1007/BF02579150
Paparrizos, K. (1991) An Infeasible (Exterior Point) Simplex Algorithm for Assignment Problems. Mathematical Programming, 51, 45-54. https://doi.org/10.1007/BF01586925
Paparrizos, K. (1993) An Exterior Point Simplex Algorithm for (General) Linear Programming Problems. Annals of Operations Research, 46-47, 497-508. https://doi.org/10.1007/BF02023111
Basu, A., De Loera, J.A. and Junod, M. (2014) On Chubanov’s Method for Linear Programming. INFORMS Journal on Computing, 26, 336-350. https://doi.org/10.1287/ijoc.2013.0569
Gleixner, A.M., Steffy, D.E. and Wolter, K. (2016) Iterative Refinement for Linear Programming. INFORMS Journal on Computing, 28, 449-464. https://doi.org/10.1287/ijoc.2016.0692
Omer, J., Rosat, S., Raymond, V. and Soumis, F. (2015) Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis. INFORMS Journal on Computing, 27, 773-787. https://doi.org/10.1287/ijoc.2015.0656
Triantafyllidis, C.P. and Samaras, N. (2020) A New Non-Monotonic Infeasible Simplex Type Algorithm for Linear Programming. PeerJ Computer Science, 6, e265. https://doi.org/10.7717/peerj-cs.265
Terlaky, T. (1996) Interior Point Methods of Mathematical Programming. Springer, Berlin. https://doi.org/10.1007/978-1-4613-3449-1
Boot, J.C.G. (1962) On Trivial and Binding Constraints in Programming Problems. Management Science, 8, 419-441. https://doi.org/10.1287/mnsc.8.4.419
Zionts, S. (1965) Size of Reduction Techniques of Linear Programming and Their Applications. Carnegie Institute of Technology, Pittsburgh.
Lisy, J. (1971) Metody pro nalezini redundant omezini v ulohach linearniho programovani. Economicko Mathematicky Obzor, 7, 198-285.
Luenberger, D.G. (1973) Introduction to Linear and Nonlinear Programming. Addison Wesley Publishing Company, San Francisco.
Mattheiss, T.H. (1973) An Algorithm for Determining Irrelevant Constraints and All Vertices in Systems of Linear Inequalities. Operations Research, 21, 247-260. https://doi.org/10.1287/opre.21.1.247
Brearley, A.L., Mitra, G. and Williams, H.P. (1975) Analysis of Mathematical Programming Problems Prior to Applying the Simplex Algorithm. Mathematical Programming, 8, 54-83. https://doi.org/10.1007/BF01580428
Gal, T. (1979) Weakly Redundant Constraints and Their Impact on Post Optimal Analysis. European Journal of Operational Research, 60, 315-326. https://doi.org/10.1016/0377-2217(92)90083-L
Telgen, J. (1983) Identifying Redundant Constraints and Implicit Equalities in Systems of Linear Constraints. Management Science, 39, 1209-1222. https://doi.org/10.1287/mnsc.29.10.1209
Hebert, T. and Tsai, S.Y.W. (1981) The Identification of Binding Constraints: A Directional Derivative Heuristic Approach. Computers, Environment and Urban Systems, 6, 115-125. https://doi.org/10.1016/0198-9715(81)90007-7
Gal, T. (1984) Linear Parameteric Programming—A Brief Survey. In: Fiacco, A.V., Ed., Sensitivity, Stability and Parametric Analysis, Springer, Berlin, 43-68. https://doi.org/10.1007/BFb0121210
Megiddo, N. (1984) Linear Programming in Linear Time When the Dimension Is Fixed. Journal of the ACM (JACM), 31, 114-127. https://doi.org/10.1145/2422.322418
Berbee, H.C.P., Boender, C.G.E., Rinnooy Ran, A.H.G., Scheffer, C.L., Smith, R.L. and Telgen, J. (1987) Hit-and-Run Algorithms for the Identification of Nonredundant Linear Inequalities. Mathematical Programming, 37, 184-207. https://doi.org/10.1007/BF02591694
Caron, R.J., McDonald, J.F. and Ponic, C.M. (1989) A Degenerate Extreme Point Strategy for the Classification of Linear Constraints as Redundant or Necessary. Journal of Optimization Theory and Applications, 62, 225-237. https://doi.org/10.1007/BF00941055
Ioslovich, I. (2002) Robust Reduction of a Class of Large-Scale Linear Programs. SIAM Journal on Optimization, 12, 262-282. https://doi.org/10.1137/S1052623497325454
Paulraj, S., Chellappan, C. and Natesan, T.R. (2006) A Heuristic Approach for Identification of Redundant Constraints in Linear Programming Models. International Journal of Computer Mathematics, 83, 675-683. https://doi.org/10.1080/00207160601014148
Gondzio, J. (1997) Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method. INFORMS Journal on Computing, 9, 73-91. https://doi.org/10.1287/ijoc.9.1.73
Stojković, N.V. and Stanimirović, P.S. (2001) Two Direct Methods in Linear Programming. European Journal of Operational Research, 131, 417-439. https://doi.org/10.1016/S0377-2217(00)00083-7
Bradley, G.H., Brown, G.G. and Graves, G.W. (1983) Structural Redundancy in Large-Scale Optimization Models. In: Karwan, M.H., Ed., Redundancy in Mathematical Programming: A State-of-the-Art Survey, Springer-Verlag, Berlin, 145-169. https://doi.org/10.1007/978-3-642-45535-3_12
Gutman, P.O. and Isolovich, I. (2007) On the Generalized Wolf Problem: Preprocessing of Nonnegative Large-Scale Linear Programming Problems with Group Constraints. Automation and Remote Control, 68, 1401-1409. https://doi.org/10.1134/S0005117907080115
Sumathi, P. and Paulraj, S. (2013) Identification of Redundant Constraints in Large Scale Linear Programming Problems with Minimal Computational Effort. Applied Mathematical Sciences, 7, 3963-3974. https://doi.org/10.12988/ams.2013.36325
Sumathi, P. and Gangadharan, A. (2014) Selection of Constraints with a New Approach in Linear Programming Problems. Applied Mathematical Sciences, 8, 1311-1321. https://doi.org/10.12988/ams.2014.42121
Nikolopoulou, E.I. (2020) A Survey on Linear Constrained Models and Applications in Operational Research. Ph.D. Thesis, University of Patras, Patras.
Nikolopoulou, E. and Androulakis, G.S. (2021) A Segmentation Rule to Determine Areas of Potential Binding and Non-Binding Constraints in LP Problems. 31st European Conference on Operational Research, Athens, 11-14 July 2021, 261.
R Core Team (2019) R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna. https://www.R-project.org/
Browne, S., Dongarra, J., Grosse, E. and Rowan, T. (1995) The Netlib Mathematical Software Repository. D-Lib Magazine, 1, 96. https://doi.org/10.1045/september95-browne
Maurer, S.B., Nering, E.D. and Tucker, A.W. (1994) Linear Programs and Related Problems. The American Mathematical Monthly, 101, 1022-1026. https://doi.org/10.2307/2975180
Breiman, L., Friedman, J.H., Olshen, R.A. and Stone, C.J. (2017) Classification and Regression Trees. Routledge, New York. https://doi.org/10.1201/9781315139470
Everitt, B.S. and Skrondal, A. (2010) The Cambridge Dictionary of Statistics. https://www.stewartschultz.com/statistics/books/Cambridge%20Dictionary%20Statistics%204th.pdf
Fielding, A.H. (2006) Cluster and Classification Techniques for the Biosciences. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511607493
Lim, T.S., Loh, W.Y. and Shih, Y.S. (2000) Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms. Machine Learning, 40, 203-228. https://doi.org/10.1023/A:1007608224229
Kass, G.V. (1980) An Exploratory Technique for Investigating Large Quantities of Categorical Data. Applied Statistics, 29, 119-127. https://doi.org/10.2307/2986296
Lewicki, P. and Hill, T. (2006) Statistics: Methods and Applications—A Comprehensive Reference for Science, Industry and Data Mining. Vol. 1, StatSoft Inc., St Tulsa.
Phelps, M.C. and Merkle, E.C. (2008) Classification and Regression Trees as Alternatives to Regression. 4th Annual GRASP Symposium, Wichita State University, 25 April 2008, 77-78.
Taylor, P.C. and Silverman, B.W. (1993) Block Diagrams and Splitting Criteria for Classification Trees. Statistics and Computing, 3, 147-161. https://doi.org/10.1007/BF00141771
Han, J., Kamber, M. and Pei, J. (2012) Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, Waltham.
Loh, W.Y. and Shin, Y.S. (1997) Split Selection Methods for Classification Trees. Statistica Sinica, 7, 815-840.