The Benders by batch algorithm: design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs
BLANCHOT, Xavier
Université de Bordeaux [UB]
Réseau de Transport d'Electricité [Paris] [RTE]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
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]
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]
See more >
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
BLANCHOT, Xavier
Université de Bordeaux [UB]
Réseau de Transport d'Electricité [Paris] [RTE]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
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]
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]
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
FROGER, Aurélien
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Reduce
Université de Bordeaux [UB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Article de revue
This item was published in
European Journal of Operational Research. 2023
Elsevier
Date
2023English Abstract
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 ...Read more >
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.Read less <
English Keywords
Benders Decomposition
Large-scale linear programming
Cut aggregation
Stochastic programming
Origin
Hal imported