[BCP] Bounding in BCP

[alikoc at mail.utexas.edu]

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