An improved bounding procedure for the constrained assignment problem

An improved lower bound procedure for the constrained assignment problem (CAP) is described and tested. The formal model (CAP) consists of a 0-1 assignment problem with a single side constraint. Earlier work proposed a branch-and-bound algorithm that solves a Lagrangean relaxation of (CAP) at each node. The side constraint is dualized, and the Lagrangean dual is solved with subgradient optimization. A Lagrangean dual ascent procedure is designed, based on a Lagrangean decomposition structure, that tightens the bound computed by the subgradient method. This procedure is invoked if a node remains unfathomed at the termination of the subgradient procedure. Computational experience reveals a reduction in the size and computational effort of the tree search.