Joint chance-constrained survivable multicommodity network design problem with demand uncertainty

Authors
Salman Khodayifar
Mohammadreza Farjaie
Institute for Advanced Studies in Basic Sciences (IASBS)
Abstract
Survivable Capacitated Networks Design Problem (SCNDP for short) is one of the most essential issues in telecommunication and transportation networks. A survivable network is a network that is designed to remain operational in the event of a component(s) failure(s) (cable cuts, electronic failures on switching centers and so forth). In SCNDP, researchers usually consider survivability with two different ways named diversification and reservation. Diversification consists of dividing the demand of source-sink node pairs into two or more node-disjoint (or arc-disjoint) paths, and in reservation after the failure of a component(s) of the network, part of the demand for node pairs can still be satisfied by rerouting. To implement reservation, the links on the network ought to have enough capacity to support the new flows after the rerouting has been made. ‎Therefore, in this paper, we first present one model for the problem of survivable capacitated network design based on the reservation strategy. In many real-world applications, the observed values are often uncertain, for example random, fuzzy, etc. Therefore, we consider the demand vector (the right hand side values) randomly and then by using joint chance-constrained and probability concepts, obtain the corresponding deterministic model. Then, we propose an approximation optimization approach and use piecewise tangent approximation and piecewise linear methods to obtain the lower and upper bounds for it, respectively. Finally, computational results show the efficiency of the proposed model and approximation methods for relatively large-scale networks.
Keywords
Network design problem
Survivability
Joint chance-constrained programming
Independent random variables
1. Barabasi, A., and Albert, R, “Emergence of scaling in random networks”, (2002) 509-512.



2. Charnes, A., and Cooper, W.W., “Chance-Constrained Programming”, Management Sci, 6

(1959) 73-79.



3. Cheng, J., and Lisser, A., “A second-order cone programming approach for linear programs

with joint probabilistic constraints”, Operation Research, 40 (2012) 325-328.



4. Cheng, J., Houda, M., Lisser, A., “Chance-constrained 0-1 quadratic programs using

Copulas”, Optim Lett, (2015).

5. Dahl, G., and Stoer, M., “A cutting plane algorithm for multicommodity survivable network

design problems”, INFORMS Jon Comput, 10 (1998) 1-11.



6. Jagannathan, R., “Chance-Constrained Programming with Joint Constraints “, Operations



Research, 22(2) (1974) 358-372.



7. Kataoka, S., “A stochastic programming model”, Econometrica, 31(1-2) (1963) 181-196.



8. Koster, A., and Kutschka, M., “An integrated model for survivable network design under



demand uncertainty”, 8th International Workshop on the Design of Reliable Communication



Networks (DRCN), (2011).



9. Ljubic, I., Mutzel, P., and Zey, B., “Stochastic survivable network design problems: Theory



and practice”, European Journal of Operation Research, (2016) 1-16.



10. Miller, B.L., Wagner, H.M., “Chance constrained programming with joint constraints”,



Operations Research, 13(6) (1965) 930-945.



11. Minoux, M., “Optimum synthesis of a network with non-simultaneous multicommodity flow Requirements”, In P. Hansen, editor, Studies on Graphs and Discrete Programming, pages,

(1981) 269-277.



12. Rios, M., Marianov, V., Gutierrez, M., “Survivable capacitated network design problem:



new formulation and Lagrangean relaxation”, The Journal of the Operational Research



Society, Vol. 51, No. 5 (May, 2000), pp, (2000) 574-582.



13. Salehi, H., Anisi, M., “Survivable multi-commodity network flow design: case of node



capacities and arc Failure”, RAIRO - Operations Research, 35, (2019) 355-365.



14. Terblanche, S.E., Wessaly, R., Hatting, J.M., “Survivable network design with demand



Uncertainty”, European Journal of Operational Research Volume 210, Issue 1, (2011) Pages



10-26.



15. Van de Panne, C., Popp, W., “Minimum-cost cattle feed under probabilistic protein



constraints”, Management Science, 9(3) (1963) 405-430.