DM826 - Modeling and Solving Constrained Optimization Problems
Sheet 5, Spring 2012 [pdf format]

Prepare the following exercises for discussion in class on Monday 5th March 2012.

Exercise 1  

Assume a CSP:

 P= ⟨ X= {x, y, z},  DE={1, 2, 3, 4},  C≡{x < y, y < z}⟩

and a branching b defined as follows:

     
b =  if  |D(x)| > 1  and  D(x) = {n1,…,nk} then          
 ⟨ {assign(x, n1)},…, {assign(x, nk)}⟩         
  else if  D(y) > 1  and  D(y) = {n1,…, nk}  then          
 ⟨{assign( y, n1 )}, …, {assign( y, nk )}⟩         
  else          
 ⟨ ⟩          

where the propagator assign(u, n) for a variable u∈ X and a value n ∈ D(u) is defined as

assign(u, n)(v) =  if  (u = v)  then  n ⋃ D(v) else  D(v)

Draw the resulting search tree.

Exercise 2  

Discussion on Assignment 1, Pentominoes and Binpacking problems.