New crash procedures for large systems of linear constraints

DOI10.1007/BF01589115MaRDI QIDQ584077zbMATH OpenOpenAlexFDO

Authors Nicholas I. M. Gould, J. K. Reid

Publication date 1989

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

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

zbMATH Keywords

initial basislinearly constrained optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)

Review text

Many algorithms for solving linearly constrained optimization problems maintain sets of basic variables. The calculation of the initial basis is of great importance as it determines to a large extent the amount of computation that will then be required to solve the problem. This paper presents a number of simple methods for obtaining an initial basis and tests to indicate how they perform on a variety of real-life problems.

Recommendations

• Strategies for Creating Advanced Bases for Large-Scale Linear Programming Problems
• scientific article; zbMATH DE number 3852786
• A practical anti-cycling procedure for linearly constrained optimization
• Linearly constrained optimization
• Dealing with degeneracy in reduced gradient algorithms

Cites work

• A practicable steepest-edge simplex algorithm
• A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
• A Structurally Stable Modification of Hellerman–Rarick’s ${\text{P}}^4 $ Algorithm for Reordering Unsymmetric Sparse Matrices
• An algorithm for profile and wavefront reduction of sparse matrices
• An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
• Evolution of linear programming computing techniques
• scientific article; zbMATH DE number 3833697 (Why is no real title available?)
• scientific article; zbMATH DE number 3976197 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms
• On the Automatic Scaling of Matrices for Gaussian Elimination

Cited in

(9)

• Advances in design and implementation of optimization software
• A two-phase support method for solving linear programs: numerical experiments
• A triangulation and fill-reducing initialization procedure for the simplex algorithm
• Crash start of interior point methods
• scientific article; zbMATH DE number 4095202 (Why is no real title available?)
• Strategies for Creating Advanced Bases for Large-Scale Linear Programming Problems
• A comprehensive simplex-like algorithm for network optimization and perturbation analysis
• MILP acceleration: a survey from perspectives of simplex initialization and learning-based branch and bound
• A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses

Describes a project that uses

Uses Software

• MINOS
• HSL

This page was built for publication: New crash procedures for large systems of linear constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q584077)