Graph Modeling for Quadratic Assignment Problem Associated with the Hypercube

jiming peng(pengjuiuc.edu)
Hans Mittelmann(beckplato.la.asu.edu)
Xiaolin Wu(wuxece.mcmaster.ca)

Abstract: In the paper we consider the quadratic ssignment problem arising from channel coding in communications where one coefficient matrix is the adjacency matrix of a hypercube in a finite dimensional space. By using the geometric structure of the hypercube, we first show that there exist at least $n$ different optimal solutions to the underlying QAPs. Moreover, the inherent symmetries in the associated hypercube allow us to obtain partial information regarding the optimal solutions and thus shrink the search space and improve the existing QAP solvers for the underlying QAPs. Secondly, we use graph modeling techniques to derive new integer linear program (ILP) models for the underlying QAPs. These new ILP models have n(n-1) binary variables and up to O(n^3\log(n)) linear constraints. This yields the smallest known number of binary variables for the ILP reformulation of QAPs. Various relaxations of the new ILP model are obtained based on the graphical characterization of the hypercube, and the lower bounds provided by the LP relaxations of the new model are analyzed and compared with several classical LP relaxations of QAPs in the literature.

Keywords: Quadratic Assignment Problem

Category 1: Applications -- Science and Engineering

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Technical Report, Department of IESE, UIUC, Urbana, IL, 61801, USA. June, 2007.

Download: [PDF]

Entry Submitted: 06/04/2007
Entry Accepted: 06/04/2007
Entry Last Modified: 06/04/2007

Modify/Update this entry