Exploiting special structure in Karmarkar's linear programming algorithm
type: Item
instance of: scholarly article
title: Exploiting special structure in Karmarkar's linear programming algorithm
zbMATH Open document ID: 0649.90070
DOI: 10.1007/BF01580755
author: Michael J. Todd
published in: Mathematical Programming. Series A. Series B
publication date: 1988-01-01T00:00:00Z
review text: Karmarkar's projective algorithm for solving linear programming problems is polynomial though the computational requirement at each iteration is very complicated. This article proposes a variant to Karmarkar's projective algorithm for solving a certain special class of linear programming problems, when linear constraints have a special structure. This variant is also polynomial. The special structure of the linear constraints permits to generate improved bounds and hence a better direction ande constrained cases are examined by the rejection, reduction and penalty methods. The relationship between our approach and the standard cases is explored. We then describe the mean value-level set method and prove its convergence (which does not depend on the choice of initial data) and the limited influence of the error propagation. The corresponding rejection, reduction and penalty algorithms are dicussed for constrained minimization problems. The optimality conditions and algorithms for integral global optimization can be implemented by the use of a proper designed Monte Carlo technique. Numerical tests have been done covering the examples of unconstrained and constrained problems and minimization of discontinuous functions and nonlinear integer programming problems, and problems with multiple global minimizers. The algorithms have been utilized to solve problems with variables up to 50 on the IBM PC. Integral global optimization algorithms have been successfully applied to many industrial and control problems such as automatic design of optical thin-film systems and prototype tenses, computer aided design of equalizers, optimal design of microwave filters, turbine wheels and speed reducers and nonlinear observation of dynamic systems.
reviewed by: Quan Zheng
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C06
zbMATH DE Number: 4060991
zbMATH Keywords: Karmarkar's projective algorithm
zbMATH Keywords: special structure
zbMATH Keywords: polynomial
zbMATH Keywords: mean value-level set method
MaRDI profile type: Publication
cites work: A monotonic projective algorithm for fractional linear programming
cites work: A variation on Karmarkar’s algorithm for solving linear programming problems
cites work: Q3318714
cites work: Generalized upper bounding techniques
cites work: The Decomposition Algorithm for Linear Programs
cites work: A polynomial Newton method for linear programming
cites work: A variant of Karmarkar's linear programming algorithm for problems in standard form
cites work: On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
cites work: The factorization approach to large-scale linear programming
cites work: A new polynomial-time algorithm for linear programming
cites work: Q5630824
cites work: Q3039035
cites work: A projective method for linear programming with box-type constraints
cites work: Q4132006
cites work: Implicit representation of generalized variable upper bounds in linear programming
cites work: An implementation of the simplex method for linear programming problems with variable upper bounds
cites work: Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
cites work: An extension of Karmarkar's algorithm for linear programming using dual variables
cites work: A modification of Karmarkar's linear programming algorithm
cites work: Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
full work available at URL: https://doi.org/10.1007/bf01580755
OpenAlex ID: W2015848061
description: scientific article; zbMATH DE number 4060991