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

[Mikael Zayenz Lagerkvist]

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