Economics at your fingertips  

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)

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.

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)
Date: 2011-02
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link) (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

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 ().

Page updated 2017-09-29
Handle: RePEc:ehu:biltok:5576