A new linearization method for quadratic assignment problems

A new linearization method for quadratic assignment problems

0.00 Avg rating0 Votes
Article ID: iaor2007413
Country: United Kingdom
Volume: 21
Issue: 5
Start Page Number: 805
End Page Number: 818
Publication Date: Oct 2006
Journal: Optimization Methods & Software
Authors: ,
Keywords: quadratic assignment, cutting plane algorithms
Abstract:

The quadratic assignment problem (QAP) is one of the great challenges in combinatorial optimization. Linearization for QAP is to transform the quadratic objective function into a linear one. Numerous QAP linearizations have been proposed, most of which yield mixed integer linear programs. Kauffmann and Broeckx's linearization (KBL) is the current smallest one in terms of the number of variables and constraints. In this article, we give a new linearization, which has the same size as KBL. Our linearization is more efficient in terms of the tightness of the continuous relaxation. Furthermore, the continuous relaxation of our linearization leads to an improvement to the Gilmore–Lawler bound. We also give a corresponding cutting plane heuristic method for QAP and demonstrate its superiority by numerical results.

Reviews

Required fields are marked *. Your email address will not be published.