[BCP] tail-off and early branching

[Mustafa Kilinc]

Hello Laci,
I am already overriding BCP_lp_user::compute_lower_bound() method. I 
think the issue is with the presolve in strong branching. I solved my 
problem by disabling strong branching.

Mustafa

On 09/30/2011 10:34 PM, Laszlo Ladanyi wrote:
> 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
>>      
>