On the Set Covering Problem.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1970
- Accession Number
- AD0714498
Entities
People
- Egon Balas
- Manfred W. Padberg
Organizations
- Carnegie Mellon University