Michael Poss

Solving bilevel combinatorial optimization as bilinear min-max optimization via a branch-and-cut algorithm

  • Artur Alves Pessoa
  • Michael Poss
  • Marcos Costa Roboredo
    • Categories Branch and Cut Algorithms Tags , , ,

    In this paper, we propose a generic branch-and -cut algorithm for a special class of bi-level combinatorial optimization problems. Namely, we study such problems that can be reformulated as bilinear min-max combinatorial optimization problems. We show that the reformulation can be efficiently solved by a branch-and-cut algorithm whose cuts represent the inner maximization feasibility set. … Read more

    A comparison of routing sets for robust network design

  • Michael Poss
    • Categories Network Optimization

    Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. In this paper, we compare the optimal capacity allocation costs for six routing sets: affine routing, volume routing and its two simplifications, the routing based on an unrestricted 2-cover of the uncertainty set, and the routing … Read more

    Robust combinatorial optimization with cost uncertainty

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

    We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates … Read more

    Robust combinatorial optimization with variable budgeted uncertainty

  • Michael Poss
    • Categories Robust Optimization

    We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty … Read more

    The robust vehicle routing problem with time windows

  • Agostinho Agra
  • Michael Poss
  • Marielle Christiansen
  • Rosa Figueiredo
  • Lars M. Hvattum
  • Cristina Requejo
    • Categories Robust Optimization, Transportation

    This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a … Read more

    Layered Formulation for the Robust Vehicle Routing Problem with Time Windows

  • Agostinho Agra
  • Michael Poss
  • Marielle Christiansen
  • Rosa Figueiredo
  • Lars M. Hvattum
  • Cristina Requejo
    • Categories Integer Programming, Robust Optimization, Transportation Tags , , , ,

    This paper studies the vehicle routing problem with time windows where travel times are uncertain and belong to a predetermined polytope. The objective of the problem is to find a set of routes that services all nodes of the graph and that are feasible for all values of the travel times in the uncertainty polytope. … 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

    Affine recourse for the robust network design problem: between static and dynamic routing

  • Michael Poss
  • Christian Raack
    • Categories Combinatorial Optimization, Network Optimization, Robust Optimization Tags , , , , ,

    Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework … Read more

    Benders decomposition for the hop-constrainted survivable network design problem

  • Quentin Botton
  • Bernard Fortz
  • Luís Gouveia
  • Michael Poss
    • Categories Branch and Cut Algorithms, Telecommunications

    Given a graph with nonnegative edge weights and a set of pairs of nodes Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia, … Read more

    Easy distributions for combinatorial optimization problems with probabilistic constraints

  • Bernard Fortz
  • Michael Poss
    • Categories Combinatorial Optimization, Stochastic Programming Tags , ,

    We show how we can linearize probabilistic linear constraints with binary variables when all coefficients are distributed according to either $\mathcal{N}(\mu_i,\lambda \mu_i)$, for some $\lambda >0$ and $\mu_i>0$, or $\Gamma(k_i,\theta)$ for some $\theta >0$ and $k_i>0$. The constraint can also be linearized when the coefficients are independent and identically distributed if they are, besides, either … Read more