The influence coverage optimization problem

We introduce the Influence Coverage Optimization Problem (ICOP), which is an influence maximization problem where the activation of nodes also depends on their location on the plane. Specifically, the ICOP assumes that there is a network where nodes become active (i.e., influenced) either by the influence they receive from interactions with active in-neighbors or by entering the coverage area of a physical ad or a Geo-fence. The objective is to locate a fixed number of ads or Geo-fences and modify the network influence rates to minimize the network activation time. Assuming a Markovian influence model, we prove that the ICOP is NP-hard, and then we present mixed-integer programming formulations for three different types of coverage modes. A reformulation of the non-linear “big-M” constraints, two types of valid cuts, and a fast heuristic based on the k-means algorithm are used as enhancements that facilitate solving the ICOP via an Iterative Decomposition Branch-and-Cut (IDBC) algorithm. In addition, we present an alternative discrete formulation of the ICOP using critical intersection points. Several experiments under various parameter configurations across instances with more than a hundred nodes and thousand arcs are conducted, showing the IDBC’s capability to provide optimal solutions within seconds or minutes for most instances. Moreover, the experiments reveal that the ICOP can significantly outperform a Geo-fence coverage model that does not consider network interactions to make location decisions.