Reliability, covering and balanced matrices

This paper addresses a certain generalized covering integer program. The original application that motivated the study of this problem was an emergency services vehicle location problem. The underlying model can also be applied to certain reliability optimization problems. The main contribution of this paper is the definition and analysis of a reformulation strategy. Specifically, the authors show how the original generalized covering problem can be reformulated as a set covering problem. They then show that for a particular special case the associated constraint matrix is balanced. This in turn implies that the integer program can be efficiently solved using linear programming techniques. This result together with the good computational results reported in a previous paper constitute substantial evidence as to the overall effectiveness of the reformulation strategy. Furthermore, they indicate that the generalized covering model addressed can be effectively solved in a fairly wide range of cases.