NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses external files.)

Title: Random binary CSPs using Asynchronous Backtracking
Author: Ionel Muscalagiu, Jose M. Vidal and Hong Jiang
Description:
This is the implementation of the Asynchronous Backtracking for the random binary problems. We generate and solve the random binary problem using the Asynchronous Backtracking algorithm from
<ul>
<li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/library/yokoo00a.pdf">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000. <a href="http://dx.doi.org/10.1023/A:1010078712316">doi:10.1023/A:1010078712316</a>
</li>
</ul>
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
where n is the number of variables, m is the uniform domain size, p1 is the portion of
the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m value pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.

In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer).