A simplified homogeneous and self-dual linear programming algorithm and its implementation

Xiaojie Xu

doi:10.1007/BF02206815

Return

A simplified homogeneous and self-dual linear programming algorithm and its implementation

1996-12-01

PRE

Xiaojie Xu

Pi-Fang Hung

Yinyu Ye

DOI：10.1007/BF02206815

Original

Original request for help

Save

Abstract

En 中文

We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves O(root nL)-iteration complexity, where n and L are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply from x = e (primal variables), y = 0 (dual variables), z = e (dual slack variables), where e is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.

Keywords:

linear programming

homogeneous and self-dual linear feasibility model

predictor-corrector algorithm

implementation

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.