On the Set-Covering Problem

This 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, we show that, for every feasible integer basis to P′, there are at least as many adjacent feasible integer bases as there are nonbasic columns. Finally, given any two basic feasible integer solutions x¹ and x² to P′, x² can be obtained from x¹ by a sequence of p pivots (where p is the number of indices j ϵ N for which x_j¹ is nonbasic and x_j² = 1), such that each solution in the associated sequence is feasible and integer. Some of our results have been conjectured earlier by Andrew, Hoffmann, and Krabek in a paper presented to ORSA in 1968.