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

[Jonathan Skovhus Andersen]

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 <zayenz at gmail.com>

> 2011/4/5 Jonathan Skovhus Andersen <jonathanskovhus at gmail.com>
>
>> 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/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110405/41139700/attachment.htm>