robust optimization

Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

  • Immanuel M. Bomze
  • Michael Kahr
  • Markus Leitner
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more

    Monitoring With Limited Information

  • Dan Iancu
  • Nikolaos Trichakis
  • Do Young Yoon
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Robust Optimization Tags , , ,

    We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which he must choose, in conjunction with a suitable stopping policy, to maximize his reward. Dealing … Read more

    Distributionally Robust Linear and Discrete Optimization with Marginals

  • Louis Chen
  • Karthik Natarajan
  • David Simchi-Levi
  • Will Ma
  • Zhenzhen Yan
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Polyhedra Tags , ,

    In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more

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

  • Christoph Buchheim
  • Marianna De Santis
    • Categories Combinatorial Optimization, Global Optimization, Robust Optimization Tags , ,

    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

    Models and algorithms for the robust resource constrained shortest path problem

  • Fatma Gzara
  • Da Lu
    • Categories Network Optimization, Robust Optimization, Transportation Tags , , ,

    We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and … Read more

    Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks

  • Martin Robinius
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Detlef Stolten
  • Lara Welder
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Robust Optimization Tags , , , , ,

    We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to … Read more

    Reducing conservatism in Robust Optimization

  • Dick den Hertog
  • Ernst Roos
    • Categories Robust Optimization Tags , ,

    Although Robust Optimization is a powerful technique in dealing with uncertainty in optimization, its solutions can be too conservative when it leads to an objective value much worse than the nominal solution or even to infeasibility of the robust problem. In practice, this can lead to robust solutions being disregarded in favor of the nominal … Read more

    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