A dynamic subgradient-based branch-and-bound procedure for set covering

A dynamic subgradient-based branch-and-bound procedure for set covering

0.00 Avg rating0 Votes
Article ID: iaor20003806
Country: United States
Volume: 44
Issue: 6
Start Page Number: 875
End Page Number: 890
Publication Date: Nov 1996
Journal: Operations Research
Authors: ,
Keywords: sets
Abstract:

We discuss a branch and bound algorithm for set covering, whose centrepiece is a new integrated upper bounding/lower bounding procedure called dynamic subgradient optimization (DYNSGRAD). This new procedure, applied to a Lagrangean dual at every node of the search tree, combines the standard subgradient method with primal and dual heuristics that interact to change the Lagrange multipliers and tighten the upper and lower bounds, fix variables, and periodically restate the Lagrangean itself. Extensive computational testing is reported. As a stand-alone heuristic, DYNSGRAD performs significantly better than other procedures in terms of the quality of solutions obtainable with a certain computational effort. When incorporated into a branch-and-bound algorithm, DYNSGRAD considerably advances the state of the art in solving set covering problems.

Reviews

Required fields are marked *. Your email address will not be published.