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

DOI10.1287/OPRE.38.6.1006zbMath0724.90037OpenAlexW2032368946MaRDI QIDQ5202502

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)

Related Items (18)

A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ A note on properties of condition numbers ⋮ A simple proof of a primal affine scaling method ⋮ Identifying an optimal basis in linear programming ⋮ An affine scaling method using a class of differential barrier functions: primal approach ⋮ Condition numbers for polyhedra with real number data ⋮ An easily computable upper bound on the Hoffman constant for homogeneous inequality systems ⋮ NORM ESTIMATIONS FOR PERTURBATIONS OF THE WEIGHTED MOORE-PENROSE INVERSE ⋮ 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 study of the dual affine scaling continuous trajectories for linear programming ⋮ A norm bound for projections with complex weights ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ An efficient search direction for linear programming problems ⋮ A modified layered-step interior-point algorithm for linear programming ⋮ On the condition numbers for polyhedra in Karmarkar's form ⋮ Pivot rules for linear programming: A survey on recent theoretical developments ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Uses Software

• DEVEX

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