Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study.

Abstract

We report on the implementation and computational testing of several versions of a set covering algorithm, based on the family of cutting planes from conditional bounds. The algorithm uses a set of heuristics to find prime covers, another set of heuristics to find feasible solutions to the dual linear program which are needed to generate cuts, and subgradient optimization to find lower bounds. It also uses implicit enumeration with some new branching rules. Each of the ingredients was implemented and tested in several versions. The variant of the algorithm that emerged as best was run on 55 randomly generated test problems (20 of them from the literature), with up to 200 constraints and 2000 variables. The results show the algorithm to be more reliable and efficient than earlier procedures on large, sparse set covering problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1979
Accession Number
ADA072458

Entities

People

  • Andrew Ho
  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Coverings
  • Evolutionary Algorithms
  • Inequalities
  • Integer Programming
  • Iterations
  • Linear Programming
  • Literature
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Sequences
  • Simplex Method
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design