A CONVEX FORM OF THE QUADRATIC ASSIGNMENT PROBLEM

The standard quadratic assignment problem suffers from the non-convex form of the objective function. In this paper we show how the objective function may be made convex, and how the convexity properties might be useful in solving the original problem. Convexity leads to a sufficient condition for any current solution to be optimal, a property not available for the non-convex form. If a current solution is not optimal, the convexity leads to easily computable bounds on the loss of optimality.