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

DOI10.1080/10556788.2019.1604702zbMATH Open1440.90022arXiv1804.09172OpenAlexW2925779151WikidataQ127953640 ScholiaQ127953640MaRDI QIDQ5113712FDOQ5113712

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

Publication date: 16 June 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1804.09172

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 Keywords

linear programmingquadratic assignment problemsquadratic penalty methods

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplier and gradient methods
• Title not available (Why is that?)
• Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming
• A survey for the quadratic assignment problem
• Title not available (Why is that?)
• Augmented Lagrangian method for large-scale linear programming problems
• Parallelizing the dual revised simplex method
• Augmented Lagrangian algorithms for linear programming
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming

Cited In (1)

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

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)