The impact of passive social media users in (competitive) influence maximization

A frequently studied problem in the context of digital marketing for online social networks is the influence maximization problem that seeks for an initial seed set of influencers that trigger an information propagation cascade (in terms of message-forwarding) of expected maximum impact. The studied problems typically neglect that the probability that individuals only view content … Read more

Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

We study the split-delivery multi-depot vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a comparably small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring … Read more

Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These … Read more

Large-scale Influence Maximization via Maximal Covering Location

Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based … Read more

Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more

Layered graph approaches for combinatorial optimization problems

Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more

Least cost influence propagation in (social) networks

Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept … Read more

Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints

The aim of Network Design Problem with Vulnerability Constraints (NDPVC), introduced by Gouveia and Leitner [EJOR, 2017], is to design survivable telecommunications networks that impose length bounds on the communication paths of each commodity pair, before and after the failure of any k links. This problem was proposed as an alternative to the Hop-Constrained Survivable … Read more

Location of charging stations in electric car sharing systems

Electric vehicles are a prime candidate for use within an urban car sharing system, both from an economic and environmental perspective. However, their relatively short range necessitates frequent and rather time-consuming recharging throughout the day. Thus, charging stations must be built throughout the system’s operational area where cars can be charged between uses. In this … Read more

Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand

In this article, we introduce and study a two-stage stochastic optimization problem suitable to solve strategic optimization problems of car-sharing systems that utilize electric cars. By combining the individual advantages of car-sharing and electric vehicles, such electric car-sharing systems may help to overcome future challenges related to pollution, congestion, or shortage of fossil fuels. A … Read more