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.
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
Andersen, E.D. and Andersen, K.D. (1995) Presolving in Linear Programming. Mathematical Programming, 71, 221-245. https://doi.org/10.1007/BF01586000
[6]
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
[7]
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
[8]
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.
[9]
Dantzig, G.B. (1955) Linear Programming under Uncertainty. Management Science, 1, 197-206. https://doi.org/10.1287/mnsc.1.3-4.197
[10]
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.
[11]
Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. (2011) Linear Programming and Network Flows. 4th Edition, Wiley, Hoboken.
[12]
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
[13]
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
[14]
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
[15]
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
[16]
Karmarkar, N. (1984) A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, 4, 373-395. https://doi.org/10.1007/BF02579150
[17]
Paparrizos, K. (1991) An Infeasible (Exterior Point) Simplex Algorithm for Assignment Problems. Mathematical Programming, 51, 45-54. https://doi.org/10.1007/BF01586925
[18]
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
[19]
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
[20]
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
[21]
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
[22]
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
[23]
Terlaky, T. (1996) Interior Point Methods of Mathematical Programming. Springer, Berlin. https://doi.org/10.1007/978-1-4613-3449-1
[24]
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
[25]
Zionts, S. (1965) Size of Reduction Techniques of Linear Programming and Their Applications. Carnegie Institute of Technology, Pittsburgh.
[26]
Lisy, J. (1971) Metody pro nalezini redundant omezini v ulohach linearniho programovani. Economicko Mathematicky Obzor, 7, 198-285.
[27]
Luenberger, D.G. (1973) Introduction to Linear and Nonlinear Programming. Addison Wesley Publishing Company, San Francisco.
[28]
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
[29]
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
[30]
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
[31]
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
[32]
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
[33]
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
[34]
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
[35]
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
[36]
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
[37]
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
[38]
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
[39]
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
[40]
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
[41]
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
[42]
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
[43]
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
[44]
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
[45]
Nikolopoulou, E.I. (2020) A Survey on Linear Constrained Models and Applications in Operational Research. Ph.D. Thesis, University of Patras, Patras.
[46]
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.
[47]
R Core Team (2019) R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna. https://www.R-project.org/
[48]
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
[49]
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
[50]
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
[51]
Everitt, B.S. and Skrondal, A. (2010) The Cambridge Dictionary of Statistics. https://www.stewartschultz.com/statistics/books/Cambridge%20Dictionary%20Statistics%204th.pdf
[52]
Fielding, A.H. (2006) Cluster and Classification Techniques for the Biosciences. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511607493
[53]
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
[54]
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
[55]
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.
[56]
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.
[57]
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
[58]
Han, J., Kamber, M. and Pei, J. (2012) Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, Waltham.
[59]
Loh, W.Y. and Shin, Y.S. (1997) Split Selection Methods for Classification Trees. Statistica Sinica, 7, 815-840.
