A Computational Study of a Solver System for Processing Two-Stage Stochastic LPs with Enhanced Benders Decomposition

We report a computational study of two-stage SP models on a large set of benchmark problems and consider the following methods: (i) Solution of the deterministic equivalent problem by the simplex method and an interior point method, (ii) Benders decomposition (L-shaped method with aggregated cuts), (iii) Regularised decomposition of Ruszczy4nski (Math Program 35:309-333, 1986), (iv) Benders decomposition with regularization of the expected recourse by the level method (Lemarichal et al. in Math Program 69:111-147, 1995), (v) Trust region (regularisation) method of Linderoth and Wright (Comput Optim Appl 24:207-250, 2003). In this study the three regularisation methods have been introduced within the computational structure of Benders decomposition. Thus second-stage infeasibility is controlled in the traditional manner, by imposing feasibility cuts. This approach allows extensions of the regularisation to feasibility issues, as in Fabian and Szuke (Comput Manag Sci 4:313-353, 2007). We report computational results for a wide range of benchmark problems from the POSTS and SLPTESTSET collections and a collection of difficult test problems compiled by us. Finally the scale-up properties and the performance profiles of the methods are presented.