Solving Set Covering Problems Using Heuristics with Branch and Bound.

Abstract

An algorithm based on simple heuristics is presented for an important class of all-binary integer linear programs known as the set covering problem. In spite of its very special form, the set covering problem has many practical applications. Optimal solutions to problems derived from these applications are difficult to obtain using known methods. Various solution techniques are investigated based on heuristic algorithms that obtain upper and lower bounds on the optimal solution value together with branch and bound enumeration. These solution techniques are effective on some problems. Computational results are reported for several large-scale real-world problems and several artificial problems. Originator-supplied keywords include: Heuristic, Branch and Bound, Algorithm, Set covering, Enumeration, Cutting Plane, Partitioning, and Separation. (Thesis).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1984
Accession Number
ADA151905

Entities

People

  • K. J. Nam

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Programming
  • Computer Programs
  • Computers
  • Data Storage Systems
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Security

Fields of Study

  • Computer science

Readers

  • Operations Research