Bounds for the Quadratic Assignment Problem Using the Bundle Method

Franz Rendl (franz.rendluni-klu.ac.at)
Renata Sotirov (rsotirovuni-klu.ac.at)

Abstract: Semidefinite Programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the Quadratic Assignment Problem suggests SDP as a way to derive tractable relaxation. We recall some SDP relaxations of QAP and solve them approximately using the Bundle Method. The computational results demonstrate the efficiency of the approach. Our bounds are the currently strongest ones available for QAP. We investigate their potential for Branch and Bound settings by looking also at the bounds in the first levels of the branching tree.

Keywords: quadratic assignment problem, semidefinite programming relaxation, bundle method, interior point method

Category 1: Combinatorial Optimization

Citation: unpublished: report, University of Klagenfurt, Universitaetsstrasse 65-67, Austria 2003

Download: [Postscript][PDF]

Entry Submitted: 08/27/2003
Entry Accepted: 08/27/2003
Entry Last Modified: 08/27/2003

Modify/Update this entry