Bounded variation in binary sequences

When addressing optimal control problems with binary switches varying over time, it often arises as a subproblem to optimize a linear function over the set of binary vectors of a given finite length satisfying certain practical constraints, such as a minimum dwell time or a bound on the number of switchings over the entire time … Read more

An oracle-based framework for robust combinatorial optimization

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

A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization

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

On the Stochastic Vehicle Routing Problem with time windows, correlated travel times, and time dependency

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

The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective

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

An Active Set Algorithm for Robust Combinatorial Optimization Based on Separation Oracles

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

Convex optimization under combinatorial sparsity constraints

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

Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

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

SDP-based Branch-and-Bound for Non-convex Quadratic Integer Optimization

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

Reliable single allocation hub location problem under hub breakdowns

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