Hi,
Please remember, MPG tells what is in Gecode and how it can be used but not how everything has been invented ;-) If you want to assess the quality, you need to compute a lower bound yourself. It might even make sense to use other methods for computing lower and/or upper bounds. An example for this you can find in MPG, "Bin packing" where both lower and upper bounds are essential. Best Christian -- Christian Schulte, www.ict.kth.se/~cschulte/ From: [email protected] [mailto:[email protected]] On Behalf Of Jonathan Skovhus Andersen Sent: Tuesday, April 05, 2011 9:51 AM To: [email protected] Subject: Re: [gecode-users] Lower bound for Branch-and-bound 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
