Exploiting special structure in Karmarkar's linear programming algorithm
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.
- A modification of Karmarkar's linear programming algorithm
- A monotonic projective algorithm for fractional linear programming
- A new polynomial-time algorithm for linear programming
- A polynomial Newton method for linear programming
- A projective method for linear programming with box-type constraints
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- A variation on Karmarkar’s algorithm for solving linear programming problems
- An extension of Karmarkar's algorithm for linear programming using dual variables
- An implementation of the simplex method for linear programming problems with variable upper bounds
- Generalized upper bounding techniques
- scientific article; zbMATH DE number 3833697 (Why is no real title available?)
- scientific article; zbMATH DE number 3849165 (Why is no real title available?)
- scientific article; zbMATH DE number 3561083 (Why is no real title available?)
- scientific article; zbMATH DE number 3356467 (Why is no real title available?)
- Implicit representation of generalized variable upper bounds in linear programming
- Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- The Decomposition Algorithm for Linear Programs
- The factorization approach to large-scale linear programming
- Interior-point methods with decomposition for solving large-scale linear programs
- Exploiting special structure in a primal-dual path-following algorithm
- El metodo de Karmarkar: Un estudio de sus variantes
- Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming
- A survey of dynamic network flows
This page was built for publication: Exploiting special structure in Karmarkar's linear programming algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106098)
