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