Network-based formulations of the quadratic assignment problem

We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 1998, Vol.104 (1), p.241-249
Main Authors: Ball, Michael O., Kaku, Bharat K., Vakhutinsky, Andrew
Format: Article
Language:English
Subjects:
Applied sciences
Assignment problem
Design
Exact sciences and technology
Facilities
Flows in networks. Combinatorial problems
Integer programming
Network programming
Operational research and scientific management
Operational research. Management science
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(96)00330-X