A Practical Approach to Karmarkar's Algorithm.

Abstract

A practical approach to implementing Karmarkar's algorithm is discussed. A variant of the algorithm is proposed which still has polynomial complexity and which eliminates the need for Karmarkar's canonical form. This method allows upper and lower bounds to be used and does not require knowledge of the objective value. Some heuristics are given which alleviate certain computational difficulties that arise when a practical implementation of the algorithm is attempted. A FORTRAN program is described that allows one to study its convergence properties. Keywords: Linear Programming; Simplex Method; Least Squares Method; Iterations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1985
Accession Number
ADA155714

Entities

People

  • I. J. Lustig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Computations
  • Computer Programming
  • Computer Programs
  • Convergence
  • Engineering
  • Illinois
  • Industrial Engineering
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Simplex Method
  • United States
  • Universities

Readers

  • Operations Research
  • Systems Analysis and Design