
Accession Number : AD0757428
Title : On the Set Covering Problem. II. An Algorithm.
Descriptive Note : Research rept. MayNov 72,
Corporate Author : CARNEGIEMELLON 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 equalityconstrained 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