Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems
Collether John, Gary A. Kochenberger · Journal of the Operational Research Society · 1988
Lagrangian relaxations have been used in a variety of IP problem settings. The main thrust of such efforts is to obtain bounding information for use in a branch-and-bound procedure. This paper examines the effect of adding a single surrogate constraint to Lagrangian subproblems in an attempt to improve upon the bounds produced by conventional Lagrangian relaxation. Computational results on some randomly generated set-covering problems are reported.