×

zbMATH — the first resource for mathematics

The incremental connected facility location problem. (English) Zbl 1458.90409
Summary: We consider the incremental connected facility location problem (incremental ConFL), in which we are given a set of potential facilities, a set of interconnection nodes, a set of customers with demands, and a planning horizon. For each time period, we have to select a set of facilities to open, a set of customers to be served, the assignment of these customers to the open facilities, and a network that connects the open facilities. Once a customer is served, it must remain served in subsequent periods. Furthermore, in each time period the total demand of all customers served must be at least equal to a given minimum coverage requirement for that period. The objective is to minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany.
MSC:
90B80 Discrete location and assignment
90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
OR-Library
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M.; Fernández, E.; Hinojosa, Y.; Puerto, J., The multi-period incremental service facility location problem, Comput. Opera. Res., 36, 1356-1375, (2009) · Zbl 1177.90242
[2] Arulselvan, A., A note on set union knapsack problem, Discret. Appl. Math., 169, 214-218, (2014) · Zbl 1288.05177
[3] Arulselvan, A.; Bley, A.; Gollowitzer, S.; Ljubić, I.; Maurer, O., MIP modeling of incremental connected facility location, Proceedings of INOC 2011. Proceedings of INOC 2011, Lecture Notes in Computer Science, 6701, 490-502, (2011) · Zbl 1346.90478
[4] Arulselvan, A.; Maurer, O.; Skutella, M., An incremental algorithm for the uncapacitated facility location problem, Networks, 65, 4, 306-311, (2015) · Zbl 1390.90365
[5] Averbakh, I.; Pereira, J., Network construction problems with due dates, Eur. J. Oper. Res., 244, 3, 715-729, (2015) · Zbl 1346.90322
[6] Balas, E.; Zemel, E., Facets of the knapsack polytope from minimal covers, SIAM J. Appl. Math., 34, 1, 119-148, (1978) · Zbl 0385.90083
[7] Bardossy, M.; Raghavan, S., Dual-based local search for the connected facility location and related problems, INFORMS J. Comput., 22, 4, 584-602, (2010) · Zbl 1243.90085
[8] Baxter, M.; Elgindy, T.; Ernst, A.; Kalinowski, T.; Savelsbergh, M., Incremental network design with shortest paths, Eur. J. Oper. Res., 238, 3, 675-684, (2014) · Zbl 1338.90074
[9] Beasley, J., 2013. OR-library. URL http://people.brunel.ac.uk/ mastjjb/jeb/orlib/steininfo.html.
[10] Bienstock, D.; Raskina, O.; Saniee, I.; Wang, Q., Combined network design and multiperiod pricing: modeling, solution techniques, and computation, Oper. Res., 54, 2, 261-276, (2006) · Zbl 1167.90417
[11] Bley, A.; Ljubić, I.; Maurer, O., Lagrangian decompositions for the two-level FTTx network design problem, EURO J. Comput. Optim., 1, 3, 221-252, (2013) · Zbl 1296.90099
[12] Cavdaroglu, B.; Hammel, E.; Mitchell, J.; Sharkey, T.; Wallace, W., Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems, Ann. Oper. Res., 203, 1, 279-294, (2013) · Zbl 1272.90014
[13] Charikar, M.; Khuller, S.; Mount, D. M.; Narasimhan, G., Algorithms for facility location problems with outliers, Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 642-651, (2001) · Zbl 1012.90026
[14] Christofides, N.; Nicos, B., Optimal expansion of an existing network, Math. Program., 6, 197-211, (1974) · Zbl 0288.90078
[15] Cordeau, J.; Furini, F.; Ljubić, I., Benders decomposition for very large scale partial set covering and maximal covering problems, Eur. J. Oper. Res., (2019) · Zbl 1430.90372
[16] Doulliez, P.; Rao, M., Optimal network capacity planning: a shortest-path scheme, Oper. Res., 23, 4, 810-818, (1975) · Zbl 0307.90026
[17] Eisenbrand, F.; Grandoni, F.; Rothvoß, T.; Schäfer, G., Connected facility location via random facility sampling and core detouring, J. Comput. Syst. Sci., 76, 709-726, (2010) · Zbl 1208.68236
[18] Engel, K.; Kalinowski, T.; Savelsbergh, M., Incremental network design with minimum spanning trees, J. Graph Algorithms Appl., 21, 4, 417-432, (2017) · Zbl 1358.05262
[19] Fischetti, M.; Leitner, M.; Ljubić, I.; Luipersbeck, M.; Monaci, M.; Resch, M.; Salvagnin, D.; Sinnl, M., Thinning out steiner trees: a node-based model for uniform edge costs, Math. Program. Comput., 9, 2, 203-229, (2017) · Zbl 1387.90132
[20] Goldschmidt, O.; Nehme, D.; Yu, G., Note: on the set-union knapsack problem, Nav. Res. Logist. (NRL), 41, 6, 833-842, (1994) · Zbl 0831.90088
[21] Gollowitzer, S.; Gendron, B.; Ljubić, I., A cutting plane algorithm for the capacitated connected facility location problem, Comput. Optim. Appl., 55, 3, 647-674, (2013) · Zbl 1275.90036
[22] Gollowitzer, S.; Ljubić, I., MIP models for connected facility location: a theoretical and computational study, Comput. Opera. Res., 38, 2, 435-449, (2011) · Zbl 1231.90267
[23] Havet, F.; Wennink, M., The push tree problem, Networks, 44, 4, 281-291, (2004) · Zbl 1058.90012
[24] Hoefer, M., 2013. UflLib. URL http://resources.mpi-inf.mpg.de/departments/d1/projects/benchmarks/UflLib/.
[25] Kalinowski, T.; Matsypura, D.; Savelsbergh, M., Incremental network design with maximum flows, Eur. J. Oper. Res., 242, 1, 51-62, (2015) · Zbl 1341.90024
[26] Kaparis, K.; Letchford, A., Separation algorithms for 0-1 knapsack polytopes, Math. Program., 124, 1-2, 69-91, (2010) · Zbl 1198.90297
[27] Lardeux, B.; Nace, D., Multi-period network design of optical transmission networks, 12th IEEE Symposium on Computers and Communications (ISCC 2007), 935-940, (2007)
[28] Leitner, M.; Ljubić, I.; J. J. Salazar-González and, M. S., An algorithmic framework for the exact solution of tree-star problems, Eur. J. Oper. Res., 261, 1, 54-66, (2017) · Zbl 1403.90577
[29] Leitner, M.; Ljubić, I.; Salazar-González, J.; Sinnl, M., The connected facility location polytope, Discret. Appl. Math., (2017)
[30] Leitner, M.; Ljubić, I.; Sinnl, M.; Werner, A., {ILP} Heuristics and a new exact method for bi-objective 0/1 ilps: application to fttx-network design, Comput. Opera. Res., 72, 128-146, (2016) · Zbl 1349.90649
[31] Leitner, M.; Raidl, G., Variable neighborhood search for a prize collecting capacity constrained connected facility location problem, Proceedings of 2008 International Symposium on Applications and the Internet (SAINT), 233-236, (2008), IEEE Computer Society
[32] Leitner, M.; Raidl, G., Branch-and-cut-and-price for capacitated connected facility location, J. Math. Model. Algorithms, 10, 3, 245-267, (2011) · Zbl 1235.90093
[33] Leitner, M.; Raidl, G., Variable neighborhood and greedy randomized adaptive search for capacitated connected facility location, (Moreno-Díaz, R.; Pichler, F.; Quesada-Arencibia, A., EUROCAST (1), (2011), Springer), 295-302
[34] Ljubić, I., A hybrid VNS for connected facility location, Lecture Notes in Computer Science, 4771, 157-169, (2007), Springer
[35] Nemhauser, G.; Wolsey, L., Integer and combinatorial optimization, (1988), Wiley-Interscience: Wiley-Interscience New York, NY, USA · Zbl 0652.90067
[36] Owen, S.; Daskin, M., Strategic facility location: a review, Eur. J. Oper. Res., 111, 3, 423-447, (1998) · Zbl 0938.90048
[37] Suhl, U.; Hilbert, H., A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs, Networks, 31, 4, 273-282, (1998) · Zbl 1002.90094
[38] Takahashi, H.; Matsuyama, A., An approximate solution for the steiner problem in graphs, Math. Japon., 24, 573-577, (1980) · Zbl 0435.05036
[39] Tomazic, A.; Ljubić, I., A GRASP algorithm for the connected facility location problem, Proceedings of 2008 International Symposium on Applications and the Internet (SAINT), 257-260, (2008)
[40] Ukkusuri, S.; Patil, G., Multi-period transportation network design under demand uncertainty, Transp. Res. Part B Methodol., 43, 6, 625-642, (2009)
[41] Wassermann, B., Operations research in action: a project for designing telecommunication access networks, (2012), University of Vienna, Ph.D. thesis
[42] Zadeh, N., On building minimum cost communication networks over time, Networks, 4, 1, 19-34, (1974) · Zbl 0284.90031
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.