In the field of robust optimization uncertain data is modeled by uncertainty sets, i.e. sets which contain all relevant outcomes of the uncertain parameters. The complexity of the related robust problem depends strongly on the shape of the uncertainty set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper we … Read more
We consider minimizing a conic quadratic objective over a polyhedron. Such problems arise in parametric value-at-risk minimization, portfolio optimization, and robust optimization with ellipsoidal objective uncertainty; and they can be solved by polynomial interior point algorithms for conic quadratic optimization. However, interior point algorithms are not well-suited for branch-and-bound algorithms for the discrete counterparts of … Read more
This paper contemplates the use of robust optimization as a framework for addressing problems that involve endogenous uncertainty, i.e., uncertainty that is affected by the decision maker’s strategy. To that end, we extend generic polyhedral uncertainty sets typically considered in robust optimization into sets that depend on the actual decisions. We present the derivation of … Read more
We study two-stage robust optimization problems with mixed discrete-continuous decisions in both stages. Despite their broad range of applications, these problems pose two fundamental challenges: (i) they constitute infinite-dimensional problems that require a finite-dimensional approximation, and (ii) the presence of discrete recourse decisions typically prohibits duality-based solution schemes. We address the first challenge by studying … Read more
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming … Read more
We propose piecewise linear kernel-based support vector clustering (SVC) as a new approach tailored to data-driven robust optimization. By solving a quadratic program, the distributional geometry of massive uncertain data can be effectively captured as a compact convex uncertainty set, which considerably reduces conservatism of robust optimization problems. The induced robust counterpart problem retains the … Read more
We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. In particular, we show how to reformulate the support functions of uncertainty sets represented in terms of matrix norms and cones. Our … Read more
In this paper, we study multi-period vehicle routing problems where the aim is to determine a minimum cost visit schedule and associated routing plan for each period using capacity-constrained vehicles. In our setting, we allow for customer service requests that are received dynamically over the planning horizon. In order to guarantee the generation of routing … Read more
This paper presents a minimization method for Lipschitz continuous, piecewise smooth objective functions based on algorithmic differentiation (AD). We assume that all nondifferentiabilities are caused by abs(), min(), and max(). The optimization method generates successively piecewise linearizations in abs-normal form and solves these local subproblems by exploiting the resulting kink structure. Both, the generation of … Read more
We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertismas and Sim (2003). We also study the … Read more