A new efficient primal dual simplex algorithm

DOI10.1016/S0305-0548(02)00077-1MaRDI QIDQ1868820zbMATH OpenFDO

Authors Konstantinos Paparrizos, Nikolaos Samaras, George Stephanides

Publication date 28 April 2003

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

zbMATH Keywords

algorithmsNumerical resultsLinear programmingExterior point algorithmTwo-path

Mathematics Subject Classification ID

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

Recommendations

• Classical simplex methods for linear programming and their developments
• A primal-dual simplex method for linear programs
• The simplex algorithm with a new primal and dual pivot rule
• A parallel primal-dual simplex algorithm
• A Revised Dual Projective Pivot Algorithm for Linear Programming

Cites work

• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• A feasible direction method for linear programming
• A new polynomial-time algorithm for linear programming
• A primal-dual simplex method for linear programs
• An efficient simplex type algorithm for sparse and dense linear programs.
• An exterior point simplex algorithm for (general) linear programming problems
• An infeasible (exterior point) simplex algorithm for assignment problems
• Combining Interior-Point and Pivoting Algorithms for Linear Programming
• Multiple centrality corrections in a primal-dual method for linear programming
• On Finding Primal- and Dual-Optimal Bases
• On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• Resolution of the problem of degeneracy in a primal and dual simplex algorithm
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• 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, Pl
• The Average number of pivot steps required by the Simplex-Method is polynomial
• The simplex algorithm with a new primal and dual pivot rule

Cited in

(13)

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

This page was built for publication: A new efficient primal dual simplex algorithm

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