.png){kind=icon}
返回
A level-2 reformulation-linearization technique bound for the quadratic assignment problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2006.03.051.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0-1 linear representations that result from a reformulation-linearization technique (rlt). The rlt provides different levels of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances. (c) 2006 Elsevier B.V. All rights reserved.
Keyword:
combinatorial optimization
assignment
branch and bound
quadratic assignment problem
reformulation-linearization technique
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method基于匈牙利方法的二次分配问题的分支定界算法
.png){kind=icon}
PREAI
分享收藏
查看更多内容