Repository logo
  • Log In
    Log in via Symplectic to deposit your publication(s).
Repository logo
  • Communities & Collections
  • Research Outputs
  • Statistics
  • Log In
    Log in via Symplectic to deposit your publication(s).
  1. Home
  2. Faculty of Engineering
  3. Computing
  4. Computing
  5. A general pricing scheme for the simplex method
 
  • Details
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.
Date Issued
2001-03-01
Citation
Departmental Technical Report: 01/3, 2001, pp.1-17
URI
http://hdl.handle.net/10044/1/95762
DOI
https://www.dx.doi.org/10.25561/95762
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/)
License URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Publication Status
Published
Article Number
01/3
About
Spiral Depositing with Spiral Publishing with Spiral Symplectic
Contact us
Open access team Report an issue
Other Services
Scholarly Communications Library Services
logo

Imperial College London

South Kensington Campus

London SW7 2AZ, UK

tel: +44 (0)20 7589 5111

Accessibility Modern slavery statement Cookie Policy

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback