The `Idiot' crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

DOI10.1080/10556788.2019.1604702MaRDI QIDQ5113712zbMATH OpenOpenAlexWikidataFDO

Authors I. L. Galabova, J. A. J. Hall

Publication date 16 June 2020

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.09172, https://www.pure.ed.ac.uk/ws/files/82448634/ERGO_18_009.pdf

zbMATH Keywords

linear programmingquadratic assignment problemsquadratic penalty methods

Mathematics Subject Classification ID

Linear programming (90C05) Discrete location and assignment (90B80)

Abstract: This paper provides the first meaningful documentation and analysis of an established technique which aims to obtain an approximate solution to linear programming problems prior to applying the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is used. Later the technique corresponds closely to a classical quadratic penalty method. There is also a discussion of the extent to which it can be used to obtain fast approximate solutions of LP problems, in particular when applied to linearizations of quadratic assignment problems.

Recommendations

• scientific article; zbMATH DE number 977754
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• A projective simplex method for linear programming
• Reoptimization With the Primal-Dual Interior Point Method
• scientific article; zbMATH DE number 4199965

Cites work

• scientific article; zbMATH DE number 107545 (Why is no real title available?)
• scientific article; zbMATH DE number 714527 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 3309655 (Why is no real title available?)
• A survey for the quadratic assignment problem
• Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming
• Augmented Lagrangian algorithms for linear programming
• Augmented Lagrangian method for large-scale linear programming problems
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Multiplier and gradient methods
• Parallelizing the dual revised simplex method

Cited in

(1)

• Faster first-order primal-dual methods for linear programming using restarts and sharpness

Describes a project that uses

Uses Software

• LANCELOT
• Benchmarks for Optimization Software
• CLP
• HiGHS

This page was built for publication: The `Idiot' crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

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