A scalable parallel implementation of the Cluster Benders Decomposition algorithm

被引：2

作者：

Mateo, Jordi ^{[1
]}

Pla, Lluis M. ^{[2
]}

Solsona, Francesc ^{[1
]}

Pages, Adela ^{[2
]}

机构：

[1] Univ Lleida, Dept Comp Sci, Jaume II 69, Lleida 25001, Spain

[2] Univ Lleida, Dept Math, Jaume II 71, Lleida 25001, Spain

来源：

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS | 2019年 / 22卷 / 03期

关键词：

Stochastic linear optimization; Parallelization; Scalability; Clustering in stochastic optimzation; Benders Decomposition;

D O I：

10.1007/s10586-018-2878-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Benders Decomposition (BD) is a method used to solve stochastic linear problems via scenario analysis. Cluster BD (CBD) is one of its smart improvements that speed up the execution time, taking advantage of tighter feasible cuts found by grouping scenarios into clusters. In this paper, we propose a new design for CBD, one which takes into account the role played by optimal cuts in the solution. Besides, we propose a new parallel scheme for CBD to deal with large-scale two-stage stochastic linear problems. Moreover, we characterise the problems for which our proposal performs best. The results obtained show computational gains from our proposal compared with the plain use of CPLEX, serial BD, parallel BD, serial CBD and parallel CBD.

引用

页码：877 / 886

页数：10

共 50 条

[41] Enhancing Benders decomposition algorithm to solve a combat logistics problem
Mohammad Marufuzzaman
Farjana Nur
Amy E. Bednar
Mark Cowan
OR Spectrum, 2020, 42 : 161 - 198
[42] Enhancing Benders decomposition algorithm to solve a combat logistics problem
Marufuzzaman, Mohammad
Nur, Farjana
Bednar, Amy E.
Cowan, Mark
OR SPECTRUM, 2020, 42 (01) : 161 - 198
[43] Microgrid sizing and energy management using Benders decomposition algorithm
Masternak, Celia
Meunier, Simon
Brisset, Stephane
Reinbold, Vincent
SUSTAINABLE ENERGY GRIDS & NETWORKS, 2024, 38
[44] Research on scalable parallel web server cluster
Zhuang, Weiqiang
Wang, Dingxing
Shen, Meiming
Zheng, Weimin
Xiaoxing Weixing Jisuanji Xitong/Mini-Micro Systems, 2000, 21 (01): : 19 - 23
[45] Performance considerations for scalable parallel tensor decomposition
Rolinger, Thomas B.
Simon, Tyler A.
Krieger, Christopher D.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2019, 129 : 83 - 98
[46] The parallel implementation of the algorithm solution of model for two-phase cluster in liquids
Korneev, VD
Vshivkov, VA
Lazareva, GG
Kedrinskii, VK
PARALLEL COMPUTING TECHNOLOGIES, 2005, 3606 : 433 - 445
[47] A Scalable Parallel Algorithm for Balanced Sampling
Lee, Alexander
Walzer-Goldfeld, Stefan
Zablah, Shukry
Riondato, Matteo
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2022, : 12991 - 12992
[48] Scalable implementation of the parallel multigrid method on massively parallel computers
Kang, K. S.
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2015, 70 (11) : 2701 - 2708
[49] ON THE GENERALIZED BENDERS DECOMPOSITION
BAGAJEWICZ, MJ
MANOUSIOUTHAKIS, V
COMPUTERS & CHEMICAL ENGINEERING, 1991, 15 (10) : 691 - 700
[50] Unit commitment algorithm based on improved Benders decomposition and perspective cut
College of Mathematics and Information Science, Guangxi University, Nanning
530004, China
不详
537000, China
不详
450001, China
不详
530004, China
Dianli Zidonghua Shebei Electr. Power Autom. Equip., 1 (133-138):

← 1 2 3 4 5 →