کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
483077 | 1446195 | 2007 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A level-2 reformulation–linearization technique bound for the quadratic assignment problem A level-2 reformulation–linearization technique bound for the quadratic assignment problem](/preview/png/483077.png)
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.
Journal: European Journal of Operational Research - Volume 180, Issue 3, 1 August 2007, Pages 983–996