Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10348231 | Computers & Operations Research | 2012 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Laureano F. Escudero, MarÃa Araceli GarÃn, MarÃa Merino, Gloria Pérez,