Quadratic stabilization of Benders decomposition
Résumé
The foundational Benders decomposition, or variable decomposition, is known to have the inherent instability of cutting plane-based methods. Several techniques have been proposed to improve this method, which has become the state of the art for important problems in operations research. This paper presents a complementary improvement featuring quadratic stabilization of the Benders cutting-plane model. Inspired by the level-bundle methods of nonsmooth optimization, this algorithmic improvement is designed to reduce the number of iterations of the method. We illustrate the interest of the stabilization on two classical problems: network design problems and hub location problems. We also prove that the stabilized Benders method has the same theoretical convergence properties as the usual Benders method.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...