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 条
  • [1] A scalable parallel implementation of the Cluster Benders Decomposition algorithm
    Jordi Mateo
    Lluís M. Plà
    Francesc Solsona
    Adela Pagès
    Cluster Computing, 2019, 22 : 877 - 886
  • [2] Scalable parallel Benders decomposition for stochastic linear programming
    Nielsen, SS
    Zenios, SA
    PARALLEL COMPUTING, 1997, 23 (08) : 1069 - 1088
  • [3] A scalable parallel algorithm for Matching Pursuit signal decomposition
    Dodero, G
    Gianuzzi, V
    Moscati, M
    Corvi, M
    HIGH-PERFORMANCE COMPUTING AND NETWORKING, 1998, 1401 : 458 - 466
  • [4] A HIGHLY SCALABLE PARALLEL IMPLEMENTATION OF BALANCING DOMAIN DECOMPOSITION BY CONSTRAINTS
    Badia, Santiago
    Martin, Alberto F.
    Principe, Javier
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2014, 36 (02): : C190 - C218
  • [5] Benders Decomposition Algorithm for Reference Network
    Zhang, Jie
    Cao, Xiangyang
    Tian, Xin
    Wang, Zhen
    Wang, Mingqiang
    Han, Xueshan
    Li, Shan
    TENCON 2015 - 2015 IEEE REGION 10 CONFERENCE, 2015,
  • [6] The Benders decomposition algorithm: A literature review
    Rahmaniani, Ragheb
    Crainic, Teodor Gabriel
    Gendreau, Michel
    Rei, Walter
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 259 (03) : 801 - 817
  • [7] A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions
    Fang, Kan
    Wang, Shijin
    Pinedo, Michael L.
    Chen, Lin
    Chu, Feng
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 291 (01) : 128 - 146
  • [8] The parallel algorithm of QR decomposition of matrix in cluster system
    Liu, Chunfeng
    Yang, Aimin
    Chang, Jincai
    He, Yali
    Yan, Shaohong
    Advances in Matrix Theory and Applications, 2006, : 261 - 264
  • [9] A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm
    Seo, Kiho
    Joung, Seulgi
    Lee, Chungmok
    Park, Sungsoo
    INFORMS JOURNAL ON COMPUTING, 2022, 34 (05) : 2804 - 2827
  • [10] Parallel Implementation of a Domain Decomposition Algorithm for Molecular Dynamics
    Berhe, G.
    Peters, B.
    Varrette, S.
    Bouvry, P.
    PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED AND GRID COMPUTING FOR ENGINEERING, 2009, (90): : 105 - 123
12345