The Slope-Circuit Hybrid Method for Solving Degenerate Two-Dimensional Linear Programs
Article Sidebar
Main Article Content
Abstract
Traditional linear programming (LP) methods, like the simplex algorithm, often struggle with the efficiency of solving degenerate LP problems. This study introduces the slopecircuit hybrid method, an innovative interior search technique designed to overcome these
challenges by strategically combining slope-based analysis and circuit direction search. This method accelerates convergence, yielding optimal solutions. Focusing on degenerate constraints, the algorithm intelligently selects an initial circuit direction using slope information. The circuit direction search adeptly navigates the next direction to improve a solution, resulting in a significant reduction in iterations. Rigorous termination at an optimal solution is guaranteed through the computation of associated dual variables. Empirical testing on degenerate 2D linear programs supports substantial performance enhancements over simplex, interior point, and slope algorithms, evident in reduced iterations and improved running time. The slope-circuit hybrid method emerges as a promising solution for optimizing resource allocation in industrial settings, especially those constrained by limited computational resources. Its potential extends to streamlining decision-making processes and enhancing efficiency across various real-world applications.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Dantzig G.B. Linear programming and extensions. RAND Corporation: Santa Monica; 1963.
Klee V, Minty G. How good is the simplex algorithm. In Equalities. Academic Press: New York; 1972.
Shamos M, Dan Hoey. Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science; 1976. p.208-15.
Megiddo N. Linear-time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing. 1983:12(4);759-76.
Dyer M. Linear time algorithms for twoand three-variable linear programs, SIAM Journal on Computing. 1984:13(1);31-45.
A. Boonperm and K. Sinapiromsaran, “The artificial-free technique along the objective direction for the simplex algorithm,” Journal of Physics: Conference Series. 2014:490;012193.
Vitor F, Easton T. The double pivot simplex method. Mathematical Methods of Operations Research. 2018:87;109-37.
Jamrunroj P, Boonperm A. A New technique for solving a 2-dimensional linear program by considering the coefficient of constraints. Advances in Intelligent Systems and Computing. 2021:1324;276-86.
Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica. 1984:(4);373-95.
Anstreicher K.M. A standard form variant and safeguarded line search for the modified Karmarkar algorithm. Mathematical
Programming. 1990:47;337-51.
Ye Y. A class of projective transformations for linear programming. SIAM Journal on Computing. 1990:19;457-66.
Ye Y. Recovering optimal basic variables in Karmarkar’s polynomial algorithm for linear programming. Mathematics of Operations Research. 1990:15(3):564-72.
den Hertog D, Roos C. A survey of search directions in interior point methods for linear programming. Mathematical Programming. 1991:52;481-509.
Visuthirattanamanee R, Sinapiromsaran K, Boonperm A. Self-Regulating Artificial-Free Linear Programming Solver Using a Jump and Simplex Method. Mathematics. 2020:8(3);356-71.
Rockafellar R.T. The elementary vectors of a subspace of RN. In Combinatorial Mathematics and its Applications, University of North Carolina Press; 1969. p.104-27.
Graver J.E. On the foundation of linear and integer programming I. Mathematical Programming. 1975:9;207-26.
Bland R.G. New finite pivoting rules for the simplex method. Mathematics of Operations Research. 1977:2(2);103–7.
Bachem A, Kern W. Linear Programming Duality: An Introduction to Oriented Matroids. Universitext. Springer Verlag, 1984.
Fukuda K, Terlaky T. Criss-cross methods: A fresh view on pivot algorithms. Mathematical Programming, Ser. B. 1997:79(1-3);369-95.
Gauthier J.B, Desrosiers J, Lubbecke M. Decomposition theorems for linear programs. Operations Research Letters. 2014:42(8);553–7.
Hemmecke R, Onn S, Weismantel R. A polynomial oracle-time algorithm for convex integer minimization. Mathematical Programming, Ser. A. 2011:126;97–117.
De Loera J.A, Hemmecke R, Lee J. On augmentation algorithms for linear and integer-linear programming: from Edmonds-Karp to Bland and beyond. SIAM Journal on Optimization. 2015:25(4);2494-511.
Borgwardt S, Finhold E, Hemmecke R. On the circuit diameter of dual transportation polyhedra. SIAM Journal on Discrete Mathematics. 2016:29(1);113-21.
Jamrunroj P, Boonperm A. The Circuit Direction Search Algorithm for Solving Two-Dimensional Linear Programming Problems. Science & Technology Asia. 2023:28(1);48–59.