Accession Number : AD0714498

Title :   On the Set Covering Problem.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Balas,Egon ; Padberg,Manfred W.

Report Date : FEB 1970

Pagination or Media Count : 19

Abstract : The paper establishes some useful properties of the equality-constrained set covering problem P and the associated linear program P'. First, the Dantzig property of transportation matrices is shown to hold for a more general class of matrices arising in connection with adjacent integer solutions to P'. Next, it is shown that for every feasible integer basis for P' there are at least as many adjacent feasible integer bases as there are nonbasic columns. Finally, given two feasible integer bases B1 and B2, it is shown that B2 can be obtained from B1 by a sequence of at most p pivots (where p is the number of columns of B2 that are not columns of B), such that each solution in the associated sequence is feasible, integer, and not worse (in terms of the objective function value) than its predecessor. (Author)

Descriptors :   (*LINEAR PROGRAMMING, PROBLEM SOLVING), (*SCHEDULING, MATHEMATICAL MODELS), MATRICES(MATHEMATICS), THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE