*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 <[email protected]> > 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 <[email protected]> > >> *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 >> [email protected] >> https://www.gecode.org/mailman/listinfo/gecode-users >> >> > > > -- > Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/ >
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
