An Empirical Investigation of OpenMP Based Implementation of Simplex Algorithm

被引：1

作者：

Banerjee, Arkaprabha ^{[1
]}

Shah, Pratvi ^{[1
]}

Nandani, Shivani ^{[1
]}

Tyagi, Shantanu ^{[1
]}

Kumar, Sidharth ^{[2
]}

Chaudhury, Bhaskar ^{[1
]}

机构：

[1] DA IICT, Grp Computat Sci & High Performance Comp, Gandhinagar, India

[2] Univ Alabama Birmingham, Birmingham, AL USA

来源：

OPENMP: ENABLING MASSIVE NODE-LEVEL PARALLELISM, IWOMP 2021 | 2021年 / 12870卷

关键词：

Large-scale problems; Linear programming; Simplex; Parallel computing; Scalable algorithms; OpenMP;

D O I：

10.1007/978-3-030-85262-7_7

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a shared-memory based parallel implementation of the standard simplex algorithm. The simplex algorithm is a popular technique for linear programming used to solve minimization and maximization problems that are subject to linear constraints. The simplex algorithm reduces the optimization problem to a series of iterative matrix operations. In this paper we perform an empirical analysis of our algorithm and also study the impact of the density of the underlying matrix on the overall performance. We observed a maximum speedup of 10.2 at 16 threads and also demonstrated that our proposed parallel algorithm scales well over a range of matrix densities. We also make an important observation that the effect of increasing the number of constraints is more significant than the effect of varying the number of variables.

引用

页码：96 / 110

页数：15

共 10 条

[1] Borgwardt K.H, 1986, PROBABILISTIC ANAL S, DOI [10.1007/978-3-642-61578-8, DOI 10.1007/978-3-642-61578-8]
[2] Coutinho D., 2018, SCALABLE SHARED MEMO
[3] Dantzig G.B., 1990, A history of scientific computing, P141, DOI DOI 10.1145/87252.88081
[4] The Complexity of the Simplex Method
Fearnley, John
Savani, Rahul
[J]. STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2015, : 201 - 208
[5] Goldfarb D, 1994, ADV OPTIMIZATION NUM, V275, DOI 10.1007/978-94-015-8330-5
[6] Ketabchi S., 2012, NEW METHODS SOLVING, DOI [10.12785/amis/070440, DOI 10.12785/AMIS/070440]
[7] Klotz Ed., 2013, SURVEYS OPERATIONS R, V18, P1, DOI [10.1016/j.sorms.2012.11.001, DOI 10.1016/J.SORMS.2012.11.001]
[8] A Hybrid Parallelization Scheme for Standard Simplex Method based on CPU/GPU Collaboration
Mamalis, Basilis
Perlitis, Marios
[J]. 20TH PAN-HELLENIC CONFERENCE ON INFORMATICS (PCI 2016), 2016,
[9] Ploskas N, 2013, OPTIMIZATION THEORY, V31
[10] A COMPARISON OF THE ORIGINAL AND REVISED SIMPLEX METHODS
WAGNER, HM
[J]. OPERATIONS RESEARCH, 1957, 5 (03) : 361 - 369

← 1 →