Solving LP problems using the ranking of the ratio of constraints’ coefficients
Authors: 
Dimitris G. Tsarmpopoulos, Christina D. Nikolakakou, George S. AndroulakisAuthors Info & Claims
Pages 130 - 133
Abstract
The present paper presents a methodology for solving a given linear programming problem. We extend the idea for the location of the binding constraints from two to n dimensions and we implement it in order to solve such LP problems. The proposed methodology classifies the constraints into two classes. The first of them consists of the majority of the binding constraints and is utilized for solving the corresponding linear programming problem. The second class is addressed primarily for verifying the validity of the remaining constraints and secondarily for the fine-tuning of the solution using the rest of the binding constraints. We test the proposed methodology in a set of random linear programming problems with interesting results.
References
[1]
Dimitris Bertsimas and John N Tsitsiklis. 1997. Introduction to Linear Optimization. Vol. 6. Athena Scientific, Belmont, MA.
[2]
A L Brearley, G Mitra, and H P Williams. 1975. Analysis of mathematical programming problems prior to applying the simplex algorithm. Mathematical Programming 8, 1 (1975), 54–83. https://doi.org/10.1007/BF01580428
[3]
R J Caron, J F McDonald, and C M Ponic. 1989. A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary. Journal of Optimization Theory and Applications 62, 2(1989), 225–237. https://doi.org/10.1007/BF00941055
[4]
Dominic Comtois. 2021. summarytools: Tools to Quickly and Neatly Summarize Data. https://github.com/dcomtois/summarytools R package version 1.0.0.
[5]
H W Corley, Jay Rosenberger, Wei-Chang Yeh, and T K Sung. 2006. The cosine simplex algorithm. The International Journal of Advanced Manufacturing Technology 27, 9(2006), 1047–1050.
[6]
Y Estiningsih, Farikhin, and R. H. Tjahjana. 2018. A comparison of Heuristic method and Llewellyn’s rules for identification of redundant constraints. Journal of Physics: Conference Series 983, 1 (2018). https://doi.org/10.1088/1742-6596/983/1/012083
[7]
Y Estiningsih, Farikhin, and R. H. Tjahjana. 2019. Some methods for identifying redundant constraints in linear programming. Journal of Physics: Conference Series 1321, 2 (2019). https://doi.org/10.1088/1742-6596/1321/2/022073
[8]
Y Estiningsih and R. H. Tjahjana. 2019. Modified Stojkovic-Stanimirovic method to find redundant constrains in linear programming problems. In Journal of Physics: Conference Series, Vol. 1321. IOP Publishing, 22074. https://doi.org/10.1088/1742-6596/1321/2/022074
[9]
Juan Frausto-Solís, Rafael Rivera-López, and F Ramos-Quintana. 2002. A Simplex-Genetic method for solving the Klee-Minty cube. WSEAS Transactions on Systems 2, 1 (2002), 232–237.
[10]
Tomas Gal. 1992. Weakly redundant constraints and their impact on postoptimal analyses in LP. European journal of operational research 60, 3 (1992), 315–326. https://doi.org/10.1016/0377-2217(92)90083-L
[11]
Simon Garnier. 2021. viridis: Colorblind-Friendly Color Maps for R. https://CRAN.R-project.org/package=viridis R package version 0.6.1.
[12]
Frederick S Hillier and Gerald J Lieberman. 2015. Introduction to operations research(10th ed.). McGraw-Hill Science, Engineering & Mathematics.
[13]
Ilya Ioslovich. 2001. Robust reduction of a class of large-scale linear programs. SIAM Journal on Optimization 12, 1 (2001), 262–282. https://doi.org/10.1137/S1052623497325454
[14]
Ilya Ioslovich and Per-Olof Gutman. 2000. Robust redundancy determination and evaluation of the dual variables of linear programming problems in the presence of uncertainty. IFAC Proceedings Volumes 33, 14 (2000), 149–154. https://doi.org/10.1016/S1474-6670(17)36220-1
[15]
Hélcio Vieira Junior and Marcos Pereira Estellita Lins. 2005. An improved initial basis for the Simplex algorithm. Computers and Operations Research 32, 8 (2005), 1983–1993. https://doi.org/10.1016/j.cor.2004.01.002
[16]
Stephen Milborrow. 2021. rpart.plot: Plot rpart Models: An Enhanced Version of plot.rpart. http://www.milbo.org/rpart-plot/index.html R package version 3.1.0.
[17]
Eirini I Nikolopoulou, George E Manoussakis, and George S. Androulakis. 2019. Locating Binding Constraints in LP Problems. American Journal of Operations Research 9, 02 (2019), 59. https://doi.org/10.4236/ajor.2019.92004
[18]
S Paulraj, C Chellappan, and T R Natesan. 2006. A heuristic approach for identification of redundant constraints in linear programming models. International Journal of computer mathematics 83, 8-9(2006), 675–683. https://doi.org/10.1080/ 00207160601014148
[19]
S Paulraj and P. Sumathi. 2010. A comparative study of redundant constraints identification methods in linear programming problems. Mathematical Problems in Engineering 2010 (2010). https://doi.org/10.1155/2010/723402
[20]
R Core Team. 2021. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/
[21]
Nebojša V Stojkovic and Predrag S Stanimirović. 2001. Two direct methods in linear programming. European Journal of Operational Research 131, 2 (2001), 417–439. https://doi.org/10.1016/S0377-2217(00)00083-7
[22]
P. Sumathi. 2016. A new approach to solve linear programming problem with intercept values. Journal of Information and Optimization Sciences 37, 4 (2016), 495–510. https://doi.org/10.1080/02522667.2014.996031
[23]
P. Sumathi, Dr P. Balachander, A. Karpagam, and P. Pugazhenthi. 2015. A New Tactic for Finding Irrelevant Constraints in Linear Programming Problems. International Journal of Scientific & Engineering Research 6, 3(2015).
[24]
P. Sumathi and A. Gangadharan. 2014. Selection of constraints with a new approach in linear programming problems. Applied Mathematical Sciences 8, 25-28 (2014), 1311–1321. https://doi.org/10.12988/ams.2014.42121
[25]
P. Sumathi and S Paulraj. 2013. Identification of redundant constraints in large scale linear programming problems with minimal computational effort. Applied Mathematical Sciences 7, 77-80 (2013), 3963–3974. https://doi.org/10.12988/ams.2013.36325
[26]
Jan Telgen. 1983. Identifying redundant constraints and implicit equalities in systems of linear constraints. Management Science 29, 10 (1983), 1209–1222. https://doi.org/10.1287/mnsc.29.10.1209s
[27]
Terry Therneau and Beth Atkinson. 2019. rpart: Recursive Partitioning and Regression Trees. https://CRAN.R-project.org/package=rpart R package version 4.1-15.
[28]
Dimitris G Tsarmpopoulos, Christina D Nikolakakou, and George S Androulakis. 2020. The sign of the slope of the objective function on identifying binding constraints in LP Problems. In 24th Panhellenic Conference on Informatics (PCI 2020). 260–263. https://doi.org/10.1145/3437120.3437320
[29]
Hadley Wickham, Winston Chang, Lionel Henry, Thomas Lin Pedersen, Kohske Takahashi, Claus Wilke, Kara Woo, Hiroaki Yutani, and Dewey Dunnington. 2021. ggplot2: Create Elegant Data Visualisations Using the Grammar of Graphics. https://CRAN.R-project.org/package=ggplot2 R package version 3.3.5.
[30]
Hadley Wickham and Jim Hester. 2021. readr: Read Rectangular Text Data. https://CRAN.R-project.org/package=readr R package version 2.0.2.
[31]
Yihui Xie. 2021. knitr: A General-Purpose Package for Dynamic Report Generation in R. https://yihui.org/knitr/ R package version 1.36.
[32]
Yaguang Yang. 2021. A modified row pivot simplex algorithm., 25 pages. arxiv:2107.08468http://arxiv.org/abs/2107.08468
[33]
Wei-Chang Yeh and H W Corley. 2009. A simple direct cosine simplex algorithm. Applied mathematics and Computation 214, 1 (2009), 178–186. https://doi.org/10.1016/ j.amc.2009.03.080
[34]
Hao Zhu. 2021. kableExtra: Construct Complex Table with kable and Pipe Syntax. https://CRAN.R-project.org/package=kableExtra R package version 1.3.4.
Index Terms
- Solving LP problems using the ranking of the ratio of constraints’ coefficients
Index terms have been assigned to the content through auto-classification.
Recommendations
A combination of a Proximity technique and Weighted average for LP Problems
PCI '22: Proceedings of the 26th Pan-Hellenic Conference on InformaticsIt is well known that, for the majority of large-scale LP problems, only a relatively small percentage of constraints are binding at the optimal solution. Redundancy may occur in the formulation phase of the LP problems and even if it does not alter ...
The sign of the slope of the objective function on identifying binding constraints in LP Problems
PCI '20: Proceedings of the 24th Pan-Hellenic Conference on InformaticsLinear programming (LP) is an important technique for solving linear optimization problems. Such problems arise in many applications and are described by a linear objective function and a set of linear constraints. In real world applications usually ...
Solving LP Problems via Weighted Centers
The feasibility problem for a system of linear inequalities can be converted into an unconstrained optimization problem by using ideas from the ellipsoid method, which can be viewed as a very simple minimization technique for the resulting nonlinear ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2021
499 pages
ISBN:9781450395557
DOI:10.1145/3503823
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 February 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
PCI 2021
Acceptance Rates
Overall Acceptance Rate 190 of 390 submissions, 49%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 44Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Sep 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format