Dynamic Subgradient-Based Branch and Bound Procedure for Set Covering. Revision

摘要

We discuss a branch and bound algorithm for set covering, whose centerpiece is anintegrated upper bounding/lower bounding procedure called dynamic subgradient optimization (DYNSGRAD), that is applied to a Lagrangian dual problem at every node of the search tree. Extensive experimentation has shown DYNSGRAD to represent a significant improvement over currently used techniques.