The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2023

The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs

Résumé

This paper introduces a new exact algorithm to solve two-stage stochastic linear programs. Based on the multicut Benders reformulation of such problems, with one subproblem for each scenario, this method relies on a partition of the subproblems into batches. The key idea is to solve at most iterations only a small proportion of the subproblems by detecting as soon as possible that a first-stage candidate solution cannot be proven optimal. We also propose a general framework to stabilize our algorithm, and show its finite convergence and exact behavior. We report an extensive computational study on large-scale instances of stochastic optimization literature that shows the efficiency of the proposed algorithm compared to nine alternative algorithms from the literature. We also obtain significant additional computational time savings using the primal stabilization schemes.
Fichier principal
Vignette du fichier
BendersByBatch_HAL_v4.pdf (1.8 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03286135 , version 1 (13-07-2021)
hal-03286135 , version 2 (06-01-2022)
hal-03286135 , version 3 (13-07-2022)
hal-03286135 , version 4 (15-12-2022)

Licence

Paternité

Identifiants

Citer

Xavier Blanchot, François Clautiaux, Boris Detienne, Aurélien Froger, Manuel Ruiz. The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs. European Journal of Operational Research, In press, ⟨10.1016/j.ejor.2023.01.004⟩. ⟨hal-03286135v4⟩

Collections

CNRS INRIA INRIA2
225 Consultations
207 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More