Abstract: Multi-state networks are composed of multi-state components that have different performance levels,and multi-state network model has been extensively used to describe the complex behaviors of many technological networks.Multi-state network reliability under cost constraint,denoted by Rel_(d,b),is defined as the probability that the network is able to transmit d units of flow from the source to the destination while satisfying the condition that the total transportation cost is within a given budget b,and can be computed in terms of minimal capacity vector with budget constraint(called(d,b)-MCV for short).Solving(d,b)-MCVs is an NP-hard problem,which means the computational time will exponentially increases with the network scale.In order to enhance the efficiency of solving(d,b)-MCVs,this paper constructs an improved model by introducing lower capacity bounds of arcs,and theoretically demonstrates the merit of the model.Furthermore,this paper employs the concept of transcendental number to establish a one-to-one mapping relationship between(d,b)-MCV and real number,based on which a novel method is proposed to remove duplicate(d,b)-MCVs.It is demonstrated from the viewpoint of time complexity that the proposed method is more practical and efficient in comparison with the existing ones.The performance of the proposed (d,b)-MCV algorithm is tes-ted by numerical experiments,and the results indicate that the algorithm is more efficient in solving(d,b)-MCVs and thus provides a new method for computing Rel_(d,b).

Key words: Multi-state network, Reliability, Cost constraint, Minimal capacity vector