Michael Poss

Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty

  • Jérémy Omer
  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , ,

    Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called Decision-Dependent Information Discovery (DDID). In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still … Read more

    A polynomial algorithm for minimizing travel time in time-dependent networks with waits

  • Jérémy Omer
  • Michael Poss
    • Categories Network Optimization

    We consider a time-dependent shortest path problem with possible waiting at each node and a global bound $W$ on the total waiting time. The goal is to minimize only the time travelled along the edges of the path, not including the waiting time. We prove that the problem can be solved in polynomial time when … Read more

    Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty

  • Artur Alves Pessoa
  • Michael Poss
  • Ruslan Sadykov
  • François Vanderbeck
    • Categories Branch and Cut Algorithms, Robust Optimization

    We examine the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). We consider two types of uncertainty sets for the customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope proposed by Gounaris et al. (2013). We show that using the set-partitioning formulation it is possible … 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

    Optimizing power generation in the presence of micro-grids

  • Boris Detienne
  • Michael Poss
  • De Boeck Jérome
  • Pan Stefania
  • Wim van Ackooij
    • Categories 0-1 Programming, Applications - Science and Engineering, Stochastic Programming Tags , , ,

    In this paper we consider energy management optimization problems in a future wherein an interaction with micro-grids has to be accounted for. We will model this interaction through a set of contracts between the generation companies owning centralized assets and the micro-grids. We will formulate a general stylized model that can, in principle, account for … 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 dynamic programming approach for a class of robust optimization problems

  • Agostinho Agra
  • Michael Poss
  • Marcio Costa
  • Dritan Nace
    • Categories Robust Optimization Tags , , , ,

    Common approaches to solve a robust optimization problem decompose the problem into a master problem (MP) and adversarial separation problems (APs). MP contains the original robust constraints, however written only for finite numbers of scenarios. Additional scenarios are generated on the fly by solving the APs. We consider in this work the budgeted uncertainty polytope … Read more

    Decomposition for adjustable robust linear optimization subject to uncertainty polytope

  • Josette Ayoub
  • Michael Poss
    • Categories Robust Optimization

    We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to poly- tope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row gen- eration or column-and-row generation algorithms. The novelty … Read more

    Robust constrained shortest path problems under budgeted uncertainty

  • Luigi di Puglia Pugliese
  • Francesca Guerriero
  • Artur Alves Pessoa
  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , , ,

    We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is \NPhard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the … Read more