A branch-and-bound algorithm for the singly constrained assignment problem

A branch-and-bound algorithm for the singly constrained assignment problem

0.00 Avg rating0 Votes
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: ,
Keywords: programming: branch and bound
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.

Reviews

Required fields are marked *. Your email address will not be published.