A review of algorithmic enhancements for Benders decomposition

Halil Şen 1, 2 Boris Detienne 1, 2 Ruslan Sadykov 1, 2 François Vanderbeck 2, 1
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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.
Type de document :
Communication dans un congrès
ISCO 2016 - 4th International Symposium on Combinatorial Optimization, May 2016, Vietri sul Mare, Italy. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01426727
Contributeur : François Vanderbeck <>
Soumis le : mercredi 4 janvier 2017 - 18:43:26
Dernière modification le : jeudi 1 février 2018 - 09:58:59

Annexe

Identifiants

  • HAL Id : hal-01426727, version 1

Collections

Citation

Halil Şen, Boris Detienne, Ruslan Sadykov, François Vanderbeck. A review of algorithmic enhancements for Benders decomposition. ISCO 2016 - 4th International Symposium on Combinatorial Optimization, May 2016, Vietri sul Mare, Italy. 2016. 〈hal-01426727〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

15