Christoph Buchheim We investigate the problem of optimizing a linear objective function over the set of all binary vectors of length n with bounded variation, where the latter is defined as the number of pairs of consecutive entries with different value. This problem arises naturally in many applications, e.g., in unit commitment problems or when discretizing binary … Read more
We propose a general solution approach for min-max-robust counterparts of combinatorial optimization problems with uncertain linear objectives. We focus on the discrete scenario case, but our approach can be extended to other types of uncertainty sets such as polytopes or ellipsoids. Concerning the underlying certain problem,the algorithm is entirely oracle-based, i.e., our approach only requires … Read more
For many classical combinatorial optimization problems such as, e.g., the shortest path problem or the spanning tree problem, the robust counterpart under general discrete, polytopal, or ellipsoidal uncertainty is known to be intractable. This implies that any algorithm solving the robust counterpart that can access the underlying certain problem only by an optimization oracle has … Read more
Most state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and- Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the fi rst approach to approximately check feasibility in the Stochastic Vehicle Routing Problem with time windows, where travel times are correlated and depend on the time of … Read more
We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full … Read more
We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the … Read more
We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in … Read more
In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more
Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed [11], which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST … Read more
The design of hub-and-spoke transport networks is a strategic planning problem, as the choice of hub locations has to remain unchanged for long time periods. However, strikes, disasters or traffic breakdown can lead to the unavailability of a hub for a short period of time. Therefore it is important to consider such events already in … Read more