Foundations of Constraint Processing Evaluation to BT Search 8 Model B 1.Input: n, a, t, p1 2.Generate n nodes 3.Generate a list of n.(n-1)/2 tuples of all combinations of 2 nodes 4.Choose e elements from above list as constraints to between the n nodes 5.If the graph is not connected, throw away, go back to step 4, else proceed 6.Generate a list of a 2 tuples of all combinations of 2 values 7.For each constraint, choose randomly a number of tuples from the list to guarantee tightness t for the constraint.

Vary parameters: Number of variables: n Domain size: a, d Constraint tightness: t = |forbidden tuples| / | all tuples | Proportion of constraints (a.k.a., constraint density, constraint probability): p 1 = e / e max Issues: Uniformity Difficulty (phase transition) Solvability of instances (for incomplete search techniques)

Foundations of Constraint Processing Evaluation to BT Search 7 Empirical evaluations: random problems Various models exist (use Model B) Models A, B, C, E, F, etc.

Foundations of Constraint Processing Evaluation to BT Search 6 Empirical evaluation: data sets Use real-world data (anecdotal evidence) Use benchmarks Solver competition benchmarks Use randomly generated problems Various models of random generators Guaranteed with a solution Uniform or structured.

Foundations of Constraint Processing Evaluation to BT Search 5 Theoretical evaluations Comparing NV and/or CC Common assumptions: for finding all solutions static/same orderings.

Foundations of Constraint Processing Evaluation to BT Search 4 Comparison criteria 1.Number of nodes visited (#NV) Every time you call label 2.Number of constraint check (#CC) Every time you call check(i,j) 3.CPU time Be as honest and consistent as possible 4.Number of Backtracks (#BT) Every un-assignment of a variable in unlabel 5.Some specific criterion for assessing the quality of the improvement proposed Presentation of values: Descriptive statistics of criterion: average, median, mode, max, min (qualified) run-time distribution Solution-quality distribution.Foundations of Constraint Processing Evaluation to BT Search 3 CSP parameters Binary: n,a,p 1,t Non-binary: n,a,p 1,k,t Number of variables: n Domain size: a, d Degree of a variable: deg Arity of the constraints: k Constraint tightness: Proportion of constraints (a.k.a., constraint density, constraint probability) p 1 = e / e max, e is number of constraints.Foundations of Constraint Processing Evaluation to BT Search 2 Outline Evaluation of (deterministic) BT search algorithms CSP parameters Comparison criteria Theoretical evaluations Empirical evaluations.

Choueiry (Shu-we-ri) Avery Hall, Room 360 Tel: +1(402)472-5444 Evaluation of (Deterministic) BT Search Algorithms

Foundations of Constraint Processing Evaluation to BT Search 1 Foundations of Constraint Processing CSCE421/821, Spring 2011 All questions to Berthe Y.

Btsearch 2008