Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479345 | European Journal of Operational Research | 2007 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
P.M.D. Lieshout, A. Volgenant,