Combinatorial Optimization

Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems

  • Thorsten Koch
  • Daniel Rehfeldt
    • Categories Combinatorial Optimization Tags ,

    This article introduces new reduction techniques for the Steiner tree problem in graphs (SPG) and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. In particular, we introduce a generalization of the Steiner bottleneck distance—the arguably most important reduction concept for SPG. While … Read more

    Branch-and-Refine for Solving Time-Dependent Problems

  • Armin Fügenschuh
  • Fabian Gnegel
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , ,

    One of the standard approaches for solving time-dependent discrete optimization problems, such as the traveling salesman problem with time-windows or the shortest path problem with time-windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a … Read more

    An algorithm for the Microaggregation problem using Column Generation

  • Jordi Castro
  • Claudio Gentile
  • Enric Spagnolo-Arrizabalaga
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Combinatorial Optimization

    The field of Statistical Disclosure Control aims at reducing the risk of re-identification of an individual when disseminating data, and it is one of the main concerns of national statistical agencies. Operations Research (OR) techniques were widely used in the past for the protection of tabular data, but not for microdata (i.e., files of individuals … Read more

    Linear Programming and Community Detection

  • Alberto Del Pia
  • Aida Khajavirad
  • Dmitriy Kunisky
    • Categories 0-1 Programming, Polyhedra, Statistics Tags , , ,

    The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior … Read more

    Decomposition-based algorithms for the crew scheduling and routing problem in road restoration

  • Douglas Alem
  • Pedro Munari
  • Alfredo Moreno
    • Categories Branch and Cut Algorithms

    The crew scheduling and routing problem (CSRP) consists of determining the best route and schedule for a single crew to repair damaged nodes in a network affected by extreme events. The problem also involves the design of paths to connect a depot to demand nodes that become accessible only after the damaged nodes in these … Read more

    Submodular Function Minimization and Polarity

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories Polyhedra

    Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lov\’asz extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational … Read more

    A Bin Packing Problem with Mixing Constraints for Containerizing Items for Logistics Service Providers

  • Sajini Anand P S
  • Stefan Guericke
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Telecommunications

    Large logistics service providers often need to containerize and route thousands or millions of items per year. In practice, companies specify business rules of how to pack and transport items from their origin to destination. Handling and respecting those business rules manually is a complex and time-consuming task. We propose a variant of the variable … Read more

    One transfer per patient suffices: Structural insights about patient-to-room assignment

  • Christina Büsing
  • Sigrid Knust
  • Tabea Brandt
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    While many heuristics have been proposed for the problem of patient-to-room assignment (PRA) with a large variety of different practical constraints, a thorough investigation of the problem’s structure itself has been neglected so far. Therefore, in this paper, we present insights about the basic, underlying combinatorial problem of PRA. At first we consider the problem … Read more

    The Multi-Stop Station Location Problem

  • Miriam Ganz
  • Erik Mühmer
  • Felix J. L. Willamowski
    • Categories Approximation Algorithms, Network Optimization, Transportation Tags , , , ,

    We introduce the (directed) multi-stop station location problem. The goal is to install stations such that ordered (multi-)sets of stops can be traversed with respect to range restrictions that are reset whenever a station is visited. Applications arise in telecommunications and transportation, e.g., charging station placement problems. The problem generalizes several network optimization problems such … Read more

    K-Adaptability in stochastic optimization

  • Enrico Malaguti
  • Michele Monaci
  • Jonas Prünte
    • Categories Branch and Cut Algorithms, Stochastic Approaches, Stochastic Programming

    We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for the underlying problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realised scenario. This paradigm … Read more