A Fast Strategy to Find Solution for Survivable Multicommodity Network
محورهای موضوعی : مجله بین المللی ریاضیات صنعتی
M. Anisi
1
(Department of Mathematics, Qazvin Branch, Islamic Azad University, Qazvin, Iran.)
کلید واژه: failure scenario, Benders decomposition, Network Design, Survivable,
چکیده مقاله :
This paper proposes an immediately efficient method, based on Benders Decomposition (BD), for solving the survivable capacitated network design problem. This problem involves selecting a set of arcs for building a survivable network at a minimum cost and within a satisfied flow. The system is subject to failure and capacity restriction. To solve this problem, the BD was initially proposed with far outperformed than mixed integer programming. The employed method in this paper is the modified BD i.e. it identifies the initial failure scenario which are to be solved by BD, proposing a new strategy on the basis of s-t cut theorem. For a comparison between the BD method and our modified BD method, four network sets including one origin, one destination, four failure scenario, one supply node and one demand node have been randomly produced. Next, by using GAMS software, the two methods are compared with respect to their required CPU time where it is shown that the proposed method vitally saves time as much as 30%. This strategy reduces iterations more greatly as compared with the BD approach. While other methods concentrate on valid inequalities for reducing iterations of BD, this study does not use such valid inequalities. In addition, the new method is easily and quickly implementable.
