Markus Leitner

Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the … Read more

    The impact of passive social media viewers in influence maximization

  • Michael Kahr
  • Markus Leitner
  • Ivana Ljubić
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Marketing Tags , ,

    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 to trigger an information propagation cascade (in terms of active message forwarders) of expected maximum impact. Previously studied problems typically neglect that the probability that individuals passively … Read more

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

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the multi-depot split-delivery 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 small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the … Read more

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

  • Elena Fernandez
  • Markus Leitner
  • Ivana Ljubić
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Production and Logistics Tags , , , , , ,

    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

  • Evren Güney
  • Markus Leitner
  • Mario Ruthmair
  • Markus Sinnl
    • Categories Applications - OR and Management Sciences, Integer Programming, Stochastic Programming Tags , , ,

    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

  • Immanuel M. Bomze
  • Michael Kahr
  • Markus Leitner
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    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

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    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

  • Matteo Fischetti
  • Michael Kahr
  • Markus Leitner
  • Michele Monaci
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization Tags , ,

    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

  • Luís Gouveia
  • Martim Joyce-Moniz
  • Markus Leitner
    • Categories Cutting Plane Approaches, Network Optimization, Telecommunications

    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

  • Georg Brandstätter
  • Markus Leitner
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , , , ,

    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