Solving Staircase Linear Programs by the Simplex Method. 2. Pricing

摘要

This and a companion paper share one goal: to solve staircase-structured linear programs faster through adaptation of the algorithms of the modern simplex method. Their means are quite different however: whereas the preceding paper concentrated on 'inversion' algorithms that factorize the basis and solve linear systems, the present paper looks are 'pricing' algorithms that select a variable to enter the basis at each iteration. Pricing involves two sets of algorithms: computation algorithm that determine reduced costs of the nonbasic variables, and selection algorithms that choose among variables whose reduced costs are favorable. This paper develops staircase adaptations of both sorts of algorithms, and reports extensive (although preliminary) computational experience. Staircase computation algorithms appear to offer modest but consistent savings; staircase selection algorithms, properly chosen, may offer substantial savings in number of iterations, time per iteration, or sometimes both. (Author)