Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems
研究了在拉格朗日子问题中加入单个替代约束，以改进传统拉格朗日松弛产生的边界，并在随机生成的集合覆盖问题上报告了计算结果。
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.