Projection algorithms for linear programming

U. Betke, P. Gritzmann

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.

Original languageEnglish
Pages (from-to)287-295
Number of pages9
JournalEuropean Journal of Operational Research
Volume60
Issue number3
DOIs
StatePublished - 10 Aug 1992
Externally publishedYes

Keywords

  • BFGS-method
  • DFP-method
  • Linear programming
  • convex programming
  • ellipsoid method
  • nearest-point map
  • polynomial-time algorithms
  • variable metric algorithms

Fingerprint

Dive into the research topics of 'Projection algorithms for linear programming'. Together they form a unique fingerprint.

Cite this