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

DOI10.1287/OPRE.38.6.1006MaRDI QIDQ5202502zbMATHOpenAlexFDO

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

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)

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

Cited in

(19)

• A simple proof of a primal affine scaling method
• Improved complexity results on solving real-number linear feasibility problems
• An affine scaling method using a class of differential barrier functions: primal approach
• scientific article; zbMATH DE number 5004702 (Why is no real title available?)
• A modified layered-step interior-point algorithm for linear programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• New characterizations of Hoffman constants for systems of linear constraints
• An easily computable upper bound on the Hoffman constant for homogeneous inequality systems
• A primal-dual interior point method whose running time depends only on the constraint matrix
• On the condition numbers for polyhedra in Karmarkar's form
• A norm bound for projections with complex weights
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• A note on properties of condition numbers
• Condition numbers for polyhedra with real number data
• 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
• Identifying an optimal basis in linear programming
• A study of the dual affine scaling continuous trajectories for linear programming
• Norm estimations for perturbations of the weighted Moore-Penrose inverse
• An efficient search direction for linear programming problems

Describes a project that uses

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)