A parallelizable algorithmic framework for solving large scale multi-stage stochastic mixed 0-1 problems under uncertainty
Laureano F. Escudero Bueno,
María Araceli Garín Martín,
María Merino Maestre and
Gloria Pérez Sainz de Rozas
No 2011-01, BILTOKI from Universidad del País Vasco - Departamento de Economía Aplicada III (Econometría y Estadística)
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.
Keywords: multi-stage stochastic mixed 0-1 optimization; nonsymmetric scenario trees; implicit and explicit nonanticipativity constraints; splitting variable and compact representations; scenario cluster partitioning (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed
Downloads: (external link)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:ehu:biltok:5576
Ordering information: This working paper can be ordered from
Dpto. de Econometría y Estadística, Facultad de CC. Económicas y Empresariales, Universidad del País Vasco, Avda. Lehendakari Aguirre 83, 48015 Bilbao, Spain
Access Statistics for this paper
More papers in BILTOKI from Universidad del País Vasco - Departamento de Economía Aplicada III (Econometría y Estadística) Contact information at EDIRC.
Series data maintained by Alcira Macías ().