کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10348231 699386 2012 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 5, May 2012, Pages 1133-1144
نویسندگان
, , , ,