Detecting ``dense columns in interior point methods for linear programs

DOI10.1007/S10589-006-9008-6MaRDI QIDQ2643620zbMATH OpenOpenAlexFDO

Authors Csaba Mészáros

Publication date 27 August 2007

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10589-006-9008-6

zbMATH Keywords

Cholesky factorizationdense columnsInterior point methodssparsity

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Recommendations

• A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
• A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming
• Symmetric indefinite systems for interior point methods
• Splitting dense columns of constraint matrix in interior point methods for large scale linear programming¹¹The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Pl
• Splitting dense columns in sparse linear systems

Cites work

• A new polynomial-time algorithm for linear programming
• A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming
• Advanced preprocessing techniques for linear and quadratic programming
• An Approximate Minimum Degree Ordering Algorithm
• Benchmarking interior point Lp/Qp solvers
• Fast Cholesky factorization for interior point methods of linear programming
• Gigaflops in linear programming
• scientific article; zbMATH DE number 724214 (Why is no real title available?)
• scientific article; zbMATH DE number 1047679 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Multiple centrality corrections in a primal-dual method for linear programming
• On free variables in interior point methods
• On the performance of the Cholesky factorization in interior point methods on Pentium 4 processors
• Solving symmetric indefinite systems in an interior-point method for linear programming
• Some properties of the Hessian of the logarithmic barrier function
• Stability of Augmented System Factorizations in Interior-Point Methods
• Symmetric indefinite systems for interior point methods
• Symmetric Quasidefinite Matrices
• The BPMPD interior point solver for convex quadratic problems
• The Cholesky factorization in interior point methods
• The Factorization of Sparse Symmetric Indefinite Matrices
• The role of the augmented system in interior point methods

Cited in

(13)

• Prior reduced fill-in in solving equations in interior point algorithms
• A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming
• A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block
• A boundary-point LP solution method and its application to dense linear programs
• On sparse matrix orderings in interior point methods
• Splitting dense columns of constraint matrix in interior point methods for large scale linear programming¹¹The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France$ef:²²A preliminary version of the paper has been presented at the Applied Mathematical Programming and Modelling Symposium APMOD’91 in London, January 14-…
• A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
• Interior point methods 25 years later
• Artificial-free simplex algorithm based on the non-acute constraint relaxation
• A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems
• Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement
• Interior point methods in the year 2025
• A massively parallel interior-point method for arrowhead linear programs with local linking structure

Describes a project that uses

Uses Software

• Benchmarks for Optimization Software
• BPMPD
• Decision tree for optimization software

This page was built for publication: Detecting ``dense columns in interior point methods for linear programs

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