Paper Info
Title
A General Pricing Scheme for the Simplex Method
Abstract
In the simplex method for linear programming the algorithmic step of checking the reduced costs of nonbasic variables is called the “pricing” step. If these reduced costs are all of the “right sign” the current basis (and solution) is optimal, if not, this procedure selects a candidate vector that looks profitable for inclusion in the basis. While theoretically the choice of any profitable vector will lead to a finite termination (provided degeneracy is handled properly) but the number of iterations until termination depends very heavily on the actual choice (which is defined by the selection rule applied). Pricing has long been an area of heuristics to help make better selection. As a result, many different and sophisticated pricing strategies have been developed, implemented and tested. So far none of them is known to be dominating all others in all cases. Therefore, advanced simplex solvers need to be equipped with many strategies so that the most suitable one can be activated for each individual problem instance. In this paper we present a general pricing scheme. It creates a large flexibility in pricing. It is controlled by three parameters. With different settings of the parameters many of the known strategies can be reproduced as special cases. At the same time, the framework makes it possible to define new strategies or variants of them. The scheme is equally applicable to general and network simplex algorithms.
Year
DOI
Venue
2003
10.1023/B:ANOR.0000004769.36807.cf
Annals of Operations Research
Keywords
Field
DocType
Good Selection,Problem Instance,Selection Rule,Price Scheme,Simplex Method
Mathematical optimization,Simplex algorithm,Degeneracy (mathematics),Simplex,Heuristics,Linear programming,Pricing strategies,Mathematics
Journal
Volume
Issue
ISSN
124
1-4
1572-9338
Citations 
PageRank 
References 
3
0.43
8
Authors
1
Name
Order
Citations
PageRank
István Maros1315.84