In recent years, the exponential growth of package volumes has posed significant challenges for logistics networks, particularly in the realm of last-mile delivery. To mitigate costs while upholding service and delivery commitments, companies are increasingly investigating autonomous assisted delivery as a viable solution. In this paper, we study the Capacitated Autonomous Vehicle Assisted Delivery Problem, where an autonomous vehicle works in conjunction with a delivery person. The autonomous vehicle drops off the delivery person at designated locations, and the delivery person completes the deliveries (with a capacity constraint) on foot to the final addresses. Once the deliveries are completed, the vehicle picks up the delivery person and travels to the next reloading point. The goal is to decide on a route to serve all customers while minimizing the route completion time. We introduce an integer programming formulation with exponentially many variables and develop a branch-and-price approach. For generating promising columns, we present a tailored pulse algorithm to solve the pricing problem. Furthermore, by leveraging the structural properties of optimal solutions, we carefully design algorithmic enhancements, valid inequalities, and preprocessing steps to improve computational tractability. By conducting computational experiments based on instances derived from real-world data, we demonstrate the positive impact of these components. More importantly, we provide optimal certificates for 426 out of the 450 instances documented in the literature. Among the 100 instances in which driving could be slower than walking, we report solutions for the 40 largest instances for the first time. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0177 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0177 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

When designing a patrol route, it is often necessary to pay more attention to locations with high crime rates. In this paper, we study a patrol routing problem for a fleet of patrol cars patrolling a region with a high-crime neighborhood (HCN) consisting of multiple hot spots. Considering the disorder and chaos in the HCN, at least one patrol car is required in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize, and the prize is collected if a patrol car visits the location. Our objective is to maximize the sum of prizes collected by the patrol cars, obeying all operational requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. The global approach consists of finding the routing solution for all patrol cars with a single integer programming (IP) formulation. The partition approach involves first partitioning the region geographically and solving the routing problem in each subregion with two IP formulations. Next, we strengthen the partition approach by developing a column generation (CG) approach in which the initial columns of the CG approach are the solutions generated from the partition approach. We conduct a detailed computational case study using instances based on real crime data from Montgomery County, Maryland. To further understand the computational tractability of our solution approaches, we also perform a sensitivity analysis using synthetic instances under various scenarios. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0192 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0192 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

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.