[gecode-users] BAB and pruning

[aqwzsxaqwzsx at orange.fr]

Hi,
 
I have a general question on BAB engine in Gecode.
Suppose I have to affect 4 jobs to 4 persons and i want to minimize
the cost of this affectation (using a MinimizeScript) :
 
cost_matrix :
    J1  J2  J3  J4
--|----------------  
A | 9,  2,  7,  8
B | 6,  4,  3,  7
C | 5,  8,  1,  8
D | 7,  6,  9,  4
 
 
Suppose also that I post these constraints :
(e.g., exactly one person to exactly one job)
 
x(*this, cols*rows, 0, 1)  // array of assignments (as rows x cols)
 
for(int r = 0; r < rows; r++)         
  { linear(*this, x_m.row(r), IRT_EQ, 1); }
 
for(int c = 0; c < cols; c++)           
  { linear(*this, x_m.col(c), IRT_EQ, 1); }
 
linear(*this, cost, x, IRT_EQ, total_cost);
branch(*this, x, INT_VAR_NONE(), INT_VAL_MAX());
               
with x an array of assignments (and x_m its matrix representation)
 
Now, let's make some reasoning :
 
- if I affect J1 to person A, the minimum cost that we can expect is 17
  (9 + 3 + 1 + 4) = 9 + (J3/B) + (J3/C) + (J4/D)
- if I affect J2 to person A, the minimum cost that we can expect is 10
  (2 + 3 + 1 + 4) = 2 + (J3/B) + (J3/C) + (J4/D)
- if I affect J3 to person A, the minimum cost that we can expect is 20
  (7 + 4 + 5 + 4) = 7 + (J2/B) + (J1/C) + (J4/D)
- if I affect J4 to person A, the minimum cost that we can expect is 18
  (8 + 3 + 1 + 6) = 8 + (J3/B) + (J3/C) + (J2/D)
 
However, i see under Gist that for instance, the total cost when exploring
the J1/A alternative is [9..59](lower bound could be 17)
Is it normal that B&B cannot estimate more precisely the lower bound ?
Can we expect that the pruning will be more efficient ?
 
Thank you.