Decomposition approaches for two-stage robust binary optimization - Analyse numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Decomposition approaches for two-stage robust binary optimization

Résumé

In this talk, we study a class of two-stage robust binary optimization problems with polyhedral uncertainty set where recourse decisions are restricted to be mixed-binary and uncertainty is present only in the objective function. We present a deterministic equivalent formulation for these problems through convexification of the recourse feasible region. However, this reformulation does not directly lead to an exploitable structure in the problem. We therefore investigate a relaxation where we replace the convex hull of the recourse feasible region with an intersection of the convex hull of the pure recourse polyhedron with the linking constraints. We additionally propose “no-good” cut-type inequalities to recover the original problem from this relaxation. The resulting exact formulation can be solved with a branch-and-price-and-cut method, generating columns from the pure recourse polyhedron and introducing “no-good” cuts as needed. We additonally present necessary conditions for the relaxation to be exact without the need for additional cuts. Finally, we present various applications where these conditions are satisfied, and investigate the numerical strength of our methodology. Speicifally, we compare our methodology to a recently introduced approximation method called K-adaptability that fixes K recourse solutions in the first stage and optimizes the recourse problem over these in the second stage.
Fichier principal
Vignette du fichier
pres.pdf (1.58 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02407421 , version 1 (19-06-2020)

Identifiants

  • HAL Id : hal-02407421 , version 1

Citer

Ayşe N Arslan, Boris Detienne. Decomposition approaches for two-stage robust binary optimization. ICSP2019 - XV International Conference on Stochastic Programming, Jul 2019, Trondheim, Norway. ⟨hal-02407421⟩
147 Consultations
36 Téléchargements

Partager

Gmail Facebook X LinkedIn More