The General Reliability Network Design Problem

摘要

We consider the important practical and theoretical problem of designing communication network with a minimum total cost to operate under condition of certain its components failing. The model with 0, 1 flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP-relaxation is NP-complete problem. For some particular cases we prove that the solution of LP-relaxation problem can be obtained by polynomial algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding this problem solution we employ the branch and bound algorithm and we also report on some computational results.