|
|||||
|
|
Lower bounds for the quadratic assignment problem |
|
| Authors: | Y. Li P. M. Pardalos K. G. Ramakrishnan M. G. C. Resende |
| Affiliation: | (1) Computer Science Department, The Pennsylvania State University, 16802 University Park, PA, USA;(2) Department of Industrial and Systems Engineering, University of Florida, 32611 Gainesville, FL, USA;(3) Mathematical Sciences Research Center, AT&T Bell Laboratories, 07974 Murray Hill, NJ, USA |
| Abstract: | We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem. |
| Keywords: | Quadratic assignment problem branch-and-bound lower bound combinatorial optimization |
| 本文献已被 SpringerLink 等数据库收录！ | |