robust optimization

Robust optimization for models with uncertain SOC and SDP constraints

  • Frans J.C.T. de Ruiter
  • Dick den Hertog
  • Ernst Roos
  • Jianzhe Zhen
    • Categories Robust Optimization Tags , , , ,

    In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem … Read more

    Derivative-Free Robust Optimization by Outer Approximations

  • Matt Menickelly
  • Stefan M. Wild
    • Categories Nonsmooth Optimization, Robust Optimization, Unconstrained Optimization Tags , , ,

    We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We … Read more

    A Primal-Dual Lifting Scheme for Two-Stage Robust Optimization

  • Angelos Georghiou
  • Angelos Tsoukalas
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags , , ,

    Two-stage robust optimization problems, in which decisions are taken both in anticipation of and in response to the observation of an unknown parameter vector from within an uncertainty set, are notoriously challenging. In this paper, we develop convergent hierarchies of primal (conservative) and dual (progressive) bounds for these problems that trade off the competing goals … Read more

    Robust Sensitivity Analysis for Linear Programming with Ellipsoidal Perturbation

  • Ruotian Gao
  • Wenxun Xing
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , , ,

    Given an originally robust optimal decision and allowing perturbation parameters of the linear programming problem to run through a maximum uncertainty set controlled by a variable of perturbation radius, we do robust sensitivity analysis for the robust linear programming problem in two scenarios. One is to keep the original decision still robust optimal, the other … 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

    Constraint Generation for Two-Stage Robust Network Flow Problem

  • David Simchi-Levi
  • He Wang
  • Yehua Wei
    • Categories Network Optimization, Robust Optimization Tags , , ,

    In this paper, we propose new constraint generation algorithms for solving the two-stage robust minimum cost flow problem, a problem that arises from various applications such as transportation and logistics. In order to develop efficient algorithms under general polyhedral uncertainty set, we repeatedly exploit the network-flow structure to reformulate the two-stage robust minimum cost flow … Read more

    Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories Combinatorial Optimization, Integer Programming, Robust Optimization Tags , , , , ,

    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

    The Adaptive Robust Multi-Period Alternating Current Optimal Power Flow Problem

  • Alvaro Lorca
  • Xu Andy Sun
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , ,

    This paper jointly addresses two major challenges in power system operations: i) dealing with non-convexity in the power flow equations, and ii) systematically capturing uncertainty in renewable power availability and in active and reactive power consumption at load buses. To overcome these challenges, this paper proposes a two-stage adaptive robust optimization model for the multi-period … Read more

    Robust Combinatorial Optimization under Budgeted-Ellipsoidal Uncertainty

  • Jannis Kurtz
    • Categories 0-1 Programming, Combinatorial Optimization, Robust Optimization Tags , , , ,

    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

    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