Package net.sf.cpsolver.ifs.example.csp

Random Binary CSP with uniform distribution.

See:
Description

Class Summary

CSPBinaryConstraint	CSP binary constraint.
CSPModel	Random Binary CSP with uniform distribution.
CSPValue	CSP value.
CSPVariable	CSP variable.
SimpleTest	Simple test of IFS CBS algorithm on random binary CSP problem CSP(25,12,198/300,36/144).
StructuredCSPModel	Random Binary CSP with kernels.
Test	Test of Structured CSP problems.

Package net.sf.cpsolver.ifs.example.csp Description

Random Binary CSP with uniform distribution.

A random CSP is defined by a four-tuple (n, d, p1, p2), where n denotes the number of variables and d denotes the domain size of each variable, p1 and p2 are two probabilities. They are used to generate randomly the binary constraints among the variables. p1 represents the probability that a constraint exists between two different variables and p2 represents the probability that a pair of values in the domains of two variables connected by a constraint are incompatible.

We use a so called model B of Random CSP (n, d, n1, n2) where n1 = p1*n*(n-1)/2 pairs of variables are randomly and uniformly selected and binary constraints are posted between them. For each constraint, n2 = p1*d^2 randomly and uniformly selected pairs of values are picked as incompatible.