Timetabling at Purdue University
April 21, 2010
Part III: Interactive Timetabling
Suggestions
Changes with class "PSY 120 Lec 5" are considered
Hana Rudová (FI MU): Timetabling at Purdue University 2/15
Demonstration
See http://www.unitime.org/uct_demo.php for online demo
Hana Rudová (FI MU): Timetabling at Purdue University 3/15
Interaction Process: Variables
Timetabling problem P = (V , D, C, wc, w)
weighted constraint satisfaction problem
Initial solution 
initial timetable of the interaction process
Selected assignments : changes made with the timetable 
during current interaction
Selected class vbb
to modify its placement or to be placed into the timetable
Hana Rudová (FI MU): Timetabling at Purdue University 4/15
Interaction Process: Variables
Timetabling problem P = (V , D, C, wc, w)
weighted constraint satisfaction problem
Initial solution 
initial timetable of the interaction process
Selected assignments : changes made with the timetable 
during current interaction
Selected class vbb
to modify its placement or to be placed into the timetable
Suggestions : set of generated assignments 
making the timetable feasible (all hard constraints are satisfied)
Conflicting assignments 
set of assignments conflicting with selected assignments 
Hana Rudová (FI MU): Timetabling at Purdue University 5/15
Simplified Interaction Process
procedure INTERACTION(P, , vbb)
 = 
A = 
while true do
 = BB(P  A, , , vbb)
Hana Rudová (FI MU): Timetabling at Purdue University 6/15
Simplified Interaction Process
procedure INTERACTION(P, , vbb)
 = 
A = 
while true do
 = BB(P  A, , , vbb)
S = COMMUNICATION()
Hana Rudová (FI MU): Timetabling at Purdue University 7/15
Simplified Interaction Process
procedure INTERACTION(P, , vbb)
 = 
A = 
while true do
 = BB(P  A, , , vbb)
S = COMMUNICATION()
case (S) commit(  ):  = join(,   ); return
abort: return
selectAssignment(dn):  =   {vbb/dn}
selectFilter(): A = vbb
end case
end while
end procedure
Hana Rudová (FI MU): Timetabling at Purdue University 8/15
Simplified Interaction Process
procedure INTERACTION(P, , vbb)
 = 
A = 
while true do
(,) = BB(P  A, , , vbb)
S = COMMUNICATION(, )
case (S) commit(  ):  = join(,   ); return
abort: return
selectAssignment(dn):  =   {vbb/dn}
selectFilter(): A = vbb
selectClass(c  {    }): vbb = c
removeClass(c  ):  = \{c/dc}
end case
end while
end procedure
Hana Rudová (FI MU): Timetabling at Purdue University 9/15
Branch and Bound (BB)  = BB(P  A, , , vbb)
Variables
weighted constraint satisfaction problem with filter P = P  A
initial timetable 
selected assignments 
class to be (re-)placed vbb
Initialization
compute conflicting assignment caused by 
Run BB to find assignments of variables for
class vbb
classes involved in conflicting assignments
Hana Rudová (FI MU): Timetabling at Purdue University 10/15
Branch and Bound (continues)
Run BB
n best suggestions  are given to user
search with timeout
best values based on Fs(, v/d) explored first
conflict-based statistics not taken into account (too expensive)
Bounds
limited search depth
to allow changes of small number of variables only
to include changes of one new class
it does make sense to change too many other classes
M: maximum depth
Fwcsp must be better than the n-th best found suggestion
[n]: n-th best suggestion
Hana Rudová (FI MU): Timetabling at Purdue University 11/15
Branch and Bound (continues)
Run BB
n best suggestions  are given to user
search with timeout
best values based on Fs(, v/d) explored first
conflict-based statistics not taken into account (too expensive)
Bounds
limited search depth
to allow changes of small number of variables only
to include changes of one new class
it does make sense to change too many other classes
M: maximum depth
Fwcsp must be better than the n-th best found suggestion
[n]: n-th best suggestion
Repeat BB: process another run of BB with
increased search depth or
increased timeout
Hana Rudová (FI MU): Timetabling at Purdue University 12/15
Branch & Bound
1: function BB(P, , , vbb)
2: if {vbb/d}   then  = \{vbb/d}
3: else d = nil
4:  = {vbb/d}
5: for vi /di   do
6: if {vi /do}   then o = {vi /do}
7: else o = 
8:  =   hardConflicts(P, , vi /di )\o
9:  = \o  {vi /di }
10: end for
11: return backtrack(P, , , , , 0)
12: end function
Hana Rudová (FI MU): Timetabling at Purdue University 13/15
Function backtrack
1: function backtrack(P, , , , , m)
2: if  + m > M +  then return 
3: if  =  then return 
4: if timeout then return 
5: if LB(Fwcsp(  )) wcsp Fwcsp([n]) then return 
6: v = selectVariableBB()
7: let v/do  
8: for d  Dv ordered by Fs(, v/d) do
9: if d = do then continue
10:  = hardConflicts(P, , v/d)
11: if    =  then continue
12:  =   backtrack(P,   {v/d},   {v/d},
\{v/do}  , , m + 1)
13: end for
14: return 
15: end function
Hana Rudová (FI MU): Timetabling at Purdue University 14/15
Experiments
Problem pu-fal07-llr pu-spr07-llr
Classes 891 803
Classes fixed in time & room (%) 31.0 33.8
Classes not fixed in time & room (%) 69.0 66.2
Time limit (s) ­ 5 ­ 5
Time spent (s) 128.6 4.7 39.9 4.2
Complete space explored 98.4 21.5 99.2 33.3
No suggestion found (%) 1.6 2.3 0.8 0.8
Number of suggestions 232.8 174.9 228.6 184.5
Number of backtracks 66367.9 2886.9 13949.1 2592
Optimal suggestion found (%) 98.4 51.5 99.2 67.0
Improvements in objective function (%) +1.1 +0.8 +0.9 +0.7
Hana Rudová (FI MU): Timetabling at Purdue University 15/15