[gecode-users] BAB Observation
Dean Hiller
hiller at employees.org
Wed Jul 31 15:53:17 CEST 2013
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
More information about the users
mailing list