Decomposition-based approaches for a class of two-stage robust binary optimization problems
| hal.structure.identifier | Institut de Recherche Mathématique de Rennes [IRMAR] | |
| hal.structure.identifier | Institut National des Sciences Appliquées - Rennes [INSA Rennes] | |
| dc.contributor.author | ARSLAN, Ayşe | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | DETIENNE, Boris | |
| dc.date.accessioned | 2024-04-04T02:50:26Z | |
| dc.date.available | 2024-04-04T02:50:26Z | |
| dc.date.issued | 2022-03 | |
| dc.identifier.issn | 1091-9856 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191911 | |
| dc.description.abstractEn | In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty where recourse decisions are restricted to be mixed-binary. For these problems, we present a deterministic equivalent formulation through the convexification of the recourse feasible region. We then explore this formulation under the lens of a relaxation, showing that the specific relaxation we propose can be solved using the branch-and-price algorithm. We present conditions under which this relaxation is exact, and describe alternative exact solution methods when this is not the case. Despite the two-stage nature of the problem, we provide NP-completeness results based on our reformulations. Finally, we present various applications in which the methodology we propose can be applied. We compare our exact methodology to those approximate methods recently proposed in the literature under the name K-adaptability. Our computational results show that our methodology is able to produce better solutions in less computational time compared to the K-adaptability approach, as well as to solve bigger instances than those previously managed in the literature. | |
| dc.description.sponsorship | Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020 | |
| dc.language.iso | en | |
| dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | |
| dc.title.en | Decomposition-based approaches for a class of two-stage robust binary optimization problems | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1287/ijoc.2021.1061 | |
| dc.subject.hal | Mathématiques [math]/Optimisation et contrôle [math.OC] | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | INFORMS Journal on Computing | |
| bordeaux.volume | 34 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-02190059 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-02190059v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2022-03&rft.volume=34&rft.issue=2&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=ARSLAN,%20Ay%C5%9Fe&DETIENNE,%20Boris&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||