The energy consumption of large-scale data centers or server clusters is expected to grow significantly in the next couple of years contributing to up to 13 percent of the worlwide energy demand in 2030. As the involved processing units require a disproportional amount of energy when they are idle, underutilized or overloaded, balancing the supply … Read more
Some popular heuristics for combinatorial optimisation start by constructing a feasible solution to a dual of the problem. We show that such dual-based heuristics can exhibit highly counter-intuitive behaviour. In particular, for some problem classes, solving the dual exactly invariably leads to much worse primal solutions than solving the dual with a simple greedy heuristic. … Read more
In this work we study binary two-stage robust optimization problems with objective uncertainty. The concept of two-stage robustness is tailored for problems under uncertainty which have two different kinds of decision variables, first-stage decisions which have to be made here-and-now and second-stage decisions which can be determined each time after an uncertain scenario occured. We … Read more
The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, … Read more
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
Team as a Service (TaaS) is a new outsourcing service that enables on-demand creation and management of distributed teams for fast growing companies. The companies that use the TaaS model form a team according to the needs of a given project and provide managerial service throughout. Motivated by this new application, we study the Team … Read more
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become … Read more
A need for an optimal solution for a given mathematical model is well known and many solution approaches have been developed to identify efficiently an optimal solution in a given situation. For example, one such class of mathematical models with industrial applications have been classified as mathematical programming models (MPM). The main idea behind these … Read more
The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization problems over a set $X \subseteq \{0,1\}^n$. In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in … Read more
Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more