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

Improved Handling of Uncertainty and Robustness in Set Covering Problems

This paper studies the emergency service facility location problem in an uncertain environment. The main focus is the integration of uncertainty regarding the covered area due to uncertain traveling times. Previous approaches only consider either probabilistic or fuzzy optimization to cope with uncertainty. However, in many real-world problems the required statistical parameters are not precisely … Read more

The Budgeted Minimum Cost Flow Problem with Unit Upgrading Cost

The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we … Read more

Robust Optimization under Multi-band Uncertainty – Part I: Theory

The classical single-band uncertainty model introduced by Bertsimas and Sim has represented a breakthrough in the development of tractable robust counterparts of Linear Programs. However, adopting a single deviation band may be too limitative in practice: in many real-world problems, observed deviations indeed present asymmetric distributions over asymmetric ranges, so that getting a higher modeling … Read more

Recoverable Robust Knapsack: the Discrete Scenario Case

Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach … Read more

Recoverable Robust Knapsacks: $\GammahBcScenarios

In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more