A truncated exponential algorithm for the lightly constrained assignment problem

This paper presents a truncated branch-and-bound algorithm to obtain a near optimal solution for the constrained assignment problem in which there are only a few side constraints. At each node of the branch-and-bound tree a lower bound is obtained by solving a singly constrained assignment problem. If needed, Lagrangean relaxation theory is applied in an attempt to improve this lower bound. A specialized branching rule is developed which exploits the requirement that every man be assigned to some job. A software implementation of the algorithm has been tested on problems with five side constraints and up to 75,000 binary variables. Solutions guaranteed to be within 10% of an optimum were obtained for these 75,000 variable problems in from two to twenty minutes of CPU time on a Dec Alpha workstation. The behavior of the algorithm for various problem characteristics is also studied. This includes the tightness of the side constraints, the stopping criteria, and the effect when the problems are unbalanced, having more jobs than men.