×

zbMATH — the first resource for mathematics

Stochastic survivable network design problems: theory and practice. (English) Zbl 1394.90450
Summary: We study survivable network design problems with edge-connectivity requirements under a two-stage stochastic model with recourse and finitely many scenarios. For the formulation in the natural space of edge variables we show that facet defining inequalities of the underlying polytope can be derived from the deterministic counterparts. Moreover, by using graph orientation properties we introduce stronger cut-based formulations. For solving the proposed mixed integer programming models, we suggest a two-stage branch & cut algorithm based on a decomposed model. In order to accelerate the computations, we suggest a new technique for strengthening the decomposed L-shaped optimality cuts which is computationally fast and easy to implement. A computational study shows the benefit of the decomposition and the cut strengthening – which significantly reduces the number of master iterations and the computational running time. Moreover, we evaluate the stability of the scenario generation method and analyze the value of the stochastic solution.

MSC:
90C15 Stochastic programming
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
Software:
DIMACS
PDF BibTeX Cite
Full Text: DOI
References:
[1] Balakrishnan, A.; Magnanti, T. L.; Mirchandani, P., Connectivity-splitting models for survivable network design, Networks, 43, 1, 10-27, (2004) · Zbl 1143.90313
[2] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252, (1962) · Zbl 0109.38302
[3] Birge, J. R.; Louveaux, F., Introduction to stochastic programming, (2011), Springer-Verlag New York · Zbl 1223.90001
[4] Bomze, I. M.; Chimani, M.; Jünger, M.; Ljubić, I.; Mutzel, P.; Zey, B., Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut, ISAAC (1), LNCS, 427-439, (2010), Springer-Verlag Berlin Heidelberg · Zbl 1311.90085
[5] Botton, Q.; Fortz, B.; Gouveia, L.; Poss, M., Benders decomposition for the hop-constrained survivable network design problem, INFORMS Journal on Computing, 25, 1, 13-26, (2013)
[6] Carœ, C. C.; Tind, J., L-shaped decomposition of two-stage stochastic programs with integer recourse, Mathematical Programming, 83, 3, 451-464, (1998) · Zbl 0920.90107
[7] Chimani, M.; Kandyba, M.; Ljubić, I.; Mutzel, P., Orientation-based models for {0, 1, 2}-survivable network design: theory and practice, Mathematical Programming, 124, 1-2, (2010)
[8] Chopra, S., The k-edge-connected spanning subgraph polyhedron, SIAM Journal on Discrete Mathematics, 7, 2, 245-259, (1994) · Zbl 0821.90123
[9] Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Operations Research, 54, 4, 756-766, (2006) · Zbl 1167.90601
[10] Fischetti, M.; Salvagnin, D.; Zanette, A., A note on the selection of benders’ cuts, Mathematical Programming, 124, 175-182, (2010) · Zbl 1198.90302
[11] Fortz, B.; Mahjoub, A. R.; McCormick, S. T.; Pesneau, P., Two-edge connected subgraphs with bounded rings: polyhedral results and branch-and-cut, Mathematical Programming, 105, 1, 85-111, (2006) · Zbl 1085.90009
[12] Grötschel, M.; Monma, C. L.; Stoer, M., Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints, Operations Research, 4, 2, 309-330, (1992) · Zbl 0749.90029
[13] Grötschel, M.; Monma, C. L.; Stoer, M., Design of survivable networks, Network models, Handbooks in operations research and management science, 7, 617-672, (1995), Elsevier · Zbl 0839.90132
[14] Grötschel, M.; Monma, C. L.; Stoer, M., Polyhedral and computational investigations for designing communication networks with high survivability requirements, Operations Research, 43, 6, 1012-1024, (1995) · Zbl 0853.90055
[15] Gupta, A.; Krishnaswamy, R.; Ravi, R., Online and stochastic survivable network design, ACM-SIAM STOC, 685-694, (2009), ACM · Zbl 1304.68139
[16] Gupta, A.; Ravi, R.; Sinha, A., LP rounding approximation algorithms for stochastic network design, Mathematics of Operations Research, 32, 2, 345-364, (2007) · Zbl 1279.90030
[17] Hokama, P.; Felice, M. C.S.; Bracht, E. C.; Usberti, F. L., A heuristic approach for the stochastic Steiner tree problem, Proceedings of the eleventh DIMACS implementation challenge, (2014)
[18] Jain, K., A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, 1, 39-60, (2001) · Zbl 1107.68533
[19] Johnson, D. S.; Minkoff, M.; Phillips, S., The prize-collecting Steiner tree problem: theory and practice, ACM-SIAM SODA, 760-769, (2000), SIAM · Zbl 0956.68112
[20] Kandyba, M., Exact algorithms for network design problems using graph orientations, (2011), Technische Universität Dortmund, Ph.D. thesis
[21] Kaut, M.; Wallace, S. W., Evaluation of scenario-generation methods for stochastic programming, Pacific Journal of Optimization, 3, 2, 257-271, (2007) · Zbl 1171.90490
[22] Kerivin, H.; Mahjoub, A. R., Design of survivable networks: A survey, Networks, 46, 1, 1-21, (2005) · Zbl 1072.90003
[23] King, A. J.; Wallace, S. W., Modeling with stochastic programming, Springer series in operations research and financial engineering, (2012), Springer-Verlag New York · Zbl 1248.90063
[24] Laporte, G.; Louveaux, F., The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13, 133-142, (1993) · Zbl 0793.90043
[25] Leitner, M., Solving two network design problems by mixed integer programming and hybrid optimization methods, (2010), Technische Universität Wien, Ph.D. thesis
[26] Leitner, M.; Ruthmair, M.; Raidl, G. R., Stabilizing branch-and-price for constrained tree problems, Networks, 61, 2, 150-170, (2013) · Zbl 1269.90020
[27] Ljubić, I.; Mutzel, P.; Zey, B., Stochastic survivable network design problems, INOC, Electronic Notes in Discrete Mathematics, 41, 0, 245-252, (2013)
[28] Ljubić, I.; Putz, P.; González, J. J.S., Exact approaches to the single-source network loading problem, Networks, 59, 1, 89-106, (2012) · Zbl 1241.90018
[29] Maggioni, F.; Wallace, S. W., Analyzing the quality of the expected value solution in stochastic programming, Annals of Operations Research, 200, 1, 37-54, (2010) · Zbl 1254.90142
[30] Magnanti, T. L.; Raghavan, S., Strong formulations for network design problems with connectivity requirements, Networks, 45, 2, 61-79, (2005) · Zbl 1067.68104
[31] Magnanti, T. L.; Wong, R. T., Accelerating benders’ decomposition: algorithmic enhancement and model selection criteria, Operations Research, 29, 3, 464-484, (1981) · Zbl 0455.90064
[32] Nash-Williams, C. S.J. A., On orientations, connectivity, and odd vertex pairings in finite graphs, Canadian Journal of Mathematics, 12, 555-567, (1960) · Zbl 0096.38002
[33] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization, (1988), Wiley-Interscience · Zbl 0652.90067
[34] Papadakos, N., Practical enhancements to the magnanti-Wong method, Operations Research Letters, 36, 4, 444-449, (2008) · Zbl 1155.90432
[35] Prékopa, A., Probabilistic programming, Stochastic programming, Handbooks in operations research and management science, 10, 267-351, (2003), Elsevier
[36] Rak, J.; Sterbenz, J., Preface: optimization issues in resilient network design and modeling, Networks, 66, 4, 251-252, (2015)
[37] Ravi, R.; Sinha, A., Hedging uncertainty: approximation algorithms for stochastic optimization problems, Mathematical Programming, 108, 1, 97-114, (2006) · Zbl 1098.90046
[38] Rodríguez-Martín, R.; Salazar-González, J.-J.; Yaman, H., A branch-and-cut algorithm for two-level survivable network design problems, Computers and Operations Research, 67, 102-112, (2016) · Zbl 1349.90171
[39] Schultz, R., Stochastic programming with integer variables, Mathematical Programming, 97, 1-2, 285-309, (2003) · Zbl 1035.90053
[40] Sen, S.; Sherali, H. D., Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Mathematical Programming, 106, 2, 203-223, (2006) · Zbl 1134.90449
[41] Sherali, H.; Lunday, B., On generating maximal nondominated benders cuts, Annals of Operations Research, 210, 57-72, (2011) · Zbl 1288.90055
[42] Shmoys, D. B.; Swamy, C., Algorithms column: approximation algorithms for 2-stage stochastic optimization problems, SIGACT News, 37, 1, 33-46, (2006)
[43] Slyke, R. V.; Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal of Applied Mathematics, 17, 4, 638-663, (1967) · Zbl 0197.45602
[44] Song, Y.; Luedtke, J. R., Branch-and-cut approaches for chance-constrained formulations of reliable network design problems, Mathematical Programming Computation, 5, 4, 397-423, (2013) · Zbl 1330.90057
[45] Song, Y.; Zhang, M., Chance-constrained multi-terminal network design problems, Naval Research Logistics, 62, 4, 321-334, (2015)
[46] SSNDPLib (2014). SSNDPLib: http://ls11-www.cs.tu-dortmund.de/staff/zey/ssndp.
[47] Stoer, M., Design of survivable networks, Lecture notes in mathematics, (1992), Springer-Verlag Berlin Heidelberg
[48] Wentges, P., Accelerating benders’ decomposition for the capacitated facility location problem, Mathematical Methods of Operations Research, 44, 267-290, (1996) · Zbl 0862.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.