The 'Idiot' crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems. (3rd May 2020)

• Record Type: Journal Article
• Authors: Galabova, I. L.; Hall, J. A. J.
• Is Part Of: Optimization methods and software. Volume 35:Number 3(2020)
• Page Start: 488
• Page End: 501
• Publication Date: 2020-05-03
• Subjects: Linear programming -- quadratic penalty methods -- quadratic assignment problems; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1604702
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: We provide the first meaningful documentation and analysis of the 'Idiot' crash implemented by Forrest in Clp that aims to obtain an approximate solution to linear programming (LP) problems for warm-starting 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. We discuss 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.