A Merge Search Approach to Find Minimal Path Vectors in Multistate Networks

摘要

A new approach namely merge search (MS) is proposed to search for minimal path vectors (MPV) in multistate networks (MSN). Also, a new advance in solving integer programming problems namely fast enumeration (FE) is integrated in this approach. Such an integrated approach can greatly improve the time efficiency of searching for MPV in MSN. Traditionally, searching for MPV in MSN involves three steps: (a) enumerate all feasible flow vectors; (b) transform these vectors to corresponding state vectors; (c) filter out MPV from these state vectors. Steps (a) and (c) are bottlenecks. Explicit enumeration is usually engaged in solving Step (a), and pairwise comparison is usually employed in solving Step (c). The integrated approach uses FE to solve Step (a), and MS to solve Step (c) instead. Some numerical examples are explored to show the superior time efficiency of the proposed approach. The results show that the proposed new approach is valuable in solving the search of MPV in MSN.