Article ID: | iaor20084698 |
Country: | Netherlands |
Volume: | 176 |
Issue: | 1 |
Start Page Number: | 151 |
End Page Number: | 164 |
Publication Date: | Jan 2007 |
Journal: | European Journal of Operational Research |
Authors: | Volgenant A., Lieshout P.M.D. |
Keywords: | programming: branch and bound |
The singly constrained assignment problem (SCAP) is a linear assignment problem (LAP) with one extra side constraint, e.g., due to a time restriction. The SCAP is, in contrast to the LAP, difficult to solve. A branch-and-bound algorithm is presented to solve the SCAP to optimality. Lower bounds are obtained by Lagrangean relaxation. Computational results show that the algorithm is able to solve different types of SCAP instances up to size