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

• Makoto Yokoo and Katsutoshi Hirayama. Algorithms for Distributed Constraint Satisfaction: A Review.
  Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000.

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).

Created with NetLogo . View/download model file:Asynchronous Backtracking - binary random problems (CSP).nlogo