A branch-and-bound algorithm for the singly constrained assignment problem |
| |
Authors: | PMD Lieshout A Volgenant |
| |
Institution: | Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, The Netherlands |
| |
Abstract: | 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 n = 1000 within short running times on a standard personal computer. |
| |
Keywords: | Linear assignment Lagrangean relaxation Branch-and-bound Side constraint |
本文献已被 ScienceDirect 等数据库收录! |
|