[Coin-discuss] Global LB and UB

[Heesu Hwang]

Hi, all.

Thanks for the comment.
I have two more doubts...

Could you explain what is the best lower bound shown in the last statistics?
Is that from the lower bound of one branch or phase?

When does the new phase start? 

Thanks in advance.

Heesu.

-----Original Message-----
From: coin-discuss-bounces at list.coin-or.org
[mailto:coin-discuss-bounces at list.coin-or.org] On Behalf Of Laszlo Ladanyi
Sent: Saturday, June 17, 2006 8:14 PM
To: Discussions about open source software for Operations Research
Subject: Re: [Coin-discuss] Global LB and UB


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

_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss