An extension of Karmarkar's algorithm for linear programming using dual variables
type: Item
instance of: scholarly article
title: An extension of Karmarkar's algorithm for linear programming using dual variables
zbMATH Open document ID: 0621.90048
DOI: 10.1007/BF01840455
author: Michael J. Todd
author: Bruce P. Burrell
published in: Algorithmica
publication date: 1986-01-01T00:00:00Z
review text: The recent, but already classic projective algorithm of Karmarkar for linear programs is an interior point method, i.e. it generates a sequence of relative interior points of the feasible region, thereby reducing the objective value by a fixed factor. With an all integer problem the process may thus be stopped after a polynomial number of steps and the optimal solution obtained by rounding. The algorithm does however not generate dual solutions, of great importance in practice. This paper describes a variant of Karmarkar's method in which both primal and dual solutions are generated, converging to optimal primal and dual solutions respectively. The method applies when the optimal value of the problem is unknown, and has the same convergence properties as Karmarkar's. Details on efficient implementation using OR factorizations indicate the complexities of the calculations involved at each step, and shows how extreme point solutions may be derived at each step with minor additional work.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C06
zbMATH DE Number: 4008095
zbMATH Keywords: duality
zbMATH Keywords: Karmarkar's algorithm
zbMATH Keywords: dual solutions
zbMATH Keywords: extreme point solutions
zbMATH Keywords: OR factorizations
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: Programming with linear fractional functionals
cites work: Q3323698
cites work: Solution of sparse linear least squares problems using Givens rotations
cites work: Q5185900
cites work: Some Extensions of an Algorithm for Sparse Linear Least Squares Problems
cites work: A class of methods for linear programming
cites work: A new polynomial-time algorithm for linear programming
cites work: Extensions of Lemke's algorithm for the linear complementarity problem
full work available at URL: https://doi.org/10.1007/bf01840455
OpenAlex ID: W1982967176
description: scientific article; zbMATH DE number 4008095