Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem (Q1184337)

Solution techniques for optimization problems often require bounds of the objective function. In this paper lower bounds are given for the quadratic assignment problem using an eigenvalue decomposition of the quadratic part and solving a linear program for the linear part. Applying ideas of parametric programming the sum of the two bounds is increased by a steepest ascent algorithm. There are numerical results showing the power of the new method.