×

Parallel distributed-memory simplex for large-scale stochastic LP problems. (English) Zbl 1276.90044

Summary: We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g. in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.

MSC:

90C15 Stochastic programming
90C05 Linear programming
90C49 Extreme-point and pivoting methods

Software:

DEVEX; PIPS; CSparse; SUTIL
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Amdahl, G. M., Validity of the single processor approach to achieving large scale computing capabilities, 483-485 (1967), New York · doi:10.1145/1465482.1465560
[2] Aykanat, C., Pinar, A., Çatalyürek, U.V.: Permuting sparse rectangular matrices into block-diagonal form. SIAM J. Sci. Comput. 25, 1860-1879 (2004) · Zbl 1070.65027 · doi:10.1137/S1064827502401953
[3] Bennett, J.M.: An approach to some structured linear programming problems. Oper. Res. 14(4), 636-645 (1966) · Zbl 0143.42203 · doi:10.1287/opre.14.4.636
[4] Birge, J., Louveaux, F.: Introduction to Stochastic Programming, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2011) · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[5] Bisschop, J., Meeraus, A.: Matrix augmentation and partitioning in the updating of the basis inverse. Math. Program. 13, 241-254 (1977) · Zbl 0372.90083 · doi:10.1007/BF01584341
[6] Dantzig, G.B., Orchard-Hays, W.: The product form for the inverse in the simplex method. Math. Tables Other Aids Comput. 8(46), 64-67 (1954) · Zbl 0055.35103 · doi:10.2307/2001993
[7] Davis, T.: Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (2006) · Zbl 1119.65021 · doi:10.1137/1.9780898718881
[8] Duff, I.S., Scott, J.A.: A parallel direct solver for large sparse highly unsymmetric linear systems. ACM Trans. Math. Softw. 30, 95-117 (2004) · Zbl 1072.65038 · doi:10.1145/992200.992201
[9] Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341-374 (1992) · Zbl 0787.90047 · doi:10.1007/BF01581089
[10] Forrest, J.J.H., Tomlin, J.A.: Updated triangular factors of the basis to maintain sparsity in the product form simplex method. Math. Program. 2, 263-278 (1972) · Zbl 0288.90048 · doi:10.1007/BF01584548
[11] Gilbert, J.R., Peierls, T.: Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Stat. Comput. 9, 862-874 (1988) · Zbl 0656.65036 · doi:10.1137/0909058
[12] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A practical anti-cycling procedure for linearly constrained optimization. Math. Program. 45, 437-474 (1989) · Zbl 0688.90038 · doi:10.1007/BF01589114
[13] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[14] Gondzio, J., Grothey, A.: Exploiting structure in parallel implementation of interior point methods for optimization. Comput. Manag. Sci. 6, 135-160 (2009) · Zbl 1170.90518 · doi:10.1007/s10287-008-0090-3
[15] Grama, A., Karypis, G., Kumar, V., Gupta, A.: Introduction to Parallel Computing, 2nd edn. Addison-Wesley, Reading (2003) · Zbl 0861.68040
[16] Gropp, W., Thakur, R., Lusk, E.: Using MPI-2: Advanced Features of the Message Passing Interface, 2nd edn. MIT Press, Cambridge (1999)
[17] Hall, J., McKinnon, K.: Hyper-sparsity in the revised simplex method and how to exploit it. Comput. Optim. Appl. 32, 259-283 (2005) · Zbl 1125.90033 · doi:10.1007/s10589-005-4802-0
[18] Hall, J.A.J., Smith, E.: A high performance primal revised simplex solver for row-linked block angular linear programming problems. Tech. Rep. ERGO-12-003, School of Mathematics, University of Edinburgh (2012) · Zbl 0688.90038
[19] Harris, P.M.J.: Pivot selection methods of the DEVEX LP code. Math. Program. 5, 1-28 (1973) · Zbl 0261.90031 · doi:10.1007/BF01580108
[20] Kall, P.: Computational methods for solving two-stage stochastic linear programming problems. Z. Angew. Math. Phys. 30, 261-271 (1979) · Zbl 0411.90056 · doi:10.1007/BF01601939
[21] Koberstein, A.: The dual simplex method, techniques for a fast and stable implementation. Ph.D. thesis, Universität Paderborn, Paderborn, Germany (2005) · Zbl 1198.90010
[22] Koberstein, A.: Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation. Comput. Optim. Appl. 41, 185-204 (2008) · Zbl 1168.90555 · doi:10.1007/s10589-008-9207-4
[23] Lasdon, L.S.: Optimization Theory for Large Systems. Macmillan, New York (1970) · Zbl 0224.90038
[24] Linderoth, J., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Comput. Optim. Appl. 24, 207-250 (2003) · Zbl 1094.90026 · doi:10.1023/A:1021858008222
[25] Lubin, M.; Petra, C. G.; Anitescu, M.; Zavala, V., Scalable stochastic optimization of complex energy systems, 64:1-64:64 (2011), New York
[26] Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manag. Sci. 3(3), 255-269 (1957) · Zbl 0995.90592 · doi:10.1287/mnsc.3.3.255
[27] Maros, I.: Computational Techniques of the Simplex Method. Kluwer Academic, Norwell (2003) · Zbl 1140.90033 · doi:10.1007/978-1-4615-0257-9
[28] Stern, J., Vavasis, S.: Active set methods for problems in column block angular form. Comput. Appl. Math. 12, 199-226 (1993) · Zbl 0802.90072
[29] Strazicky, B., Some results concerning an algorithm for the discrete recourse problem, 263-274 (1980), London
[30] Suhl, L.M., Suhl, U.H.: A fast LU update for linear programming. Ann. Oper. Res. 43, 33-47 (1993) · Zbl 0784.90049 · doi:10.1007/BF02025534
[31] Suhl, U.H., Suhl, L.M.: Computing sparse LU factorizations for large-scale linear programming bases. ORSA J. Comput. 2(4), 325 (1990) · Zbl 0755.90059 · doi:10.1287/ijoc.2.4.325
[32] Vladimirou, H., Zenios, S.: Scalable parallel computations for large-scale stochastic programming. Ann. Oper. Res. 90, 87-129 (1999) · Zbl 0937.90077 · doi:10.1023/A:1018977102079
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.