Enormous global popularity of online social network sites has initiated numerous studies and methods investigating different aspects of their use, so some concepts from network-based studies in optimization theory can be used for research into online networks. In Gaji\’c (2014) are given a several new mixed integer linear programming formulations for first and second problem of exploration of online social networks introduced in Stanimirovi\’c and Mi\v{s}kovi\’c (2012). This paper introduces a new mixed integer linear programming formulation for remaining (third) problem. Numerical experiments show the performance of a commercial exact solver when applied to the proposed model. The new model is also compared with a model proposed in the literature using instances from single source capacitated facility location problem and randomly generated instances. The obtained results indicate that the proposed formulation clearly outperforms the existing formulation. Moreover, new formulation has small number of decision variables, so it is capable to find, by exact solver, upper and lower bounds on large-scale problem instances. The paper also noted and tried to correct some wrong considerations presented in the previous work.
Citation
Faculty of Technical Sciences, University of Novi Sad