[gecode-users] Lower bound for Branch-and-bound

[Jonathan Skovhus Andersen]

*Thanks for the quick response.*

I have read the documentation, but the 2 pages describing the circuit
constraint seems quite inadequate to me.

But anyway. The main problem I have is that I am dealing with problems where
it is not feasible to let the BAB search finish. Then I would like to
estimate how close this solution is to the optimum solution. Do you know if
there is any quick way to do this or do I have to implement my own
calculations of a lower bound to compare my solution to?

*Regards,*
*Jonathan Skovhus.*

2011/4/5 Mikael Zayenz Lagerkvist <zayenz at gmail.com>

> Hi,
>
> If you look in the code of the TSP example, you can see that the model uses
> a circuit constraint with costs variables. The propagation of this
> constraint is what computes the bounds for the cost variable. When a tour is
> found, the cost variable will be fixed.
>
> As for running BAB search for finding optimum solutions, the short answer
> is yes. It is what BAB search is used for.
>
> Please read the documentation in Modeling and Programming with Gecode,
> where it is all described. Section 2.5 and 8.1 describe best solution search
> and circuit constraints respectively.
>
> Cheers,
> Mikael
>
> 2011/4/5 Jonathan Skovhus Andersen <jonathanskovhus at gmail.com>
>
>> *Hi,*
>>
>> I have been using the Travelling Salesman Problem-case in Gecode for some
>> time now. I am using Branch-and-bound.
>>
>>    - I can't see exactly how Gecode computes the lower and upper bound?
>>    There are many ways of computing a lower bound for a TSP and I would like to
>>    know how Gecode does it. When I open Gist it shows what I believe to be the
>>    lower and upper bound when I double click the root node (see attached
>>    image).
>>    - Does it makes sense to use the lower bound for assessing the quality
>>    of the tour found?
>>    - If I let the branch-and-bound algorithm finish am I sure of finding
>>    the optimum tour?
>>
>> I hope that you will bear with me - I am new in this field.
>>
>> *Regards,*
>> *Jonathan Skovhus*
>> *Aalborg University*
>> *Denmark*
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
>>
>>
>
>
> --
> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110405/ed996d26/attachment.htm>