BLANCHOT, Xavier; CLAUTIAUX, François; DETIENNE, Boris; FROGER, Aurélien; RUIZ, Manuel

doi:10.1016/j.ejor.2023.01.004

Metadatos

Licencia de uso del documento

BLANCHOT, Xavier
Université de Bordeaux [UB]
Réseau de Transport d'Electricité [Paris] [RTE]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

CLAUTIAUX, François
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]

DETIENNE, Boris
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Idioma

Article de revue

Este ítem está publicado en

European Journal of Operational Research. 2023

Elsevier

Fecha de defensa

2023

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

Benders Decomposition

Large-scale linear programming

Cut aggregation

Stochastic programming

Metadatos

Compartir este ítem

Licencia de uso del documento

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

Idioma

Este ítem está publicado en

Fecha de defensa

Resumen en inglés

Palabras clave en inglés

URI

DOI

Orígen

Centros de investigación