Circular Layout Cutsets: An Approach for Improving Consecutive Cutset Bounds for Network Reliability

摘要

In this paper, we introduce a new type of parameterized class of cutsets for the 2-terminal network reliability problem, called the circular layout (CL) cutsets with parameter k, and devise a polynomial time algorithm for computing upper bounds from such structures. The CL cutsets, and the devised bounding method are characterized by the following aspects. 1) CL cutsets include the well known class of consecutive minimal cutsets, introduced by Shanthikumar, as a proper subset. Thus, bounds obtained by our main algorithm yield strict improvements on the basic consecutive cutsets algorithm. We note that extensive empirical studies done to date have shown that the consecutive cutsets method, when empowered by heuristics for choosing suitable cutsets, yields competitive bounds. 2) CL cutsets satisfy the semilattice structure required by Shier's algorithm for computing upper bounds in time polynomial in the number of cuts in a given cutset. Thus, CL cutsets define a new class of efficiently constructible cutsets of polynomial size that benefit from such generalized algorithm. 3) For any fixed value of the parameter k, the devised bounding method can be adapted to satisfy stringent constant-time update constraints, required by the most probable state algorithm of Colbourn & Harms , for obtaining iteratively improvable bounds, without adding significant time overhead to the method. Moreover, the devised bounding algorithm is easy to implement, and the obtained numerical results show more than a 32% improvement over bounds obtained by the basic consecutive cutsets algorithm