COMPLEX: A COMPLEMENTARY SLACKNESS, OUT-OF-KILTER ALGORITHM FOR LINEAR PROGRAMMING
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
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.
- Operations Research