[gecode-users] BAB Observation

[Dean Hiller]

I was having a problem with finding all my solutions while using BAB.
I finally created a very simple model that demonstrated my problem
and using that model, I was able to find a solution to the problem.

I could not find this issue discussed anywhere, so I am going to
describe it here in case any one else runs into it and is looking
for a solution to it.

This is the scenario:

IntVar X(0,1);
branch(X, INT_VAL_MIN());
IntVar Y(0,2);
branch(Y, INT_VAL_MIN());
IntArgs C(1,2);
IntVarArray V(2, 0, 2);
rel(V[0] == X);
rel(V[1] == Y);
IntVar Cost(0,5);
linear(C, X, V, IRT_EQ, Cost);

If I solve this with DFS, I get 6 solutions.
If I solve this with BAB and in the constrain function say
rel(cost > b.cost);
I only get 4 solutions.

Note: If I run with GIST and expand the nodes in the
correct order, I can cause BAB to display all 6 solutions,
but the normal search order does not find all of them.

To have BAB find all 6 solutions, I removed the above
two branch statements and replaced them with
branch(Cost, INT_VAL_MIN());

So, the general rule I would conclude from this test is
that when using linear to create a cost function for
BAB, always branch on the output of the equation rather
than on the terms making up the equation.

I don't know if this holds true for other uses of linear.

Dean