The Sequential Covering Problem Under Uncertainty

Abstract

The formulation of the set covering problem in the literature is under the assumption that its binary variables are deterministic. In this paper we consider a randomized set covering problem where there is a positive probability that a decision to include a variable in the cover (xi = 1) will in fact be realized, because of failure, as ineffective (xi = 0). Furthermore, in the present formulation of the covering problems, the values of all variables are determined simultaneously. We allow a sequential selection of variables and present an efficient heuristic procedure which minimizes the expected costs necessary for the construction of a cover. An example for such problem is the detection of the state of a system by a sequential testing of its interrelated elements. Each element may have different testing costs and its functioning probability is independent of others. More applications of this model are described in the paper, and computational experience is reported.