Solving Staircase Linear Programs by the Simplex Method, 1: Inversion.
Abstract
Problems of economic planning, production scheduling, inventory, transportation, control and multi-stage structural design have been modeled as linear programs that have a 'staircase' structure: their activities fall into a sequence of disjoint stages or periods, while their constraints relate only successive periods. At one time it was hoped that staircase linear programs would be particularly easy to solve, owing to their special structure, but experience with the most common solution technique -- the general simplex method -- has shown otherwise. Over the years many alternatives to the simplex method have also been proposed, but as yet none of these has been proved superior in solving a wide variety of staircase problems. This and a companion paper consider how the modern simplex method -- as implemented for large computers -- may be adapted to solve staircase linear programs more efficiently. Each paper looks at a set of algorithms within the simplex method: this one deals with 'inversion' of the basis -- more accurately, solution of linear systems by Gaussian elimination -- and its successor considers the task of 'pricing'.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1979
- Accession Number
- ADA081713
Entities
People
- Robert Fourer
Organizations
- Stanford University