On the chance-constrained minimum spanning \(k\)-core problem. (English) Zbl 1428.90172
Summary: A graph is called a \(k\)-core if every vertex has at least \(k\) neighbors. If the parameter \(k\) is sufficiently large relative to the number of vertices, a \(k\)-core is guaranteed to possess 2-hop reachability between all pairs of vertices. Furthermore, it is guaranteed to preserve those pairwise distances under arbitrary single-vertex deletion. Hence, the concept of a \(k\)-core can be used to produce 2-hop survivable network designs, specifically to design inter-hub networks. Formally, given an edge-weighted graph, the minimum spanning \(k\)-core problem seeks a spanning subgraph of the given graph that is a \(k\)-core with minimum total edge weight. For any fixed \(k\), this problem is equivalent to a generalized graph matching problem and can be solved in polynomial time. This article focuses on a chance-constrained version of the minimum spanning \(k\)-core problem under probabilistic edge failures. We first show that this probabilistic version is NP-hard, and we conduct a polyhedral study to strengthen the formulation. The quality of bounds produced by the strengthened formulation is demonstrated through a computational study.
MSC:
| 90C35 | Programming involving graphs or networks |
Keywords:
chance-constrained optimization; minimum spanning \(k\)-core; hop-constrained survivable network designReferences:
| [1] | Andreas, A.K., Smith, J.C.: Mathematical programming algorithms for two-path routing problems with reliability considerations. INFORMS J. Comput. 20(4), 553-564 (2008) · Zbl 1243.90220 · doi:10.1287/ijoc.1080.0266 |
| [2] | Andreas, A.K., Smith, J.C., Küçükyavuz, S.: Branch-and-price-and-cut algorithms for solving the reliable h-paths problem. J. Glob. Optim. 42(4), 443-466 (2008) · Zbl 1159.90012 · doi:10.1007/s10898-007-9254-x |
| [3] | Balakrishnan, A., Altinkemer, K.: Using a hop-constrained model to generate alternative communication network design. ORSA J. Comput. 4(2), 192-205 (1992) · Zbl 0825.90395 · doi:10.1287/ijoc.4.2.192 |
| [4] | Balasundaram, B.: Graph theoretic generalizations of clique: Optimization and extensions. Ph.D. thesis, Texas A&M University, College Station, Texas, USA (2007) |
| [5] | Bendali, F., Diarrassouba, I., Mahjoub, A., Mailfert, J.: The \[k\] k edge-disjoint 3-hop-constrained paths polytope. Discrete Optim. 7(4), 222-233 (2010) · Zbl 1241.90155 · doi:10.1016/j.disopt.2010.05.001 |
| [6] | Beraldi, P., Bruni, M.E., Guerriero, F.: Network reliability design via joint probabilistic constraints. IMA J. Manag. Math. 21, 213-226 (2010) · Zbl 1184.90055 · doi:10.1093/imaman/dpp005 |
| [7] | Botton, Q., Fortz, B., Gouveia, L., Poss, M.: Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1), 13-26 (2013) · doi:10.1287/ijoc.1110.0472 |
| [8] | Brueckner, J.K., Spiller, P.T.: Competition and mergers in airline hub-and-spoke networks. Int. J. Ind. Organ. 9, 323-342 (1991) · doi:10.1016/0167-7187(91)90015-D |
| [9] | Carvalho, M., Sorokin, A., Boginski, V., Balasundaram, B.: Topology design for on-demand dual-path routing in wireless networks. Optim. Lett. 7(4), 695-707 (2013) · Zbl 1269.90028 · doi:10.1007/s11590-012-0453-0 |
| [10] | Dave, D.B.: Patterns of freight flow and design of a less-than-truckload distribution network. Ph.D. thesis, Georgia Institute of Technology (2004) |
| [11] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) · Zbl 0411.68039 |
| [12] | Jaillet, P., Song, G., Yu, G.: Airline network design and hub location problems. Locat. Sci. 4(3), 195-212 (1996) · Zbl 0929.90048 · doi:10.1016/S0966-8349(96)00016-2 |
| [13] | Kerivin, H., Mahjoub, A.R.: Design of survivable networks: a survey. Networks 46(1), 1-21 (2005) · Zbl 1072.90003 · doi:10.1002/net.20072 |
| [14] | Kim, Y., Chen, Y.S., Linderman, K.: Supply network disruption and resilience: a network structural perspective. J. Oper. Manag. 33-34, 43-59 (2015) · doi:10.1016/j.jom.2014.10.006 |
| [15] | Koster, A.M., Kutschka, M., Raack, C.: Robust network design: formulations, valid inequalities, and computations. Networks 61(2), 128-149 (2013) · Zbl 1269.90029 · doi:10.1002/net.21497 |
| [16] | Küçükyavuz, S.: On mixing sets arising in chance-constrained programming. Math. Program. 132(1), 31-56 (2012) · Zbl 1262.90110 · doi:10.1007/s10107-010-0385-3 |
| [17] | Liu, X., Kılınç-Karzan, F., Küçükyavuz, S.: On intersection of two mixing sets with applications to joint chance-constrained programs. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1231-2 · Zbl 1412.90095 |
| [18] | Luedtke, J.; Eisenbrand, F. (ed.); Shepherd, F. (ed.), An integer programming and decomposition approach to general chance-constrained mathematical programs, No. 6080, 271-284 (2010), Berlin · Zbl 1285.90024 · doi:10.1007/978-3-642-13036-6_21 |
| [19] | Luedtke, J.: A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. 146(1-2), 219-244 (2014) · Zbl 1297.90092 · doi:10.1007/s10107-013-0684-6 |
| [20] | Luedtke, J., Ahmed, S., Nemhauser, G.: An integer programming approach for linear programs with probabilistic constraints. Math. Program. 12(2), 247-272 (2010) · Zbl 1184.90115 · doi:10.1007/s10107-008-0247-4 |
| [21] | Ma, J., Balasundaram, B.: Solving chance-constrained spanning \[k\] k-core problem via decomposition and integer programming. In: Proceedings of the 2013 Industrial and Systems Engineering Research Conference (ISERC 2013), pp. 2774-2783. Institute of Industrial Engineers, Norcross, GA (2013) |
| [22] | Ma, J., Pajouh, F.M., Balasundaram, B., Boginski, V.: The minimum spanning \[k\] k-core problem with bounded CVaR under probabilistic edge failures. INFORMS J. Comput. 28(2), 295-307 (2016) · Zbl 1343.90102 · doi:10.1287/ijoc.2015.0679 |
| [23] | Magnanti, T.L., Raghavan, S.: Strong formulations for network design problems with connectivity requirements. Networks 45(2), 61-79 (2005) · Zbl 1067.68104 · doi:10.1002/net.20046 |
| [24] | Mahjoub, A.R., Simonetti, L., Uchoa, E.: Hop-level flow formulation for the survivable network design with hop constraints problem. Networks 61(2), 171-179 (2013) · Zbl 1269.90023 · doi:10.1002/net.21483 |
| [25] | Minoux, M.: Network synthesis and optimum network design problems: models, solution methods, and applications. Networks 19, 313-360 (1989) · Zbl 0666.90032 · doi:10.1002/net.3230190305 |
| [26] | Monma, C.L., Shallcross, D.F.: Methods for designing communications networks with certain two-connected survivability constraints. Oper. Res. 37(4), 531-541 (1989) · doi:10.1287/opre.37.4.531 |
| [27] | Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1999) · Zbl 0944.90001 |
| [28] | O’Kelly, M.E., Miller, H.J.: The hub network design problem: a review and synthesis. J. Transp. Geogr. 2(1), 31-40 (1994) · doi:10.1016/0966-6923(94)90032-9 |
| [29] | Pastukhov, G., Veremyev, A., Boginski, V., Pasiliao, E.L.: Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks. J. Comb. Optim. 27(3), 462-486 (2014) · Zbl 1296.90134 · doi:10.1007/s10878-012-9523-6 |
| [30] | Rodríguez-Martín, I., Salazar-González, J.J., Yaman, H.: A branch-and-cut algorithm for two-level survivable network design problems. Comput. Oper. Res. 67, 102-112 (2016) · Zbl 1349.90171 · doi:10.1016/j.cor.2015.09.008 |
| [31] | Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269-287 (1983) · doi:10.1016/0378-8733(83)90028-X |
| [32] | Smith, J.C., Lim, C., Sudargho, F.: Survivable network design under optimal and heuristic interdiction scenarios. J. Glob. Optim. 38(2), 181-199 (2007) · Zbl 1179.90056 · doi:10.1007/s10898-006-9067-3 |
| [33] | Song, Y., Luedtke, J.R.: Branch-and-cut approaches for chance-constrained formulations of reliable network design problems. Math. Program. Comput. 5(4), 397-432 (2013) · Zbl 1330.90057 · doi:10.1007/s12532-013-0058-3 |
| [34] | Sorokin, A., Boginski, V., Nahapetyan, A., Pardalos, P.M.: Computational risk management techniques for fixed charge network flow problems with uncertain arc failures. J. Comb. Optim. 25(1), 99-122 (2013) · Zbl 1269.90132 · doi:10.1007/s10878-011-9422-2 |
| [35] | Veremyev, A.; Boginski, V.; Sorokin, A. (ed.); Murphey, R. (ed.); Thai, MT (ed.); Pardalos, PM (ed.), Robustness and strong attack tolerance of low-diameter networks, No. 20, 137-156 (2012), New York · Zbl 1268.90120 |
| [36] | Zheng, Q.P., Shen, S., Shi, Y.: Loss-constrained minimum cost flow under arc failure uncertainty with applications in risk-aware kidney exchange. IIE Trans. 47(9), 961-977 (2015) · doi:10.1080/0740817X.2014.991476 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
