Exploiting special structure in a primal-dual path-following algorithm

DOI10.1007/BF01581258zbMath0793.90031OpenAlexW1975916211MaRDI QIDQ1803615

Donald Goldfarb, In-Chan Choi

Publication date: 29 June 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581258

zbMATH Keywords

upper boundsinterior point methodstructured linear programprimal-dual path- following algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Deterministic network models in operations research (90B10)

Related Items

Solving nonlinear multicommodity flow problems by the analytic center cutting plane method, Modified primal path-following scheme for the monotone variational inequality problem, A cutting plane method from analytic centers for stochastic programming, Interior point methods 25 years later, Design and implementation of a modular interior-point solver for linear optimization, Using an interior point method for the master problem in a decomposition approach, A primal-dual decomposition algorithm for multistage stochastic convex programming, Interior-point methods with decomposition for solving large-scale linear programs

Cites Work

• A new polynomial-time algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Exploiting special structure in Karmarkar's linear programming algorithm
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Speeding up Karmarkar's algorithm for multicommodity flows
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A POLYNOMIAL TIME INTERIOR POINT ALGORITHM FOR MINIMUM COST FLOW PROBLEMS
• POLYNOMIAL TIME INTERIOR POINT ALGORITHMS FOR TRANSPORTATION PROBLEMS
• Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming
• On the Implementation of a Primal-Dual Interior Point Method
• Further Development of a Primal-Dual Interior Point Method
• An Efficient Heuristic Procedure for Partitioning Graphs
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item