[BCP] Bounding in BCP

[alikoc at mail.utexas.edu]

This helps,

Thanks,

ali

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