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

Abstract

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

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1992
Accession Number
ADA257416

Entities

People

  • Egon Balas
  • Maria C. Carrera

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computer Programming
  • Computers
  • Coverings
  • Data Sets
  • Evolutionary Algorithms
  • Heuristic Methods
  • Inequalities
  • Integer Programming
  • Linear Programming
  • Mathematics
  • Military Research
  • Operations Research
  • Optimization
  • Simplex Method
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Operations Research