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

[Mikael Zayenz Lagerkvist]

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/1e04074f/attachment.htm>