DOI: 10.17798/bitlisfen.1804064 ISSN: 2147-3129

Geometric initialization: A strategy for accelerating the Simplex method

Ahmet Ağaoğlu
Show PDF Cite
The performance of the simplex method in solving linear programming (LP) problems is heavily influenced by the choice of the initial basic feasible solution. While Phase I of the simplex method identifies a feasible starting point, it does not explicitly aim to optimize this choice in terms of proximity to the optimal solution. This paper presents a geometry-driven initialization strategy that leverages the convex polytope structure of the feasible region to improve the quality of the starting point and reduce the number of simplex iterations.The method begins from a feasible point and performs a series of interior moves to approach a boundary point near optimality. Once such a point is reached, the algorithm locates the nearest vertex, which is then used as the starting point for Phase II of the simplex method. The proposed approach preserves compatibility with the classical simplex framework and introduces no additional pivoting logic. Numerical experiments on synthetically generated LP instances, including problems with up to 200 variables and 400 constraints, demonstrate that the method consistently reduces both iteration counts and computation times. The method achieves an average iteration savings of 46.5% and a time savings of 30.4% compared to classical simplex implementations, with improvements being especially pronounced in large-scale problems.

More from our Archive