Adding laziness in BnB-ADOPT+

descriptionPublicationkeyboard_double_arrow_right Article 17 Dec 2014 English Publisher:Springer Science and Business Media LLCJournal:Constraints, volume 20, pages 274-282 (issn: 1383-7133, eissn: 1572-9354,

Copyright policy )

Authors: Jimmy Ho-Man Lee; Pedro Meseguer; Wen Su;

doi: 10.1007/s10601-014-9177-3

handle: 10261/130231

Adding laziness in BnB-ADOPT+

- Summary
- Subjects
- Metrics

Abstract

In distributed constraint optimization, agents executing BnB-ADOPT+ react eagerly to cost changes: they send non-redundant COST messages to their parents as soon as they receive new messages. We have observed that a lazier reaction (not sending COST messages until a condition is met) substantially decrements the number of messages sent and causes only a small variation in ENCCCs. This approach combines nicely with soft arc consistency maintenance during search. We provide experimental evidence of the benefits of this approach on several benchmarks.

This research has been supported by the following grants: CUHK413808, CUHK413710 and CUHK413713 from the Research Grants Council of Hong Kong SAR, the CSIC / RGC Joint Research Scheme grants S-HK003/12 and 2011HK0017, TIN2013-45732-C4-4-P from Spanish MINECO, and Generalitat de Catalunya SGR- 2014-118

Peer Reviewed

Related Organizations

Spanish National Research Council
Spain
The Chinese University of Hong kong
Hong Kong
Chinese University of Hong Kong
China (People's Republic of)

Keywords

Arc consistency, Cost changes, Non-redundant, Integer programming, Distributed constraint optimizations, Constrained optimization, Experimental evidence, Small variations

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average