| Article ID: | iaor19981441 |
| Country: | Netherlands |
| Volume: | 83 |
| Issue: | 2 |
| Start Page Number: | 365 |
| End Page Number: | 375 |
| Publication Date: | Jun 1995 |
| Journal: | European Journal of Operational Research |
| Authors: | Malucelli Federico, Pretolani Daniele |
| Keywords: | quadratic assignment, Lagrangean decomposition |
This paper presents a class of lower bounds for the Quadratic Semi-Assignment Problem (QSAP). These bounds are based on recent results on polynomially solvable cases; in particular we will consider the QSAPs whose quadratic cost coefficients define a reducible graph. The idea is to decompose the problem into several subproblems, each defined on a reducible subgraph. A Lagrangean decomposition technique is used to improve the results. Several lower bounds are computationally compared on several types of test problems.