A DYNAMIC SUBGRADIENT-BASED BRANCH-AND-BOUND PROCEDURE FOR SET COVERING

We discuss a branch and bound algorithm for set covering, whose center piece is a new integrated upper bounding/lower bounding procedure call ed dynamic subgradient optimization (DYNSGRAD). This new procedure, ap plied to a Lagrangean dual at every node of the search tree, combines the standard subgradient method with primal and dual heuristics that i nteract to change the Lagrange multipliers and tighten the upper and l ower bounds, fix variables, and periodically restate the Lagrangean it self. Extensive computational testing is reported. As a stand-alone he uristic, DYNSGRAD performs significantly better than other procedures in terms of the quality of solutions obtainable with a certain computa tional effort. When incorporated into a branch-and-bound algorithm, DY NSGRAD considerably advances the state of the art in solving set cover ing problems.