×

zbMATH — the first resource for mathematics

A review of literature on parallel constraint solving. (English) Zbl 1452.68177
Summary: As multi-core computing is now standard, it seems irresponsible for constraints researchers to ignore the implications of it. Researchers need to address a number of issues to exploit parallelism, such as: investigating which constraint algorithms are amenable to parallelisation; whether to use shared memory or distributed computation; whether to use static or dynamic decomposition; and how to best exploit portfolios and cooperating search. We review the literature, and see that we can sometimes do quite well, some of the time, on some instances, but we are far from a general solution. Yet there seems to be little overall guidance that can be given on how best to exploit multi-core computers to speed up constraint solving. We hope at least that this survey will provide useful pointers to future researchers wishing to correct this situation.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W10 Parallel algorithms in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M.; Biere, A.; Kirsch, C. M.; Niemetz, A.; Preiner, M., (2013)
[2] Akgün, Ö., Extensible Automated Constraint Modelling via Refinement of Abstract Problem Specifications, (2014), University of St Andrews
[3] Akgün, Ö.; Frisch, A. M.; Gent, I. P.; Hussain, B. S.; Jefferson, C.; Kotthoff, L.; Miguel, I.; Nightingale, P., International Conference on Principles and Practice of Constraint Programming, Automated symmetry breaking and model selection in CONJURE, 107-116, (2013), Springer
[4] Akgün, Ö.; Gent, I. P.; Jefferson, C.; Miguel, I.; Nightingale, P., (2014)
[5] Akgün, Ö.; Miguel, I.; Jefferson, C., (2010)
[6] Akgün, Ö.; Miguel, I.; Jefferson, C.; Frisch, A. M.; Hnich, B., (2011)
[7] Amadini, R.; Gabbrielli, M.; Mauro, J., (2015)
[8] Amadini, R.; Gabbrielli, M.; Mauro, J., (2015)
[9] Arbelaez, A.; Codognet, P., (2012)
[10] Arbelaez, A.; Codognet, P., (2013)
[11] Arbelaez, A.; Codognet, P., (2014)
[12] Arbelaez, A.; Hamadi, Y., (2011)
[13] Audemard, G.; Hoessen, B.; Jabbour, S.; Lagniez, J.-M.; Piette, C., (2012)
[14] Audemard, G.; Simon, L., (2014)
[15] Bader, D. A.; Hart, W. E.; Phillips, C. A., Tutorials on Emerging Methodologies and Applications in Operations Research, Parallel algorithm design for branch and bound, 1-44, (2005), International Series in Operations Research & Management Science: International Series in Operations Research & Management Science, Springer, New York, NY, USA
[16] Balyo, T.; Sanders, P.; Sinz, C., (2015)
[17] Baudot, B.; Deville, Y., (1997)
[18] Bergman, D.; Cire, A. A.; Sabharwal, A.; Samulowitz, H.; Saraswat, V.; Van Hoeve, W.-J., (2014)
[19] Biere, A., (2010)
[20] Biere, A.; Balint, A.; Belov, A.; Heule, M.; Järvisalo, M., (2013)
[21] Bordeaux, L.; Hamadi, Y.; Samulowitz, H., (2009)
[22] Campeotto, F.; Dal Palù, A.; Dovier, A.; Fioretto, F.; Pontelli, E., (2014)
[23] Campeotto, F.; Dovier, A.; Fioretto, F.; Pontelli, E., (2014)
[24] Caniou, Y.; Codognet, P.; Diaz, D.; Abreu, S., (2011)
[25] Caniou, Y.; Codognet, P.; Richoux, F.; Diaz, D.; Abreu, S., Large-scale parallelism for constraint-based local search: the costas array case study, Constraints, 20, 1, 30-56, (2015) · Zbl 1316.90040
[26] Charnley, J.; Colton, S.; Miguel, I., (2006)
[27] Chrabakh, W.; Wolski, R., GridSAT: A system for solving satisfiability problems using a computational grid, Parallel Computing, 32, 9, 660-687, (2006)
[28] Chu, G.; Schulte, C.; Stuckey, P., Principles and Practices of Constraint Programming, 226-241, (2009), Springer
[29] Chu, G.; Stuckey, P. J.; Harwood, A., (2008)
[30] Cire, A. A.; Kadioglu, S.; Sellmann, M., (2014)
[31] Clearwater, S. H.; Huberman, B. A.; Hogg, T., Cooperative solution of constraint satisfaction problems, Science, 254, 1181-1183, (1991)
[32] Clocksin, W., Principles of the Delphi parallel inference machine, The Computer Journal, 30, 5, 386-392, (1987)
[33] Colton, S.; Miguel, I., (2001)
[34] Crainic, T. G.; Le Cun, B.; Roucairol, C., Parallel Combinatorial Optimization, 1-28, (2006), John Wiley & Sons: John Wiley & Sons, Hoboken, NJ, USA
[35] Dal Palù, A.; Dovier, A.; Formisano, A.; Pontelli, E., CUD@SAT: SAT solving on GPUs, Journal of Experimental & Theoretical Artificial Intelligence, 27, 293-316, (2015)
[36] Davenport, A. J.; Tsang, E. P. K.; Wang, C. J.; Zhu, K., (1994)
[37] De Bruin, A.; Kindervater, G. A. P.; Trienekens, H. W. J. M.; Ferreira, A.; Rolim, J. D. P., (1995)
[38] Diaz, D., (2001)
[39] Diaz, D.; Abreu, S.; Codognet, P., Targeting the cell broadband engine for constraint-based local search, Concurrency and Computation: Practice and Experience, 24, 6, 647-660, (2012)
[40] Dovier, A.; Formisano, A.; Pontelli, E.; Vella, F., (2016)
[41] Drakakis, K., A review of Costas arrays, Journal of Applied Mathematics, 2006, 32, (2006) · Zbl 1188.94028
[42] Ehlers, T.; Stuckey, P. J., (2016)
[43] Faltings, B.; Rossi, Francesca; Van Beek, Peter; Walsh, Toby, (2006)
[44] Fioretto, F.; Le, T.; Pontelli, E.; Yeoh, W.; Son, T. C., (2015)
[45] Fioretto, F.; Le, T.; Yeoh, W.; Pontelli, E.; Son, T. C., (2014)
[46] Fioretto, F.; Yeoh, W.; Pontelli, E., (2016)
[47] Fischetti, M.; Monaci, M.; Salvagnin, D.; Simonis, H., (2014)
[48] Flener, P.; Frisch, A.; Hnich, B.; Kiziltan, Z.; Miguel, I.; Pearson, J.; Walsh, T., (2001)
[49] Flener, P.; Frisch, A. M.; Hnich, B.; Kiziltan, Z.; Miguel, I.; Walsh, T., (2002)
[50] Freuder, E. C., A sufficient condition for backtrack-free search, Journal of the ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[51] Frisch, A. M.; Grum, M.; Jefferson, C.; Hernández, B. M.; Miguel, I., (2005)
[52] Frisch, A. M.; Grum, M.; Jefferson, C.; Hernández, B. M.; Miguel, I., (2007)
[53] Frisch, A. M.; Harvey, W.; Jefferson, C.; Hernández, B. M.; Miguel, I., Essence: A constraint language for specifying combinatorial problems, Constraints, 13, 3, 268-306, (2008) · Zbl 1147.68424
[54] Frisch, A. M.; Jefferson, C.; Hernández, B. M.; Miguel, I., (2007)
[55] Frisch, A. M.; Jefferson, C.; Miguel, I., (2004)
[56] Frühwirth, T. W.; Michel, L.; Schulte, C.; Rossi, Francesca; Van Beek, Peter; Walsh, Toby, Handbook of Constraint Programming, Foundations of Artificial Intelligence, Constraints in procedural and concurrent languages, 453-494, (2006)
[57] Furukawa, K.; Ueda, K.; Nori, K. V.; Kumar, S., (1988)
[58] Garcia, V.; Debreuve, E.; Barlaud, M., (2008)
[59] (2006)
[60] Gent, I. P.; Jefferson, C.; Miguel, I.; Moore, N. C. A.; Nightingale, P.; Prosser, P.; Unsworth, C., (2011)
[61] Gent, I. P.; Miguel, I.; Rendl, A., (2008)
[62] Gharbi, N., (2015)
[63] Gomes, C. P.; Selman, B., Algorithm portfolios, Artificial Intelligence, 126, 1-2, 43-62, (2001) · Zbl 0969.68047
[64] Granvilliers, L.; Hains, G., A conservative scheme for parallel interval narrowing, Information Processing Letters, 74, 3-4, 141-146, (2000) · Zbl 1339.65252
[65] Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A., Asymmetric distributed constraint optimization problems, Journal of Artificial Intelligence Research, 47, 613-647, (2013) · Zbl 1269.68101
[66] Guo, L.; Hamadi, Y.; Jabbour, S.; Sais, L., (2010)
[67] Gustafson, J. L., Reevaluating Amdahl’s law, Communications of the ACM, 31, 5, 532-533, (1988)
[68] Hamadi, Y., Optimal distributed arc-consistency, Constraints, 7, 3-4, 367-385, (2002) · Zbl 1028.68155
[69] Hamadi, Y.; Jabbour, S.; Piette, C.; Sais, L., Deterministic parallel DPLL, Journal on Satisfiability, Boolean Modeling and Computation, 7, 4, 127-132, (2011) · Zbl 1331.68208
[70] Hamadi, Y.; Jabbour, S.; Sais, L., (2009)
[71] Hamadi, Y.; Jabbour, S.; Sais, L., ManySAT: A parallel SAT solver, Journal on Satisfiability, Boolean Modeling and Computation, 6, 245-262, (2009) · Zbl 1193.68227
[72] Hamadi, Y.; Wintersteiger, C., Seven challenges in parallel SAT solving, AI Magazine, 34, 2, 99-106, (2013)
[73] Held, J.; Bautista, J.; Koehl, S., (2006)
[74] Henz, M.; Smolka, G.; Würtz, J., (1993)
[75] Heule, M. J.; Kullmann, O.; Wieringa, S.; Biere, A., Haifa Verification Conference, 50-65, (2011), Springer
[76] Heule, M. J. H.; Kullmann, O., The science of brute force, Communications of the ACM, 60, 70-79, (2017)
[77] Heule, M. J. H.; Kullmann, O.; Marek, V. W., (2016)
[78] Hirayama, K.; Yokoo, M., The distributed breakout algorithms, Artificial Intelligence, 161, 1-2, 89-115, (2005) · Zbl 1132.68701
[79] Hölldobler, S.; Manthey, N.; Nguyen, V. H.; Stecklina, J.; Steinke, P., (2011)
[80] Hoos, H.; Kaminski, R.; Lindauer, M.; Schaub, T., aspeed: Solver scheduling via answer set programming, Theory and Practice of Logic Programming, 15, 1, 117-142, (2015) · Zbl 1379.68283
[81] Huberman, B. A.; Lukose, R. M.; Hogg, T., An economics approach to hard computational problems, Science, 275, 5296, 51-54, (1997)
[82] Hurley, B.; Kotthoff, L.; Malitsky, Y.; O’Sullivan, B., (2014)
[83] Hyvärinen, A.; Junttila, T.; Niemelä, I., Incorporating clause learning in grid-based randomized SAT solving, Journal on Satisfiability, Boolean Modeling and Computation, 6, 223-244, (2009) · Zbl 1190.68055
[84] Hyvärinen, A. E. J.; Manthey, N.; Cimatti, A.; Sebastiani, R., Theory and Applications of Satisfiability Testing - SAT 2012, Designing scalable parallel SAT solvers, 214-227, (2012), Springer: Springer, Berlin, Heidelberg · Zbl 1268.68009
[85] Jaffar, J.; Santosa, A. E.; Yap, R. H. C.; Zhu, K. Q., (2004)
[86] Järvisalo, M.; Heule, M.; Biere, A., (2012)
[87] Kadioglu, S.; Malitsky, Y.; Sabharwal, A.; Samulowitz, H.; Sellmann, M., (2011)
[88] Karp, R. M.; Zhang, Y., Randomized parallel algorithms for backtrack search and branch-and-bound computation, Journal of the ACM, 40, 765-789, (1993) · Zbl 0789.68066
[89] Kasif, S., On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artificial Intelligence, 45, 3, 275-286, (1990) · Zbl 0717.68043
[90] Kasif, S.; Delcher, A. L., Local consistency in parallel constraint satisfaction networks, Artificial Intelligence, 69, 1-2, 307-327, (1994) · Zbl 0821.68115
[91] Katsirelos, G.; Sabharwal, A.; Samulowitz, H.; Simon, L., (2013)
[92] Kirousis, L. M., Fast parallel constraint satisfaction, Artificial Intelligence, 64, 1, 147-160, (1993) · Zbl 0787.68091
[93] Kotthoff, L., Algorithm selection for combinatorial search problems: A survey, AI Magazine, 35, 3, 48-60, (2014)
[94] Kotthoff, L.; Moore, N. C. A., (2010)
[95] Lai, T.; Sahni, S., Anomalies in parallel branch-and-bound algorithms, Communications of the ACM, 27, 6, 594-602, (1984) · Zbl 0587.68032
[96] Léauté, T.; Ottens, B.; Szymanek, R., (2009)
[97] Li, G.; Wah, B. W., Coping with anomalies in parallel branch-and-bound algorithms, IEEE Transactions on Computers, 35, 6, 568-573, (1986)
[98] Lindauer, M.; Hoos, H.; Hutter, F., International Conference on Learning and Intelligent Optimization, 1-16, (2015), Springer
[99] Lindauer, M.; Hoos, H.; Leyton-Brown, K.; Schaub, T., Automatic construction of parallel portfolios via algorithm configuration, Artificial Intelligence, 244, 272-290, (2017) · Zbl 1404.68144
[100] Machado, R.; Pedro, V.; Abreu, S., (2013)
[101] Maher, M. J., (1987)
[102] Malapert, A.; Régin, J.-C.; Rezgui, M., Embarrassingly parallel search in constraint programming, Journal of Artificial Intelligence Research, 57, 421-464, (2016) · Zbl 1401.68292
[103] Malitsky, Y.; Sabharwal, A.; Samulowitz, H.; Sellmann, M., (2012)
[104] Malitsky, Y.; Sabharwal, A.; Samulowitz, H.; Sellmann, M., (2013)
[105] Malitsky, Y.; Sabharwal, A.; Samulowitz, H.; Sellmann, M., (2013)
[106] Manolios, P.; Zhang, Y., (2006)
[107] Manthey, N., (2011)
[108] Manthey, N., (2011)
[109] Martins, R.; Manquinho, V.; Lynce, I., An overview of parallel SAT solving, Constraints, 17, 304-347, (2012) · Zbl 1309.90057
[110] Mccreesh, C.; Prosser, P., The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound, ACM Transactions on Parallel Computing, 2, 1, 8:1-8:27, (2015)
[111] Menouer, T.; Rezgui, M.; Cun, B. L.; Régin, J., Mixing static and dynamic partitioning to parallelize a constraint programming solver, International Journal of Parallel Programming, 44, 3, 486-505, (2016)
[112] Michel, L.; See, A.; Van Hentenryck, P., (2006)
[113] Michel, L.; See, A.; Van Hentenryck, P., (2007)
[114] Michel, L.; See, A.; Van Hentenryck, P., Parallel and distributed local search in COMET, Computers & Operations Research, 36, 2357-2375, (2009) · Zbl 1179.90288
[115] Moisan, T.; Gaudreault, J.; Quimper, C.-G., (2013)
[116] Moisan, T.; Quimper, C.-G.; Gaudreault, J., (2014)
[117] Montelius, J.; Ali, K. A. M., An and/or-parallel implementation of AKL, New Generation Computing, 14, 1, 31-52, (1996)
[118] Munawar, A.; Wahib, M.; Munetomo, M.; Akama, K., Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework, Genetic Programming and Evolvable Machines, 10, 391-415, (2009)
[119] Munera, D.; Diaz, D.; Abreu, S.; Hanus, M.; Rocha, R., Declarative Programming and Knowledge Management: Declarative Programming Days, KDPD 2013, Unifying INAP, WFLP, and WLP, Kiel, Germany, September 11-13, 2013, Revised Selected Papers, 169-184, (2014), Springer International Publishing
[120] Munera, D.; Diaz, D.; Abreu, S.; Codognet, P.; Blum, C.; Ochoa, G., Evolutionary Computation in Combinatorial Optimisation: 14th European Conference, EvoCOP 2014, Granada, Spain, April 23-25, 2014, Revised Selected Papers, 13-24, (2014), Springer: Springer, Berlin, Heidelberg
[121] Munera, D.; Diaz, D.; Abreu, S.; Rossi, F.; Saraswat, V. A.; Codognet, P., (2015)
[122] Netzer, A.; Meisels, A.; Zivan, R., Distributed envy minimization for resource allocation, Autonomous Agents and Multi-Agent Systems, 30, 2, 364-402, (2016)
[123] Nguyen, T.; Deville, Y., (1995)
[124] Nguyen, T.; Deville, Y., A distributed arc-consistency algorithm, Science of Computer Programming, 30, 227-250, (1998) · Zbl 0895.68120
[125] Nightingale, P.; Akgün, Ö.; Gent, I. P.; Jefferson, C.; Miguel, I., (2014)
[126] Nightingale, P.; Akgün, O.; Gent, I. P.; Jefferson, C.; Miguel, I.; Spracklen, P., Automatically improving constraint models in Savile Row, Artificial Intelligence, 251, 35-61, (2017) · Zbl 1419.68099
[127] Nightingale, P.; Spracklen, P.; Miguel, I., International Conference on Principles and Practice of Constraint Programming, Automatically improving SAT encoding of constraint problems through common subexpression elimination in Savile Row, (2015), Springer
[128] O’Mahony, E.; Hebrard, E.; Holland, A.; Nugent, C.; O’Sullivan, B., (2008)
[129] Otten, L.; Dechter, R., AND/OR branch-and-bound on a computational grid, Journal of Artificial Intelligence Research, 59, (2017) · Zbl 1418.68189
[130] Palmieri, A.; Régin, J.; Schaus, P., (2016)
[131] Perron, L., (1999)
[132] Prosser, P.; Conway, C.; Muller, C., A constraint maintenance system for the distributed resource allocation problem, Intelligent Systems Engineering, 1, 1, 76-83, (1992)
[133] Ralphs, T.; Shinano, Y.; Berthold, T.; Koch, T., (2017)
[134] Rao, V.; Kumar, V., (1988)
[135] Reynolds, J. C., The discoveries of continuations, LISP and Symbolic Computation, 6, 3-4, 233-247, (1993)
[136] Rice, J. R., The algorithm selection problem, Advances in Computers, 15, 65-118, (1976)
[137] Rolf, C.; Kuchcinski, K., (2010)
[138] Rossi, F.; Van, Beek, P.; Walsh, T., Handbook of Constraint Programming, (2006), Elsevier Science · Zbl 1175.90011
[139] Roussel, O., (2011)
[140] Ruiz-Andino, A.; Araujo, L.; Sáenz, F.; Ruz, J. J., (1998)
[141] Salido, M. A.; Barber, F., Distributed CSPs by graph partitioning, Applied Mathematics and Computation, 183, 1, 491-498, (2006) · Zbl 1107.68105
[142] Saraswat, V. A.; Rinard, M., (1990)
[143] Sassi, N.; Salah, K. B.; Ghédira, K., DOC-BRelax: A new multi-agent system to solve distributed constraint optimization problems, Future Generation Computer Systems, 73, 44-51, (2017)
[144] Schubert, T.; Lewis, M.; Becker, B., PaMiraXT: Parallel sat solving with threads and message passing, Journal on Satisfiability, Boolean Modeling and Computation, 6, 203-222, (2009) · Zbl 1190.68057
[145] Schulte, C., (2000)
[146] Singer, D., Parallel Combinatorial Optimization, Parallel resolution of the satisfiability problem: A survey, 123-147, (2006), E.-G. Talbi: E.-G. Talbi, Wiley
[147] Smith-Miles, K. A., Cross-disciplinary perspectives on meta-learning for algorithm selection, ACM Computing Surveys (CSUR), 41, 1, 6:1-6:25, (2009)
[148] Sun, X.-H.; Chen, Y., Reevaluating Amdahl’s law in the multicore era, Journal of Parallel and Distributed Computing, 70, 2, 183-188, (2010) · Zbl 1233.68089
[149] Van, Hentenryck, P.; Michel, L., Constraint-Based Local Search, (2009), The MIT Press
[150] Van, Roy, P.; Haridi, S., Mozart: A programming system for agent applications, AgentLink News, 4, 3-8, (1999)
[151] Verhoeven, M. G. A.; Aarts, E. H. L., Parallel local search, Journal of Heuristics, 1, 43-65, (1995) · Zbl 0853.68156
[152] Wahbi, M.; Brown, K. N., (2014)
[153] Wang, C. J.; Tsang, E. P. K., (1991)
[154] Wang, C. J.; Tsang, E. P. K., (1992)
[155] Wetter, J.; Akgün, Ö.; Miguel, I., (2015)
[156] Wotzlaw, A.; Van, Der Grinten, A.; Speckenmeyer, E.; Porschen, S., (2012)
[157] Xie, F.; Davenport, A. J.; Lodi, A.; Milano, M.; Toth, P., (2010)
[158] Xu, L.; Hutter, F.; Hoos, H. H.; Leyton-Brown, K., SATzilla: Portfolio-based algorithm selection for SAT, Journal of Artificial Intelligence Research, 32, 565-606, (2008) · Zbl 1182.68272
[159] Yokoo, M.; Hirayama, K., Algorithms for distributed constraint satisfaction: A review, Autonomous Agents and Multi-Agent Systems, 3, 2, 185-207, (2000)
[160] Yokoo, M.; Ishida, T.; Durfee, E. H.; Kuwabara, K., (1992)
[161] Yun, X.; Epstein, S. L., Learning and Intelligent Optimization, Learning algorithm portfolios for parallel execution, 323-338, (2012), Springer: Springer, Berlin, Heidelberg
[162] Zhang, W.; Wang, G.; Xing, Z.; Wittenburg, L., Distributed stochastic search and distributed breakout: Properties, comparison and applications to constraint optimization problems in sensor networks, Artificial Intelligence, 161, 1, 55-87, (2005) · Zbl 1132.68718
[163] Zhang, Y.; Mackworth, A. K., (1991)
[164] Zivan, R.; Yedidsion, H.; Okamoto, S.; Glinton, R.; Sycara, K., Distributed constraint optimization for teams of mobile sensing agents, Autonomous Agents and Multi-Agent Systems, 29, 3, 495-536, (2015)
[165] Zoeteweij, P.; Arbab, F., (2004)
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.