[BCP] tail-off and early branching

[Mustafa Kilinc]

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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/bcp/attachments/20110930/b58ab731/attachment.html>