A review of algorithmic enhancements for Benders decomposition
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
dc.contributor.author | ŞEN, Halil | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
dc.contributor.author | DETIENNE, Boris | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
dc.contributor.author | SADYKOV, Ruslan | |
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | VANDERBECK, François | |
dc.date.accessioned | 2024-04-04T03:11:55Z | |
dc.date.available | 2024-04-04T03:11:55Z | |
dc.date.created | 2016-05-16 | |
dc.date.issued | 2016-05-16 | |
dc.date.conference | 2016-05-16 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193815 | |
dc.description.abstractEn | In Benders decomposition approach to mixed integer programs , the optimization is carried in two stages: key first-stage decision variables are optimized using a polyhedral approximation of the full-blown problem projection, then a separation problem expressed in the second-stage variables is solved to check if the current first-stage solution is truly feasible, and otherwise, it produces a violated inequality. Such cutting-plane algorithms suffer from several drawbacks and may have very bad convergence rates. We review the battery of approaches that have been proposed in the literature to address these drawbacks and to speed-up the algorithm. Our contribution consists in explaining these techniques in simple terms and unified notations, showing that in several cases, different proposals of the literature boil down to the same key ideas. We classify methods into specific initialization mode, stabilization techniques, strategies to select the separation point, and cut generation strategies. Where available, we highlight numerical benchmarks that have resulted from such enhancements. | |
dc.language.iso | en | |
dc.subject.en | Benders Decomposition | |
dc.subject.en | Cutting Plane Algorithm | |
dc.subject.en | Stabi- lization Techniques | |
dc.title.en | A review of algorithmic enhancements for Benders decomposition | |
dc.type | Communication dans un congrès | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
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 | ISCO 2016 - 4th International Symposium on Combinatorial Optimization | |
bordeaux.country | IT | |
bordeaux.conference.city | Vietri sul Mare | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01426727 | |
hal.version | 1 | |
hal.invited | non | |
hal.proceedings | oui | |
hal.conference.end | 2016-05-18 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01426727v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2016-05-16&rft.au=%C5%9EEN,%20Halil&DETIENNE,%20Boris&SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |