Christoph Buchheim We investigate a robust approach for solving the Capacitated Vehicle Routing Problem (CVRP) with uncertain travel times. It is based on the concept of K-adaptability, which allows to calculate a set of k feasible solutions in a preprocessing phase before the scenario is revealed. Once a scenario occurs, the corresponding best solution may be picked … Read more
We present a coordinate ascent method for a class of semidefinite programming problems that arise in non-convex quadratic integer optimization. These semidefinite programs are characterized by a small total number of active constraints and by low-rank constraint matrices. We exploit this special structure by solving the dual problem, using a barrier method in combination with … Read more
In this paper we consider an extended version of the classical capacitated single allocation hub location problem in which the size of the hubs must be chosen from a finite and discrete set of allowable capacities. We develop a Lagrangian relaxation approach that exploits the problem structure and decomposes the problem into a set of … Read more
We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness … Read more
We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select … Read more
Optimal control problems (OCP) containing both integrality and partial differential equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, it results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we … Read more
In this paper, we address a new version of the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) in which transportation costs on each edge are given by piecewise constant cost functions. In the classical USApHMP, transportation costs are modelled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is … Read more
We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. We address this class of convex mixed-integer minimization problems … Read more
The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min-max-min problem. In this paper, we consider the case where no first stage variables exist and propose to … Read more
We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between … Read more