8th North America Conference on Industrial Engineering and Operations Management

A New Formulation of Quadratic Assignment Problem (QAP)

R.R.K. Sharma
Publisher: IEOM Society International
0 Paper Citations
Track: Operations Research

Different formulations of QAP (such as Linear Integer Formulation, MILP formulation, Formulation by Permutations, Trace Formulation and Graph Formulation) are given in Loiola et. al. (2007).  Different linearization of QAP are summarized in Singh and Sharma (2008). We give here a new QAP formulation and describe its advantages. For many different contributions to layout problems refer to Sharma (2019, 2019, 2020, 2020, 2021 and 2022). In this paper we
give a new formulation of QAP.

Problem QAP

Min sum over (i,j,k,l): x(i,j)*x(k,l)*D(j,l)*F(i,k)      (a)

Sum(i), x(i,j) = 1 for all j                                           (b)

Sum(j), x(i,j) = 1 for all i                                           (c)

x(i,j) = (0,1) for all i and j                                         (d)

x(i,j) = 1 if facility ‘i’ gets into ‘j’ th slot, D(j,l) is the distance between ‘j’ th and ‘l’ th slot and F(i,k) is flow between facility ‘i’ and ‘k’.

Here we give a new formulation of QAP. We put following constraints.

x(i,j) + M*(1 – y(i,j)) >= 1  for all i,j                        (e)

x(i,j) - M*(y(i,j)) <= 0         for all i,j                        (f)

y(i,j) = (0,1)                         for all i,j                        (g)

and add (h) in place of (d)

x(i,j) >= 0  for all i,j                                                  (h)

when x(i,j) is 1, then y(i,j) = 1; and when x(i,j) is 0, then y(0,j) is 0. Any x(i,j) in open interval (0,1) is infeasible (say x(i,j) = 0.5 is infeasible with either y(i,j) = 0 or 1). Thus though x(I,j) is real >= 0, it acts like binary due to (e), (f) and (g).

Then new formulation (NF_QAP) of QAP is

(a), s.t. (b), (c), (e), (f), (g) and (h).

It has N2 real, N2 binary and 2*( N2 +N) constraints; and has quadratic objective function in real variables. These are the merits of our new formulation of QAP. For a detailed comparison see Singh and Sharma (2008). Similar formulations are possible in DPLP (dynamic plant layout problem) also

Published in: 8th North America Conference on Industrial Engineering and Operations Management , Houston, United States of America

Publisher: IEOM Society International
Date of Conference: June 13-15, 2023

ISBN: 979-8-3507-0546-1
ISSN/E-ISSN: 2169-8767