A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases

DOI10.1007/BF01585094zbMath0492.90050OpenAlexW1988390398MaRDI QIDQ3955153

Publication date: 1982

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

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

zbMATH Keywords

decompositions sparse matrices simplex method implementation computational comparison test results Bartels and Golub algorithm Forrest and Fomlin algorithm updating lp basis factorizations

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)

Related Items

A pathsearch damped Newton method for computing general equilibria, On the integer properties of scheduling set partitioning models, A numerically stable reduced-gradient type algorithm for solving large- scale linearly constrained minimization problems, An experimental investigation of enumerative methods for the linear complementarity problem, The simplex method is not always well behaved, Cutting Plane Generation through Sparse Principal Component Analysis, Partitioning mathematical programs for parallel solution, Approximating polyhedra with sparse inequalities, Limit analysis in plasticity as a mathematical programming problem, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, Stable algorithm for updating denseLUfactorization after row or column exchange and row and column addition or deletion, An efficient algorithm for sparse null space basis problem using ABS methods, The Null Space Problem II. Algorithms, An efficient approach to updating simplex multipliers in the simplex algorithm, Permutations in the Factorization of Simplex Bases, A computational analysis of LCP methods for bilinear and concave quadratic programming, A sequential LCP method for bilevel linear programming, Improving a primal–dual simplex-type algorithm using interior point methods, The double pivot simplex method, A primal deficient-basis simplex algorithm for linear programming, Mixed integer programming: A historical perspective with Xpress-MP, A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses, A survey of direct methods for sparse linear systems, Unnamed Item, Matrix augmentation and partitioning in the updating of the basis inverse, A bump triangular dynamic factorization algorithm for the simplex method, New crash procedures for large systems of linear constraints, The projection method of optimization applied to engineering plasticity problems, A degeneracy exploiting LU factorization for the simplex method, Métodos tipo dual simplex para problemas de otimização linear canalizados e esparsos, A practicable steepest-edge simplex algorithm, Vector processing in simplex and interior methods for linear programming, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II, Maintaining LU factors of a general sparse matrix, Optimal solutions for the cutting stock problem, Upper bound limit analysis using discontinuous velocity fields, A sparse counterpart of Reichel and Gragg's package QRUP, Large-scale linear programming: Geometry, working bases and factorizations, Solving staircase linear programs by the simplex method, 2: Pricing, Solving embedded generalized network problems, A fast LU update for linear programming, Solving staircase linear programs by the simplex method, 1: Inversion, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, MOPS -- Mathematical optimization system, Novel update techniques for the revised simplex method, Sensitivity method for basis inverse representation in multistage stochastic linear programming problems, Sparse PSD approximation of the PSD cone

Uses Software

XMP

Cites Work