An efficient simplex type algorithm for sparse and dense linear programs.

DOI10.1016/S0377-2217(02)00400-9zbMath1035.90041OpenAlexW2094456378MaRDI QIDQ1810522

Konstantinos Paparrizos, George Stephanides, Nikolaos Samaras

Publication date: 9 June 2003

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00400-9

zbMATH Keywords

AlgorithmevaluationLinear programmingNumerical experimentsBig-\(M\) methodSimplex type algorithms

Mathematics Subject Classification ID

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

Related Items (11)

A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs ⋮ Three nearly scaling-invariant versions of an exterior point algorithm for linear programming ⋮ An improved initial basis for the simplex algorithm ⋮ Efficient GPU-based implementations of simplex type algorithms ⋮ A two-phase support method for solving linear programs: numerical experiments ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ Improving a primal–dual simplex-type algorithm using interior point methods ⋮ Deepest point of a polyhedron and linear programming ⋮ A hybrid direction algorithm for solving linear programs ⋮ An experimental investigation of a primal–dual exterior point simplexalgorithm ⋮ A new efficient primal dual simplex algorithm

Uses Software

• Matlab
• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An infeasible (exterior point) simplex algorithm for assignment problems
• An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
• Worst case behavior of the steepest edge simplex method
• The generalized simplex method
• 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
• Steepest-edge simplex algorithms for linear programming
• Algorithms and Data Structures for Sparse Symmetric Gaussian Elimination
• Sparse Matrices in MATLAB: Design and Implementation
• Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases
• Commentary—Progress in Linear Programming
• A Monotonic Build-Up Simplex Algorithm for Linear Programming
• Distributed Schur Complement Techniques for General Sparse Linear Systems
• Sparse Matrix Methods in Optimization

This page was built for publication: An efficient simplex type algorithm for sparse and dense linear programs.