A scenario decomposition metaheuristic for solving two-stage stochastic problems with integrality constraints

Many important modern-day problems involve uncertainty, such as meeting electricity demand with a growing fraction of variable energy sources. Stochastic programs facilities making decisions based on all realizations of the uncertain parameters, however the number of variables in these models grow with the number of scenarios considered. Several years of historical data may be available, providing a rich description of the uncertainty, but if the problem contains integrality constraints it is limited how many scenarios can be considered before it becomes intractable.

Progressive Hedging is a scenario decomposition method originally developed for convex problems. The non-anticipativity constraints are Lagrangian relaxed, making it possible to solve a series of computationally easier subproblems that only account for a few scenarios each. Consensus is then enforced between subproblems through objective penalties. This method has also been used as a heuristic for problems with integer variables, however, only minor modifications have been made to the framework which still reflects a non-integer design.

In this presentation, we will introduce novel improvements to the Progressive Hedging framework for use as a metaheuristic for stochastic linear problems with integer variables. Computational results for various two-stage stochastic optimization problems underline its general usefulness.