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) : Balas,Egon ; Padberg,Manfred

Report Date : NOV 1972

Pagination or Media Count : 37

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 :   (*LINEAR PROGRAMMING, ALGORITHMS), CONVEX SETS, VECTOR SPACES, SIMPLEX METHOD, GRAPHICS, PERMUTATIONS, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE