{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:57:29Z","timestamp":1719881849493},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T00:00:00Z","timestamp":1608336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Collectiveware","award":["TIN2015-66863-C2-1-R"],"award-info":[{"award-number":["TIN2015-66863-C2-1-R"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In the context of solving large distributed constraint optimization problems, belief-propagation and incomplete inference algorithms are candidates of choice. However, in general, when the problem structure is very cyclic, these solution methods suffer from bad performance, due to non-convergence and many exchanged messages. As to improve performances of the MaxSum inference algorithm when solving cyclic constraint optimization problems, we propose here to take inspiration from the belief-propagation-guided decimation used to solve sparse random graphs ($k$-satisfiability). We propose the novel DeciMaxSum method, which is parameterized in terms of policies to decide when to trigger decimation, which variables to decimate and which values to assign to decimated variables. Based on an empirical evaluation on a classical constraint optimization benchmarks (graph coloring, random graph and Ising model), some of these combinations of policies, using periodic decimation, cycle detection-based decimation, parallel and non parallel decimation, random or deterministic variable selection and deterministic or random sampling for value selection, outperform state-of-the-art competitors in many settings.<\/jats:p>","DOI":"10.1093\/jigpal\/jzaa069","type":"journal-article","created":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T20:09:53Z","timestamp":1605384593000},"page":"72-95","source":"Crossref","is-referenced-by-count":2,"title":["Solving Highly Cyclic Distributed Optimization Problems Without Busting the Bank: A Decimation-based Approach"],"prefix":"10.1093","volume":"29","author":[{"given":"Jes\u00fas","family":"Cerquides","sequence":"first","affiliation":[{"name":"Artificial Intelligence Research Institute (IIIA-CSIC), Campus de la UAB, 08193 Bellaterra, Spain"}]},{"given":"Juan Antonio","family":"Rodr\u00edguez-Aguilar","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Institute (IIIA-CSIC), Campus de la UAB, 08193 Bellaterra, Spain"}]},{"given":"R\u00e9mi","family":"Emonet","sequence":"additional","affiliation":[{"name":"Univ Lyon, UJM-Saint-Etienne, CNRS, Institut d\u2019Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023 Saint-Etienne, France"}]},{"given":"Gauthier","family":"Picard","sequence":"additional","affiliation":[{"name":"Mines Saint-Etienne, Univ Lyon, Univ Jean Monnet, IOGS, CNRS, UMR 5516 LHC, Institut Henri Fayol, Departement ISI, F-42023 Saint-Etienne, France"}]}],"member":"286","published-online":{"date-parts":[[2020,12,19]]},"reference":[{"key":"2021012207115255600_ref1","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1093\/comjnl\/bxt146","article-title":"A tutorial on optimization for multi-agent systems","volume":"57","author":"Cerquides","year":"2014","journal-title":"The Computer Journal"},{"key":"2021012207115255600_ref2","first-page":"1285","article-title":"Designing a marketplace for the trading and distribution of energy in the smart grid","volume-title":"International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Cerquides","year":"2015"},{"key":"2021012207115255600_ref3","first-page":"639","article-title":"Decentralised coordination of low-power embedded devices using the max-sum algorithm","volume-title":"International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Farinelli","year":"2008"},{"key":"2021012207115255600_ref4","article-title":"Distributed constraint optimization problems and applications: A survey","author":"Fioretto","year":"2016","journal-title":"CoRR"},{"key":"2021012207115255600_ref5","first-page":"909","article-title":"A privacy-preserving algorithm for distributed constraint optimization","volume-title":"Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems","author":"Grinshpoun","year":"2014"},{"key":"2021012207115255600_ref6","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1007\/978-3-319-98334-9_44","article-title":"A large neighboring search schema for multi-agent optimization","author":"Hoang","year":"2018","journal-title":"Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)"},{"key":"2021012207115255600_ref7","doi-asserted-by":"crossref","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","article-title":"Convergent tree-reweighted message passing for energy minimization","volume":"28","author":"Kolmogorov","year":"2006","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2021012207115255600_ref8","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Krzakala","year":"2007","journal-title":"Proceedings of the National Academy of Science"},{"key":"2021012207115255600_ref9","article-title":"Distributed constraint optimization: privacy guarantees and stochastic uncertainty","volume-title":"PhD thesis","author":"L\u00e9aut\u00e9","year":"2011"},{"key":"2021012207115255600_ref10","volume-title":"Disributed Algorithms","author":"Lynch","year":"1996"},{"key":"2021012207115255600_ref11","volume-title":"Information Theory, Inference and Learning Algorithms","author":"Mackay","year":"2003"},{"key":"2021012207115255600_ref12","first-page":"432","article-title":"Distributed algorithms for dcop: A graphical-game-based approach","volume-title":"Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS)","author":"Maheswaran","year":"2004"},{"key":"2021012207115255600_ref13","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.artint.2004.09.003","article-title":"ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees","volume":"161","author":"Modi","year":"2005","journal-title":"Artificial Intelligence"},{"key":"2021012207115255600_ref14","article-title":"Solving constraint satisfaction problems through belief propagation-guided decimation","author":"Montanari","year":"2007","journal-title":"CoRR"},{"key":"2021012207115255600_ref15","first-page":"2169","article-title":"libDAI: A free and open source C++ library for discrete approximate inference in graphical models","volume":"11","author":"Mooij","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2021012207115255600_ref16","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"M\u00e8zard","year":"2009"},{"key":"2021012207115255600_ref17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pcbi.1004347","article-title":"Decreasing-rate pruning optimizes the construction of efficient and robust distributed networks","volume":"11","author":"Navlakha","year":"2015","journal-title":"PLoS Computational Biology"},{"key":"2021012207115255600_ref18","first-page":"266","article-title":"A scalable method for multiagent constraint optimization","author":"Petcu","year":"2005","journal-title":"International Joint Conference on Artificial Intelligence (IJCAI\u201905)"},{"key":"2021012207115255600_ref19","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1016\/j.artint.2010.11.001","article-title":"Bounded approximate decentralised coordination via the max-sum algorithm","volume":"175","author":"Rogers","year":"2011","journal-title":"Artificial Intelligence"},{"key":"2021012207115255600_ref20","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1016\/j.artint.2010.11.001","article-title":"Bounded approximate decentralised coordination via the max-sum algorithm","volume":"175","author":"Rogers","year":"2011","journal-title":"Artificial Intelligence"},{"key":"2021012207115255600_ref21","article-title":"Using message-passing DCOP algorithms to solve energy-efficient smart environment configuration problems","volume-title":"International Joint Conference on Artificial Intelligence (IJCAI)","author":"Rust","year":"2016"},{"key":"2021012207115255600_ref22","first-page":"149","article-title":"Divide and coordinate: solving dcops by agreement","volume-title":"International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)","author":"Vinyals","year":"2010"},{"key":"2021012207115255600_ref23","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s10458-010-9132-7","article-title":"Constructing a unifying theory of dynamic programming dcop algorithms via the generalized distributive law","volume":"22","author":"Vinyals","year":"2010","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"2021012207115255600_ref24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.artint.2004.10.004","article-title":"Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks","volume":"161","author":"Zhang","year":"2005","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"2021012207115255600_ref25","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1007\/s10458-017-9360-1","article-title":"Balancing exploration and exploitation in incomplete min\/max-sum inference for distributed constraint optimization","volume":"31","author":"Zivan","year":"2017","journal-title":"Autonomous Agents and Multi-Agent Systems"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/jigpal\/article-pdf\/29\/1\/72\/35933719\/jzaa069.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/jigpal\/article-pdf\/29\/1\/72\/35933719\/jzaa069.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,23]],"date-time":"2021-01-23T17:58:10Z","timestamp":1611424690000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/29\/1\/72\/6039978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,19]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,12,19]]},"published-print":{"date-parts":[[2021,1,25]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzaa069","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"value":"1367-0751","type":"print"},{"value":"1368-9894","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,2]]},"published":{"date-parts":[[2020,12,19]]}}}