The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results

DOI10.1007/BF01584344zbMath0384.90084OpenAlexW2091195410MaRDI QIDQ4165158

J.-M. Gauthier, M. Benichou, Gerard Ribiere, G. Hentges

Publication date: 1977

Published in: Mathematical Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Linear programming (90C05) Formal languages and automata (68Q45) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Related Items (44)

A phase-1 approach for the generalized simplex algorithm ⋮ Updated triangular factors of the working basis in winkler's decomposition approach ⋮ Convergence results and numerical experiments on a linear programming hybrid algorithm ⋮ A linear programming decomposition focusing on the span of the nondegenerate columns ⋮ A dual approach to primal degeneracy ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ The positive edge pricing rule for the dual simplex ⋮ Karmarkar's projective method for linear programming: a computational survey ⋮ On maintenance scheduling of production units ⋮ Scaling linear optimization problems prior to application of the simplex method ⋮ A projective simplex algorithm using LU decomposition ⋮ Efficient nested pricing in the simplex algorithm ⋮ Formal optimization of some reduced linear programming problems ⋮ A primal deficient-basis simplex algorithm for linear programming ⋮ On scaling linear programs—some experimental results ⋮ On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method ⋮ Branch and bound, integer, and non-integer programming ⋮ Cycling in linear programming problems ⋮ Systematic construction of examples for cycling in the simplex method ⋮ Complexity of the gravitational method for linear programming ⋮ Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis ⋮ A comparative analysis of linear fitting for non-linear functions on optimization. A case study: Air pollution problems ⋮ A basis-defiency-allowing variation of the simplex method for linear programming ⋮ A practical anti-cycling procedure for linearly constrained optimization ⋮ Vector processing in simplex and interior methods for linear programming ⋮ Analisis de estrategias en el ajuste lineal de funciones no-lineales en problemas de optimizacion ⋮ A computational comparison of scaling techniques for linear optimization problems on a graphical processing unit ⋮ Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation ⋮ An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming ⋮ A pathological case in the reduction of linear programs ⋮ Solving staircase linear programs by the simplex method, 2: Pricing ⋮ Solving Linear Programs in Polynomial-Time ⋮ Solving Linear Programs in Polynomial-Time ⋮ Implementations of special ordered sets in MP software ⋮ On the use of the simplex algorithm for the absolute deviation curve fitting problem ⋮ On the use of dense matrix techniques within sparse simplex ⋮ A fast LU update for linear programming ⋮ Selected bibliography on degeneracy ⋮ Degeneracy graphs: Theory and applications. An updated survey ⋮ Advances in design and implementation of optimization software ⋮ Encounters with degeneracy: A personal view ⋮ Solving staircase linear programs by the simplex method, 1: Inversion ⋮ MOPS -- Mathematical optimization system ⋮ A general phase-I method in linear programming

Uses Software

• DEVEX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Condition numbers and equilibration of matrices
• Condition, equilibration and pivoting in linear algebraic systems
• The Elimination form of the Inverse and its Application to Linear Programming
• An Algorithm for Scaling Matrices
• Practical Solution of Large Mixed Integer Programming Problems with Umpire
• Experiments in mixed-integer linear programming using pseudo-costs
• On pricing and backward transformation in linear programming
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method
• A Technique for Resolving Degeneracy in Linear Programming
• The simplex method of linear programming using LU decomposition
• Some Results on Sparse Matrices
• Experiments in mixed-integer linear programming
• Integer Programming Algorithms: A Framework and State-of-the-Art Survey
• On the Automatic Scaling of Matrices for Gaussian Elimination
• Pivoting for Size and Sparsity in Linear Programming Inversion Routes

This page was built for publication: The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results