A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm

DOI10.1287/OPRE.38.6.1006zbMATH Open0724.90037OpenAlexW2032368946MaRDI QIDQ5202502FDOQ5202502

Authors: Michael J. Todd 

Publication date: 1990

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.38.6.1006

Recommendations

• An extension of Karmarkar's algorithm for linear programming using dual variables
• scientific article; zbMATH DE number 4085412
• scientific article; zbMATH DE number 5004702
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• scientific article; zbMATH DE number 969963

zbMATH Keywords

Dantzig-Wolfe decompositionKarmarkar's projective algorithmprimal simplex pivot rule

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cited In (19)

• An affine scaling method using a class of differential barrier functions: primal approach
• An efficient search direction for linear programming problems
• New characterizations of Hoffman constants for systems of linear constraints
• A note on properties of condition numbers
• An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A norm bound for projections with complex weights
• A simple proof of a primal affine scaling method
• Pivot rules for linear programming: A survey on recent theoretical developments
• A study of the dual affine scaling continuous trajectories for linear programming
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Condition numbers for polyhedra with real number data
• A modified layered-step interior-point algorithm for linear programming
• On the condition numbers for polyhedra in Karmarkar's form
• Improved complexity results on solving real-number linear feasibility problems
• Title not available (Why is that?)
• Identifying an optimal basis in linear programming
• Norm estimations for perturbations of the weighted Moore-Penrose inverse

Uses Software

• DEVEX

This page was built for publication: A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5202502)