Linear programming is a method for solving linear optimization problems with constraints, widely met in real-world applications. In the vast majority of these applications , the number of constraints is significantly larger than the number of variables. Since the crucial subject of these problems is to detect th e constraints that will be verified as equality in an optimal solution, there are methods for investigating such constraints to accelerate the whole proces s. In this paper, a technique named proximity technique is addressed, which under a proposed theoretical framework gives an ascending order to the constraints in such a way that those with low ranking are characterized of high priority to be binding. Under this framework, two new Linear programming optimization algorithms are introduced, based on a proposed Utility matrix and a utility vector accordingly. For testing the addressed algorithms firstly a generator of 10,000 random linear programming problems of dimension n with m constraints, where , is introduced in order to simulate as many as possible real-world problems, and secondly, real-life linear programming examples from the NETLIB repository are tested. A discussion of the numerical results is given. Furthermore, already known methods for solving linear programming problems are suggested to be fitted under the proposed framework.
Bertsimas, D. and Tsitsiklis, J.N. (1997) Introduction to Linear Optimization. Athena Scientific, Belmont. http://athenasc.com/linoptbook.html
Sumathi, P., Balachander, P., Karpagam, A. and Pugazhenthi, P. (2015) A New Tactic for Finding Irrelevant Constraints in Linear Programming Problems. International Journal of Scientific & Engineering Research, 6, 66-69.
Tsarmpopoulos, D.G., Nikolakakou, C.D. and Androulakis, G.S. (2020) The Sign of the Slope of the Objective Function on Identifying Binding Constraints in LP Problems. 24th Panhellenic Conference on Informatics (PCI 2020), Athens, 20-22 November 2020, 260-263. https://doi.org/10.1145/3437120.3437320
Corley Jr., H.W. and Rosenberger, J.M. (2011) System, Method and Apparatus for Allocating Resources by Constraint Selection. https://patentimages.storage.googleapis.com/28/74/03/78654f1a05591b/US8082549.pdf
Corley, H.W., Noroziroshan, A. and Rosenberger, J.M. (2017) Posterior Constraint Selection for Nonnegative Linear Programming. American Journal of Operations Research, 7, 26-40. https://doi.org/10.4236/ajor.2017.71002
Noroziroshan, A., Corley, H.W. and Rosenberger, J.M. (2015) A Dynamic Active-Set Method for Linear Programming. American Journal of Operations Research, 5, 526-535. https://doi.org/10.4236/ajor.2015.56041
Saito, G. (2012) Constraint Optimal Selection Techniques (Costs) for Linear Programming. https://rc.library.uta.edu/uta-ir/handle/10106/11066
Saito, G., Corley, H.W., Rosenberger, J.M., Sung, T.-K. and Noroziroshan, A. (2015) Constraint Optimal Selection Techniques (Costs) for Nonnegative Linear Programming Problems. Applied Mathematics and Computation, 251, 586-598. https://doi.org/10.1016/j.amc.2014.11.080
Sumathi, P. (2016) A New Approach to Solve Linear Programming Problem with Intercept Values. Journal of Information and Optimization Sciences, 37, 495-510. https://doi.org/10.1080/02522667.2014.996031
Corley, H.W., Rosenberger, J., Yeh, W.-C. and Sung, T.K. (2006) The Cosine Simplex Algorithm. The International Journal of Advanced Manufacturing Technology, 27, 1047-1050. https://doi.org/10.1007/s00170-004-2278-1
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
Dongarra, J. and Grosse, E. (1985) Netlib Repository at UTK and ORNL. http://www.netlib.org/
Telgen, J. (1983) Identifying Redundant Constraints and Implicit Equalities in Systems of Linear Constraints. Management Science, 29, 1209-1222. https://doi.org/10.1287/mnsc.29.10.1209
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
Gal, T. (1992) Weakly Redundant Constraints and Their Impact on Postoptimal Analyses in LP. European Journal of Operational Research, 60, 315-326. https://doi.org/10.1016/0377-2217(92)90083-L
Stojkovic, 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
Estiningsih, Y. and Tjahjana, R.H. (2019) Modified Stojkovic-Stanimirovic Method to Find Redundant Constrains in Linear Programming Problems. Journal of Physics: Conference Series, 1321, Article ID: 022074. https://doi.org/10.1088/1742-6596/1321/2/022074
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
Yang, Y.G. (2021) A Modified Row Pivot Simplex Algorithm. https://arxiv.org/abs/2107.08468v1
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
Ioslovich, I. and Gutman, P.-O. (2000) Robust Redundancy Determination and Evaluation of the Dual Variables of Linear Programming Problems in the Presence of Uncertainty. IFAC Proceedings Volumes, 33, 149-154. https://doi.org/10.1016/S1474-6670(17)36220-1
Ioslovich, I. (2001) Robust Reduction of a Class of Large-Scale Linear Programs. SIAM Journal on Optimization, 12, 262-282. https://doi.org/10.1137/S1052623497325454
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
Llewellyn, R.W. (1964) Linear Programming. Holt, Rinehart and Winston, New York. http://lib.ugent.be/catalog/rug01:000485171
Telgen, J. (1979) OnR.W. Llewellyn’s Rules to Identify Redundant Constraints: A Detailed Critique and Some Generalizations. Zeitschrift für Operations Research, 23, 197-206. https://doi.org/10.1007/BF01919484
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
Veni, K.K. and Balachandar, S.R. (2010) A New Heuristic Approach for Large Size Zero One Multi Knapsack Problem Using Intercept Matrix. International Journal of Computing Science and Mathematics, 4, 259-263.
Estiningsih, Y., Farikhin and Tjahjana, R.H. (2018) A Comparison of Heuristic Method and Llewellyn’s Rules for Identification of Redundant Constraints. Journal of Physics: Conference Series, 983, Article ID: 012069. https://doi.org/10.1088/1742-6596/983/1/012083
Estiningsih, Y., Farikhin and Tjahjana, R.H. (2019) Some Methods for Identifying Redundant Constraints in Linear Programming. Journal of Physics: Conference Series, 1321, Article ID: 022074. https://doi.org/10.1088/1742-6596/1321/2/022074
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
Tsarmpopoulos, D.G., Nikolakakou, C.D. and Androulakis, G.S. (2021) Solving LP Problems Using the Ranking of the Ratio of Constraints’ Coefficients. Proceedings of the 25th Pan-Hellenic Conference on Informatics, PCI’21, Volos, 26-28 November 2021, 130-133. https://doi.org/10.1145/3503823.3503848
Tsarmpopoulos, D.G., Nikolopoulou, E.I., Nikolakakou, C.D. and Androulakis, G.S. (2022) A Combination of a Proximity Technique and Weighted Average for LP Problems. In: Proceedings of the 26th Pan-Hellenic Conference on Informatics, PCI’22, Athens, 25-27 November 2022, 181-186. https://doi.org/10.1145/3575879.3575990
Hillier, F.S. and Lieberman, G.J. (2015) Introduction to Operations Research. 10th Edition, McGraw-Hill, New York.
Paulraj, S. and Sumathi, P. (2010) A Comparative Study of Redundant Constraints Identification Methods in Linear Programming Problems. Mathematical Problems in Engineering, 2010, Article ID: 723402. https://doi.org/10.1155/2010/723402
Jibrin, S. and Stover, D. (2007) Identifying Redundant Linear Constraints in Systems of Linear Matrix Inequality Constraints. Journal of Interdisciplinary Mathematics, 10, 601-617. https://doi.org/10.1080/09720502.2007.10700521
The R Project for Statistical Computing. https://www.r-project.org/
Wickham, H., Hester, J. and Bryan, J. (2022) readr: Read Rectangular Text Data. https://readr.tidyverse.org https://github.com/tidyverse/readr
Xie, Y.H. (2016) Bookdown: Authoring Books and Technical Documents with R Markdown. Chapman and Hall/CRC, Boca Raton. https://doi.org/10.1201/9781315204963
Xie, Y.H. (2022) Bookdown: Authoring Books and Technical Documents with R Markdown. R Package Version 0.25. https://bookdown.org/yihui/bookdown
Wickham, H., François, R., Henry, L., Müller, K. and Vaughan, D. (2023) dplyr: A Grammar of Data Manipulation. https://dplyr.tidyverse.org https://github.com/tidyverse/dplyr
Xie, Y.H. (2021) knitr: A General-Purpose Package for Dynamic Report Generation in R. R Package Version 1.37. https://yihui.org/knitr/
Wood, S. (2023) mgcv: Mixed GAM Computation Vehicle with Automatic Smoothness Estimation. R Package Version 1.9-0. https://CRAN.R-project.org/package=mgcv
Pinheiro, J., Bates, D. and R-Core (2021) nlme: Linear and Nonlinear Mixed Effects Models. R Package Version 3.1-153. https://svn.r-project.org/R-packages/trunk/nlme/
Wood, S.N. (2011) Fast Stable Restricted Maximum Likelihood and Marginal Likelihood Estimation of Semiparametric Generalized Linear Models. Journal of the Royal Statistical Society (B), 73, 3-36. https://doi.org/10.1111/j.1467-9868.2010.00749.x
Wood, S.N., Pya, N. and Safken, B. (2016) Smoothing Parameter and Model Selection for General Smooth Models (with Discussion). Journal of the American Statistical Association, 111, 1548-1575. https://doi.org/10.1080/01621459.2016.1180986
Wood, S.N. (2004) Stable and Efficient Multiple Smoothing Parameter Estimation for Generalized Additive Models. Journal of the American Statistical Association, 99, 673-686. https://doi.org/10.1198/016214504000000980
Wood, S.N. (2017) Generalized Additive Models: An Introduction with R. 2nd Edition, Chapman and Hall/CRC, Boca Raton. https://doi.org/10.1201/9781315370279
Wood, S.N. (2003) Thin-Plate Regression Splines. Journal of the Royal Statistical Society (B), 65, 95-114. https://doi.org/10.1111/1467-9868.00374
Wickham, H., Chang, W., Henry, L., Pedersen, T.L., Takahashi, K., Wilke, C., Woo, K., Yutani, H. and Dunnington, D. (2021) ggplot2: Create Elegant Data Visualisations Using the Grammar of Graphics. R Package Version 3.4.4. https://CRAN.R-project.org/package=ggplot2
Auguie, B. and Antonov, A. (2017) gridExtra: Miscellaneous Functions for “Grid” Graphics. R Package Version 2.3. https://CRAN.R-project.org/package=gridExtra
Neuwirth, E. (2014) RColorBrewer: ColorBrewer Palettes. R Package Version 1.1-3. https://CRAN.R-project.org/package=RColorBrewer
Lüdecke, D. (2021) sjPlot: Data Visualization for Statistics in Social Science. R Package Version 2.8.10. https://strengejacke.github.io/sjPlot/
Garnier, S., Ross, N., Rudis, R., Camargo, A.P., Sciaini, M., et al. (2021) viridis: Colorblind-Friendly Color Maps for R. R Package Version 0.6.4. https://CRAN.R-project.org/package=viridis
Garnier, S., Ross, N., Rudis, R., Camargo, A.P., Sciaini, M., et al. (2021) viridis: Colorblind-Friendly Color Maps for R. viridislite Package Version 0.4.2. https://CRAN.R-project.org/package=viridisLite
Wickham, H. (2016) ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag, New York. https://doi.org/10.1007/978-3-319-24277-4_9
Cheng, J., Sievert, C., Schloerke, B., Chang, W., Xie, Y.H. and Allen, J. (2021) htmltools: Tools for HTML. R Package Version 0.5.2. https://github.com/rstudio/htmltools
Long, J.A. (2021) jtools: Analysis and Presentation of Social Scientific Data. R Package Version 2.1.4. https://jtools.jacob-long.com
Zhu, H., et al. (2021) kableExtra: Construct Complex Table with “kable” and Pipe Syntax. https://CRAN.R-project.org/package=kableExtra
Therneau, T., et al. (2023) rpart: Recursive Partitioning and Regression Trees. R Package Version 4.1.21. https://CRAN.R-project.org/package=rpart
Milborrow, S. (2021) rpart.plot: Plot rpart Models: An Enhanced Version of plot.rpart. R Package Version 3.1.1. https://cran.r-project.org/web/packages/rpart.plot/inde
Data Repository for PRMAc and PRVac Algorithm for Linear Programming. https://github.com/gandroul/PRMac-PRVac
Nering, E.D. and Tucker, A.W. (1992) Linear Programs & Related Problems: A Volume in the Computer Science and Scientific Computing Series. Elsevier, Amsterdam.
Maurer, S.B. (1994) Linear Programs and Related Problems, by Evar D. Nering and Albert W. Tucker. The American Mathematical Monthly, 101, 1022-1026. https://doi.org/10.1080/00029890.1994.12004586
Daniel, R.C. (1998) Review of Linear Programming: Foundations and Extensions by R.J. Vanderbei. The Journal of the Operational Research Society, 49, 94-94. https://doi.org/10.2307/3010658
Vanderbei, R.J. (2014) Linear Programming Foundations and Extensions. 4th Edition, Springer, New York. https://doi.org/10.1007/978-1-4614-7630-6