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

Mokhtar S. Bazaraa and Hanif D. Sherali

Naval Research Logistics Quarterly, 1980, vol. 27, issue 1, 29-41

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.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1002/nav.3800270104

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:27:y:1980:i:1:p:29-41

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().