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 the constraints that
will be verified as equality in an optimal solution, there are methods for
investigating such constraints to accelerate the whole process. 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.
References
[1]
Bertsimas, D. and Tsitsiklis, J.N. (1997) Introduction to Linear Optimization. Athena Scientific, Belmont. http://athenasc.com/linoptbook.html
[2]
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.
[3]
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
[4]
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
[5]
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
[6]
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
[7]
Saito, G. (2012) Constraint Optimal Selection Techniques (Costs) for Linear Programming. https://rc.library.uta.edu/uta-ir/handle/10106/11066
[8]
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
[9]
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
[10]
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
[11]
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
[12]
Dongarra, J. and Grosse, E. (1985) Netlib Repository at UTK and ORNL. http://www.netlib.org/
[13]
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
[14]
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
[15]
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
[16]
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
[17]
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
[18]
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
[19]
Yang, Y.G. (2021) A Modified Row Pivot Simplex Algorithm. https://arxiv.org/abs/2107.08468v1
[20]
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
[21]
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
[22]
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
[23]
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
[24]
Llewellyn, R.W. (1964) Linear Programming. Holt, Rinehart and Winston, New York. http://lib.ugent.be/catalog/rug01:000485171
[25]
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
[26]
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
[27]
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.
[28]
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
[29]
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
[30]
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
[31]
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
[32]
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
[33]
Hillier, F.S. and Lieberman, G.J. (2015) Introduction to Operations Research. 10th Edition, McGraw-Hill, New York.
[34]
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
[35]
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
[36]
The R Project for Statistical Computing. https://www.r-project.org/
[37]
Wickham, H., Hester, J. and Bryan, J. (2022) readr: Read Rectangular Text Data. https://readr.tidyverse.org https://github.com/tidyverse/readr
[38]
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
[39]
Xie, Y.H. (2022) Bookdown: Authoring Books and Technical Documents with R Markdown. R Package Version 0.25. https://bookdown.org/yihui/bookdown
[40]
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
[41]
Xie, Y.H. (2021) knitr: A General-Purpose Package for Dynamic Report Generation in R. R Package Version 1.37. https://yihui.org/knitr/
[42]
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
[43]
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/
[44]
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
[45]
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
[46]
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
[47]
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
[48]
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
[49]
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
[50]
Auguie, B. and Antonov, A. (2017) gridExtra: Miscellaneous Functions for “Grid” Graphics. R Package Version 2.3. https://CRAN.R-project.org/package=gridExtra
[51]
Neuwirth, E. (2014) RColorBrewer: ColorBrewer Palettes. R Package Version 1.1-3. https://CRAN.R-project.org/package=RColorBrewer
[52]
Lüdecke, D. (2021) sjPlot: Data Visualization for Statistics in Social Science. R Package Version 2.8.10. https://strengejacke.github.io/sjPlot/
[53]
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
[54]
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
[55]
Wickham, H. (2016) ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag, New York. https://doi.org/10.1007/978-3-319-24277-4_9
[56]
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
[57]
Long, J.A. (2021) jtools: Analysis and Presentation of Social Scientific Data. R Package Version 2.1.4. https://jtools.jacob-long.com
[58]
Zhu, H., et al. (2021) kableExtra: Construct Complex Table with “kable” and Pipe Syntax. https://CRAN.R-project.org/package=kableExtra
[59]
Therneau, T., et al. (2023) rpart: Recursive Partitioning and Regression Trees. R Package Version 4.1.21. https://CRAN.R-project.org/package=rpart
[60]
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
[61]
Data Repository for PRMAc and PRVac Algorithm for Linear Programming. https://github.com/gandroul/PRMac-PRVac
[62]
Nering, E.D. and Tucker, A.W. (1992) Linear Programs & Related Problems: A Volume in the Computer Science and Scientific Computing Series. Elsevier, Amsterdam.
[63]
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
[64]
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
[65]
Vanderbei, R.J. (2014) Linear Programming Foundations and Extensions. 4th Edition, Springer, New York. https://doi.org/10.1007/978-1-4614-7630-6
