Proximal Simplex: Bridging Interior-Point Methods and Combinatorial Paths
Fuente:
Zenodo
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Recurso digital |
| Publié: |
Zenodo
2025
|
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866901471672401920 |
|---|---|
| author | SÉRGIO DE ANDRADE, PAULO |
| author_facet | SÉRGIO DE ANDRADE, PAULO |
| 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. |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_17604458 |
| institution | Zenodo |
| language | |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Proximal Simplex: Bridging Interior-Point Methods and Combinatorial Paths SÉRGIO DE ANDRADE, PAULO 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. |
| title | Proximal Simplex: Bridging Interior-Point Methods and Combinatorial Paths |
| url | https://doi.org/10.5281/zenodo.17604458 |