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

DOI10.1007/BF01584344zbMath0384.90084MaRDI QIDQ4165158

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

Publication date: 1977

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

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C06: Large-scale problems in mathematical programming

90C10: Integer programming

90C05: Linear programming

68Q45: Formal languages and automata

90-04: Software, source code, etc. for problems pertaining to operations research and mathematical programming

Related Items

Solving staircase linear programs by the simplex method, 2: Pricing, Complexity of the gravitational method for linear programming, Solving Linear Programs in Polynomial-Time, Solving Linear Programs in Polynomial-Time, Vector processing in simplex and interior methods for linear programming, Implementations of special ordered sets in MP software, Efficient nested pricing in the simplex algorithm, On the use of the simplex algorithm for the absolute deviation curve fitting problem, A general phase-I method in linear programming, Convergence results and numerical experiments on a linear programming hybrid algorithm, A dual approach to primal degeneracy, On maintenance scheduling of production units, A comparative analysis of linear fitting for non-linear functions on optimization. A case study: Air pollution problems, A practical anti-cycling procedure for linearly constrained optimization, 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, Encounters with degeneracy: A personal view, MOPS -- Mathematical optimization system, Advances in design and implementation of optimization software, A phase-1 approach for the generalized simplex algorithm, Cycling in linear programming problems, A basis-defiency-allowing variation of the simplex method for linear programming, A pathological case in the reduction of linear programs, A projective simplex algorithm using LU decomposition, A primal deficient-basis simplex algorithm for linear programming, Systematic construction of examples for cycling in the simplex method, On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Formal optimization of some reduced linear programming problems, Karmarkar's projective method for linear programming: a computational survey, On scaling linear programs—some experimental results, Analisis de estrategias en el ajuste lineal de funciones no-lineales en problemas de optimizacion, An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming, Solving staircase linear programs by the simplex method, 1: Inversion, Updated triangular factors of the working basis in winkler's decomposition approach

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