The Slope-Circuit Hybrid Method for Solving Degenerate Two-Dimensional Linear Programs

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.