Decomposition and variance reduction techniques for stochastic mixed integer programs

Obtaining upper and lower bounds on the optimal value of a stochastic integer program can require solution of multiple-scenario problems, which are computationally expensive or intractable using off-the-shelf integer-programming software. Additionally, optimal solutions to a two-stage problem whose second stage spans long time horizons may be optimistic, due to the model's inappropriate ability to plan for future periods which are not known in practice. To that end, we present a framework for optimizing system design in the face of a restricted class of policies governing system operation, which aim to model realistic operation. This leads to a natural decomposition of the problem yielding upper and lower bounds which we can compute quickly. We illustrate these ideas using a model that seeks to design and operate a microgrid to support a forward operating base. Here, designing the microgrid includes specifying the number and type of diesel generators, PV systems, and batteries while operating the grid involves dispatching these assets to satisfy load at minimum cost. We extend our approach to solve the same problem under load and photovoltaic uncertainty, and propose a method to generate appropriately correlated scenarios by simulating building occupancy via a bottom-up approach, then using the occupancy levels to inform environmental control unit loads on the base. Finally, in a separate line of work, we optimize the design of the strata for a stratified sampling estimator to reduce variance. We extend this method to the multivariate setting by optimizing the strata for a nonuniform Latin hypercube estimator. We then present empirical results that show that our method reduces the variance of the estimator, compared to one using equal-probability strata.