Thank you Christian and Mikael, this is helpful. I do have some side-constraints that have kept me from trying to implement a solution to the TSP myself in C# or C++.
Wouldn't it actually be possible to greatly improve the performance of the BAB search by calculating a more precise lower bound (for example the Held-Karp TSP bound). I just didn't know if this already has been done in Gecode. If anybode has tried this I would like to know. *Regards,* *Jonathan Skovhus*. 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/ 2011/4/5 Mikael Zayenz Lagerkvist <[email protected]> > 2011/4/5 Jonathan Skovhus Andersen <[email protected]> > >> I have read the documentation, but the 2 pages describing the circuit >> constraint seems quite inadequate to me. >> > > Looking at the source code (gecode/graph/circuit.cpp) shows that the cost > variant of circuit currently uses linear to compute the total cost. This > will not give a very good quality bound, since the computation does not use > the fact that the costs come from a circuit. > > > 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? >> > > My guess would be that a custom estimator is probably worth it, given that > there is something reasonable to implement. I haven't looked into this > though. Anybody else know anything? > > In general, for pure TSP problems I don't believe that CP is the best > technology choice. You might have interesting side-constraints though? > > Cheers, > Mikael > > -- > Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/ >
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
