[gecode-users] BAB Observation

[Guido Tack]

Hi,

BAB is not meant to produce all solutions, the only guarantee it gives is that the last solution is going to be optimal, but intermediate solutions can be skipped (that's in fact the whole point of BAB).
If you need all solutions and still want to know which one is best, simply use DFS and then sort the solutions afterwards.

Cheers,
Guido

On 31/07/2013, at 11:53 PM, Dean Hiller <hiller at employees.org> wrote:

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