Comments on: Static and dynamic source locations in undirected networks

TOP (2015) 23:647–649 DOI 10.1007/s11750-015-0393-9 DISCUSSION Comments on: Static and dynamic source locations in undirected networks Emilio Carrizosa1 Published online: 25 September 2015 © Sociedad de Estadí-stica e Investigación Operativa 2015 The set covering problem (SCP) is among the most studied problems in Operations Research, see García and Marín (2015) for an excellent up-to-date review. Given a set V={v1,...,v n}of users, and a set P={p1,...,pm}of potential locations for the facilities, at cost f1,f2,..., fm,the aim of the SCP is to select a minimum-cost set S⊂Pof facilities covering V,in the sense that for any user v∈Vthere exists some p∈Scovering (i.e., close enough to) v. Denoting by aij the coefficient aij =1,if viis covered by pj 0,else SCP amounts to solving the (hard) linear problem in binary variables min m j=1fjxj s.t. m j=1aijxj≥1∀i=1,...,n xj∈{0,1}∀j=1,...,m. (1) Hence, if the matrix A=(aij)ij is built in a preprocessing step, then the problem can be handled by means of the bunch of exact and heuristic approaches already available for solving (1). However, SCP is known to be NP-hard, and thus it may be wise to explore and exploit the particular structure of subclasses of covering problems to This comment refers to the invited paper available at doi:10.1007/s11750-015-0395-7. BEmilio Carrizosa [email protected]; [email protected] 1Instituto de Matemáticas de la Universidad de Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain 123 648 E. Carrizosa devise more efficient algorithms. This is the approach successfully followed in this paper for an interesting class of SCPs, in which the sets Vof users and Pof potential facilities are the vertices of an undirected capacitated network, and coverage is not modeled by shortest-path distances, but by maximal flows. The SCP model above correponds to single cover, in which each user has to be covered by at least one vertex in the cover. This paper also addresses multiple cover problems, which, instead of the SCP, are linked to the so-called cooperative covering models, e.g. Berman et al. (2011). In several real-world contexts, coverage, either single or multiple, is more related with the ability to send a high flow from the source to the users rather than to the shortest-path source-user distance. As succinctly described in this paper, such modeling approach is relevant in different fields, such as evacuation planning, logistics, transportation or multimedia networks design and control. I would add Social Networks to the list. Indeed, several indices have been proposed to measure how central an individual is within a social network. Traditional measures, such as the so-called degree or closeness centrality, identify the centrality of an individual as the extent he is close to the remaining individuals in the social network. In the last decade, however, alternative centrality measures have been suggested, in which the centrality of an individual is related with the flow (e.g. of information) emanating from him that can reach the remaining individuals, e.g. Borgatti (2005); extending naturally the concept of flow centrality of an individual to flow centrality of a group, as in Everett and Borgatti (1999), finding the minimum-cardinality set of individuals in a social network with a given flow-centrality value amounts to finding an optimal single cover on a network, either static or dynamic depending on the way flow moves are modeled. The authors claim that source location problems deserve much more attention than they have received in the past. I agree. With this interesting paper, the authors manage to draw the readers attention to a rather unexplored class of optimization problems with important technical challenges and timely potential applications. Relevant advances on the state of the art are also achieved in this paper. These include, for single cover static problems, a primal greedy algorithm and a new and elegant validity proof of the dual greedy algorithm of Tamura et al. based on the analysis of the matroidal structure of the problem. For plural cover static problems on trees, sophisticated linear-time and pseudopolynomial-time algorithms are derived for non-simultaneous and simultaneous flow, respectively. For the, in my view, more interesting and challenging case of dynamic single covers, complexity results (NP-hardness) are derived, and particular classes of networks are identified for which the problem becomes polynomially solvable. How to exploit algorithmically the structure of the matrix Ain (1) for dynamic single cover problems in general undirected networks remains an open relevant problem. The problems addressed in the paper, as members of the class of flow location problems, combine two ingredients in Combinatorial Optimization, namely, flow problems, either static or dynamic, and (difficult) discrete location problems, thus remaining within the field of Discrete Optimization. As a complement to the discussion of possible extensions presented in the paper, I would add two for the dynamic single cover problem which would make the problem even more challenging since it would add a Continuous Optimization dimension. First, one can allow sources to be located along 123 Comments on: Static and dynamic source locations... 649 the edges, and not only at vertices of the network. The identification of a finite dominating set for the uniform cost case is not, at least at first glance, straightforward. Second, one can also assume that users are distributed along the edges of the network, as e.g. in Blanquero and Carrizosa (2013) for median problems and Blanquero et al. (2014) for covering problems. Since the much easier problems discussed in Blanquero and Carrizosa (2013) and Blanquero et al. (2014) call for the use of nonlinear mixed integer programming tools, it is expected that this source location problem will be, at least, as hard. In summary, this valuable piece of research contains interesting results on important flow location problems. The authors of this stimulating paper have left the door open for further developments, both from a theoretical and an algorithmic perspective, as well as extensions, mainly in the dynamic case. Acknowledgments Emilio Carrizosa acknowledges the support of research projects MTM2012-36163, Spain, and P11-FQM-7603, Junta de Andalucía, both with EU ERD Funds. References Blanquero R, Carrizosa E (2013) Solving the median problem with continuous demand on a network. Comput Optim Appl 56:723–734 Blanquero R, Carrizosa E, Tóth BG (2014) Maximal covering location problems on networks with regional demand. http://optimization-online.org/DB_HTML/2014/09/4553.html. Accessed 1 Sept 2015 Berman O, Drezner Z, Krass D (2011) Discrete cooperative covering problems. J Oper Res Soc 62:2002– 2012 Borgatti SP (2005) Centrality and network flow. Soc Netw 27:55–71 Everett MG, Borgatti SP (1999) The centrality of groups and classes. J Math Soc 23:181–201 García S, Marín A (2015) Covering location problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer, New York, pp 93–114 123