A parallelizable algorithmic framework for solving large scale multi-stage stochastic mixed 0-1 problems under uncertainty

Abstract

In this paper we present a parallelizable scheme of the Branch-and-Fix Coordination algorithm for solving medium and large scale multi-stage mixed 0-1 optimization problems under uncertainty. The uncertainty is represented via a nonsymmetric scenario tree. An information structuring for scenario cluster partitioning of nonsymmetric scenario trees is also presented, given the general model formulation of a multi-stage stochastic mixed 0-1 problem. The basic idea consists of explicitly rewriting the nonanticipativity constraints (NAC) of the 0-1 and continuous variables in the stages with common information. As a result an assignment of the constraint matrix blocks into independent scenario cluster submodels is performed by a so-called cluster splitting-compact representation. This partitioning allows to generate a new information structure to express the NAC which link the related clusters, such that the explicit NAC linking the submodels together is performed by a splitting variable representation. The new algorithm has been implemented in a C++ experimental code that uses the open source optimization engine COIN-OR, for solving the auxiliary linear and mixed 0-1 submodels. Some computational experience is reported to validate the new proposed approach. We give computational evidence of the model tightening effect that have preprocessing techniques in stochastic integer optimization as well, by using the probing and Gomory and clique cuts identification and appending schemes of the optimization engine.