Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem
作者:
Mokhtar S. Bazaraa,
Hanif D. Sherali,
期刊:
Naval Research Logistics Quarterly
(WILEY Available online 1980)
卷期:
Volume 27,
issue 1
页码: 29-41
ISSN:0028-1441
年代: 1980
DOI:10.1002/nav.3800270104
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractIn 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 provi
点击下载:
PDF
(756KB)
返 回