×

zbMATH — the first resource for mathematics

mplrs: a scalable parallel vertex/facet enumeration code. (English) Zbl 1400.90222
Summary: We describe a new parallel implementation, mplrs, of the vertex enumeration code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C\({++}\) which runs on a shared memory machine. By improving load balancing we are able to greatly improve performance for medium to large scale parallelization of lrs. We report computational results comparing parallel and sequential codes for vertex/facet enumeration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested. The software that was reviewed as part of this submission is included in lrslib-062.tar.gz which has MD5 hash be5da7b3b90cc2be628dcade90c5d1b9.

MSC:
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, DP; Cobb, J; Korpela, E; Lebofsky, M; Werthimer, D, SETI@home: an experiment in public-resource computing, Commun. ACM, 45, 56-61, (2002)
[2] Anstreicher, K; Brixius, N; Goux, JP; Linderoth, J, Solving large quadratic assignment problems on computational grids, Math. Program., 91, 563-588, (2002) · Zbl 1030.90105
[3] Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: http://www.math.uwaterloo.ca/tsp/concorde.html. Accessed 6 Nov 2017
[4] Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton (2007)
[5] Assarf, B; Gawrilow, E; Herr, K; Joswig, M; Lorenz, B; Paffenholz, A; Rehn, T, Computing convex hulls and counting integer points with polymake, Math. Program. Comput., 9, 1-38, (2017) · Zbl 1370.90009
[6] Avis, D.: http://cgm.cs.mcgill.ca/ avis/C/lrs.html. Accessed 6 Nov 2017
[7] Avis, D.: A revised implementation of the reverse search vertex enumeration algorithm. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes—Combinatorics and Computation, vol. 29, pp. 177-198. DMV Seminar, Birkhäuser, Basel (2000) · Zbl 0960.68171
[8] Avis, D; Devroye, L, Estimating the number of vertices of a polyhedron, Inf. Process. Lett., 73, 137-143, (2000) · Zbl 1014.68200
[9] Avis, D., Devroye, L.: An analysis of budgeted parallel search on conditional Galton-Watson trees. arXiv:1703.10731 (2017)
[10] Avis, D; Fukuda, K, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8, 295-313, (1992) · Zbl 0752.68082
[11] Avis, D; Fukuda, K, Reverse search for enumeration, Discrete Appl. Math., 65, 21-46, (1996) · Zbl 0854.68070
[12] Avis, D., Jordan, C.: A parallel framework for reverse search using mts. arXiv:1610.07735 (2016)
[13] Avis, D., Roumanis, G.: A portable parallel implementation of the lrs vertex enumeration code. In: Combinatorial Optimization and Applications—7th International Conference, COCOA 2013, Lecture Notes in Computer Science, vol. 8287, pp. 414-429. Springer, New York (2013) · Zbl 1406.68058
[14] Bagnara, R., Hill, P.M., Zaffanella, E.: The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Sci. Comput. Program. 72(1-2), 3-21 (2008)
[15] Balyo, T., Sanders, P., Sinz, C.: HordeSat: a massively parallel portfolio SAT solver. In: Proceedings of the 18th International Conference on Theory and Applications of Satisfiability Testing (SAT 2015), Lecture Notes in Computer Science, vol. 9340, pp. 156-172 (2015) · Zbl 06512571
[16] Blumofe, RD; Leiserson, CE, Scheduling multithreaded computations by work stealing, J. ACM, 46, 720-748, (1999) · Zbl 1065.68504
[17] Brüngger, A; Marzetta, A; Fukuda, K; Nievergelt, J, The parallel search bench ZRAM and its applications, Ann. Oper. Res., 90, 45-63, (1999) · Zbl 0937.90088
[18] Bruns, W; Ichim, B; Söger, C, The power of pyramid decomposition in normaliz, J. Symb. Comput., 74, 513-536, (2016) · Zbl 1332.68298
[19] Carle, M.A.: The quest for optimality. http://www.thequestforoptimality.com. Accessed 6 Nov 2017
[20] Casado, LG; Martínez, JA; García, I; Hendrix, EMT, Branch-and-bound interval global optimization on shared memory multiprocessors, Optim. Methods Softw., 23, 689-701, (2008) · Zbl 1154.90573
[21] Ceder, G; Garbulsky, G; Avis, D; Fukuda, K, Ground states of a ternary fcc lattice model with nearest- and next-nearest-neighbor interactions, Phys. Rev. B: Condens. Matter, 49, 1-7, (1994)
[22] Christof, T., Loebel, A.: http://porta.zib.de. Accessed 6 Nov 2017
[23] Chvátal, V.: Linear Programming. W.H. Freeman, San Francisco (1983) · Zbl 0537.90067
[24] Cornuéjols, G; Karamanov, M; Li, Y, Early estimates of the size of branch-and-bound trees, INFORMS J. Comput., 18, 86-96, (2006) · Zbl 1241.90090
[25] Crainic, T.G., Le Cun, B., Roucairol, C.: Parallel Branch-and-Bound Algorithms, pp. 1-28. Wiley, New York (2006)
[26] Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Springer, New York (1997) · Zbl 0885.52001
[27] Djerrah, A., Le Cun, B., Cung, V.D., Roucairol, C.: Bob++: framework for solving optimization problems with branch-and-bound methods. In: 2006 15th IEEE International Conference on High Performance Distributed Computing, pp. 369-370 (2006)
[28] Ferrez, J; Fukuda, K; Liebling, T, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, Eur. J. Oper. Res., 166, 35-50, (2005) · Zbl 1066.90101
[29] Fischetti, M., Monaci, M., Salvagnin, D.: Self-splitting of workload in parallel computation. In: Integration of AI and OR Techniques in Constraint Programming, CPAIOR 2014, Lecture Notes in Computer Science, vol. 8451, pp. 394-404 (2014) · Zbl 06298806
[30] Fisikopoulos, V; Peñaranda, LM, Faster geometric algorithms via dynamic determinant computation, Comput. Geom., 54, 1-16, (2016) · Zbl 1338.65118
[31] Fukuda, K.: http://www.inf.ethz.ch/personal/fukudak/cdd_home. Accessed 6 Nov 2017
[32] Goux, JP; Kulkarni, S; Yoder, M; Linderoth, J, Master-worker: an enabling framework for applications on the computational grid, Clust. Comput., 4, 63-70, (2001)
[33] Graham, RL, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 416-429, (1969) · Zbl 0188.23101
[34] Grama, A; Kumar, V, State of the art in parallel search techniques for discrete optimization problems, IEEE Trans. Knowl. Data Eng., 11, 28-35, (1999)
[35] Gurobi, I.: Gurobi optimizer. http://www.gurobi.com/. Accessed 6 Nov 2017
[36] Hall, M; Knuth, DE, Combinatorial analysis and computers, Am. Math Mon., 10, 21-28, (1965) · Zbl 0127.09003
[37] Hamadi, Y., Wintersteiger, C.M.: Seven challenges in parallel SAT solving. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI’12), pp. 2120-2125 (2012)
[38] Herrera, J.F.R., Salmerón, J.M.G., Hendrix, E.M.T., Asenjo, R., Casado, L.G.: On parallel branch and bound frameworks for global optimization. J. Glob. Optim. 69(3), 547-560. https://doi.org/10.1007/s10898-017-0508-y · Zbl 1386.68213
[39] Heule, M.J., Kullmann, O., Wieringa, S., Biere, A.: Cube and conquer: guiding CDCL SAT solvers by lookaheads. In: Hardware and Software: Verification and Testing (HVC’11), Lecture Notes in Computer Science, vol. 7261, pp. 50-65 (2011)
[40] Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization (Nonconvex Optimization and Its Applications). Springer, New York (2000) · Zbl 0966.90073
[41] Hyatt, RM; Suter, BW; Nelson, HL, A parallel alpha/beta tree searching algorithm, Parallel Comput., 10, 299-308, (1989) · Zbl 0673.68043
[42] ILOG, I.: ILOG CPLEX. http://www-01.ibm.com/software/info/ilog/. Accessed 6 Nov 2017
[43] Kilby, P., Slaney, J., Thiébaux, S., Walsh, T.: Estimating search tree size. In: Proceedings of the 21st National Conference on Artificial Intelligence (AAAI’06), pp. 1014-1019 (2006)
[44] Koch, T; Ralphs, T; Shinano, Y, Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 67-93, (2012) · Zbl 1262.90106
[45] Kumar, V; Grama, AY; Vempaty, NR, Scalable load balancing techniques for parallel computers, J. Parallel Distrib. Comput., 22, 60-79, (1994)
[46] Kumar, V; Rao, VN, Parallel depth first search. part II. analysis, Int. J. Parallel Prog., 16, 501-519, (1987) · Zbl 0665.68049
[47] Malapert, A; Régin, JC; Rezgui, M, Embarrassingly parallel search in constraint programming, J. Artif. Intell. Res., 57, 421-464, (2016) · Zbl 1401.68292
[48] Marzetta, A.: ZRAM: A library of parallel search algorithms and its use in enumeration and combinatorial optimization. Ph.D. thesis, Swiss Federal Institute of Technology Zurich (1998)
[49] Mattson, T., Sanders, B., Massingill, B.: Patterns Parallel Program. Addison-Wesley Professional, Boston (2004)
[50] McCreesh, C; Prosser, P, The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound, ACM Trans. Parallel Comput., 2, 8:1-8:27, (2015) · Zbl 1328.90127
[51] Moran, B., Cohen, F., Wang, Z., Suvorova, S., Cochran, D., Taylor, T., Farrell, P., Howard, S.: Bounds on multiple sensor fusion. ACM Trans. Sensor Netw. 16(1), 16:1-16:26 (2016)
[52] Normaliz: (2015). https://www.normaliz.uni-osnabrueck.de/. Accessed 6 Nov 2017
[53] Otten, L; Dechter, R, AND/OR branch-and-bound on a computational grid, J. Artif. Intell. Res., 59, 351-435, (2017) · Zbl 1418.68189
[54] Reinders, J.: Intel Threading Building Blocks. O’Reilly & Associates, Inc., Sebastopol (2007)
[55] Reinelt, G., Wenger, K.M.: Small instance relaxations for the traveling salesman problem. In: Operations Research Proceedings 2003, Operations Research Proceedings, vol. 2003, pp. 371-378. Springer, Berlin (2004) · Zbl 1059.90125
[56] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP: a parallel extension of SCIP. Competence in High Performance Computing 2010, pp. 135-148. Springer, Berlin (2012)
[57] Shirazi, B.A., Kavi, K.M., Hurson, A.R. (eds.): Scheduling and Load Balancing in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos (1995)
[58] Weibel, C.: Implementation and parallelization of a reverse-search algorithm for Minkowski sums. In: 2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 34-42 (2010)
[59] Wilkinson, B., Allen, M.: Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall, Upper Saddle River (2005)
[60] Xu, Y.: Scalable algorithms for parallel tree search. Ph.D. thesis, Lehigh University (2007)
[61] Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995) · Zbl 0823.52002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.