We propose a novel two-phase bounding and decomposition approach to compute optimal and near-optimal solutions to large-scale mixed-integer investment planning problems that have to consider a large num-ber of operating subproblems,each of which is a convexoptimization.Our motivating application is the planning of power transmission andg enerationin which policy constraints are designed to incentivize high amounts of intermittent generation in electric power systems.The bounding phase exploits Jensen’sinequal-ity to define a lower bound,which we extend to stochastic programs that use expected-value constraints to enforce policy objectives.The decomposition phase,in which the bounds are tightened,improve supon the standard Benders’algorithm by accelerating the convergence of the bounds.Thelower bound is tightened by using a Jensen’sinequality-based approach to introduce anauxiliary lower bound into the Benders master problem. Upper bounds for both phases are computed using a sub-sampling approach executed on a parallel computer system. Numerical results show that only the bounding phase is necessary if loose optimality gaps ar eacceptable. However,thedecomposition phase is required to attain optimality gaps. Use of bothphases performs better,interms of convergence speed, than attempting to solve the problem using just the bounding phase or regular Benders decomposition separately.

European Journal of Operational Research 248 (2016) 888-898