DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA067754
Title:
The Simplex SON Algorithm for LP/Embedded Network Problems.
Descriptive Note:
Research rept.,
Corporate Author:
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Report Date:
1979-01-01
Pagination or Media Count:
52.0
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 LPembedded 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, LPembedded network problems can be solved with less computer storage and significantly greater efficiency than available from standard linear programming methods.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE
