On Finding Primal- and Dual-Optimal Bases

DOI10.1287/IJOC.3.1.63zbMath0755.90056OpenAlexW2146325267MaRDI QIDQ4025897

Nimrod Megiddo

Publication date: 18 February 1993

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.3.1.63

zbMATH Keywords

strongly polynomial time algorithm

Mathematics Subject Classification ID

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

Related Items (32)

Descent approaches for quadratic bilevel programming ⋮ Theoretical complexity of grid cover problems used in radar applications ⋮ Recovering an optimal LP basis from an interior point solution ⋮ Experimental investigations in combining primal dual interior point method and simplex based LP solvers ⋮ Solving real-world linear ordering problems using a primal-dual interior point cutting plane method ⋮ On solving stochastic production planning problems via scenario modelling ⋮ A general parametric analysis approach and its implication to sensitivity analysis in interior point methods ⋮ Modified fictitious play for solving matrix games and linear-programming problems ⋮ A linear programming primer: from Fourier to Karmarkar ⋮ Measure transformation and efficient quadrature in reduced-dimensional stochastic modeling of coupled problems ⋮ Could we use a million cores to solve an integer program? ⋮ Vanishing Price of Decentralization in Large Coordinative Nonconvex Optimization ⋮ Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems ⋮ Balanced matrices ⋮ Converging upon basic feasible solutions through Dantzig-Wolfe decomposition ⋮ Implementation of an interior point method with basis preconditioning ⋮ On the uniqueness of optimal strategies in symmetric matrix games ⋮ Improving a primal–dual simplex-type algorithm using interior point methods ⋮ On the finite convergence of interior-point algorithms for linear programming ⋮ Polynomial Interior Point Cutting Plane Methods ⋮ Recovering an optimal LP basis from an optimal dual solution ⋮ Experiments with a hybrid interior point/combinatorial approach for network flow problems ⋮ Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra ⋮ LPAKO: A Simplex-based Linear Programming Program ⋮ Message-recovery laser fault injection attack on the \textit{classic McEliece} cryptosystem ⋮ Using fast matrix multiplication to find basic solutions ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ Pivot rules for linear programming: A survey on recent theoretical developments ⋮ Finding an interior point in the optimal face of linear programs ⋮ A new efficient primal dual simplex algorithm

This page was built for publication: On Finding Primal- and Dual-Optimal Bases