robust optimization

Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra

  • Alper Atamturk
  • Andrés Gómez
    • Categories Quadratic Programming, Robust Optimization, Second-Order Cone Programming Tags ,

    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

    Robust Optimization for Decision-making under Endogenous Uncertainty

  • Chrysanthos E. Gounaris
  • Nikolaos Lappas
    • Categories Robust Optimization Tags , ,

    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

    K-Adaptability in Two-Stage Mixed-Integer Robust Optimization

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags , , ,

    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

    Robust Quadratic Programming with Mixed-Integer Uncertainty

  • Can Gokalp
  • Grani A. Hanasusanto
  • Areesh Mittal
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , ,

    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

    Data-Driven Robust Optimization Based on Kernel Learning

  • Xiaolin Huang
  • Chao Shang
  • Fengqi You
    • Categories Chemical Engineering, Robust Optimization Tags , , , ,

    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

    Extending the Scope of Robust Quadratic Optimization

  • Aharon Ben-Tal
  • Dick den Hertog
  • Ahmadreza Marandi
  • Bertrand Melenberg
    • Categories Quadratic Programming, Robust Optimization Tags , , ,

    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

    Robust Multi-Period Vehicle Routing under Customer Order Uncertainty

  • Chrysanthos E. Gounaris
  • Anirudh Subramanyam
  • Jose M. Lainez-Aguirre
  • Frank Mufalli
  • Jose M. Pinto
    • Categories Robust Optimization, Transportation Tags , ,

    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

    Algorithmic Differentiation for Piecewise Smooth Functions: A Case Study for Robust Optimization

  • Sabrina Fiege
  • Andreas Griewank
  • Kshitij Kulshreshtha
  • Andrea Walther
    • Categories Nonsmooth Optimization Tags , , ,

    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

    Robust combinatorial optimization with knapsack uncertainty

  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , ,

    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

    A Robust Approach to the Capacitated Vehicle Routing Problem with Uncertain Costs

  • Christoph Buchheim
  • Uwe Clausen
  • Jannis Kurtz
  • Lars Eufinger
    • Categories Combinatorial Optimization, Robust Optimization, Transportation Tags , ,

    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