nach oben

vorheriges Kapitel Stability in Heterogeneous Dynamic Multimedia N...

nächstes Kapitel An Introduction to Temporal Graphs: An Algorith...

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2015 | OriginalPaper | Buchkapitel

Advances in the Parallelization of the Simplex Method

Erstes Kapitel lesen

Autoren: Basilis Mamalis, Grammati Pantziou

Verlag: Springer International Publishing

Erschienen in: Algorithms, Probability, Networks, and Games

» Jetzt Zugang zum Volltext erhalten

Abstract

The simplex method has been successfully used in solving linear programming problems for many years. Parallel approaches for the simplex method have been extensively studied in the literature due to the intensive computations required, especially for the solution of large linear problems (LPs). In this paper, first a detailed overview is given of the parallelization attempts concerning the standard and the revised simplex method made to date. Next, some of the most recent and significant relevant attempts are selected and presented in more detail along with experimental results. The latter include some impressive results obtained for the revised simplex method over a modern supercomputer, as well as the recent advances in GPU-based related attempts.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Jetzt einloggen Kostenlos registrieren

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Jetzt informieren

Note also that the techniques applied in the proposed approaches, have been the basis for the integration of FICO Xpress parallel solver [ 42], which was the first commercial parallel simplex solver and has been regarded quite faster than the pre-existing ones in various kinds of large-scale LPs.

Note also that this paper has received recently the COAP (Computational Optimization and Applications) journal Best Paper Award for year 2013.

Murty, K.: Linear Programming. Wiley, New York (1983) MATH

Hall, J.A.: Towards a practical parallelization of the simplex method. Comput. Manag. Sci. 7(2), 139–170 (2010) MathSciNetCrossRefMATH

Yarmish, G., Slyke, R.V.: A distributed scaleable simplex method. J. Supercomput. 49(3), 373–381 (2009) CrossRef

Badr, E.S., Moussa, M., Paparrizos, K., Samaras, N., Sifaleras, A.: Some Computational Results on MPI Parallel Implementation of Dense Simplex Method. World Academy of Science, Engineering and Technology (WASET), vol. 23, pp. 778–781 (2008)

Qin, J., Nguyen, D.T.: A parallel-vector simplex algorithm on distributed-memory computers. Struct. Optim. 11(3), 260–262 (1996) CrossRef

Hall, J., Huangfu, Q.: A high performance dual revised simplex solver. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2011, Part I. LNCS, vol. 7203, pp. 143–151. Springer, Heidelberg (2012) CrossRef

Huangfu, Q., Hall, J.A.: Parallelizing the dual revised simplex method. Technical report ERGO-14-011 (2014). http://www.maths.ed.ac.uk/hall/Publications.html

Lubin, M., Hall, J.A., Petra, C.G., Anitescu, M.: Parallel distributed-memory simplex for large-scale stochastic LP problems. Comput. Optim. Appl. 55(3), 571–596 (2013) MathSciNetCrossRefMATH

Hall, J.A., McKinnon, K.: ASYNPLEX an asynchronous parallel revised simplex algorithm. Ann. Oper. Res. 81, 27–49 (1998) MathSciNetCrossRefMATH

10.

Shu, W.: Parallel implementation of a sparse simplex algorithm on MIMD distributed memory computers. J. Parallel Distrib. Comput. 31(1), 2540 (1995) CrossRef

11.

Thomadakis M.E., Liu, J.C.: An efficient steepest-edge simplex algorithm for SIMD computers. In: Proceedings of the International Conference on Supercomputing (ICS 96), Philadelphia, pp. 286–293 (1996)

12.

Eckstein, J., Boduroglu, I., Polymenakos, L., Goldfarb, D.: Data-parallel implementations of dense simplex methods on the connection machine CM-2. ORSA J. Comput. 7(4), 402–416 (1995) CrossRefMATH

13.

Stunkel, C.B.: Linear optimization via message-based parallel processing. In: Proceedings of International Conference on Parallel Processing (ICPP), Pennsylvania, pp. 264–271 (1988)

14.

Klabjan, D., Johnson, L.E., Nemhauser, L.G.: A parallel primal-dual simplex algorithm. Oper. Res. Lett. 27(2), 47–55 (2000) MathSciNetCrossRefMATH

15.

Maros, I., Mitra, G.: Investigating the sparse simplex method on a distributed memory multiprocessor. Parallel Comput. 26(1), 151–170 (2000) CrossRefMATH

16.

Mamalis, B., Pantziou, G., Dimitropoulos, G., Kremmydas, D.: Reexamining the parallelization schemes for standard full tableau simplex method on distributed memory environments. In: Proceedings of the 10th IASTED PDCN (Parallel and Distributed Computing and Networks) Conference, Innsbruck, Austria, pp. 115–123 (2011)

17.

Mamalis, B., Pantziou, G., Dimitropoulos, G., Kremmydas, D.: Highly scalable parallelization of standard simplex method on a myrinet connected cluster platform. ACTA Intl. J. Comput. Appl. 35(4), 152–161 (2013)

18.

Mamalis, B., Perlitis, M.: Hybrid parallelization of standard full tableau simplex method with MPI and OpenMP. In: Proceedings of the 18th Panhellenic Conference in Informatics (PCI 2014), ACM ICPS, October 2–4, Athens, Greece, pp. 1–6 (2014)

19.

Finkel, R.A.: Large-grain parallelism: three case studies. In: Jamieson, L.H., Gannon, D., Douglas, R.J. (eds.) The Characteristics of Parallel Algorithms, pp. 21–63. MIT Press, Cambridge (1987)

20.

Boffey, T.B., Hay, R.: Implementing parallel simplex algorithms. In: CONPAR 88, p. 169176. Cambridge University Press, Cambridge (1989)

21.

Babaev, D.A., Mardanov, S.S.: A parallel algorithm for solving linear programming problems. ZhVychislitelnoi Matematiki Matematicheskoi Fiziki 31(1), 8695 (1991) MathSciNetMATH

22.

Agrawal, A., Blelloch, G.E., Krawitz, R.L., Phillips, C.A.: Four vectormatrix primitives. In: ACM Symposium on Parallel Algorithms and Architectures, pp. 292–302 (1989)

23.

Cvetanovic, Z., Freedman, E.G., Nofsinger, C.: Efficient decomposition and performance of parallel PDE, FFT, Monte-Carlo simulations, simplex, and sparse solvers. J. Supercomput. 5, 1938 (1991) CrossRefMATH

24.

Luo, J., Reijns, G.L.: Linear programming on transputers. In: van Leeuwen, J. (ed.) Algorithms, Software, Architecture. IFIP Transactions A (Computer Science and Technology), pp. 525–534. Elsevier, Amsterdam (1992)

25.

Boduroglu, I.: Scalable massively parallel simplex algorithms for block-structured linear programs. Ph.D. thesis, GSAS, Columbia University, New York (1997)

26.

Pfefferkorn, C.E., Tomlin, J.A.: Design of a linear programming system for the ILLIAC IV. Technical report SOL 76–8. Systems Optimization Laboratory, Stanford University (1976)

27.

Helgason, R.V., Kennington, L.J., Zaki, H.A.: A parallelisation of the simplex method. Ann. Oper. Res. 14, 1740 (1988) CrossRef

28.

McKinnon, K., Plab, F.: An upper bound on parallelism in the forward transfor-mation within the revised simplex method. Technical report, Department of Mathematics and Statistics, University of Edinburgh (1997)

29.

Ho, J.K., Sundarraj, R.P.: On the efficacy of distributed simplex algorithms for linear programming. Comput. Optim. Appl. 3(4), 349363 (1994) MathSciNetCrossRefMATH

30.

Bixby, R.E., Martin, A.: Parallelizing the dual simplex method. INFORMS J. Comput. 12, 4556 (2000) MathSciNetCrossRefMATH

31.

Rosander, R.: Multiple pricing and suboptimization in dual linear programming algorithms. Math. Program. Study 4, 108–117 (1975) MathSciNetCrossRefMATH

32.

Mittelmann, H.: Benchmarks for optimization software (2014). http://plato.la.asu.edu/bench.html. Accessed 30 July 2014

33.

Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2011) CrossRefMATH

34.

Spampinato, D.G., Elster, A.C.: Linear optimization on modern GPUs. In: Proceedings of the 23rd IEEE IPDPS09 Conference, Rome, Italy (2009)

35.

Bieling, J., Peschlow, P., Martini, P.: An efficient GPU implementation of the revised simplex method. In: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium, (IPDPS 2010), Atlanta (2010)

36.

Lalami, M.E., Boyer, V., El-Baz, D.: Efficient Implementation of the simplex method on a CPU-GPU system. In: IEEE International Parallel and Distributed Processing Symposium, pp. 1994–2001 (2011)

37.

Lalami, M.E., El-Baz, D., Boyer, V.: Multi GPU implementation of the simplex algorithm. In: Proceedings of the 2011 IEEE 13th International Conference on High Performance Computing and Communications (HPCC), Banff, pp. 179–186 (2011)

38.

Meyer, X., Albuquerque, P., Chopard, B.: A multi-GPU implementation and performance model for the standard simplex method. In: Proceedings of the 1st International Symposium and 10th Bal-kan Conference on Operational Research, Thessaloniki, Greece, pp. 312–319 (2011)

39.

Ploskas, N., Samaras, N.: Efficient GPU-based implementations of simplex type algorithms. Appl. Math. Comput. 250, 552570 (2015) MATH

40.

Yarmish, G.: A distributed implementation of the simplex method. Ph.D. thesis, Polytechnic University, Brooklyn (2001)

41.

Hall, J.A., McKinnon, K.: PARSMI: a parallel revised simplex algorithm incorporating minor iterations and Devex pricing. In: Madsen, K., Olesen, D., Waśniewski, J., Dongarra, J. (eds.) PARA 1996. LNCS, vol. 1184, pp. 67–76. Springer, Heidelberg (1996)

42.

FICO Xpress Optimization Suite, A parallel simplex solver (2014). http://www.fico.com/en/products/fico-xpress-optimization-suite

Titel

Advances in the Parallelization of the Simplex Method

Buch

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_17

Autoren:

Basilis Mamalis
Grammati Pantziou

Verlag

Springer International Publishing

Sequenznummer

Premium Partner

Bildnachweise