Department of
Computer Science
695 Park Ave.
NY, NY 10021

 

Susan L. Epstein

The CUNY Graduate School, Department of Computer Science and

 Hunter College, Department of Computer Science

 

 

 

 

 

     Home 
     Publications 
     Collaborators 
     Courses 
     Contact

 

 

 

 

 

PARAMETERIZED PROBLEMS (CSP)

 

A parameterized problem is a randomly-generated CSP whose constraint graph is connected. A parameterized problem is described here as <n, k, d, t>. -vt after the parameters indicates that the problems in the file have varying tightness, -vs means varying solvability and -u means that all problems are unsolvable (over-constrained).

The results below come from experiments using ACE with variable-ordering heuristic mean domain/dynamic degree. Results using a mixture of heuristics (Advisors) will be reported soon. Results reported were averaged over ACE runs on the first 100 problems in each file.

#PROBLEMS indicates how many problems are available on file

VISITED NODES indicates the average number of nodes visited during search.

CONSTRAINT CHECKS indicates the average number of constrant checks.

PROBLEM CLASS # PROBLEMS VISITED NODES CONSTRAINT CHECKS RECCOMMENDED ADVISORS
10-5-0.005-0.6
1000
10.05
70.35
  
10-8-0.1-0.5
1000
10.01
261.55
  
20-5-0.005-0.6
1000
20.23
184.64
  
20-8-0.14-0.5
1000
21.15
1658.99
  
20-8-0.22-0.5
1000
26.38
5181.32
  
20-30-0.32-0.9-vt
1000
22.80
6495.23
  
20-30-0.33-0.95-vt
1000
30.68
15874.82
  
20-30-0.34-0.95-vt
1000
55.74
47577.15
  
20-30-0.35-0.95
1000
29.74
19072.46
  
20-30-0.444-0.5-vt
1000
2332.90
3240849.20
  
20-30-0.444-0.5
1000
2321.39
3189755.70
  
30-5-0.01-0.6
1000
30.42
325.68
  
30-5-0.02-0.6
1000
30.64
379.41
  
30-5-0.005-0.6
1000
30.35
269.20
  
30-5-0.015-0.6
1000
30.73
360.94
  
30-5-0.025-0.6
1000
30.95
390.56
  
30-8-0.05-0.5
1000
30.05
1599.65
  
30-8-0.08-0.5
1000
30.51
2297.59
  
30-8-0.1-0.5
1000
34.29
4088.83
  
30-8-0.12-0.5
1000
39.70
8128.68
  
30-8-0.26-0.28
1000
32.77
5549.46
  
30-8-0.26-0.34-u
1000
3103.86
2277696.70
  
30-8-0.26-0.34-vt
1000
106.32
46477.96
  
30-8-0.26-0.34.
1000
103.06
45561.04
  
30-8-0.075-0.5
1000
30.53
2208.12
  
30-8-0.266-0.34
1000
119.63
56768.89
  
30-10-0.11-0.6
1000
38.34
12420.92
  
40-5-0.005-0.6
1000
40.79
442.93
  
50-5-0.005-0.6
1000
50.60
583.21
  
50-5-0.015-0.6
300
50.89
648.65
  
50-8-0.04-0.5
1000
50.49
3988.07
  
50-8-0.06-0.5
1000
63.59
12158.97
  
50-8-0.045-0.6
1000
58.16
10919.49
  
50-10-0.38-0.2
1000
6688.09
5076926.00
  
50-10-0.38-0.2-vt
1000
8734.16
6980675.00
  
80-10-0.1042-0.35
100
11544.32
12175658.00
  
 
 
 
 

[top of the page]

Home