Reliability, Covering and Balanced Matrices

Abstract

The 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. In this paper, we show that the same model can be applied to a general system reliability optimization problem. The main contribution of this paper is the definition and analysis of a reformulation strategy. Specifically, we show how the original generalized covering problem can be reformulated as a set covering problem. We 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.