Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | |
| Published: |
Zenodo
2025
|
| Online Access: | https://doi.org/10.5281/zenodo.17604458 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- This paper introduces the Proximal Simplex algorithm, a novel hybrid method for solving linear programming problems. The algorithm is designed to bridge the gap between the two predominant classes of linear programming solvers: the combinatorial simplex method and continuous interior-point methods. Traditional simplex algorithms traverse the vertices of the feasible polyhedron, which can be inefficient in the worst case, while interior-point methods follow a central path in the interior of the feasible region but do not naturally yield the basic feasible solutions often required in practice. The Proximal Simplex method introduces a proximal regularization term to the linear objective function, creating a sequence of strictly convex subproblems. By carefully designing the solution of these subproblems and the update of the regularization parameter, the algorithm generates a trajectory that cuts through the interior of the feasible set while being drawn towards the combinatorial path of vertices. This approach combines the path-following nature of interior-point methods with the vertex-oriented progression of the simplex method. We provide a theoretical framework for the algorithm, analyze its convergence properties, and present computational results on a set of benchmark problems. The experiments demonstrate that the Proximal Simplex can offer a competitive alternative, sometimes outperforming standard simplex and interior-point implementations, particularly in terms of generating high-quality basic solutions efficiently.