{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T00:10:03Z","timestamp":1748563803451,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319232188"},{"type":"electronic","value":"9783319232195"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23219-5_9","type":"book-chapter","created":{"date-parts":[[2015,8,12]],"date-time":"2015-08-12T10:17:33Z","timestamp":1439374653000},"page":"121-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming"],"prefix":"10.1007","author":[{"given":"Ferdinando","family":"Fioretto","sequence":"first","affiliation":[]},{"given":"Tiep","family":"Le","sequence":"additional","affiliation":[]},{"given":"Enrico","family":"Pontelli","sequence":"additional","affiliation":[]},{"given":"William","family":"Yeoh","sequence":"additional","affiliation":[]},{"given":"Tran Cao","family":"Son","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,13]]},"reference":[{"key":"9_CR1","unstructured":"Abdennadher, S., Schlenker, H.: Nurse scheduling using constraint logic programming. In: Proceedings of the Conference on Innovative Applications of Artificial Intelligence (IAAI), pp. 838\u2013843 (1999)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Apt, K.: Principles of constraint programming. Cambridge University Press (2003)","DOI":"10.1017\/CBO9780511615320"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Arbelaez, A., Codognet, P.: A GPU implementation of parallel constraint-based local search. In: Proceedings of the Euromicro International Conference on Parallel, Distributed and network-based Processing (PDP), pp. 648\u2013655 (2014)","DOI":"10.1109\/PDP.2014.28"},{"issue":"5439","key":"9_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.cor.2011.03.014","volume":"39","author":"V Boyer","year":"2012","unstructured":"Boyer, V., El Baz, D., Elkihel, M.: Solving knapsack problems on GPU. Computers & Operations Research 39(1), 42\u201347 (2012)","journal-title":"Computers & Operations Research"},{"key":"9_CR6","unstructured":"Brito, I., Meseguer, P.: Improving DPOP with function filtering. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 141\u2013158 (2010)"},{"key":"9_CR7","unstructured":"Burke, D., Brown, K.: Efficiently handling complex local problems in distributed constraint optimisation. In: Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 701\u2013702 (2006)"},{"issue":"6","key":"9_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1023\/B:JOSH.0000046076.75950.0b","volume":"7","author":"EK Burke","year":"2004","unstructured":"Burke, E.K., De Causmaecker, P., Berghe, G.V., Van Landeghem, H.: The state of the art of nurse rostering. Journal of scheduling 7(6), 441\u2013499 (2004)","journal-title":"Journal of scheduling"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Campeotto, F., Dovier, A., Fioretto, F., Pontelli, E.: A GPU implementation of large neighborhood search for solving constraint optimization problems. In: Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 189\u2013194 (2014)","DOI":"10.3233\/978-1-61499-419-0-189"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Dechter, R.: Bucket elimination: a unifying framework for probabilistic inference. In: Learning in graphical models, pp. 75\u2013104. Springer (1998)","DOI":"10.1007\/978-94-011-5014-9_4"},{"key":"9_CR11","volume-title":"Constraint Processing","author":"R Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann Publishers Inc., San Francisco (2003)"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Dechter, R., Pearl, J.: Network-based heuristics for constraint-satisfaction problems. Springer (1988)","DOI":"10.1007\/978-1-4613-8788-6_11"},{"key":"9_CR13","unstructured":"Farinelli, A., Rogers, A., Petcu, A., Jennings, N.: Decentralised coordination of low-power embedded devices using the Max-Sum algorithm. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 639\u2013646 (2008)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-3-319-10428-7_24","volume-title":"Principles and Practice of Constraint Programming","author":"F Fioretto","year":"2014","unstructured":"Fioretto, F., Le, T., Yeoh, W., Pontelli, E., Son, T.C.: Improving DPOP with branch consistency for solving distributed constraint optimization problems. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 307\u2013323. Springer, Heidelberg (2014)"},{"issue":"6","key":"9_CR15","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/j.compind.2009.02.006","volume":"60","author":"J Gaudreault","year":"2009","unstructured":"Gaudreault, J., Frayret, J.-M., Pesant, G.: Distributed search for supply chain coordination. Computers in Industry 60(6), 441\u2013451 (2009)","journal-title":"Computers in Industry"},{"key":"9_CR16","unstructured":"Hamadi, Y., Bessi\u00e8re, C., Quinqueton, J.: Distributed intelligent backtracking. In: Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 219\u2013223 (1998)"},{"key":"9_CR17","unstructured":"Kumar, A., Faltings, B., Petcu, A.: Distributed constraint optimization with structured resource constraints. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 923\u2013930 (2009)"},{"key":"9_CR18","first-page":"179","volume":"11","author":"ME Lalami","year":"2011","unstructured":"Lalami, M.E., El Baz, D., Boyer, V.: Multi GPU implementation of the simplex algorithm. Proceedings of the International Conference on High Performance Computing and Communication (HPCC) 11, 179\u2013186 (2011)","journal-title":"Proceedings of the International Conference on High Performance Computing and Communication (HPCC)"},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"L\u00e9aut\u00e9, T., Faltings, B.: Distributed constraint optimization under stochastic uncertainty. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 68\u201373 (2011)","DOI":"10.1609\/aaai.v25i1.7812"},{"key":"9_CR20","unstructured":"Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., Varakantham, P.: Taking DCOP to the real world: Efficient complete solutions for distributed event scheduling. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 310\u2013317 (2004)"},{"issue":"1\u20132","key":"9_CR21","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.artint.2004.09.003","volume":"161","author":"P Modi","year":"2005","unstructured":"Modi, P., Shen, W.-M., Tambe, M., Yokoo, M.: ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence 161(1\u20132), 149\u2013180 (2005)","journal-title":"Artificial Intelligence"},{"key":"9_CR22","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information sciences 7, 95\u2013132 (1974)","journal-title":"Information sciences"},{"key":"9_CR23","unstructured":"Paw\u0142owski, K., Kurach, K., Michalak, T., Rahwan, T.: Coalition structure generation with the graphic processor unit. Technical Report CS-RR-13-07, Department of Computer Science, University of Oxford (2014)"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp. 482\u2013495 (2004)","DOI":"10.1007\/978-3-540-30201-8_36"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Petcu, A., Faltings, B.: A scalable method for multiagent constraint optimization. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1413\u20131420 (2005)","DOI":"10.1007\/11600930_71"},{"key":"9_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/11889205_64","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"C-G Quimper","year":"2006","unstructured":"Quimper, C.-G., Walsh, T.: Global grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 751\u2013755. Springer, Heidelberg (2006)"},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1007\/978-3-540-76631-5_106","volume-title":"MICAI 2007: Advances in Artificial Intelligence","author":"LCA Rodrigues","year":"2007","unstructured":"Rodrigues, L.C.A., Magat\u00e3o, L.: Enhancing supply chain decisions using constraint programming: a case study. In: Gelbukh, A., Kuri Morales, \u00c1.F. (eds.) MICAI 2007. LNCS (LNAI), vol. 4827, pp. 1110\u20131121. Springer, Heidelberg (2007)"},{"key":"9_CR28","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Elsevier (2006)"},{"key":"9_CR29","unstructured":"Sanders, J., Kandrot, E.: CUDA by Example. An Introduction to General-Purpose GPU Programming. Addison Wesley (2010)"},{"key":"9_CR30","unstructured":"Sultanik, E., Modi, P.J., Regli, W.C.: On modeling multiagent task scheduling as a distributed constraint optimization problem. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1531\u20131536 (2007)"},{"issue":"1\u20134","key":"9_CR31","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1023\/A:1021801522545","volume":"118","author":"MA Trick","year":"2003","unstructured":"Trick, M.A.: A dynamic programming approach for consistency and propagation for knapsack constraints. Annals of Operations Research 118(1\u20134), 73\u201384 (2003)","journal-title":"Annals of Operations Research"},{"key":"9_CR32","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1613\/jair.2849","volume":"38","author":"W Yeoh","year":"2010","unstructured":"Yeoh, W., Felner, A., Koenig, S.: BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. Journal of Artificial Intelligence Research 38, 85\u2013133 (2010)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3","key":"9_CR33","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1609\/aimag.v33i3.2429","volume":"33","author":"W Yeoh","year":"2012","unstructured":"Yeoh, W., Yokoo, M.: Distributed problem solving. AI Magazine 33(3), 53\u201365 (2012)","journal-title":"AI Magazine"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Yokoo, M. (ed.): Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-agent Systems. Springer (2001)","DOI":"10.1007\/978-3-642-59546-2"},{"key":"9_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2014.03.002","volume":"212","author":"R Zivan","year":"2014","unstructured":"Zivan, R., Okamoto, S., Peled, H.: Explorative anytime local search for distributed constraint optimization. Artificial Intelligence 212, 1\u201326 (2014)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"9_CR36","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10458-014-9255-3","volume":"29","author":"R Zivan","year":"2015","unstructured":"Zivan, R., Yedidsion, H., Okamoto, S., Glinton, R., Sycara, K.: Distributed constraint optimization for teams of mobile sensing agents. Journal of Autonomous Agents and Multi-Agent Systems 29(3), 495\u2013536 (2015)","journal-title":"Journal of Autonomous Agents and Multi-Agent Systems"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23219-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:47:55Z","timestamp":1748562475000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23219-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319232188","9783319232195"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23219-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"13 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}