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 Ruszczynski (Math Program 35: 309-333, 1986), (iv) Benders decomposition with regularization of the expected recourse by the level method (Lemarechal 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 Szoke (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.