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.
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
