The Simplex SON Algorithm for LP/Embedded Network Problems.
Abstract
This paper develops a special partitioning method for solving LP problems with embedded network structure. These problems include many of the large-scale LP problems of practical importance, particularly in the fields of energy, scheduling, and distribution. The special partitioning method, called the simplex special ordered network (SON) procedure, applies to LP problems that contain both non-network rows and non-network columns, with no restriction on the form of the rows and columns that do not exhibit a network structure. These LP/embedded network problems include as a special case multicommodity network problems and constrained network problems previously treated in the literature, by simultaneously encompassing both side constraints and side activities. The simplex SON procedure solves these problems by exploiting the network topology of the basis, whose properties are characterized by means of a specially constructed master basis tree. A set of fundamental exchange rules are developed which identify admissible ways to modify the master basis tree, and hence the composition of the partitioned basis inverse. The simplex SON method implements these rules by a set of streamlined labeling algorithms, while maintaining the network portion of the basis as large as possible, thereby accelerating the basis exchange step. As a result, LP/embedded network problems can be solved with less computer storage and significantly greater efficiency than available from standard linear programming methods.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1979
- Accession Number
- ADA067754
Entities
People
- Darwin Dee Klingman
- Fred W. Glover
Organizations
- University of Texas at Austin