Article ID: | iaor19961440 |
Country: | Netherlands |
Volume: | 65 |
Issue: | 3 |
Start Page Number: | 407 |
End Page Number: | 416 |
Publication Date: | Mar 1993 |
Journal: | European Journal of Operational Research |
Authors: | White Douglas J. |
Keywords: | programming: assignment |
The standard quadratic assignment problem suffers from the non-convex form of the objective function. The paper shows 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.