caa a22 4500 463207130 CHVBK 20180405153129.0 cr unu---uuuuu 170326e20070601xx s 000 0 eng 10.1007/s10462-008-9072-7 doi (NATIONALLICENCE)springer-10.1007/s10462-008-9072-7 Using relaxations to improve search in distributed constraint optimisation [Elektronische Daten] [David Burke, Kenneth Brown] Densely connected distributed constraint optimisation problems (DisCOP) can be difficult to solve optimally, but finding good lower bounds on constraint costs can help to speed up search. We show how good lower bounds can be found by solving relaxed problems obtained by removing inter-agent constraints. We present modifications to the Adopt DisCOP algorithm that allow an arbitrary number of relaxations to be performed prior to solving the original problem. We identify useful relaxations based on the solving structure used by Adopt, and demonstrate that when these relaxations are incorporated as part of the search it can lead to significant performance improvements. In particular, where agents have significant local constraint costs, we achieve over an order of magnitude reduction in messages exchanged between agents. Finally, we identify cases where such relaxation techniques produce less consistent benefits. Springer Science+Business Media B.V., 2008 Distributed constraint optimisation nationallicence Multi-agent systems nationallicence Burke David Centre for Telecommunications Value-chain Research and Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland aut Brown Kenneth Centre for Telecommunications Value-chain Research and Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland aut Artificial Intelligence Review Springer Netherlands 28/1(2007-06-01), 35-50 0269-2821 28:1<35 2007 28 10462 https://doi.org/10.1007/s10462-008-9072-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10462-008-9072-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Burke David Centre for Telecommunications Value-chain Research and Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland aut NATIONALLICENCE 700 1- Brown Kenneth Centre for Telecommunications Value-chain Research and Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland aut NATIONALLICENCE 773 0- Artificial Intelligence Review Springer Netherlands 28/1(2007-06-01), 35-50 0269-2821 28:1<35 2007 28 10462 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer