Accession Number:

AD0662668

Title:

COMPLEX: A COMPLEMENTARY SLACKNESS, OUT-OF-KILTER ALGORITHM FOR LINEAR PROGRAMMING

Descriptive Note:

Research rept.

Corporate Author:

CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s):

Report Date:

1967-03-01

Pagination or Media Count:

96.0

Abstract:

An algorithm has been developed which uses the complementary slackness principle to take completely arbitrary primal and dual solutions to a linear program with doubly-bounded variables into the optimal solutions. The algorithm is not a new method viewed in the proper context, it can be thought of either as an elaboration of the primal-dual, composite, breakpoint-tracing, or complementary pivot algorithms as an extension of the out-of-kilter or black-box methods for network flows or, finally, even as a special way of looking at the original simplex algorithm. Almost all of the simpler procedures, such as Phase I, the dual simplex method, parametric programming, the primal-dual algorithm, etc. can be viewed as special cases of the complex algorithm which use special starting solutions and special heuristics.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE