Steepest-edge simplex algorithms for linear programming

DOI10.1007/BF01581089zbMath0787.90047OpenAlexW2004747092MaRDI QIDQ1802952

Donald Goldfarb, John J. Forrest

Publication date: 29 June 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581089

zbMATH Keywords

dual simplex methodDevex variantssteepest-edge simplex algorithms

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vector processing in simplex and interior methods for linear programming
• An analysis of an available set of linear programming test problems
• A practicable steepest-edge simplex algorithm
• Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases
• Implementing the Simplex Method: The Initial Basis
• Implementing the simplex method for the Optimization Subroutine Library
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method
• The Composite Simplex Algorithm
• Pivot selection methods of the Devex LP code

Related Items (52)

A phase-1 approach for the generalized simplex algorithm ⋮ Numerical aspects in developing LP softwares, LPAKO and LPABO ⋮ A computationally stable solution algorithm for linear programs ⋮ Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision ⋮ Parallelizing the dual revised simplex method ⋮ Progress in the dual simplex method for large scale LP problems: Practical dual phase 1 algorithms ⋮ The positive edge pricing rule for the dual simplex ⋮ A dual strategy for solving the linear programming relaxation of a driver scheduling system ⋮ Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ Applying steepest-edge techniques to a network primal-dual algorithm ⋮ The positive edge criterion within COIN-OR's CLP ⋮ Parallel distributed-memory simplex for large-scale stochastic LP problems ⋮ Implementing the simplex method as a cutting-plane method, with a view to regularization ⋮ A dual projective simplex method for linear programming ⋮ Customizing the solution process of COIN-OR's linear solvers with python ⋮ Exact optimization for the \(\ell ^{1}\)-compressive sensing problem using a modified Dantzig-Wolfe method ⋮ Interior point methods 25 years later ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Permutations in the Factorization of Simplex Bases ⋮ A projective simplex algorithm using LU decomposition ⋮ A largest-distance pivot rule for the simplex algorithm ⋮ Efficient nested pricing in the simplex algorithm ⋮ Improving a primal–dual simplex-type algorithm using interior point methods ⋮ The implicit LX method of the ABS class ⋮ A computational approach to pivot selection in the LP relaxation of set problems ⋮ A primal deficient-basis simplex algorithm for linear programming ⋮ Towards a practical parallelisation of the simplex method ⋮ Computational study of the GDPO dual phase-1 algorithm ⋮ Hyper-sparsity in the revised simplex method and how to exploit it ⋮ Primal-dual methods for sustainable harvest scheduling problems ⋮ On the sparseness of 1-norm support vector machines ⋮ A new least square algorithm for linear programming ⋮ Optimal pivot path of the simplex method for linear programming based on reinforcement learning ⋮ Steepest-edge rule and its number of simplex iterations for a nondegenerate LP ⋮ A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method ⋮ A basis-defiency-allowing variation of the simplex method for linear programming ⋮ LPAKO: A Simplex-based Linear Programming Program ⋮ An efficient simplex type algorithm for sparse and dense linear programs. ⋮ Vector Space Decomposition for Solving Large-Scale Linear Programs ⋮ Linear programing formulations and algorithms for radiotherapy treatment planning ⋮ Fast quantum subroutines for the simplex method ⋮ A triangulation and fill-reducing initialization procedure for the simplex algorithm ⋮ A new steepest edge approximation for the simplex method for linear programming ⋮ Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation ⋮ The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study ⋮ Computing in combinatorial optimization ⋮ The minimum mean cycle-canceling algorithm for linear programs ⋮ An affine-scaling pivot algorithm for linear programming ⋮ Reinforcement learning of simplex pivot rules: a proof of concept ⋮ ABS algorithms for linear equations and optimization ⋮ Advances in design and implementation of optimization software ⋮ Pivot rules for linear programming: A survey on recent theoretical developments

Uses Software

• DEVEX
• OSL

This page was built for publication: Steepest-edge simplex algorithms for linear programming