A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering

Egon Balas and Maria C. Carrera
Additional contact information
Maria C. Carrera: Queues Enforth Development, Inc., Cambridge, Massachusetts

Operations Research, 1996, vol. 44, issue 6, 875-890

Abstract: We discuss a branch and bound algorithm for set covering, whose centerpiece 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.

Keywords: integer programming; set covering algorithms; subgradient optimization; dynamic version (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.6.875 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:6:p:875-890

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().