GPU-accelerated transportation simplex algorithm
References
[1]
Background on transportation simplex algorithm (2023) : https://arxiv.org/search/?query=Mohit+Mahajan&searchtype=author.
[2]
V. Boyer, D. El Baz, Recent advances on gpu computing in operations research, in: 2013 IEEE International Symposium on Parallel Distributed Processing, Workshops and Phd Forum, 2013, pp. 1778–1787,.
[3]
H. Bulut, Multiloop transportation simplex algorithm, Optim. Methods Softw. 32 (6) (2017) 1206–1217,.
[4]
A. Charnes, W.W. Cooper, The stepping stone method of explaining linear programming calculations in transportation problems, Manag. Sci. 1 (1) (1954).
[5]
(2022): CUDA toolkit documentation. https://docs.nvidia.com/cuda/.
[6]
G.B. Dantzig, 14. The Classical Transportation Problem, Princeton University Press, 2016,.
[7]
K. Date, R. Nagi, Gpu-accelerated Hungarian algorithms for the linear assignment problem, Parallel Comput. 57 (2016) 52–72,.
[8]
U. Derigs, The Hitchcock Transportation Problem, Springer, Berlin Heidelberg, Berlin, Heidelberg, 1988,.
[9]
U. Ekanayake, P. C., W. Daundasekera, J. S., An effective alternative new approach in solving transportation problems, Am. J. Electr. Comput. Eng. 5 (2021) 1,.
[10]
F. Hillier, G. Lieberman, Introduction to Operations Research, McGraw-Hill International Editions, McGraw-Hill, 2001, https://books.google.com/books?id=SrfgAAAAMAAJ.
[11]
Z. Juman, M. Hoque, An efficient heuristic to obtain a better initial feasible solution to the transportation problem, Appl. Soft Comput. 34 (2015) 813–826,. https://www.sciencedirect.com/science/article/pii/S1568494615003099.
[12]
G. Kara, C. Özturan, Parallel network simplex algorithm for the minimum cost flow problem, Concurr. Comput., Pract. Exp. 34 (4) (2022),.
[13]
D. Klingman, R. Russell, Solving constrained transportation problems, Oper. Res. 23 (1) (1975) 91–106,.
[14]
S. Korukoğlu, S. Ballı, An improved Vogel's approximation method for the transportation problem, Math. Comput. Appl. 16 (2) (2011) 370–381,. https://www.mdpi.com/2297-8747/16/2/370.
[15]
G.V. Loch, A.C.L. da Silva, A computational study on the number of iterations to solve the transportation problem, Appl. Math. Sci. 8 (2014) 4579–4583,.
[16]
T. Matsui, R. Scheifele, A linear time algorithm for the unbalanced Hitchcock transportation problem, Networks 67 (2) (2016) 170–182,.
[17]
D. Merrill, M. Garland, A. Grimshaw, Scalable gpu graph traversal, in: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, Association for Computing Machinery, New York, NY, USA, 2012, pp. 117–128,.
[18]
J. Owens, M. Houston, D. Luebke, S. Green, J. Stone, J. Phillips, Gpu computing, Proc. IEEE 96 (2008) 879–899,.
[19]
N. Ploskas, N. Samaras, Gpu accelerated pivoting rules for the simplex algorithm, J. Syst. Softw. 96 (2014) 1–9,.
[20]
N.V. Reinfeld, W.R. Vogel, Mathematical Programming, Prentice-Hall, 1958.
[21]
(2022): Simple maps. https://simplemaps.com/data/us-zips.
[22]
H.A. Taha, Operations Research: An Introduction, 8th edition, Prentice-Hall, Inc., USA, 2006.
Index Terms
- GPU-accelerated transportation simplex algorithm
Index terms have been assigned to the content through auto-classification.
Recommendations
A simplex algorithm for piecewise-linear programming I: Derivation and proof
The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical ...
Multi GPU Implementation of the Simplex Algorithm
HPCC '11: Proceedings of the 2011 IEEE International Conference on High Performance Computing and CommunicationsThe Simplex algorithm is a well known method to solve linear programming (LP) problems. In this paper, we propose an implementation via CUDA of the Simplex method on a multi GPU architecture. Computational tests have been carried out on randomly ...
Artificial-free simplex algorithm based on the non-acute constraint relaxation
Solving a general linear programming problem using the simplex algorithm relies on introducing artificial variables that creates a large search space. This paper presents the non-acute constraint relaxation technique that not only eliminates the need ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier Inc.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 February 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 09 Mar 2025