Mathematical Programming Computation, Volume 4, Number 3, September 2012

Font Size:  Small  Medium  Large

A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition

Victor Zverovich, Csaba I. Fabian, Eldon F. D. Ellison, Gautam Mitra


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 deter- ministic equivalent problem by the simplex method and an interior point method, (ii) Benders decomposition (L-shaped method with aggregated cuts), (iii) Regular- ised decomposition of Ruszczyn ?ski (Math Program 35:309–333, 1986), (iv) Bend- ers decomposition with regularization of the expected recourse by the level method (Lemare?chal et al. in Math Program 69:111–147, 1995), (v) Trust region (regularisa- tion) 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 Fa?bia?n and Szo ?ke (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.

Full Text: PDF

mpc footer
© MPS 2008-2016