Eduardo Moreno
Professor
Faculty of Engineering and Science
Universidad Adolfo Ibáñez
Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs
Benders decomposition is one of the most applied methods to solve two-stage
stochastic problems (TSSP) with a large number of scenarios. The main idea
behind the Benders decomposition is to solve a large problem by replacing the
values of the second-stage subproblems with individual variables, and
progressively forcing those variables to reach the optimal value of the
subproblems, dynamically inserting additional valid constraints, known as
Benders cuts. Most traditional implementations add a cut for each scenario
(multi-cut) or a single-cut that includes all scenarios. In this paper we
present a novel Benders adaptive-cuts method, where the Benders cuts are
aggregated according to a partition of the scenarios, which is dynamically
refined using the LP-dual information of the subproblems. This scenario
aggregation/disaggregation is based on the Generalized Adaptive Partitioning
Method (GAPM), which has been successfully applied to TSSPs. We formalize this
hybridization of Benders decomposition and the GAPM, by providing sufficient
conditions under which an optimal solution of the deterministic equivalent can
be obtained in a finite number of iterations. Our new method can be interpreted
as a compromise between the Benders single-cuts and multi-cuts methods, drawing
on the advantages of both sides, by rendering the initial iterations faster (as
for the single-cuts Benders) and ensuring the overall faster convergence (as
for the multi-cuts Benders). Computational experiments on two stochastic
network flow problems validate these statements, showing that the new method
outperforms the other implementations of Benders method, as well as other
standard methods for solving TSSPs, in particular when the number of scenarios
is very large.