Timetabling at Purdue University
March 31, 2010
Part II: Iterative Forward Search
Iterative Forward Search
IFS(P, Fwcsp, <wcsp, ) P = (V , D, C, wc, w)
1: function IFS(P, F, <, )
2: i = 0
3:  = 
4:  = 
5: while canContinue(, i) do
6: i = i + 1
7: v = selectVariable(P, )
8: d = selectValue(P, , , F, <, v)
9:  = hardConflicts(P, , v/d)
10:  = \  {v/d}
11: if F(, ) < F(, ) then  = 
12: end while
13: return 
14: end function
Hana Rudová (FI MU): Timetabling at Purdue University 2/5
Function for computing conflicting variables
1: function hardConflicts(P, , v/d)
2: if dv : v/dv   then  = {v/dv }
3: else  = 
4: for c  Ch  v  scope(c) do
5:  = \  {v/d}
6: if  c then
7: find   \ such that \ c
8:  =   
9: end if
10: end for
11: return 
12: end function
Hana Rudová (FI MU): Timetabling at Purdue University 3/5
Conflict-based statistics for class CS 101 Lab 2
Hana Rudová (FI MU): Timetabling at Purdue University 4/5
Conflict-based statistics
Example
x = 1  3 ×  y = 2, 4 ×  y = 3, 2 ×  z = 1, 120 ×  v = 1
CBS[x = dx   y = dy ] = cxy : the assignment x = dx caused a
hard conflict with the assignment y = dy cxy times in the past.
Hana Rudová (FI MU): Timetabling at Purdue University 5/5
Conflict-based statistics
Example
x = 1  3 ×  y = 2, 4 ×  y = 3, 2 ×  z = 1, 120 ×  v = 1
CBS[x = dx   y = dy ] = cxy : the assignment x = dx caused a
hard conflict with the assignment y = dy cxy times in the past.
If a value d is selected for a variable v within the IFS, then
hardConflicts(P, , v/d) chooses previous assignments
 = {v1/d1, v2/d2, . . . vn/dn} to be unassigned in order to enforce
consistency of the new partial assignment.
As a consequence, the counters are incremented
CBS[v = d   v1 = d1], CBS[v = d   v2 = d2], ...,
CBS[v = d   vn = dn] .
Hana Rudová (FI MU): Timetabling at Purdue University 6/5
Conflict-based statistics
Example
x = 1  3 ×  y = 2, 4 ×  y = 3, 2 ×  z = 1, 120 ×  v = 1
CBS[x = dx   y = dy ] = cxy : the assignment x = dx caused a
hard conflict with the assignment y = dy cxy times in the past.
If a value d is selected for a variable v within the IFS, then
hardConflicts(P, , v/d) chooses previous assignments
 = {v1/d1, v2/d2, . . . vn/dn} to be unassigned in order to enforce
consistency of the new partial assignment.
As a consequence, the counters are incremented
CBS[v = d   v1 = d1], CBS[v = d   v2 = d2], ...,
CBS[v = d   vn = dn] .
Conflict-based statistics are used as part of the value selection
criterion. Evaluation for value d of v
vi /di   vi /di hardConflicts(P,,v/d)
CBS[v = d  vi = di ]
Hana Rudová (FI MU): Timetabling at Purdue University 7/5
Particular runs with results for student enrollments (S),
time preferences (T), room preferences (R),
distribution preferences (D)
Final Run separately Run combined Bound
Problem S T R D S T R D S T R D S T R
pu-spr07-llr 98.63 89.71 92.86 66.67 98.86 93.20 86.90 72.22 97.67 90.11 84.86 63.47 99.42 98.82 99.4
pu-fal07-llr 98.76 81.77 91.69 96.55 99.00 89.49 78.05 93.56 98.25 88.18 74.98 63.69 99.54 96.29 98.9
pu-spr07-ms 99.37 68.34 76.22 57.14 99.62 75.45 75.96 48.39 98.28 77.42 73.98 55.98 99.87 86.11 94.5
pu-fal07-ms 97.80 71.48 80.00 72.73 99.62 71.88 86.33 63.68 98.99 70.60 85.42 52.86 99.71 84.39 97.5
pu-spr07-cs 94.85 83.86 100.00 33.33 97.15 73.91 100.00 33.33 93.56 70.92 100.00 44.17 98.55 86.27 100.0
pu-fal07-cs 94.14 83.20 90.48 100.00 98.53 76.40 83.49 89.67 97.15 76.09 83.17 70.19 99.28 96.91 100.0
pu-spr07-cfs 93.72 87.32 94.44 100.00 97.66 89.74 82.22 82.50 93.70 93.32 79.63 64.17 98.42 99.12 100.0
pu-fal07-cfs 94.09 96.30 50.00 86.67 98.12 97.14 85.00 92.67 94.70 94.97 66.67 84.30 98.52 100.00 100.0
pu-spr07-vpa 92.70 2.44 40.00 100.00 97.08 88.62 76.67 100.00 95.41 81.30 76.00 100.00 97.69 90.24 100.0
pu-fal07-vpa 93.19 0.00 100.00 100.00 96.79 0.00 100.00 100.00 95.06 0.00 100.00 100.00 96.79 0.00 100.0
pu-spr07-lab 97.45 87.60 75.76 68.02 99.39 94.08 69.19 50.30 97.71 94.58 68.15 57.00 99.82 97.67 83.3
pu-fal07-lab 85.42 89.74 71.46 77.03 97.71 84.73 44.25 38.15 97.29 85.95 39.32 22.00 98.12 93.69 87.6
pu-spr07-c8 97.99 84.87 82.81 61.39 98.69 90.16 77.37 50.70 98.16 89.91 75.79 56.58 98.95 97.55 91.9
pu-fal07-c8 98.35 83.01 87.55 78.00 98.63 86.70 73.49 61.04 98.55 86.62 70.43 54.18 99.35 95.76 96.3
Hana Rudová (FI MU): Timetabling at Purdue University 8/5
IFS as a Generic Framework
IFS for classical initial problem:
IFS(P, Fwcsp, <wcsp, )
IFS for feasibility problem:
IFS(P, Fcsp, <csp, )
IFS for minimal perturbation problem:
IFS(P, Fmpp, <mpp, )
Hana Rudová (FI MU): Timetabling at Purdue University 9/5
Feasibility Problem
Feasibility problem allows the detection of possible inconsistencies in
hard constraints
Any inconsistencies must be removed from the problem by the human
schedule manager
Cost of feasibility problem
Fcsp =  .
The ordering csp between costs of feasibility problem of two
consistent assignments:
Fcsp csp Fcsp  (    ) .
Any solution  has the best possible value Fcsp corresponding to the
number of the variables in the problem.
Hana Rudová (FI MU): Timetabling at Purdue University 10/5
Minimal Perturbation Problem (MPP)
Existing timetable + requests for changes
MPP: minimization of changes to the original solution (perturbations)
Definition of MPP:
constraint satisfaction problem (V , D, C) to be solved
initial assignment : consistent assignment of the original problem
distance function : evaluates the number of changes
between two assignments
Hana Rudová (FI MU): Timetabling at Purdue University 11/5
Minimal Perturbation Problem (MPP)
Existing timetable + requests for changes
MPP: minimization of changes to the original solution (perturbations)
Definition of MPP:
constraint satisfaction problem (V , D, C) to be solved
initial assignment : consistent assignment of the original problem
distance function : evaluates the number of changes
between two assignments
Distance functions:
var(, ) = {x/d1|x/d1    x/d2    d1 = d2}
time(, ) = {x/d1|x/d1    x/d2    time(d1) = time(d2)}
Optimal solution of MPP:
solution  of (V , D, C) having minimal distance (, )
Hana Rudová (FI MU): Timetabling at Purdue University 12/5
MPP in IFS
Weighted constraint satisfaction problem P = (V , D, C, wc, w)
Cost of MPP
Fmpp(, ) = (  , Fs + wmpp(, )) .
The ordering between costs of MPP for two consistent assignments
 and  wrt. the same initial assignment :
Fmpp(, ) mpp Fmpp(, ) 
((  >  )  ((  =  )  (Fs + wmpp(, )  Fs + wmpp(, )))
Hana Rudová (FI MU): Timetabling at Purdue University 13/5
MPP and Value Ordering
Consistent assignment  and an initial assignment  with
Fmpp = (  , Fs + wmpp(, ))
New assignment v/d, v not in 
The possible contribution to Fs() is Fs(, v/d):
same as for the initial problem
The contribution to the distance function var:
var(, v/d) =
wmpp v/di    di = d
0 otherwise .
The total contribution: Fs(, v/d) + (, v/d)
used as a value ordering heuristic
Hana Rudová (FI MU): Timetabling at Purdue University 14/5
Evaluation of MPP: Additional Classes Moved in Time
0
2
4
6
8
10
12
14
16
0 5 10 15 20 25 30 35 40 45 50
Numberofadditionalclassesmovedintime
Number of classes requiring a time change
Fall 2007: Additional vs given class changes in time
Hana Rudová (FI MU): Timetabling at Purdue University 15/5
Evaluation of MPP: Additional Affected Students
0.0%
0.5%
1.0%
1.5%
2.0%
2.5%
3.0%
0% 1% 2% 3% 4% 5% 6% 7%
Additionalaffectedstudents
Given affected students
Fall 2007: Additional to given students affected by a time change
Hana Rudová (FI MU): Timetabling at Purdue University 16/5
Evaluation of MPP: Changes in Criteria
84%
86%
88%
90%
92%
94%
96%
98%
100%
0 5 10 15 20 25 30 35 40 45 50
Changeofcriteria
Number of classes requiring a time change
Fall 2007: Solution quality
Student Enrollments
Time Preferences
Room Preferences
Distribution Preferences
Hana Rudová (FI MU): Timetabling at Purdue University 17/5