An Improved Algorithm for the Generalized Quadratic Assignment Problem

Artur Pessoa(arturproducao.uff.br)
Peter Hahn(hahnseas.upenn.edu)
Monique Guignard(guignardwharton.upenn.edu)
Yi-Rong Zhu(yrzhuseas.upenn.edu)

Abstract: In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the GQAP. The new method allowed us to optimally solve 18 out of 19 instances from the literature with up to 35 facilities, 6 of which were open.

Keywords: Quadratic assignment, Lagrangean relaxation, Branch-and-bound

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 05/15/2008
Entry Accepted: 05/15/2008
Entry Last Modified: 05/15/2008

Modify/Update this entry