zbMATH — the first resource for mathematics

A variant of Karmarkar’s linear programming algorithm for problems with some unrestricted variables. (English) Zbl 0667.65048
Authors’ Summary: “A variant of the projective linear programming algorithm of N. Karmarkar [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] that can be used on problems with some unrestricted variables is considered. The variant is derived in two ways. One derivation involves eliminating the unconstrained variables, and the other involves solving a constrained least squares problem. The results of C. Gonzaga [A canonical projection algorithm for linear programming, Math. Programming (to appear)] are used to show that our algorithm converges in O(nq) iterations where n is the number of nonnegative variables and q is the precision required in the objective function value.”
The algorithm applies to problems, the value of which is not known in advance. A lower bound on this value is updated in each step in a similar way as proposed earlier by the second author and B. Burrell [Algorithmica 1, 409-424 (1986; Zbl 0621.90048)] for the case of only restricted variables.
Reviewer: R.Hettich

65K05 Numerical mathematical programming methods
90C05 Linear programming
65F50 Computational methods for sparse matrices
Full Text: DOI