Paper Info
Title
Improved Primal Simplex: A More General Theoretical Framework And An Extended Experimental Analysis
Abstract
In this article, we propose a general framework for an algorithm derived from the primal simplex that guarantees a strict improvement in the objective after each iteration. Our approach relies on the identification of compatible variables that ensure a nondegenerate iteration if pivoted into the basis. The problem of finding a strict improvement in the objective function is proved to be equivalent to two smaller problems, respectively, focusing on compatible and incompatible variables. We then show that the improved primal simplex (IPS) is a particular implementation of this generic theoretical framework. The resulting new description of IPS naturally emphasizes what should be considered as necessary adaptations of the framework versus specific implementation choices. This provides original insight into IPS that allows for the identification of weaknesses and potential alternative choices that would extend the efficiency of the method to a wider set of problems. We perform experimental tests on an extended collection of data sets including instances of Mittelmann's benchmark for linear programming. The results confirm the excellent potential of IPS and highlight some of its limits while showing a path toward an improved implementation of the generic algorithm.
Year
DOI
Venue
2015
10.1287/ijoc.2015.0656
INFORMS JOURNAL ON COMPUTING
Keywords
Field
DocType
linear programming, simplex, degeneracy, decomposition, primal algorithms
Mathematical optimization,Data set,Compatibility (mechanics),Degeneracy (mathematics),Simplex,Linear programming,Mathematics,Genetic algorithm
Journal
Volume
Issue
ISSN
27
4
1091-9856
Citations 
PageRank 
References 
3
0.41
13
Authors
4
Name
Order
Citations
PageRank
Jérémy Omer1133.80
Samuel Rosat2162.72
Vincent Raymond330.41
François Soumis482197.64