Afficher la notice abrégée

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

hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierRéseau de Transport d'Electricité [Paris] [RTE]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorBLANCHOT, Xavier
hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorDETIENNE, Boris
hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorFROGER, Aurélien
hal.structure.identifierRéseau de Transport d'Electricité [Paris] [RTE]
dc.contributor.authorRUIZ, Manuel
dc.date2023
dc.date.accessioned2024-04-04T02:37:05Z
dc.date.available2024-04-04T02:37:05Z
dc.date.issued2023
dc.identifier.issn0377-2217
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190774
dc.description.abstractEnThis 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.
dc.language.isoen
dc.publisherElsevier
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enBenders Decomposition
dc.subject.enLarge-scale linear programming
dc.subject.enCut aggregation
dc.subject.enStochastic programming
dc.title.enThe Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejor.2023.01.004
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalEuropean Journal of Operational Research
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-03286135
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03286135v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2023&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=BLANCHOT,%20Xavier&CLAUTIAUX,%20Fran%C3%A7ois&DETIENNE,%20Boris&FROGER,%20Aur%C3%A9lien&RUIZ,%20Manuel&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée