SelfSplit parallelization for mixed-integer linear programming. (English) Zbl 1391.90429
Summary: SelfSplit is a simple static mechanism to convert a sequential tree-search code into a parallel one. In this paradigm, tree-search is distributed among a set of identical workers, each of which is able to autonomously determine – without any communication with the other workers – the job parts it has to process. SelfSplit already proved quite effective in parallelizing constraint programming solvers. In the present paper, we investigate the performance of SelfSplit when applied to a mixed-integer linear programming (MILP) solver. Both ad-hoc and general purpose MILP codes have been considered. Computational results show that SelfSplit, in spite of its simplicity, can achieve good speedups even in the MILP context.
MSC:
| 90C11 | Mixed integer programming |
| 65K05 | Numerical mathematical programming methods |
| 65Y05 | Parallel numerical computation |
Keywords:
parallel computing; enumerative algorithms; mixed-integer programming; computational analysisReferences:
| [1] | Achterberg, T.; Wunderling, R., Mixed integer programming: analyzing 12 years of progress, Facets of Combinatorial Optimization, 449-481, (2013) · Zbl 1317.90206 |
| [2] | Anstreicher, K. M.; Brixius, N. W.; Goux, J.-P.; Linderoth, J., Solving large quadratic assignment problems on computational grids, Math. Progr., 91, 3, 563-588, (2002) · Zbl 1030.90105 |
| [3] | Balas, E.; Fischetti, M., A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets, Math. Progr., 58, 1-3, 325-352, (1993) · Zbl 0780.90100 |
| [4] | Balas, E.; Fischetti, M., Lifted cycle inequalities for the asymmetric traveling salesman problem, Math. Oper. Res., 24, 2, 273-292, (1999) · Zbl 0977.90040 |
| [5] | Balas, E.; Fischetti, M., Polyhedral theory for the asymmetric traveling salesman problem, The Traveling Salesman Problem and its Variations, 117-168, (2007), Springer US · Zbl 1113.90349 |
| [6] | Bordeaux, L.; Hamadi, Y.; Samulowitz, H., Experiments with massively parallel constraint solving, (Boutilier, C., Proceedings of the IJCAI, (2009)), 443-448 |
| [7] | Bussieck, M. R.; Ferris, M. C.; Meeraus, A., Grid-enabled optimization with GAMS, INFORMS J Comput, 21, 3, 349-362, (2009) · Zbl 1243.90255 |
| [8] | Carvajal, R.; Shabbir, A.; Nemhauser, G.; Furman, K.; Goel, V.; Shao, Y., Using diversification, communication and parallelism to solve mixed-integer linear programs, Oper. Res. Lett., 42, 186-189, (2014) · Zbl 1408.90194 |
| [9] | Chen, Q.; Ferris, M. C.; Linderoth, J., FATCOP 2.0: advanced features in an opportunistic mixed integer programming solver, Ann. OR, 103, 1-4, 17-32, (2001) · Zbl 1039.90046 |
| [10] | Chu, G.; Schulte, C.; Stuckey, P. J., Confidence-based work stealing in parallel constraint programming, (Gent, I. P., Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming, (2009), Springer), 226-241 |
| [11] | Cornuéjols, G.; Karamanov, M.; Li, Y., Early estimates of the size of branch-and-bound trees, INFORMS J. Comput., 18, 1, 86-96, (2006) · Zbl 1241.90090 |
| [12] | Dean, J.; Ghemawat, S., Mapreduce: simplified data processing on large clusters, CACM, 51, 1, 107-113, (2008) |
| [13] | Eckstein J., Philips C., Hart W. (2006) PEBBL 1.0 User Guide. RUTCOR Research Report RRR 19-2006. http://rutcor.rutgers.edu/pub/rrr/reports2006/19_2006.ps; Eckstein J., Philips C., Hart W. (2006) PEBBL 1.0 User Guide. RUTCOR Research Report RRR 19-2006. http://rutcor.rutgers.edu/pub/rrr/reports2006/19_2006.ps |
| [14] | El-Dessouki, O. I.; Huen, W. H., Distributed enumeration on between computers, IEEE Trans. Comput., C-29, 9, 818-825, (1980) |
| [15] | Fischetti, M., Facets of the asymmetric traveling salesman polytope, Math. Oper. Res., 16, 1, 42-56, (1991) · Zbl 0742.90079 |
| [16] | Fischetti, M.; Ljubić, I.; Sinnl, M., Redesigning benders decomposition for large scale facility location, Manag. Sci., 63, 2146-2162, (2016) |
| [17] | Fischetti, M.; Lodi, A.; Toth, P., Exact methods for the asymmetric traveling salesman problem, The Traveling Salesman Problem and its Variations, 169-205, (2007), Springer US · Zbl 1113.90351 |
| [18] | Fischetti, M.; Monaci, M., Exploiting erraticism in search, Oper. Res., 62, 114-122, (2014) · Zbl 1291.90148 |
| [19] | Fischetti, M.; Monaci, M.; Salvagnin, D., Self-splitting of workload in parallel computation, Proceedings of the International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, 8451, 394-404, (2014), Springer US |
| [20] | Fischetti, M.; Toth, P., An additive bounding procedure for the asymmetric travelling salesman problem, Math. Progr., 53, 173-197, (1992) · Zbl 0773.90082 |
| [21] | Fischetti, M.; Toth, P., A polyhedral approach to the asymmetric traveling salesman problem, Manag. Sci., 43, 11, 1520-1536, (1997) · Zbl 0902.90159 |
| [22] | Gecode Team, 2012. Gecode: generic constraint development environment. Available at http://www.gecode.org; Gecode Team, 2012. Gecode: generic constraint development environment. Available at http://www.gecode.org |
| [23] | Gendron, B.; Crainic, T. G., Parallel branch-and-branch algorithms: survey and synthesis, Oper. Res., 42, 6, 1042-1066, (1994) · Zbl 0824.90096 |
| [24] | Gent, I. P.; Jefferson, C.; Miguel, I.; Moore, N. C.; Nightingale, P.; Prosser, P.; Unsworth, C., A preliminary review of literature on parallel constraint solving, Proceedings Workshop on Parallel Methods for Constraint Solving (PMCS), (2011) |
| [25] | Gomes, C. P.; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. Autom. Reason., 24, 67-100, (2000) · Zbl 0967.68145 |
| [26] | Grama, A.; Kumar, V., State of the art in parallel search techniques for discrete optimization problems, IEEE Trans. Knowl. Data Eng., 11, 1, 28-35, (1999) |
| [27] | Harvey, W. D.; Ginsberg, M. L., Limited discrepancy search, Proceedings of the International Joint Conference on Artificial Intelligence, 607-615, (1995) |
| [28] | Henrich, D., 1993. “Initialization of parallel branch-and-bound algorithms”, Workshop on Parallel Processing in Artificial Intelligence (PPAI-93), Aug. 28, Chambery, France.; Henrich, D., 1993. “Initialization of parallel branch-and-bound algorithms”, Workshop on Parallel Processing in Artificial Intelligence (PPAI-93), Aug. 28, Chambery, France. |
| [29] | Knuth, D. E., Estimating the efficiency of backtrack programs, Math. Comput., 29, 129, 121-136, (1975) · Zbl 0297.68037 |
| [30] | Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R. E.; Danna, E.; Gamrath, G.; Gleixner, A. M.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, D. E.; Wolter, K., MIPLIB 2010 - mixed integer programming library version 5, Math. Progr. Comput., 3, 103-163, (2011) |
| [31] | Koch, T.; Ralphs, T. K.; Shinano, Y., Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 1, 67-93, (2012) · Zbl 1262.90106 |
| [32] | Körkel, M., On the exact solution of large-scale simple plant location problems, Eur. J. Oper. Res., 39, 2, 157-173, (1989) · Zbl 0673.90032 |
| [33] | Laursen, P. S., Can parallel branch and bound without communication be effective, SIAM J. Optim., 4, 2, 288-296, (1994) · Zbl 0806.65061 |
| [34] | Michel, L.; See, A.; Hentenryck, P. V., Transparent parallelization of constraint programming, INFORMS J. Comput., 21, 3, 363-382, (2009) · Zbl 1243.90008 |
| [35] | Miller, D.; Pekny, J., Results from a parallel branch and bound algorithm for the asymmetric traveling salesman problem, Oper. Res. Lett., 8, 129-135, (1989) · Zbl 0668.90089 |
| [36] | Mohan, J., A study in parallel computation: the traveling salesman problem, Technical Report, (1982), Computer Science Department. Carnagie-Mellon University, Pittsburgh, Penn. |
| [37] | Moisan, T.; Gaudreault, J.; Quimper, C.-G., Parallel discrepancy-based search, (Schulte, C., Proceedings of the International Conference on Principles and Practice of Constraint Programming, (2013), Springer Berlin Heidelberg), 30-46 |
| [38] | Özaltin, O. Y.; Hunsaker, B.; Schaefer, A. J., Predicting the solution time of branch-and-bound algorithms for mixed-integer programs, INFORMS J. Comput., 23, 3, 392-403, (2011) · Zbl 1243.90251 |
| [39] | Pekny, J.; Miller, D., A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, Math. Progr., 55, 17-33, (1992) · Zbl 0758.90075 |
| [40] | Ralphs, T.; Shinano, Y.; Berthold, T.; Koch, T., Parallel solvers for mixed integer linear optimization, Technical Report, (2017), COR@L |
| [41] | Régin, J.-C.; Rezgui, M.; Malapert, A., Embarrassingly parallel search, (Schulte, C., Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 8124, (2013), Springer Berlin Heidelberg), 596-610 · Zbl 1284.68030 |
| [42] | Sanders, P., Randomized receiver initiated load-balancing algorithms for tree-shaped computations, Comput. J., 45, 5, 561-573, (2002) · Zbl 1089.68664 |
| [43] | Shinano, Y.; Heinz, S.; Vigerske, S.; Winkler, M., Fiberscip - a shared memory parallelization of SCIP, INFORMS J. Comput., 30, 1, 11-30, (2018) · Zbl 1528.90165 |
| [44] | Tukey, J. W., Exploratory Data Analysis, (1977), Addison-Wesley · Zbl 0409.62003 |
| [45] | Vornberger, O., Implementing branch-and-bound in a ring of processors, Proceedings of the International Conference on Parallel Processing, 157-164, (1986), Springer |
| [46] | Xu, Y.; Ralphs, T. K.; Ladányi, L.; Saltzmann, M. J., Computational experience with a software framework for parallel integer programming, INFORMS J. Comput., 21, 3, 383-397, (2009) · Zbl 1243.90010 |
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.
