A general pricing scheme for the simplex method
File(s)DTR01-3.pdf (137.57 KB)
Published version
Author(s)
Maros, Istvan
Type
Report
Abstract
Pricing is a term in the simplex method for linear programming used to refer to the
step of checking the reduced costs of nonbasic variables. If they 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.
step of checking the reduced costs of nonbasic variables. If they 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.
Date Issued
2001-03-01
Citation
Departmental Technical Report: 01/3, 2001, pp.1-17
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
17
Journal / Book Title
Departmental Technical Report: 01/3
Copyright Statement
© 2001 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Publication Status
Published
Article Number
01/3