Christina Büsing

Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

  • Christina Büsing
  • Timo Gersing
  • Arie M.C.A. Koster
    • Categories 0-1 Programming, Polyhedra, Robust Optimization Tags , , , ,

    Robust combinatorial optimization with budget uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when … Read more

    Multithread Interval Scheduling with Flexible Machine Availabilities: Complexity and Efficient Algorithms

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Krabs
  • Tobias Mömke
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more

    Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints

  • SabrinaSchmitz
  • Christina Büsing
    • Categories Robust Optimization Tags , , , ,

    In this paper, we study a robust two-stage concept of combinatorial optimization problems under discrete demand uncertainty. Combinatorial optimization problems are based on a finite set of elements for which we decide whether they are part of a solution. We divide the elements into two types, the so-called fixed and free elements. In a first … Read more

    A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty

  • Christina Büsing
  • Timo Gersing
  • Arie M.C.A. Koster
    • Categories 0-1 Programming, Branch and Cut Algorithms, Robust Optimization Tags , , , ,

    Since its introduction in the early 2000s, robust optimization with budget uncertainty has received a lot of attention. This is due to the intuitive construction of the uncertainty sets and the existence of a compact robust reformulation for (mixed-integer) linear programs. However, despite its compactness, the reformulation performs poorly when solving robust integer problems due … Read more

    Efficient Algorithms for Multi-Threaded Interval Scheduling with Machine Availabilities

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Krabs
  • Tobias Mömke
    • Categories Scheduling Tags ,

    In the known Interval Scheduling Problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specific time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more

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

  • Christina Büsing
  • Sigrid Knust
  • Tabea Krabs
    • 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

    Robust Optimal Aiming Strategies in Concentrated Solar Tower Power Plants

  • Christina Büsing
  • Pascal Richter
  • Jeff Cumpston
  • Fynn Kepp
  • Sascha Kuhnke
    • Categories Robust Optimization Tags , , , ,

    A concentrated solar tower power plant consists of a receiver mounted atop of a central tower and a field of movable mirrors called heliostats. The heliostats concentrate solar radiation onto the receiver where a fluid is heated to produce electricity in a conventional thermodynamic cycle. Aiming strategies are used to assign each heliostat to an … Read more

    Globalized Robust Optimization with Gamma-Uncertainties

  • Andreas Bärmann
  • Christina Büsing
  • Frauke Liers
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Robust Optimization Tags , , ,

    Globalized robust optimization has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection depending on the distance of the realized scenario from the predefined uncertainty set. In this work, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its … Read more

    Planning Out-of-Hours Services for Pharmacies

  • Christina Büsing
  • Arie M.C.A. Koster
  • Timo Gersing
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Scheduling Tags , , , , ,

    The supply of pharmaceuticals is one important factor in a functioning health care system. In the German health care system, the chambers of pharmacists are legally obliged to ensure that every resident can find an open pharmacy at any day and night time within an appropriate distance. To that end, the chambers of pharmacists create … Read more

    Minimum Color-Degree Perfect b -Matchings

  • Mariia Anapolska
  • Christina Büsing
  • Martin Comis
  • Tabea Krabs
    • Categories Dynamic Programming, Graphs and Matroids Tags , , , , ,

    The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more