Robust Optimization

Robust Network Design: Formulations, Valid Inequalities, and Computations

  • Arie M.C.A. Koster
  • Manuel Kutschka
  • Christian Raack
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , , ,

    Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim (2004). We present three different mathematical formulations for this problem, provide valid inequalities, … Read more

    Improving Robust Rolling Stock Circulation in Rapid Transit Networks

  • Luís Cadarso
  • Ángel Marín
    • Categories Civil and Environmental Engineering, Robust Optimization, Transportation Tags , ,

    The routing of the rolling stock depends strongly on the rolling stock assignment to di erent opera- tions and the shunting schedule. Therefore, the integration of these decision making is justi ed and is appropriate to introduce robustness in the model. We propose a new approach to obtain better circula- tions of the rolling stock material, solving … Read more

    A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Robust Optimization, Scheduling Tags , , ,

    In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the … Read more

    A comparison of routing sets for robust network design

  • Michael Poss
    • Categories Network Optimization, Robust Optimization

    Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. The problem can be seen a two-stage robust program where the recourse function consists in choosing the routing for each demand vector. Allowing the routing to change arbitrarily as the demand varies yields a very difficult … Read more

    Optimal Job Scheduling with Day-ahead Price and Random Local Distributed Generation: A Two-stage Robust Approach

  • Mehrnaz Abdollahian
  • Bo Zeng
  • Anna Danandeh
  • Long Zhao
    • Categories Robust Optimization, Scheduling Tags , , , ,

    In this paper, we consider a job scheduling problem with random local generation, in which some jobs must be scheduled day-ahead while the others can be scheduled in a real time fashion. To capture the randomness of the local distributed generation, we develop a two-stage robust optimization model by assuming an uncertainty set without probability … Read more

    Decision Making under Uncertainty when Preference Information is Incomplete

  • Benjamin Armbruster
  • Erick Delage
    • Categories Finance and Economics, Robust Optimization, Stochastic Programming Tags , , ,

    We consider the problem of optimal decision making under uncertainty but assume that the decision maker’s utility function is not completely known. Instead, we consider all the utilities that meet some criteria, such as preferring certain lotteries over certain other lotteries and being risk averse, s-shaped, or prudent. This extends the notion of stochastic dominance. … Read more

    A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

  • Daniel Kuhn
  • Paula Rocha
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    We consider quadratic stochastic programs with random recourse – a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space of recourse decisions to those linear and quadratic in the observations, thereby obtaining an upper bound on the original problem. … Read more

    Hidden convexity in partially separable optimization

  • Aharon Ben-Tal
  • Dick den Hertog
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Robust Optimization Tags , ,

    The paper identifies classes of nonconvex optimization problems whose convex relaxations have optimal solutions which at the same time are global optimal solutions of the original nonconvex problems. Such a hidden convexity property was so far limited to quadratically constrained quadratic problems with one or two constraints. We extend it here to problems with some … Read more

    Hidden convexity in partially separable optimization

  • Aharon Ben-Tal
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Robust Optimization Tags , ,

    The paper identifies classes of nonconvex optimization problems whose convex relaxations have optimal solutions which at the same time are global optimal solutions of the original nonconvex problems. Such a hidden convexity property was so far limited to quadratically constrained quadratic problems with one or two constraints. We extend it here to problems with some … Read more

    Robust solutions of optimization problems affected by uncertain probabilities

  • Aharon Ben-Tal
  • Dick den Hertog
  • Anja De Waegenaere
  • Bertrand Melenberg
  • Gijs Rennen
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , ,

    In this paper we focus on robust linear optimization problems with uncertainty regions defined by phi-divergences (for example, chi-squared, Hellinger, Kullback-Leibler). We show how uncertainty regions based on phi-divergences arise in a natural way as confidence sets if the uncertain parameters contain elements of a probability vector. Such problems frequently occur in, for example, optimization … Read more