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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1967
Accession Number
AD0662668

Entities

People

  • William S. Jewell

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Commerce
  • Composite Materials
  • Computer Programming
  • Contracts
  • Convex Programming
  • Diagrams
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • Operations Research
  • Optimization
  • Simplex Method

Readers

  • Operations Research