A dynamic subgradient-based branch-and-bound procedure for set covering
成果类型：
Article
署名作者：
Balas, E; Carrera, MC
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.44.6.875
发表日期：
1996
页码：
875-890
关键词：
摘要：
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.