A CONSTRUCTIVE METHOD FOR IMPROVING LOWER BOUNDS FOR A CLASS OF QUADRATIC ASSIGNMENT PROBLEMS
成果类型：
Article
署名作者：
CHAKRAPANI, J; SKORINKAPOV, J
署名单位：
State University of New York (SUNY) System; Stony Brook University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.5.837
发表日期：
1994
页码：
837-845
关键词：
摘要：
A new approach to evaluate lower bounds for a class of quadratic assignment problems (QAP) is presented. An instance of a QAP of size n is specified by two n x n matrices D and F, and is denoted by QAP(D, F). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices F(opt) and F(res) are constructed such that F = F(opt) + F(res), and the optimal solution to QAP(D, F(opt)) is known. Any existing lower bound can then be applied to QAP(D, F(res)), which in sum with the optimal value for QAP(D, F(opt)), provides a lower bound to QAP(D, F). Thus, this method could serve as a reduction process to possibly improve the results from a variety of bounding techniques. This approach is tested on two bounds from the literature, the Gilmore-Lawler bound (GLB) and an eigenvalue bound (PB), for various problems of size ranging from 6-49. Computational results show a good improvement in bounds for all the test problems. An extension of our method to a more general class of QAPs is also presented.