Computational Advances in the Solution of Large-Scale Set Covering and Set Partitioning Problems.

Abstract

The Set Covering Problem (SCP) and the Set Partitioning Problem (SPP) represent an important class of all-binary (0-1) Integer Linear Programs (ILP). A review of the literature reveals extensive application of the APP/SCP model to a wide set of practical problems. The basic model is explained, and then many of the actual applications of this powerful model discovered in the literature review are discussed. The problems derived from these applications are difficult to solve with any method, and are particularly difficult to solve with optimal or exact algorithms. Various solution techniques were investigated within the framework of the classical simplex method with branch and bound enumeration. Several reformulations of the SPP/SCP as Integer Generalized Networks are examined. Extensive computational results are reported for several real world large-scale problems, and a convenient, compact format for data input is proposed as a standard for this problem class. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1982
Accession Number
ADA123774

Entities

People

  • Dan O. Bausch

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Ground and Sea Platforms
  • Materials and Manufacturing Processes
  • Weapons Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Computations
  • Computer Programming
  • Computers
  • Data Storage Systems
  • Heuristic Methods
  • Information Retrieval
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Scheduling (Production)
  • Simplex Method
  • Standards
  • Tanker Aircraft

Readers

  • Operations Research
  • Systems Analysis and Design