A Lagrangean Dual Ascent Procedure for the Constrained Assignment Problem.

We describe and test a Lagrangean dual ascent procedure for the assignment problem (CAP). 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. In practice, the dual solution computed by subgradient optimization is not optimal (although it is quite strong). Thus, we design a Lagrangean dual ascent procedure, 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.