[BCP] Bounding in BCP

[fmargot at andrew.cmu.edu]

I believe you are looking too much into the code. Try to set
BCP_Granularity to 1.0 in the parameter file. Without changing a single
line of code, BCP will output a solution within 1.0 of the optimal value.
You have nothing else to do than setting BCP_Granularity to the value you
want.

Fot the relative gap, I would try in your derived class of 
BCP_lp_user::test_feasibility() something like

   BCP_solution *curr_sol = BCP_lp_user::test_feasibility(lp_result, vars, cuts);

   if(curr_sol != NULL) {
     if(curr_sol->objective_value() > 0.95 * upper_bound()) {
       delete(curr_sol);
       return(NULL);
     }
     return(curr_sol);
   }

I don't think anything else is needed. I agree that a parameter for relative
gap would be simpler.

Francois


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.
>>>
>>>
>>>
>>
>
>
>
>
>