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

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.Both authors would like to thank the Natural Sciences and Engineering Research Council Canada and the Austrian Government for their support.This author would like to acknowledge partial support from the Department of Combinatorics and Optimization at the University of Waterloo.Research partially supported by Natural Sciences and Engineering Research Council Canada.