An algorithmic framework for solving large‐scale multistage stochastic mixed 0–1 problems with nonsymmetric scenario trees

In this paper we present a parallelizable Branch‐and‐Fix Coordination algorithm for solving medium and large‐scale multistage 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 multistage 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. Some computational experience is reported on a test of randomly generated instances as well as a large‐scale real‐life problem by using CPLEX as a solver of the auxiliary submodels within the open source engine COIN‐OR.