Algorithmic approaches for network design with facility location: A survey

Document Type : Review Article

Author

Department of Computer Science and Statistics, Faculty of Mathematics, K. N. Toosi University of Technology, Tehran, Iran

Abstract

We consider a family of problems that combine network design and facility location. Such problems arise in many practical applications in different fields such as telecommunications, transportation networks, logistic, and energy supply networks. In facility location problems, we want to decide which facilities to open and how to assign clients to the open facilities so as to minimize the sum of the facility opening costs and client connection costs. These problems typically do not involve decisions concerning the routing of the clients’ demands to the open facilities; once we decided on the set of open facilities, each client is served by the closest open facility. In network design problems, on the other hand, we generally want to design and dimension a minimum-cost routing network providing sufficient capacities to route all clients’ demands to their destinations. These problems involve deciding on the routing of each client’s demand. But, in contrast to facility location problems, demands’ destinations are predetermined. In many modern day applications, however, all these decisions are interdependent and affect each other. Hence, they should be taken simultaneously. The aim of this work is to survey models, algorithmic approaches and methodologies concerning such combined network design facility location problems.

Keywords

Main Subjects


[1] Z. Abrams, A. Meyerson, K. Munagala, and S. Plotkin, The integrality gap of capacitated facility location, Technical Report CMU-CS-02-199, Carnegie Mellon University, (2002).
[2] A. Aggarwal, A. Louis, M. Bansal, N. Garg, N. Gupta, S. Gupta, and S. Jain, A 3-approximation algorithm for the facility location problem with uniform capacities, Mathematical Programming, 141 (2013).
[3] S. Ahmadian and C. Swamy, Improved approximation guarantees for lower-bounded facility location, Approximation and Online Algorithms, (2012), pp. 257–271.
[4] H.-C. An, M. Singh, and O. Svensson, LP-based algorithms for capacitated facility location, In proceedings of FOCS 2014, (2014), pp. 256–265.
[5] M. Andrews, Hardness of buy-at-bulk network design, Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, (2004), pp. 115–124.
[6] A. Arulselvan, M. Rezapour, and W. A. Welz, Exact approaches for designing multifacility buy-at-bulk networks, INFORMS Journal on Computing, 29 (2017), pp. 597–611.
[7] B. Awerbuch and Y. Azar, Buy-at-bulk network design, Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, (1997), pp. 542–547.
[8] M. Bansal, N. Garg, and N. Gupta, A 5-approximation for capacitated facility location, In proceedings of ESA 2012, (2012), pp. 133–144.
[9] M. G. Bardossy and S. Raghavan, Dual-based local search for the connected facility location and related problems, INFORMS Journal on Computing, 22 (2010), pp. 584–602.
[10] Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, (1996), pp. 184–193.
[11] , On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, (1998), pp. 161–168.
[12] J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische mathematik, 4 (1962), pp. 238–252.
[13] M. Bern and P. Plassmann, The steiner problem with edge lengths 1 and 2, Information Processing Letters, 32 (1989), pp. 171–176.
[14] A. Bley, S. M. Hashemi, and M. Rezapour, Approximation algorithms for a combined facility location buy-at-bulk network design problem, Theory and Applications of Models of Computation (TAMC), Lecture Notes in Computer Science Vol. 7876, (2013), pp. 72–83.
[15] , Ip modeling of the survivable hop constrained connected facility location problem, Electronic Notes in Discrete Mathematics, 41 (2013), pp. 463–470.
[16] A. Bley and M. Rezapour, Combinatorial approximation algorithms for buy-at-bulk connected facility location problems, Discrete Applied Mathematics, 213 (2016), pp. 34–46.
[17] Q. Botton, B. Fortz, L. Gouveia, and M. Poss, Benders decomposition for the hop-constrained survivable network design problem, INFORMS journal on computing, 25 (2013), pp. 13–26.
[18] J. Byrka and K. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM Journal on Computing, 39 (2010), pp. 2212–2231.
[19] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanita`, An improved lp-based approximation for steiner tree, Proceedings of the 42nd ACM symposium on Theory of computing, (2010), pp. 583–592.
[20] M. Charikar and S. Guha, Improved combinatorial algorithms for the facility location and k-median problems, Foundations of Computer Science, 1999. 40th Annual Symposium on, (1999), pp. 378–388.
[21] M. Charikar and A. Karagiozova, On non-uniform multicommodity buy-at-bulk network design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, (2005), pp. 176–182.
[22] C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Approximation algorithms for nonuniform buy-at-bulk network design, SIAM Journal on Computing, 39 (2010), pp. 1772–1798.
[23] C. Chekuri, S. Khanna, and J. S. Naor, A deterministic algorithm for the cost-distance problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, (2001), pp. 232–233.
[24] M. Chleb´ık and J. Chleb´ıkova´, The steiner tree problem on graphs: Inapproximability results, Theoretical Computer Science, 406 (2008), pp. 207–214.
[25] F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM Journal on Computing, 33 (2003), pp. 1–25.
[26] F. A. Chudak and D. P. Williamson, Improved approximation algorithms for capacitated facility location problems, Mathematical programming, 102 (2005).
[27] J. Chuzhoy, A. Gupta, J. S. Naor, and A. Sinha, On the approximability of some network design problems, ACM Transactions on Algorithms (TALG), 4 (2008), p. 23.
[28] V. Chvatal, A greedy heuristic for the set-covering problem, Mathematics of operations research, 4 (1979), pp. 233–235.
[29] G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations research, 8 (1960), pp. 101–111.
[30] F. Eisenbrand, F. Grandoni, T. Rothvoß, and G. Schafer ¨ , Connected facility location via random facility sampling and core detouring, Journal of Computer and System Sciences, 76 (2010), pp. 709–726.
[31] J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, (2003), pp. 448–455.
[32] L. Fleischer, K. Jain, and D. P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, Journal of Computer and System Sciences, 72 (2006), pp. 838–867.
[33] Z. Friggstad, M. Rezapour, and M. R. Salavatipour, Approximating connected facility location with lower and upper bounds via lp rounding, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), (2016).
[34] Z. Friggstad, M. Rezapour, M. R. Salavatipour, and J. A. Soto, Lp-based approximation algorithms for facility location in buy-at-bulk network design, Algorithmica, 81 (2019), pp. 1075–1095.
[35] M. Garey and D. Johnson, Computers and intractability: a guide to the theory of np-completeness, WH Freeman & Co., San Francisco, (1979).
[36] N. Garg, R. Khandekar, G. Konjevod, R. Ravi, F. S. Salman, and A. Sinha, On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem, Integer Programming and Combinatorial Optimization, (2001), pp. 170–184.
[37] M. X. Goemans, A. V. Goldberg, S. A. Plotkin, D. B. Shmoys, E. Tardos, and D. P. Williamson, Improved approximation algorithms for network design problems., SODA, 94 (1994), pp. 223–232.
[38] S. Gollowitzer and I. Ljubic´, Mip models for connected facility location: A theoretical and computational study, Computers & Operations Research, 38 (2011), pp. 435–449.
[39] F. Grandoni and T. Rothvoß, Network design via core detouring for problems without a core, Automata, Languages and Programming, (2010), pp. 490–502.
[40] , Approximation algorithms for single and multi-commodity connected facility location, Integer Programming and Combinatoral Optimization, (2011), pp. 248–260.
[41] S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, Journal of algorithms, 31 (1999), pp. 228–248.
[42] S. Guha, A. Meyerson, and K. Munagala, Hierarchical placement and network design problems, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 603–612.
[43] , A constant factor approximation for the single sink edge installation problems, Proceedings of the thirtythird annual ACM symposium on Theory of computing, (2001), pp. 383–388.
[44] , A constant factor approximation for the single sink edge installation problem, SIAM Journal on Computing, 38 (2009), pp. 2426–2442.
[45] A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, (2001), pp. 389–398.
[46] A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, (2003), pp. 365–372.
[47] N. Gupta, S. Grover, and R. Dabas, Respecting lower bounds in uniform lower and upper bounded facility location problem, International Computing and Combinatorics Conference, (2021), pp. 463–475.
[48] M. K. Hasan, H. Jung, and K.-Y. Chwa, Approximation algorithms for connected facility location problems, Journal of Combinatorial Optimization, 16 (2008), pp. 155–172.
[49] S. M. Hashemi, A. Moradi, and M. Rezapour, An aco algorithm to design umts access network using divided and conquer technique, Engineering Applications of Artificial Intelligence, 21 (2008), pp. 931–940.
[50] S. M. Hashemi, M. Rezapour, and A. Moradi, An effective hybrid pso-based algorithm for planning umts terrestrial access networks, Engineering Optimization, 42 (2010), pp. 241–251.
[51] D. S. Hochbaum, Heuristics for the fixed cost median problem, Mathematical programming, 22 (1982), pp. 148–162.
[52] J. Hromkovic, Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics, Springer-Verlag, (2010).
 [53] D. Huygens, M. Labbe, A. R. Mahjoub, and P. Pesneau ´ , The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut, Networks, 49 (2007), pp. 116–133.
[54] K. Jain, A factor 2 approximation algorithm for the generalized steiner network problem, Combinatorica, 21 (2001), pp. 39–60.
[55] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp, Journal of the ACM (JACM), 50 (2003), pp. 795–824.
[56] K. Jain, M. Mahdian, and A. Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, (2002), pp. 731–740.
[57] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation, Journal of the ACM (JACM), 48 (2001), pp. 274–296.
[58] R. Jothi and B. Raghavachari, Improved approximation algorithms for the single-sink buy-at-bulk network design problems, Algorithm Theory-SWAT 2004, (2004), pp. 336–348.
[59] H. Jung, M. K. Hasan, and K.-Y. Chwa, A 6.55 factor primal-dual approximation algorithm for the connected facility location problem, Journal of combinatorial optimization, 18 (2009), pp. 258–271.
[60] D. Karget and M. Minkoff, Building steiner trees with incomplete global knowledge, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 613–623.
[61] N. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the sixteenth annual ACM symposium on Theory of computing, (1984), pp. 302–311.
[62] G. Kortsarz and Z. Nutov, Approximating some network design problems with node costs, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (2009), pp. 231–243.
[63] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, Journal of algorithms, 37 (2000), pp. 146–188.
[64] R. Levi, D. B. Shmoys, and C. Swamy, LP-based approximation algorithms for capacitated facility location, Mathematical programming, 131 (2012).
[65] S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Information and Computation, 222 (2013), pp. 45–58.
[66] , On facility location with general lower bounds, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (2019), pp. 2279–2290.
[67] J.-H. Lin and J. S. Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, 44 (1992), pp. 245–249.
[68] I. Ljubic´, A hybrid vns for connected facility location, Hybrid Metaheuristics, (2007), pp. 157–169.
[69] I. Ljubic, P. Putz, and J.-J. Salazar-Gonz ´ alez ´ , Exact approaches to the single-source network loading problem, Networks, 59 (2012), pp. 89–106.
[70] M. E. Lubbecke and J. Desrosiers ¨ , Selected topics in column generation, Operations Research, 53 (2005), pp. 1007–1023.
[71] M. Mahdian, Y. Ye, and J. Zhang, Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 36 (2006), pp. 411–432.
[72] A. R. Mahjoub, L. Simonetti, and E. Uchoa, Hop-level flow formulation for the survivable network design with hop constraints problem, Networks, 61 (2013), pp. 171–179.
[73] P. Manyem, Constrained spanning, steiner trees and the triangle inequality, Optimization, (2009), pp. 355– 367.
[74] A. Meyerson, K. Munagala, and S. Plotkin, Cost-distance: Two metric network design, Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, (2000), pp. 624–630.
[75] M. Pal, E. Tardos, and T. Wexler, Facility location with nonuniform hard capacities, In proceedings of FOCS 2001, (2001), pp. 329–338.
[76] S. Raghavan and D. Stanojevic´, A note on search by objective relaxation, Telecommunications planning: innovations in pricing, network design and management, (2006), pp. 181–201.
[77] C. Randazzo, H. P. L. Luna, P. Mahey, et al., Benders decomposition for local access network design with two technologies., Discrete Mathematics & Theoretical Computer Science, 4 (2001), pp. 235–246.
[78] R. Ravi and A. Sinha, Approximation algorithms for problems combining facility location and network design, Operations Research, 54 (2006), pp. 73–81.
[79] M. Rezapour, Network design with facility location: Approximation and exact techniques, Ph.D. Thesis, Technische Universit¨at Berlin, (2015).
[80] G. Robins and A. Zelikovsky, Improved steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, (2000), pp. 770–779.
[81] F. S. Salman, R. Ravi, and J. N. Hooker, Solving the capacitated local access network design problem, INFORMS Journal on Computing, 20 (2008), pp. 243–254.
[82] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer, 24 (2003).
[83] D. B. Shmoys, E. Tardos, and K. Aardal ´ , Approximation algorithms for facility location problems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, (1997), pp. 265–274.
[84] M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, Integer programming and combinatorial optimization, (2002), pp. 240–257.
[85] Z. Svitkina, Lower-bounded facility location, ACM Transactions on Algorithms (TALG), 6 (2010), p. 69.
[86] C. Swamy and A. Kumar, Primal–dual algorithms for connected facility location problems, Algorithmica, 40 (2004), pp. 245–269.
[87] H. Takahashi and A. Matsuyama, An approximate solution for the steiner problem in graphs, Math. Japonica, 24 (1980), pp. 573–577.
[88] K. Talwar, The single-sink buy-at-bulk lp has constant integrality gap, Integer Programming and Combinatorial Optimization, (2002), pp. 475–486.
[89] A. Tomazic and I. Ljubic´, A grasp algorithm for the connected facility location problem, Applications and the Internet, 2008. SAINT 2008. International Symposium on, (2008), pp. 257–260.
[90] V. V. Vazirani, Approximation algorithms, springer, (2001).
[91] J. Vygen, Approximation algorithms facility location problems, Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, (2005).
[92] D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, (1993), pp. 708–717.
[93] , A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica, 15 (1995), pp. 435–454.
[94] D. P. Williamson and D. B. Shmoys, The design of approximation algorithms, Cambridge University Press, (2011).
[95] L. A. Wolsey, Integer programming, Wiley New York, 42 (1998).