# Accession Number:

## AD0757428

# Title:

## On the Set Covering Problem. II. An Algorithm.

# Descriptive Note:

## Research rept. May-Nov 72,

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

# Personal Author(s):

# Report Date:

## 1972-11-01

# Pagination or Media Count:

## 37.0

# Abstract:

In an earlier paper the authors proved that any feasible integer solution to the linear program associated with the equality-constrained set covering problem can be obtained from any other feasible integer solution by a sequence of less than m pivots where m is the number of equations, such that each solution generated in the sequence is integer. However, degeneracy makes it difficult to find a sequence of pivots leading to an integer optimum. In the paper the authors give a constructive characterization of adjacency relations between integer vertices of the feasible set, which enables them to generate edges all, if necessary connecting a given integer vertex to adjacent integer vertices. This helps overcome the difficulties caused by degeneracy and leads to a class of algorithms of which two are discussed. Author Modified Abstract

# Descriptors:

# Subject Categories:

- Operations Research