A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
Computational Optimization in Action, Edinburgh, 8 June 2018
Julian Hall and Ivet Galabova
Abstract
This talk will present and analyse an established but previously undocumented 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 will also be 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.
Slides:
COA18.pdf |
Paper:
A quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
I. L. Galabova and J. A. J. Hall
Technical Report ERGO-18-009
Submitted to Optimization Methods and Software