Decomposition approaches for two-stage robust binary optimization
| hal.structure.identifier | Institut de Recherche Mathématique de Rennes [IRMAR] | |
| dc.contributor.author | ARSLAN, Ayşe | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | DETIENNE, Boris | |
| dc.date.accessioned | 2024-04-04T02:52:07Z | |
| dc.date.available | 2024-04-04T02:52:07Z | |
| dc.date.conference | 2019-07-29 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/192034 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020 | |
| dc.language.iso | en | |
| dc.subject.en | Robust optimization | |
| dc.subject.en | Integer programming | |
| dc.subject.en | Decomposition methods | |
| dc.subject.en | Integer recourse | |
| dc.title.en | Decomposition approaches for two-stage robust binary optimization | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Mathématiques [math] | |
| dc.subject.hal | Mathématiques [math]/Combinatoire [math.CO] | |
| dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ICSP2019 - XV International Conference on Stochastic Programming | |
| bordeaux.country | NO | |
| bordeaux.conference.city | Trondheim | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-02407421 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | non | |
| hal.conference.end | 2019-08-02 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-02407421v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=ARSLAN,%20Ay%C5%9Fe&DETIENNE,%20Boris&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||