A triangulation and fill-reducing initialization procedure for the simplex algorithm
Tóm tắt
The computation of an initial basis is of great importance for simplex algorithms since it determines to a large extent the number of iterations and the computational effort needed to solve linear programs. We propose three algorithms that aim to construct an initial basis that is sparse and will reduce the fill-in and computational effort during LU factorization and updates that are utilized in modern simplex implementations. The algorithms rely on triangulation and fill-reducing ordering techniques that are invoked prior to LU factorization. We compare the performance of the CPLEX 12.6.1 primal and dual simplex algorithms using the proposed starting bases against CPLEX using its default crash procedure over a set of 95 large benchmarks (NETLIB, Kennington, Mészáros, Mittelmann). The best proposed algorithm utilizes METIS (Karypis and Kumar in SIAM J Sci Comput 20:359–392, 1998), produces remarkably sparse starting bases, and results in 5% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. Although the proposed algorithm improves CPLEX’s primal simplex algorithm across all problem types studied in this paper, it performs better on hard problems, i.e., the instances for which the CPLEX default requires over 1000 s. For these problems, the proposed algorithm results in 37% reduction of the geometric mean of the execution time of CPLEX’s primal simplex algorithm. The proposed algorithm also reduces the execution time of CPLEX’s dual simplex on hard instances by 10%. For the instances that are most difficult for CPLEX, and for which CPLEX experiences numerical difficulties as it approaches the optimal solution, the best proposed algorithm speeds up CPLEX by more than 10 times. Finally, the proposed algorithms lead to a natural way to parallelize CPLEX with speedups over CPLEX’s dual simplex of 1.2 and 1.3 on two and four cores, respectively.
Tài liệu tham khảo
Al-Najjar, C., Malakooti, B.: Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods. Comput. Oper. Res. 38, 427–434 (2011)
Amestoy, P.R., Davis, T.A., Duff, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 886–905 (1996)
Andersen, E.D., Andersen, K.D.: Presolving in linear programming. Math. Program. 71, 221–245 (1995)
Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Boston (1997)
Bixby, R.E.: Implementing the simplex method: the initial basis. ORSA J. Comput. 4, 267–284 (1992)
Carstens, D.M.: Crashing techniques. In: Orchard-Hays, W. (ed.) Advanced Linear-Programming Computing Techniques, pp. 131–139. McGraw-Hill, New York (1968)
Chvátal, V.: Linear Programming. W. H. Freeman, New York (1983)
Curtis, A.R., Reid, J.K.: On the automatic scaling of matrices for Gaussian elimination. J. Inst. Math. Appl. 10, 118–124 (1972)
Dantzig, G.B.: Programming in a linear structure. Econometrica 17, 73–74 (1949)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
Davis, T.A.: Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization. ACM Trans. Math. Softw. 38, 8–29 (2011)
Davis, T.A., Gilbert, J.R., Larimore, S.I., Ng, E.G.: A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 353–376 (2004)
Davis, T.A., Gilbert, J.R., Larimore, S.I., Ng, E.G.: Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 377–380 (2004)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Elble, J.M., Sahinidis, N.V.: A review of LU factorization in the simplex algorithm. Int. J. Math. Oper. Res. 4, 319–365 (2012)
Elble, J.M., Sahinidis, N.V.: A review of the LU update in the simplex algorithm. Int. J. Math. Oper. Res. 4, 366–399 (2012)
Elble, J.M., Sahinidis, N.V.: Scaling linear optimization problems prior to application of the simplex method. Comput. Optim. Appl. 52, 345–371 (2012)
Erisman, A.M., Grimes, R.G., Lewis, J.G., Poole Jr., W.G.: A structurally stable modification of Hellerman–Rarick’s \(P^4\) algorithm for reordering unsymmetric sparse matrices. SIAM J. Numer. Anal. 22, 369–385 (1985)
Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341–374 (1992)
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)
Gilbert, J.R., Moler, C.B., Schreiber, R.: Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13, 333–356 (1992)
Goldfarb, D.: On the Bartels–Golub decomposition for linear programming bases. Math. Program. 13, 272–279 (1977)
Gould, N.I.M., Reid, J.K.: New crash procedures for large systems of linear constraints. Math. Program. 45, 475–501 (1989)
Gould, N.I.M., Toint, P.L.: Preprocessing for quadratic programming. Math. Program. 100, 95–132 (2004)
Gülpinar, N., Mitra, G., Maros, I.: Creating advanced bases for large scale linear programs exploiting embedded network structure. Comput. Optim. Appl. 21, 71–93 (2002)
Harris, P.M.J.: Pivot selection methods of the Devex LP code. Math. Program. 5, 1–28 (1973)
Huangfu, Q., Hall, J.: Parallelizing the dual revised simplex method. Math. Program. Comput. 10, 119–142 (2018)
Junior, H.V., Lins, M.P.E.: An improved initial basis for the simplex algorithm. Comput. Oper. Res. 32, 1983–1993 (2005)
Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Pol. Sci. Lett. 35, 355–357 (1937)
Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359–392 (1998)
Lenstra, J.K., Rinnoy Kan, A.H.G., Schrijver, A. (eds.): History of Mathematical Programming. CWI North Holland, Amsterdam (1991)
Luh, H., Tsaih, R.: An efficient search direction for linear programming problems. Comput. Oper. Res. 29, 195–203 (2002)
Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manag. Sci. 3, 255–269 (1957). (Originally at The RAND Corporation, Research Memorandum RM-1452, 1955)
Maros, I.: Computational Techniques of the Simplex Method. Kluwer Academic Publishers, Boston (2003)
Maros, I., Mitra, G.: Strategies for creating advanced bases for large-scale linear programming problems. INFORMS J. Comput. 10, 248–260 (1998)
Mészáros, C., Suhl, U.H.: Advanced preprocessing techniques for linear and quadratic programming. OR Spectr. 25, 575–595 (2003)
Murtagh, B.A., Saunders, M.A.: MINOS 5.1 User’s Guide. Technical report, Department of Operations Research, Stanford University, Stanford, CA (1987)
Nabli, H.: An overview on the simplex algorithm. Appl. Math. Comput. 210, 479–489 (2009)
Nabli, H., Chahdoura, S.: Algebraic simplex initialization combined with the nonfeasible basis methods. Eur. J. Oper. Res. 245, 384–391 (2015)
Pan, P.Q.: Linear Programming Computation. Springer, Berlin (2014)
Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola (1998)
Ploskas, N., Samaras, N.: GPU accelerated pivoting rules for the simplex algorithm. J. Syst. Softw. 96, 1–9 (2014)
Ploskas, N., Samaras, N.: A computational comparison of scaling techniques for linear optimization problems on a graphical processing unit. Int. J. Comput. Math. 92, 319–336 (2015)
Terlaky, T., Zhang, S.: Pivot rules for linear programming: a survey on recent theoretical developments. Ann. Oper. Res. 46, 203–233 (1993)
Tomlin, J.A.: An accuracy test for updating triangular factors. Math. Program. Study 4, 142–145 (1975)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2, 77–79 (1981)
Ye, Y.: Eliminating columns in the simplex method for linear-programming. J. Optim. Theory Appl. 63, 69–77 (1989)