UniTime.org Logo University Timetabling
Comprehensive Academic Scheduling Solutions
Random Binary CSP
Problem Description
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 is incompatible. We use a so called model B of Random CSP (n, d, n1, n2) where n1 = p1n(n-1)/2 pairs of variables are randomly and uniformly selected and binary constraints are posted between them. For each constraint, n2 = p2d^2 randomly and uniformly selected pairs of values are picked as incompatible.

For some tests, we turned the random CSP problem into an optimization problem (minCSP). The goal is to minimize the total sum of values for all variables.

java -Xmx512m -cp ifs-1.2 net.sf.cpsolver.ifs.example.csp.Test file.cfg [output_dir]
file.cfg ... configuration file
output_dir ... output folder
java -Xmx512m -cp ifs-1.2 net.sf.cpsolver.ifs.example.rpp.Test CSP(25,15,198,22).cfg .\output\CSP(25,15,198,22)
java -Xmx512m -cp ifs-1.2 net.sf.cpsolver.ifs.example.rpp.Test minCSP(50,12,250,32).cfg .\output\minCSP(50,12,250,32)
Output is located in the folder output_dir\<date>, generated input problem (compatibility matrix of each constraint) as well as the solution (list of assignments) is written in the file info.txt.

Example configuration files: [CSP(25,15,198/300,22)] [minCSP(50,12,250/1250,32)]
For more details about the problem implementation and parameters (i.e., content of the configuration file file.cfg), please consult the documentation of the main class ifs.example.csp.Test and the problem implementation (package net.sf.cpsolver.ifs.example.csp).
  © 2017 UniTime