Targeted marketing strategies are of significant interest in the smartapp economy. Typically, one seeks to identify individuals to strategically target in a social network so that the network is influenced at a minimal cost. In many practical settings, the effects of direct influence predominate, leading to the positive influence dominating set with partial payments (PIDS-PP) problem that we discuss in this paper. The PIDS-PP problem is NP-complete because it generalizes the dominating set problem. We discuss several mixed integer programming formulations for the PIDS-PP problem. First, we describe two compact formulations on the payment space. We then develop a stronger compact extended formulation. We show that when the underlying graph is a tree, this compact extended formulation provides integral solutions for the node selection variables. In conjunction, we describe a polynomial-time dynamic programming algorithm for the PIDS-PP problem on trees. We project the compact extended formulation onto the payment space, providing an equivalently strong formulation that has exponentially many constraints. We present a polynomial time algorithm to solve the associated separation problem. Our computational experience on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) demonstrates the efficacy of our strongest payment space formulation. It finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality. Summary of Contribution: The study of influence propagation is important in a number of applications including marketing, epidemiology, and healthcare. Typically, in these problems, one seeks to identify individuals to strategically target in a social network so that the entire network is influenced at a minimal cost. With the ease of tracking consumers in the smartapp economy, the scope and nature of these problems have become larger. Consequently, there is considerable interest across multiple research communities in computationally solving large-scale influence maximization problems, which thus represent significant opportunities for the development of operations research–based methods and analysis in this interface. This paper introduces the positive influence dominating set with partial payments (PIDS-PP) problem, an influence maximization problem where the effects of direct influence predominate, and it is possible to make partial payments to nodes that are not targeted. The paper focuses on model development to solve large-scale PIDS-PP problems. To this end, starting from an initial base optimization model, it uses several operations research model strengthening techniques to develop two equivalent models that have strong computational performance (and can be theoretically shown to be the best model for trees). Computational experiments on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) attest to the efficacy of the best model, which finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality.

Motivated by applications arising on social networks, we study a generalization of the celebrated dominating set problem called the Positive Influence Dominating Set (PIDS). Given a graph G with a set V of nodes and a set E of edges, each node i in V has a weight bi, and a threshold requirement gi. We seek a minimum weight subset T of V, so that every node i not in T is adjacent to at least gi members of T. When gi is one for all nodes, we obtain the weighted dominating set problem. First, we propose a strong and compact extended formulation for the PIDS problem. We then project the extended formulation onto the space of the natural node-selection variables to obtain an equivalent formulation with an exponential number of valid inequalities. Restricting our attention to trees, we show that the extended formulation is the strongest possible formulation, and its projection (onto the space of the node variables) gives a complete description of the PIDS polytope on trees. We derive the necessary and sufficient facet-dening conditions for the valid inequalities in the projection and discuss their polynomial time separation. We embed this (exponential size) formulation in a branch-and-cut framework and conduct computational experiments using real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. On a test-bed of 100 real-world graph instances, our approach finds solutions that are on average 0.2% from optimality and solves 51 out of the 100 instances to optimality. Summary of Contribution: In influence maximization problems, a decision maker wants to target individuals strategically to cause a cascade at a minimum cost over a social network. These problems have attracted significant attention as their applications can be found in many different domains including epidemiology, healthcare, marketing, and politics. However, computationally solving large-scale influence maximization problems to near optimality remains a substantial challenge for the computing community, which thus represent significant opportunities for the development of operations-research based models, algorithms, and analysis in this interface. This paper studies the positive influence dominating set (PIDS) problem, an influence maximization problem on social networks that generalizes the celebrated dominating set problem. It focuses on developing exact methods for solving large instances to near optimality. In other words, the approach results in strong bounds, which then provide meaningful comparative benchmarks for heuristic approaches. The paper first shows that straightforward generalizations of well-known formulations for the dominating set problem do not yield strong (i.e., computationally viable) formulations for the PIDS problem. It then strengthens these formulations by proposing a compact extended formulation and derives its projection onto the space on the natural node-selection variables, resulting in two equivalent (stronger) formulations for the PIDS problem. The projected formulation on the natural node-variables contains a new class of valid inequalities that are shown to be facet-defining for the PIDS problem. These theoretical results are complemented by in-depth computational experiments using a branch-and-cut framework, on a testbed of 100 real-world graph instances, with up to approximately 2.5 million nodes and 8 million edges. They demonstrate the effectiveness of the proposed formulation in solving large scale problems finding solutions that are on average 0.2% from optimality and solving 51 of the 100 instances to optimality.

Abstract There is significant interest in understanding the dynamics of influence diffusion on a social network. The weighted target set selection (WTSS) problem is a fundamental viral marketing problem arising on social networks. In this problem, the goal is to select a set of influential nodes to target (e.g., for promoting a new product) that can influence the rest of the network. The WTSS problem is APX‐hard. With the goal of generating insights to solve the WTSS problem on arbitrary graphs, we study in this paper the WTSS problem on trees and cycles. For trees, we propose a linear‐time dynamic programming algorithm and present a tight and compact extended formulation. Furthermore, we project the extended formulation onto the space of the natural node variables yielding the polytope of the WTSS problem on trees. This projection leads to an exponentially sized set of valid inequalities whose polynomial‐time separation is also discussed. Next, we focus on cycles: we describe a linear‐time algorithm and present the complete description of the polytope for the WTSS problem on cycles. Finally, we describe how these formulations can be applied to arbitrary graphs.

Viral-marketing strategies are of significant interest in the online economy. Roughly, in these problems, one seeks to identify which individuals to strategically target in a social network so that a given proportion of the network is influenced at minimum cost. Earlier literature has focused primarily on problems where a fixed inducement is provided to those targeted. In contrast, resembling the practical viral-marketing setting, we consider this problem where one is allowed to "partially influence" (by the use of monetary inducements) those selected for targeting. We thus focus on the "least-cost influence problem (LCIP)": an influence-maximization problem where the goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentive) required to influence a given proportion of the population. Motivated by the desire to develop a better understanding of fundamental problems in social-network analytics, we seek to develop (exact) optimization approaches for the LCIP. Our paper makes several contributions, including (i) showing that the problem is NP-complete in general as well as under a wide variety of special conditions; (ii) providing an influence greedy algorithm to solve the problem polynomially on trees, where we require 100% adoption and all neighbors exert equal influence on a node; and (iii) a totally unimodular formulation for this tree case.

Abstract This paper studies a problem in the online targeted marketing setting called the least cost influence problem (LCIP) that is known to be NP‐hard. The goal is to find the minimum total amount of inducements (individuals to target and associated tailored incentives) required to influence a given population. We develop a branch‐and‐cut approach to solve this LCIP on arbitrary graphs. We build upon Günneç et al.'s novel totally unimodular (TU) formulation for the LCIP on trees. The key observation in applying this TU formulation to arbitrary graphs is to enforce an exponential set of inequalities that ensure the influence propagation network is acyclic. We also design several enhancements to the branch‐and‐cut procedure that improve its performance. We provide a large set of computational experiments on real‐world graphs with up to 155 000 nodes and 327 000 edges that demonstrates the efficacy of the branch‐and‐cut approach. This branch‐and‐cut approach finds solutions that are on average 1.87% away from optimality based on a test‐bed of 160 real‐world graph instances. We also develop a heuristic that prioritizes nodes that receive low influence from their peers. This heuristic works particularly well on arbitrary graphs, providing solutions that are on average 1.99% away from optimality. Finally, we observe that partial incentives can result in significant cost savings, over 55% on average, compared to the setting where partial incentives are not allowed.

The sample average approximation (SAA) approach is a widely used technique, based on Monte‐Carlo simulation, often applied to large‐scale stochastic optimization problems. In this approach, a set of sample average problems with multiple copies of sampled scenarios are generated and solved exactly. In other words, there is an implicit assumption that the sample average problems are solvable to optimality. In some instances, however, the sample average problems might be NP‐hard problems, often difficult or impractical to solve to optimality. In this article, we broaden the scope of the SAA approach and show that even without solving the sample problems to optimality, by combining a heuristic and a lower bounding approach, high‐quality solutions with tight confidence bounds on the optimal solution value can be obtained. We demonstrate this “inexact SAA approach” on two problems. First, we apply it to the Stochastic Connected Facility Location (SConFL) problem, the motivating application for this article, that arises in the design of telecommunications networks. As an additional application, we also use it for the Stochastic Uncapacitated Facility Location (SUFL) problem. Our computational results demonstrate the effectiveness of the inexact SAA approach. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 19–33 2017

We consider a network design application that is modeled as the two-level network design problem under uncertainty. In this problem, one of the two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. The decision maker is confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated with the possible realizations of primary customers is available. The network is built in two stages. In the first stage the network topology must be determined. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded, if necessary to primary technology, but at higher recovery cost. The overall goal then is to build a “recoverable robust” spanning tree in the first stage that serves all customers by at least the lower level technology, and that minimizes the first-stage installation cost plus the worst-case cost needed to upgrade the edges of the selected tree, so that the primary customers of each scenario can be served using the primary technology. We discuss the complexity of the problem, provide mixed-integer programming models, and develop a branch-and-cut algorithm to solve it. Our extensive computational experiments demonstrate the efficacy of our approach.

In an optical network a signal can only travel a maximum distance dmaxbefore its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. In this paper we introduce the generalized regenerator location problem (GRLP) in which we are given a set S of nodes that corresponds to candidate locations for regenerators, and a set T of nodes that must communicate with each other. If S = T = N, we obtain the regenerator location problem (RLP), which we have studied previously and shown to be NP-complete. Our solution procedure to the RLP is based on its equivalence to the maximum leaf spanning tree problem (MLSTP). Unfortunately, this equivalence does not apply to the GRLP, nor do the procedures developed previously for the RLP. To solve the GRLP, we propose reduction procedures, two construction heuristics, and a local search procedure that we collectively refer to as a heuristic framework. We also establish a correspondence between the (node-weighted) directed Steiner forest problem and the GRLP. Using this fact, we provide several ways to derive natural and extended integer programming (IP) and mixed-integer programming (MIP) models for the GRLP and compare the strength of these models. Using the strongest model derived on the natural node selection variables we develop a branch-and-cut approach to solve the problem to optimality. The results indicate that the exact approach can easily solve instances with up to 200 nodes to optimality, whereas the heuristic framework is a high-quality approach for solving large-scale instances.

The reload cost spanning tree problem (RCSTP) is an NP‐hard problem, where we are given a set of nonnegative pairwise demands between nodes, each edge is colored and a reload cost is incurred when a color change occurs on the path between a pair of demand nodes. The goal is to find a spanning tree with minimum total reload cost. We propose a tree–nontree edge swap neighborhood for the RCSTP and an efficient way to search this neighborhood using preprocessed information. We then embed this edge swap neighborhood within a local search and a tabu search heuristic. We also discuss an initial solution procedure that is used by the local search and tabu search heuristic in a multistart framework. On a test set of 630 instances (that includes benchmark instances from Gamvros et al. [6]), the local search solution improves upon the initial solution in 416 instances by an average of 23.62%, and the tabu search solution improves upon the local search solution in 364 instances by an average of 35.79%. Out of 495 test instances from this set that we know the optimal solutions for, the initial solution is optimal 113 times, the local search solution is optimal 224 times, and the tabu search solution is optimal 481 times. On a second set of benchmark instances from Khalil and Singh [9], the tabu search solution improves upon the best known solution in 32 out of 44 instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 380–394 2015

We study the power of fractional allocations of resources to maximize our influence in a network. This work extends in a natural way the well-studied model by Kleinberg, Kempe, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no chance to apply intermediate levels of influence. This model captures some settings precisely, such as exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away a single free product.

Given a graph G = (N, E), the covering salesman problem (CSP) is to identify the minimum length tour “covering” all the nodes. More specifically, it seeks the minimum-length tour visiting a subset of the nodes in N such that each node i not on the tour is within a predetermined distance di of a node on the tour. In this paper, we define and develop a generalized version of the CSP, and we refer to it as the generalized covering salesman problem (GCSP). Here, each node i needs to be covered at least ki times, and there is a cost associated with visiting each node. We seek a minimum-cost tour such that each node i is covered at least ki times by the tour. We define three variants of the GCSP. In the first case, each node can be visited by the tour at most once. In the second case, visiting a node i more than once is possible, but an overnight stay is not allowed (i.e., to revisit a node i, the tour has to visit another node before it can return to i). Finally, in the third case, the tour can visit each node more than once consecutively. In this paper, we develop two local search heuristics to find high-quality solutions to the three GCSP variants. To test the proposed algorithms, we generated data sets based on traveling salesman problem library instances. Because the CSP and the generalized traveling salesman problem are special cases of the GCSP, we tested our heuristics on both of those problems as well. Overall, the results show that our proposed heuristics find high-quality solutions very rapidly.

Abstract In this article, we consider the notion of “reload costs” in network design. Reload costs occur naturally in many different settings including telecommunication networks using diverse technologies. However, reload costs have not been studied extensively in the literature. Given that reload costs occur naturally in many settings, we are motivated by the desire to develop “good” models for network design problems involving reload costs. In this article, and as a first step in this direction, we propose and discuss the reload cost spanning tree problem (RCSTP). We show that the RCSTP is NP‐complete. We discuss several ways of modeling network design problems with reload costs. These involve models that expand the original graph significantly—to a directed line graph and a colored graph—to model reload costs. We show that the different modeling approaches lead to models with the same linear programming bound. We then discuss several variations of reload cost spanning tree and network design problems, and discuss both their complexity and models for these variations. To assess the effectiveness of the proposed models to solve RCSTP instances, we present results taken from instances with up to 50 nodes, 300 edges, and nine technologies for several variations of the problem. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

The second generation of optical networks with wavelength division multiplexing (WDM) is based on the notion of two layer networks, where the first layer represents a logical topology defined over the physical topology of optical fibers and the second layer represents multiple traffic requests combined (multiplexed) over the paths established in the logical topology. Because the design of both of these layers is challenging by itself, researchers have mainly focused on solving these problems either independently or in a sequential fashion. In this paper, we look at the WDM optical network design problem with nonbifurcated traffic flows and propose an exact branch-and-price procedure that simultaneously solves logical topology design and traffic routing over the established logical topology. The unique feature of the proposed algorithm is that it works with a row-incomplete mathematical formulation and two types of variables that exponentially grow in number with the problem size. We discuss computational issues related to the use of this procedure and propose two approximate branch-and-price procedures that can be used to obtain lower and upper bounds for this problem. Finally, we present the results of our computational experiments for two design objectives and alternative optical network settings.

The connected facility location (ConFL) problem arises in a number of applications that relate to the design of telecommunication networks as well as data distribution and management problems on networks. It combines features of the uncapacitated facility location problem with the Steiner tree problem and is known to be NP-complete. In this setting, we wish to install a set of facilities on a communication network and assign customers to the installed facilities. In addition, the set of selected facilities needs to be connected by a Steiner tree. In this paper, we propose a dual-based local search heuristic that combines dual ascent and local search, which together yield strong lower and upper bounds to the optimal solution. Our procedure is applied to a slightly more general version of the ConFL problem that embraces a family of four different problems—the Steiner tree-star problem, the general Steiner tree-star problem, the ConFL problem, and the rent-or-buy problem—that combine facility location decisions with connectivity requirements. Consequently, our solution methodology successfully applies to all of them. We discuss a wide range of computational experiments that indicate that our heuristic is a very effective procedure that finds high-quality solutions very rapidly.

Abstract In this article, we introduce the regenerator location problem (RLP), which deals with a constraint on the geographical extent of transmission in optical networks. Specifically, an optical signal can only travel a maximum distance of dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. We show that the RLP is NP‐Complete. We then devise three heuristics for the RLP. We show how to represent the RLP as a max leaf spanning tree problem (MLSTP) on a transformed graph. Using this fact, we model the RLP as a Steiner arborescence problem (SAP) with a unit degree constraint on the root node. We also devise a branch‐and‐cut procedure to the directed cut formulation for the SAP problem. In our computational results over 740 test instances, the heuristic procedures obtained the optimal solution in 454 instances, whereas the branch‐and‐cut procedure obtained the optimal solution in 536 instances. These results indicate the quality of the heuristic solutions are quite good, and the branch‐and‐cut approach is viable for the optimal solution of problems with up to 100 nodes. Our approaches are also directly applicable to the MLSTP indicating that both the heuristics and branch‐and‐cut approach are viable options for the MLSTP. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

In this paper, we consider the multilevel capacitated minimum spanning tree (MLCMST) problem, a generalization of the well-known capacitated minimum spanning tree (CMST) problem, that allows for multiple facility types in the design of the network. We develop two flow-based mixed integer programming formulations that can be used to find tight lower bounds for MLCMST problems with up to 150 nodes. We also develop several heuristic procedures for the MLCMST problem. First, we present a savings-based heuristic. Next, we develop local search algorithms that use exponential size, node-based, cyclic and path exchange neighborhoods. Finally, we develop a hybrid genetic algorithm for the MLCMST. Extensive computational results on a large set of test problems indicate that the genetic algorithm is robust and, among the heuristics, generates the best solutions. They are typically 6.09% from the lower bound and 0.25% from the optimal solution value.

The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, and even finding a constant factor approximation algorithm is NP-hard. In this paper, we present two heuristic search approaches for the GMST problem: local search and a genetic algorithm. Our computational experiments show that these heuristics rapidly provide high-quality solutions for the GMST and outperform some previously suggested heuristics for the problem. In our computational tests on 211 test problems (including 169 problems from the TSPLIB set), our local-search heuristic found the optimal solution in 179 instances and our genetic-algorithm procedure found the optimal solution in 185 instances (out of the 211 instances, the optimal solution is known in 187 instances). Further, on each of the 19 unsolved instances from TSPLIB, both our local-search heuristic and genetic-algorithm procedure improved upon the best previously known solution.

The network design problem with connectivity requirements (NDC) includes as special cases a wide variety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and survivable network design problems. We develop strong formulations for two versions of the edge-connectivity NDC problem: unitary problems requiring connected network designs, and nonunitary problems permitting nonconnected networks as solutions. We (1) present a new directed formulation for the unitary NDC problem that is stronger than a natural undirected formulation; (2) project out two classes of valid inequalities—partition inequalities, and combinatorial design inequalities—that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem; and (3) show how to strengthen and direct nonunitary problems. Our results provide a unifying framework for strengthening formulations for NDC problems, and demonstrate the power of flow-based formulations for network design problems with connectivity requirements. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 61–79 2005

Abstract Network survivability is a critical issue for modern fiber‐optic telecommunication networks. Networks with alternate routes between pairs of nodes permit users to communicate in the face of equipment failure. In this paper, we consider the following low‐connectivity network design (LCND) problem: Given a graph G = (N, E) and a connectivity requirement di ∈ {0, 1, 2} for each node and edge costs ce for each edge e ∈ E, design a minimum‐cost network that contains at least dst = min{ds, dt} disjoint paths between nodes s and t. We present linear‐time algorithms for both node‐ and edge‐connectivity versions of the problem on series‐parallel graphs. Due to the sparsity of telecommunications networks, this algorithm can be applied to obtain partial solutions and decompositions that may be embedded in a heuristic solution procedure as well as exact solution algorithms for the problem on general graphs. © 2004 Wiley Periodicals, Inc.

In dealing with a very large data set, it might be impractical to construct a decision tree using all of the points. Even when it is possible, this might not be the best way to utilize the data. As an alternative, subsets of the original data set can be extracted, a tree can be constructed on each subset, and then parts of individual trees can be combined in a smart way to produce an improved final set of feasible trees or a final tree. In this paper, we take trees generated by a commercial decision tree package, namely, C4.5, and allow them to crossover and mutate (using a genetic algorithm) for a number of generations in order to yield trees of better quality. We conduct a computational study of our approach using a real-life marketing data set. In this study, we divide the data set into training, scoring, and test sets, and find that our approach produces uniformly high-quality decision trees. In addition, we investigate the impact of scaling and demonstrate that our approach can be used effectively on very large data sets.