The Use of Specially Structured Models for Obtaining Bounds in the Quadratic Assignment Problem

Abstract

In this paper we study a procedure for finding bounds for the quadratic assignment problem. This procedure may be used as a sub-routine in hybrid procedures for solving this problem. The approach is based upon a data decomposition method, linking the actual data to the data of a special class of assignment problems for which bounds are computationally tractable.

Keywords:

• quadratic assignment problem
• programming
• layout