Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

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

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

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

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

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

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

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

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

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

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