A new efficient primal dual simplex algorithm

DOI10.1016/S0305-0548(02)00077-1zbMath1031.90011MaRDI QIDQ1868820

Nikolaos Samaras, Konstantinos Paparrizos, George Stephanides

Publication date: 28 April 2003

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

algorithmsLinear programmingNumerical resultsExterior point algorithmTwo-path

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Related Items

A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs, Algebraic simplex initialization combined with the nonfeasible basis method, An improved initial basis for the simplex algorithm, Efficient GPU-based implementations of simplex type algorithms, Exterior point simplex-type algorithms for linear and network optimization problems, Improving a primal–dual simplex-type algorithm using interior point methods, Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods, The complex interior-boundary method for linear and nonlinear programming with linear constraints, An overview on the simplex algorithm, An experimental investigation of a primal–dual exterior point simplexalgorithm

Cites Work

• A primal-dual simplex method for linear programs
• A new polynomial-time algorithm for linear programming
• A feasible direction method for linear programming
• An infeasible (exterior point) simplex algorithm for assignment problems
• Pivot rules for linear programming: A survey on recent theoretical developments
• An exterior point simplex algorithm for (general) linear programming problems
• The simplex algorithm with a new primal and dual pivot rule
• Resolution of the problem of degeneracy in a primal and dual simplex algorithm
• An efficient simplex type algorithm for sparse and dense linear programs.
• Multiple centrality corrections in a primal-dual method for linear programming
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
• On Finding Primal- and Dual-Optimal Bases
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• Splitting dense columns of constraint matrix in interior point methods for large scale linear programming¹¹The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France$ef:²²A preliminary version of the paper has been presented at the Applied Mathematical Programming and Modelling Symposium APMOD’91 in London, January 14-…
• Combining Interior-Point and Pivoting Algorithms for Linear Programming