[BCP] Bounding in BCP

[Laszlo Ladanyi]

You don't need to play tricks :-), or more precisely you should not...

There are two parameters:
BCP_TerminationGap_Absolute and BCP_TerminationGap_Relative.

Here is the piece of code that shows how they are used (it's in the 
BCP_tm_start_one_node function in BCP_tm_functions.cpp):

 	if (next_node->getTrueLB() > p.ub() - p.granularity())
 	    process_this = false;
 	if (next_node->getTrueLB() >
 	    p.ub() - p.param(BCP_tm_par::TerminationGap_Absolute))
 	    process_this = false;
 	if (next_node->getTrueLB() >
 	    p.ub() * (1 - p.param(BCP_tm_par::TerminationGap_Relative)))
 	    process_this = false;

next_node is the next candidate node in the priority queue. If there is no 
upper bound yet then the node is processed. If there is an ub then these are 
tested, and if process_this remains true then the node is processed, otherwise 
it is discarded.

I hope this helps,
--Laci

On Fri, 15 Feb 2008, alikoc at mail.utexas.edu wrote:

> Hi,
>
> Thanks much. But some parts still remain unclear for me.
>
> I can use BCP_Granularity only in 'LP_user' classes. But when TM sends next
> candidate node to one of available 'LP_user' class, it also checks whether the
> lower bound of the node is worse than the incumbent. There, it does not use
> BCP_Granularity. There, I need to be able to prevent the node from being sent,
> if it is within \epsilon.
>
> On updating the upper bound for relative termination:
> There are two 'upper_bound' variables; one in LP_prob class, which we have
> access when we are solving the LP relaxation of the current node through
> LP_user class. This upper bound is local. Updating this upper bound has effect
> to current node being processed. The next nodes we are processing will not be
> aware of whether we updated this or not.
>
> If we want to update the global upper bound; there is one in TM_prob class. But
> we cannot directly set its value to something else, as the user interface by
> the TM_user class is very limited. What we can do is, whenever we find a
> feasible solution, we set its objective value to 0.95xz* instead of z*. Then TM
> class, when processing the 'feasible solution' message, will take care of
> updating the global upper bound accordingly.
>
> But in this last case, there will be inconsistency in our feasible solution.
>
> I put what I was able to dig out in two days. I think it is confusing enough. It
> would be better if there was two global parameters for both absolute and
> relative terminations that also works in both LP and TM classes, without making
> us do some trickier stuff.
>
> Thanks,
>
> Ali
>
>
> Quoting fmargot at andrew.cmu.edu:
>
>>
>> For absolute termination gap, you may use the parameter BCP_Granularity
>> (set by default to 1e-8). For relative termination (say with a gap of 5%),
>> the simplest way is that each time a new fesible solution is found with value
>> v, update the BCP upper bound to 0.95 * v instead of v.
>>
>> Francois
>>
>>
>> On Thu, 14 Feb 2008, alikoc at mail.utexas.edu wrote:
>>
>>> Hi all,
>>>
>>> I am trying to see how early-termination works with BCP.
>>>
>>> If I want to terminate the search tree as soon as I am within \epsilon
>>> neighbourhood of the incumbent, either absolute or relative, what would I
>> do?
>>>
>>> One thing worked is returning 'BCP_DoNotBranch_Fathomed' in method
>>> 'select_branching_candidates()' as soon as i am within \epsilon. But, in
>> two
>>> more other locations, 'BCP_lp_main_loop class' is comparing the upper and
>> lower
>>> bounds, namely, after checking the true lower bound, and after generating
>> the
>>> heuristic solution. In those places, I cannot instruct BCP to use my
>> 'absolute'
>>> or 'relative' termination gap.
>>>
>>> Also, I tried two parameters: BCP_TerminationGap_Relative, and
>>> BCP_TerminationGap_Absolute, but could not succeed early termination. What
>> are
>>> these parameters for?
>>>
>>> Maybe I am confused. Appreciate any help.
>>>
>>> Thanks.
>>>
>>>
>>>
>>
>
>
>
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>