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

[Jonathan Skovhus Andersen]

*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*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110405/e2f1e904/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TSP.jpg
Type: image/jpeg
Size: 105638 bytes
Desc: not available
URL: <http://www.gecode.org/pipermail/users/attachments/20110405/e2f1e904/attachment-0001.jpg>