[Coin-discuss] Global LB and UB

[Laszlo Ladanyi]

Hi Heesu,

On Fri, 16 Jun 2006, Heesu Hwang wrote:

> Hello, all.
> 
> I have been working on BCP, and I have some doubts on followings;
> 1. I want to access global lower bound (GLB) and upper bound (GUB). 
>     Could you tell me an easy way to access them?

I've got some good and some bad news...
GUB is easy. In the BCP_xx_user classes (from which you derive your
own) there's a non-virtual method upper_bound(). That will return to you the
current best solution value. Unfortunately there is no way at the moment to
extract GLB (not even in the tree manager since the priority queue may be
ordered differently than increasing lower bounds). 

> 2. I think COIN sets GLB right after the root node by solving the relaxed
> problem, then I wonder when COIN updates GLB again.

See answer above. Individual lower bounds are used for fathoming, so I never
bothered to store GLB. Come to think of it, I could add the feature, since it
may be handy for branching decisions, but I don't have the time at the moment.

> 3. At each node, if I generate more columns, LB for the node can be smaller
> value than that of old_lower_bound. 
>     In compute_lower_bound() if I return the new LB, then is old_lower_bound
> updated with the new LB?

Whatever you return there will be considered an honest-to-god true lower bound
which is a lower bound even if further columns are generated. BCP believes you
know what you are doing when you say it's a lower bound. In the next call to
compute_lower_bound() (supposing you are still in the same search tree node
:-) old_lower_bound will be what you have returned in the previous one.
Actually, that's not quite true. If the value you return is *less* than
old_lower_bound, then old_lower_bound will not get updated. After all, if both
values are true lower bounds then BCP can safely take the larger one.

> 
> Thanks,
> 
> Heesu.

Hope this helps,
--Laci