Track: Operations Research

Abstract

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 N² real, N² binary and 2*( N² +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