×

A parallel interior point algorithm for linear programming on a network of transputers. (English) Zbl 0784.90048

Summary: Interior point algorithms have become a very successful tool for solving large-scale linear programming problems. The dual affine algorithm is one of the interior point algorithms implemented in the computer program OB1. It is a good candidate for implementation on a parallel computer because it is very computing-intensive. A parallel dual affine algorithm is presented which is suitable for a parallel computer with a distributed memory. The algorithm obtains its speedup from parallel sparse linear algebra computations such as Cholesky factorization, matrix multiplication, and triangular system solving, which form the bulk of the computing work. Efficient algorithms based on the grid distribution of matrices are presented for each of these computations. The algorithm is implemented in occam 2 on a square mesh of transputers. The resulting parallel program is connected to the sequential FORTRAN 77 program OB1, which performs the preprocessing and the postprocessing. Experimental results on a mesh of 400 transputers are given for a test set of seven realistic planning and scheduling problems from Shell and seven problems from the NETLIB LP collection; the results show a speedup of 88 for the largest problem.

MSC:

90C05 Linear programming
90C06 Large-scale problems in mathematical programming
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, Data structures and programming techniques for the implementation of Karmarkar’s algorithm, ORSA J. Comput. 1(1989)84–106. · Zbl 0752.90043
[2] I. Adler, M.G.C. Resende, G. Veiga and N. Karmarkar, An implementation of Karmarkar’s algorithm for linear programming, Math. Progr. 44(1989)297–335. · Zbl 0682.90061 · doi:10.1007/BF01587095
[3] E. Anderson and Y. Saad, Solving sparse triangular linear systems on parallel computers, Int. J. High Speed Comput. 1(1989)73–95. · Zbl 0726.65026 · doi:10.1142/S0129053389000056
[4] C. Ashcraft, S.C. Eisenstat and J.W.H. Liu, A fan-in algorithm for distributed sparse numerical factorization, SIAM J. Sci. Stat. Comput. 11(1990)593–599. · Zbl 0724.65024 · doi:10.1137/0911033
[5] C. Ashcraft, S.C. Eisenstat, J.W.H. Liu and A.H. Sherman, A comparison of three column-based distributed sparse factorization schemes, Technical Report CS-90-09, Dept. of Computer Science, York University, North York, Ontario, Canada (1990).
[6] R.H. Bisseling and J.G.G. van de Vorst, Parallel LU decomposition on a transputer network, in:Lecture Notes in Computer Science 384 (Springer, Berlin, 1989) pp. 61–77.
[7] R.H. Bisseling and J.G.G. van de Vorst, Parallel triangular system solving on a mesh network of transputers, SIAM J. Sci. Stat. Comput. 12(1991)787–799. · Zbl 0734.65015 · doi:10.1137/0912041
[8] I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Oxford University Press, Oxford, UK, 1986). · Zbl 0604.65011
[9] G.C. Fox, M.A. Johnson, G.A. Lyzenga, S.W. Otto, J.K. Salmon and D.W. Walker,Solving Problems on Concurrent Processors, Vol. 1 (Prentice-Hall, Englewood Cliffs, NJ, 1988).
[10] D.M. Gay, Electronic mail distribution of linear programming test problems, Math. Progr. Soc. COAL Newsl. 13(Dec. 1985)10–12.
[11] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10(1973)345–363. · Zbl 0259.65087 · doi:10.1137/0710032
[12] A. George, M.T. Heath, J. Liu and E. Ng, Sparse Cholesky factorization on a local-memory multiprocessor, SIAM J. Sci. Stat. Comput. 9(1988)327–340. · Zbl 0642.65018 · doi:10.1137/0909021
[13] A. George and J.W.H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Rev. 31(1989)1–19. · Zbl 0671.65024 · doi:10.1137/1031001
[14] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, A note on nonlinear approaches to linear programming, Technical Report SOL 86-7, Department of Operations Research, Standford University, Stanford, CA (1986). · Zbl 0624.90062
[15] G.H. Golub and C.F. Van Loan,Matrix Computations, 2nd ed. (The Johns Hopkins University Press, Baltimore, MD, 1989). · Zbl 0733.65016
[16] M.T. Heath, E. Ng and B.W. Peyton, Parallel algorithms for sparse linear systems, SIAM Rev. 33(1991)420–460. · Zbl 0738.65014 · doi:10.1137/1033099
[17] R.V. Helgason, J.L. Kennington and H.A. Zaki, A parallelization of the Simplex method, Ann. Oper. Res. 14(1988)17–40. · doi:10.1007/BF02186472
[18] Inmos Ltd.,occam 2 Reference Manual (Prentice-Hall, Hemel Hempstead, UK, 1988).
[19] S.L. Johnsson, Communication efficient basic linear algebra computations on hypercube architectures, J. Parallel Distr. Comput. 4(1987)133–172. · doi:10.1016/0743-7315(87)90002-5
[20] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(1984)373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[21] D.E. Knuth,The Art of Computer Programming, Vol. 1, 2nd ed. (Addison-Wesley, Reading, MA, 1973). · Zbl 0191.17903
[22] M. Kojima, S. Mizuno and A. Yoshise, A Primal-Dual Interior Point algorithm for linear programming, in: N. Megiddo (ed.),Progress in Mathematical Programming, (Springer, New York, 1988) pp. 29–47. · Zbl 0708.90049
[23] R. Levkovitz and G. Mitra, Solution of large sparse symmetric equations on a transputer network, in:Proc. 3rd Int. Conf. on Applications of Transputers, T.S. Durrani et al. (eds.), (IOS Press, Amsterdam, 1991) pp. 105–110.
[24] R. Levkovitz and G. Mitra, Cholesky factorization of sparse symmetric positive definite matrices on distributed parallel computers, in:Transputing in Numerical and Neural Network Applications, ed. G.L. Reijns and J. Luo (IOS Press, Amsterdam, 1992) pp. 30–47.
[25] J.W.H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Softw. 11(1985)141–153. · Zbl 0568.65015 · doi:10.1145/214392.214398
[26] J.W.H. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Trans. Math. Softw. 12(1986)127–148. · Zbl 0605.65015 · doi:10.1145/6497.6499
[27] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11(1990)134–172. · Zbl 0697.65013 · doi:10.1137/0611010
[28] L.D.J.C. Loyens, A design method for parallel programs, Ph.D. Thesis, Dept. of Mathematics and Computing Science, Edindhoven University of Technology, The Netherlands (1992). · Zbl 0762.68045
[29] L.D.J.C. Loyens and R.H. Bisseling, The formal construction of a parallel triangular system solver, in:Lecture Notes in Computer Science 375 (Springer, Berlin, 1989) pp. 325–334.
[30] I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a Primal-Dual Interior Point method for linear programming, Lin. Alg. Appl. 152(1991)191–222. · Zbl 0731.65049 · doi:10.1016/0024-3795(91)90275-2
[31] I.J. Lustig, R.E. Marsten and D.F. Shanno, On implementing Mehrotra’s predictor-corrector Interior-Point method for linear programming, SIAM J. Optim. 2(1992)435–449. · Zbl 0771.90066 · doi:10.1137/0802022
[32] R.E. Marsten, M.J. Saltzman, D.F. Shanno, G.S. Pierce and J.F. Ballintijn, Implementation of a Dual Affine Interior Point algorithm for linear programming, ORSA J. Comput. 1(1989)287–297. · Zbl 0752.90046
[33] R. Marsten, R. Subramanian, M. Saltzman, I. Lustig and D. Shanno, Interior Point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick!, Interfaces 20(1990)105–116. · doi:10.1287/inte.20.4.105
[34] S. Mehrotra, On the implementation of a Primal-Dual Interior Point method, SIAM J. Optim. 2(1992)575–601. · Zbl 0773.90047 · doi:10.1137/0802028
[35] D.P. O’Leary and G.W. Stewart, Data-flow algorithms for parallel matrix computations, Commun. ACM 28(1985)840–853. · Zbl 0606.65029 · doi:10.1145/4021.4025
[36] R. Schreiber, A new implementation of sparse Gaussian elimination, ACM Trans. Math. Softw. 8(1982)256–276. · Zbl 0491.65013 · doi:10.1145/356004.356006
[37] A.F. van der Stappen, R.H. Bisseling and J.G.G. van de Vorst, Parallel sparse LU decomposition on a mesh network of transputers, SIAM J. Matrix Anal. Appl. 14(1993)853–879. · Zbl 0783.65022 · doi:10.1137/0614059
[38] C.B. Stunkel and D.A. Reed, Hypercube implementation of the Simplex algorithm, in:Proc. 3rd Conf. on Hypercube Concurrent Computers and Applications, Vol. 2, G. Fox (ed.) ACM Press, New York, 1988) pp. 1473–1482.
[39] J.A. Tomlin, An experimental approach to Karmarkar’s projective method for linear programming, Math. Progr. Study 31(1987)175–191. · Zbl 0634.90044
[40] J.G.G. van de Vorst, The formal development of a parallel program performing LU-decomposition, Acta Inform. 26(1988)1–17. · Zbl 0633.65007 · doi:10.1007/BF02915443
[41] J.G.G. van de Vorst, Solving the least squares problem using a parallel linear algebra library, Future Generation Comp. Syst. 4(1989)293–297. · doi:10.1016/0167-739X(89)90006-X
[42] J.G.G. van de Vorst, An attempt to use parallel computing in large scale optimisation, in:Logistics: where ends have to meet, C.F.H. van Rijn (ed.) (Pergamon Press, Oxford, UK, 1989) pp. 112–119.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.