A Lagrangean relaxation method for the constrained assignment problem (Q1086162)

This paper addresses the problem of finding a minimal weight assignment subject to a knapsack-type constraint. It develops a two-stage algorithm based on the Lagrangean relaxation formulation of this problem. The first stage obtains the optimal Lagrange multiplier in a polynominal effort by generating the efficient frontier in a bicriteria framework. The second stage uses this information very effectively to zero in on the optimal solution in a relatively lower depth of search in the ordered-generation- of-assignments framework. The algorithm is supported by a numerical example and its advantages over other schemes are shown.