Optimization Online


A new mixed integer linear programming formulation for one problem of exploration of online social networks

Aleksandra Petrovic (ap5309311***at***gmail.com)

Abstract: 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.

Keywords: Mixed integer linear programming; Location problems; Social networks; Combinatorial optimization

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Network Optimization

Category 3: Applications -- OR and Management Sciences (Marketing )

Citation: Faculty of Technical Sciences, University of Novi Sad

Download: [PDF]

Entry Submitted: 05/22/2014
Entry Accepted: 05/26/2014
Entry Last Modified: 10/13/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society