[gecode-users] BAB Observation

[Christian Schulte]

Next() makes perfect sense: each solution delivered by next() is better than
the previous. The last is a best solution.

Christian

--
Christian Schulte, www.ict.kth.se/~cschulte

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Dean Hiller
Sent: Thursday, August 1, 2013 05:43 AM
To: Guido Tack
Cc: users at gecode.org
Subject: Re: [gecode-users] BAB Observation

Are you saying that using "next" in a loop makes no sense with BAB in that
only the first result is the optimal result and the "next"
result is not the next optimal result, but just another possible result?

Thanks,
Dean


On Wed, 31 Jul 2013 23:19:37 -0400, Guido Tack <tack at gecode.org> wrote:

> 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

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users