Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem

✍ Scribed by Mokhtar S. Bazaraa; Hanif D. Sherali

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 757 KB
• Volume: 27
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/nav.3800270104

✦ Synopsis

Abstract

In this paper we present a new formulation of the quadratic assignment problem. This is done by transforming the quadratic objective function into a linear objective function by introducing a number of new variables and constraints. The resulting problem is a 0‐1 linear integer program with a highly specialized structure. This permits the use of the partitioning scheme of Benders where only the original variables need be considered. The algorithm described thus iterates between two problems. The master problem is a pure 0‐1 integer program, and the subproblem is a transportation problem whose optimal solution is shown to be readily available from the master problem in closed form. Computational experience on problems available in the literature is provided.