<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body text="#000000" bgcolor="#ffffff">
Hello,<br>
I am trying to solve a very hard problem with column generation. I am
using Bcp-1.3.0<br>
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.<br>
<br>
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. <br>
<br>
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 <br>
child nodes true lower bound values are set to LP relaxation value.
Below is the relevant part of the output. <br>
<br>
<i>LP: Starting strong branching:<br>
<br>
LP: Default prepare_for_optimization() executed.<br>
CPX0000<br>
CPX0000 Iteration log . . .<br>
CPX0000 Iteration: 1 Dual objective = -4472.140155<br>
CPX0000 Iteration: 77 Dual objective = -4453.177474<br>
CPX0000 Iteration: 148 Dual objective = -4436.405125<br>
CPX0000 Iteration: 221 Dual objective = -4429.682745<br>
LP: Default test_feasibility() executed.<br>
LP: Default test_full() executed.<br>
LP: Default prepare_for_optimization() executed.<br>
LP: Default test_feasibility() executed.<br>
LP: Default test_full() executed.<br>
LP: Default pack_feasible_solution() executed.<br>
TM: Default unpack_feasible_solution() executed.<br>
TM: Solution found at 84.289 sec.<br>
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<br>
LP: Presolving:
(27,0.0000,0.0000;28,0.0000,0.0000;................../ )
[-4429.3249,2,251] [-4472.2686,2,0]<br>
LP: Default compare_presolved_branching_objects() executed.<br>
LP: Default set_actions_for_children() executed.<br>
<br>
LP: SB selected candidate 0 out of 1.<br>
LP: Default prepare_for_optimization() executed.<br>
CPX0000 Parallel mode: deterministic, using up to 2 threads for
concurrent optimization.<br>
LP: Returned children to TM. Waiting for new node.<br>
TM: Pruning NODE 1 LEVEL 1 instead of sending it.<br>
TM: Pruning NODE 2 LEVEL 1 instead of sending it.<br>
TM: final statistics:<br>
TM: Running time: 34.321</i>
<br>
<br>
<br>
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.<br>
<br>
<i><br>
at ../../../Bcp/src/TM/BCP_tm_functions.cpp:172<br>
<br>
if (next_node->getTrueLB() > p.ub() - p.granularity())<br>
process_this = false;<br>
if (next_node->getTrueLB() ><br>
p.ub() - p.param(BCP_tm_par::TerminationGap_Absolute))<br>
process_this = false;<br>
if (next_node->getTrueLB() ><br>
p.ub() * (1 - p.param(BCP_tm_par::TerminationGap_Relative)))<br>
process_this = false;<br>
<br>
at /home/mrk46/Bcp/Bcp-1.3.0/CoinUtils/src/CoinSearchTree.hpp:96<br>
96 inline double getTrueLB() const { return
true_lower_bound_; }<br>
</i><br>
<br>
Is there a way that I can avoid pruning of child nodes and accomplish
what I want in Bcp? <br>
<br>
Thanks,<br>
Mustafa Kilinc<br>
<br>
<br>
</body>
</html>