[BCP] tail-off and early branching

[Laszlo Ladanyi]

I suppose you did override the BCP_lp_user::generate_vars_in_lp()
method, but you also need to override the
BCP_lp_user::compute_lower_bound() method. There you can return a true
lower bound you compute with the dual information.

--Laci

On 09/30/2011 12:29 PM, Mustafa Kilinc wrote:
> Hello,
> I am trying to solve a very hard problem with column generation. I am
> using Bcp-1.3.0
> Because of tail-off, there are still too many variables with negative
> reduced cost. I can not prove that LP relaxation of reduced master is
> optimal, but I can bound it by using dual information.
> 
> I want to branch before pricing out all variables. I hope that I would
> get good lower bounds after branching. To do this,  I set
> BCP_LpValueIsTrueLowerBound to zero.
> 
> Since I happen to have a very good upped bound (equal to last root LP
> relaxation), child nodes are pruned at the tree manager. I tried to
> understand why this is happening. I realized that
> child nodes true lower bound values are set to LP relaxation value. 
> Below is the relevant part of the output.
> 
> /LP: Starting strong branching:
> 
> LP: Default prepare_for_optimization() executed.
> CPX0000
> CPX0000  Iteration log . . .
> CPX0000  Iteration:     1   Dual objective     =         -4472.140155
> CPX0000  Iteration:    77   Dual objective     =         -4453.177474
> CPX0000  Iteration:   148   Dual objective     =         -4436.405125
> CPX0000  Iteration:   221   Dual objective     =         -4429.682745
> LP: Default test_feasibility() executed.
> LP: Default test_full() executed.
> LP: Default prepare_for_optimization() executed.
> LP: Default test_feasibility() executed.
> LP: Default test_full() executed.
> LP: Default pack_feasible_solution() executed.
>  TM: Default unpack_feasible_solution() executed.
> TM: Solution found at 84.289 sec.
> TM 34.301: Sol from proc: 1  val: -4472.268574 (prev best:
> -4472.268574)  tree size/procd: 1/0  cand list ins/size: 1/0
> LP:   Presolving: 
> (27,0.0000,0.0000;28,0.0000,0.0000;................../  )
> [-4429.3249,2,251] [-4472.2686,2,0]
> LP: Default compare_presolved_branching_objects() executed.
> LP: Default set_actions_for_children() executed.
> 
> LP:   SB selected candidate 0 out of 1.
> LP: Default prepare_for_optimization() executed.
> CPX0000  Parallel mode: deterministic, using up to 2 threads for
> concurrent optimization.
> LP:   Returned children to TM. Waiting for new node.
> TM: Pruning NODE 1 LEVEL 1 instead of sending it.
> TM: Pruning NODE 2 LEVEL 1 instead of sending it.
> TM: final statistics:
> TM: Running time: 34.321/
> 
> 
> The relevant parts of the BCP code are given below. At line 172 of
> ../../../Bcp/src/TM/BCP_tm_functions.cpp, next_node->getTrueLB() is
> called to get true lower bound and this is an inline function at line 96
> of Bcp/Bcp-1.3.0/CoinUtils/src/CoinSearchTree.hpp.
> 
> /
> at ../../../Bcp/src/TM/BCP_tm_functions.cpp:172
> 
>        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;
> 
> at /home/mrk46/Bcp/Bcp-1.3.0/CoinUtils/src/CoinSearchTree.hpp:96
> 96        inline double       getTrueLB()        const { return
> true_lower_bound_; }
> /
> 
> Is there a way that I can avoid pruning of child nodes and accomplish
> what I want in Bcp?
> 
> Thanks,
> Mustafa Kilinc
> 
> 
> 
> 
> 
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp