How to get the global lower bound in COIN BCP framework

Question

I'm currently working on a branch and price (BAP) algorithm using the COIN OR BCP framework. It's a nice framework but a bit old and the documentation is not good. I hope that someone here is able to answer my question.

My BAP algorithm is working fine, but i noticed that, what I thought was the global lower bound, was actually only a lower bound on the specific node in the branch and price tree. Sometimes I get slightly negative gaps :)

Thus, I dug into the internal parts of the framework looking for how to retrieve a globally valid lower bound. Strangely, it seems like this is not a feature of framework!

What I need is to get the lower bound in my tree class (dervived from BCP_tm_user) in order to report the solution gap.

Answer 1

I've been unable to get the global bounds using a nice and clean approach. I was however able to get hold of these values using an indirect approach. I'll share some insights below.

Lower Bound

It seems like the BCP tree manager keeps track of lower bounds at tree nodes in a std multiset data-structure. It puzzles me why they keep track of more than the lowest, since they only ever need the best lower bound at any time. It is possible to access the multiset datastructure in the *BCP_tm_user*, however these values are not global lower bounds. I did therefore try to obtain the root LP bound by overriding every possible virtual function (especiallyd *display_node_information*) in *BCP_tm_user*. The idea was to read the best lower bound right after the root node has been solved. It was unfortunately an unsuccessful approach, the best value in multiset was not the LP root bound.

Upper Bound

Similarly, I was unable to get a good method for extracting the best upper bound (i.e. feasible solution) in *BCP_tm_user*. The obvious method and simple method for getting the upper bound is to override *display_feasible_solution* and extract the value here. There is however a caveat to this apprach, if you decided to remove all (or most) BCP output, then *display_feasible_solution* is not called anymore!

My solution

Both bounds are accessible in the *BCP_lp_user* class, if you override *select_branching_candidates*. Calling *upper_bound()* here will give you the best upper bound available! And the LP relaxation solution value generated (once no columns with negative reduced cost exist) is a global lower bound in the root node. You know it is the root node if *this->current_level()==0* holds. If you need the bounds in the tree-manager, I suggest that you transfer (pack/unpack) them with the solutions that you send.

Answer 2

You can iterate through the tree, and find the lowest lower bound amongst the live nodes:

BCP_tree &search_tree = getTmProblemPointer().search_tree;
double global_lower_bound = BCP_DBL_MAX;
for (auto itt = search_tree.begin(); itt != search_tree.end(); itt++) {
    BCP_tm_node *tm_node = *itt;
    if (tm_node == NULL || tm_node->status == BCP_ProcessedNode) continue;
    double trueLB = tm_node->getTrueLB();
    global_lower_bound = min(global_lower_bound, trueLB);
}