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

[Christian Schulte]

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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Jonathan Skovhus Andersen
Sent: Tuesday, April 05, 2011 9:51 AM
To: users at gecode.org
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 <zayenz at gmail.com>

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

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
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users




-- 
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/2e24b3e0/attachment-0001.htm>