BCP_lp_branching.cpp

Go to the documentation of this file.

// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
//#include <cfloat>
#include <cstdio>
#include <numeric>
#include <utility> // for pair<>

#include "CoinWarmStart.hpp"
#include "CoinTime.hpp"

#include "BCP_math.hpp"
#include "BCP_enum.hpp"
#include "BCP_matrix.hpp"
#include "BCP_warmstart.hpp"
#include "BCP_lp_result.hpp"
#include "BCP_lp_node.hpp"
#include "BCP_lp_user.hpp"
#include "BCP_lp_functions.hpp"
#include "BCP_lp_pool.hpp"
#include "BCP_lp_branch.hpp"
#include "BCP_lp.hpp"

//#############################################################################

static inline std::pair<int,int>
BCP_add_branching_objects(BCP_lp_prob& p,
                          BCP_vec<BCP_lp_branching_object*>& candidates);
static inline void
BCP_mark_result_of_strong_branching(BCP_lp_prob& p,
                                    const BCP_lp_branching_object* can,
                                    const int added_col_num,
                                    const int added_row_num);
static inline BCP_branching_decision
BCP_lp_select_branching_object(BCP_lp_prob& p,
                               BCP_presolved_lp_brobj*& best_presolved);
static inline void
BCP_lp_make_parent_from_node(BCP_lp_prob& p);

//#############################################################################

static inline void
BCP_print_brobj_stat(BCP_lp_prob& p,
                     const int orig_varnum,
                     const int candidate_num, const int selected,
                     const BCP_presolved_lp_brobj* best_presolved)
{
    const BCP_lp_branching_object* can = best_presolved->candidate();

    if (p.param(BCP_lp_par::LpVerb_StrongBranchResult)) {
        p.user->print(true, "\nLP:   SB selected candidate %i out of %i.\n\n",
                      selected, candidate_num);
        p.user->print(true, "LP:   The selected object is:");
        if (p.param(BCP_lp_par::LpVerb_StrongBranchPositions)) {
            can->print_branching_info(orig_varnum,
                                      p.lp_result->x(),
                                      p.lp_solver->getObjCoefficients());
        }
        for (int i = 0; i < can->child_num; ++i) {
            const BCP_lp_result& res = best_presolved->lpres(i);
            const double lb = res.objval();
            p.user->print(true,
                          (lb>BCP_DBL_MAX/10 ? " [%e,%i,%i]":" [%.4f,%i,%i]"),
                          lb, res.termcode(), res.iternum());
        }
        p.user->print(true, "\n");
    }
    // Print some statistics
    if (p.param(BCP_lp_par::LpVerb_ChildrenInfo)){
        const BCP_vec<BCP_child_action>& action = best_presolved->action();
        for (int i = can->child_num - 1; i >= 0; --i)
            switch (action[i]){
            case BCP_KeepChild:
            case BCP_ReturnChild:
                break;
            case BCP_FathomChild:
                p.user->print(true, "LP:   Child %i is fathomed.\n", i);
                break;
            }
    }
}

//#############################################################################

static inline std::pair<int,int>
BCP_add_branching_objects(BCP_lp_prob& p,
                          BCP_vec<BCP_lp_branching_object*>& candidates){
    // to make things short
    if (candidates.size() == 0)
        return std::pair<int,int>(0, 0);

    BCP_lp_branching_object* can;
    BCP_vec<BCP_lp_branching_object*>::iterator cani;
    BCP_vec<BCP_lp_branching_object*>::iterator lastcani = candidates.end();
    BCP_var_set& vars = p.node->vars;
    BCP_cut_set& cuts = p.node->cuts;

    // first count the number of cols/rows to add
    int newvar_num = 0;
    int newcut_num = 0;
    for (cani = candidates.begin(); cani != lastcani; ++cani){
        can = *cani;
        can->init_pos_for_added(vars.size() + newvar_num,
                                cuts.size() + newcut_num);
        if (can->vars_to_add)
            newvar_num += can->vars_to_add->size();
        if (can->cuts_to_add)
            newcut_num += can->cuts_to_add->size();
    }

    const int orig_col_num = vars.size();
    const int orig_row_num = cuts.size();

    OsiSolverInterface* lp = p.lp_solver;

    // deal with the vars
    if (newvar_num > 0){
        BCP_vec<BCP_var*> new_vars;
        new_vars.reserve(newvar_num);
        for (cani = candidates.begin(); cani != lastcani; ++cani){
            can = *cani;
            if (can->vars_to_add)
                new_vars.append(*can->vars_to_add);
        }

        BCP_vec<BCP_col*> cols;
        cols.reserve(newvar_num);
        p.user->vars_to_cols(cuts, new_vars, cols,
                             *p.lp_result, BCP_Object_Branching, false);
        BCP_lp_add_cols_to_lp(cols, lp);
        purge_ptr_vector(cols);

        for (int i = 0; i < newvar_num; ++i) {
            new_vars[i]->set_bcpind(-BCP_lp_next_var_index(p));
        }
        vars.append(new_vars);
    }

    // now add the rows
    if (newcut_num > 0){
        BCP_vec<BCP_cut*> new_cuts;
        new_cuts.reserve(newcut_num);
        for (cani = candidates.begin(); cani != lastcani; ++cani){
            can = *cani;
            if (can->cuts_to_add)
                new_cuts.append(*can->cuts_to_add);
        }

        BCP_vec<BCP_row*> rows;
        rows.reserve(newcut_num);
        BCP_fatal_error::abort_on_error = false;
        try {
            p.user->cuts_to_rows(vars, new_cuts, rows,
                                 *p.lp_result, BCP_Object_Branching, false);
        }
        catch (...) {
        }
        BCP_fatal_error::abort_on_error = true;
        BCP_lp_add_rows_to_lp(rows, lp);
        purge_ptr_vector(rows);

        for (int i = 0; i < newcut_num; ++i) {
            new_cuts[i]->set_bcpind(-BCP_lp_next_cut_index(p));
        }
        cuts.append(new_cuts);
        p.node->lb_at_cutgen.insert(p.node->lb_at_cutgen.end(), newcut_num,
                                    p.lp_result->objval());
    }

    // mark the newly added vars as fixed to 0, and the newly added cuts as
    // free. (var_indices and cut_indices simply contain the indices of the
    // added vars/cuts.)

    if (newvar_num > 0) {
        for (int i = orig_col_num; i < orig_col_num + newvar_num; ++i)
            lp->setColBounds(i, 0.0, 0.0);
    }
    if (newcut_num > 0) {
        const double inf = lp->getInfinity();
        for (int i = orig_row_num; i < orig_row_num + newcut_num; ++i)
            lp->setRowBounds(i, -inf, inf);
    }

    return std::pair<int,int>(newvar_num, newcut_num);
}

//#############################################################################

static inline void
BCP_mark_result_of_strong_branching(BCP_lp_prob& p,
                                    const BCP_lp_branching_object* can,
                                    const int added_col_num,
                                    const int added_row_num)
{
    BCP_var_set& vars = p.node->vars;
    if (can->forced_var_pos) {
        BCP_vec<int>::const_iterator ii = can->forced_var_pos->begin();
        BCP_vec<int>::const_iterator lastii = can->forced_var_pos->end();
        for ( ; ii != lastii; ++ii)
            vars[*ii]->make_non_removable();
    }
    if (can->implied_var_pos) {
        // just to make sure that these vars are not deleted before the implied
        // bound change takes place...
        BCP_vec<int>::const_iterator ii = can->implied_var_pos->begin();
        BCP_vec<int>::const_iterator lastii = can->implied_var_pos->end();
        for ( ; ii != lastii; ++ii)
            vars[*ii]->make_active();
    }
      
    if (added_col_num) {
        BCP_var_set::iterator vari = vars.entry(vars.size() - added_col_num);
        BCP_var_set::const_iterator lastvari = vars.end();
        for ( ; vari != lastvari; ++vari) {
            if (! (*vari)->is_non_removable())
                (*vari)->make_to_be_removed();
        }
    }

    BCP_cut_set& cuts = p.node->cuts;
    if (can->forced_cut_pos) {
        BCP_vec<int>::const_iterator ii = can->forced_cut_pos->begin();
        BCP_vec<int>::const_iterator lastii = can->forced_cut_pos->end();
        for ( ; ii != lastii; ++ii)
            cuts[*ii]->make_non_removable();
    }
    if (can->implied_cut_pos) {
        // just to make sure that these cuts are not deleted before the implied
        // bound change takes place...
        BCP_vec<int>::const_iterator ii = can->implied_cut_pos->begin();
        BCP_vec<int>::const_iterator lastii = can->implied_cut_pos->end();
        for ( ; ii != lastii; ++ii)
            cuts[*ii]->make_active();
    }
    if (added_row_num > 0){
        BCP_cut_set::iterator cuti = cuts.entry(cuts.size() - added_row_num);
        BCP_cut_set::const_iterator lastcuti = cuts.end();
        for ( ; cuti != lastcuti; ++cuti) {
            if (! (*cuti)->is_non_removable())
                (*cuti)->make_to_be_removed();
        }
    }
}

//#############################################################################

static inline int
BCP_lp_perform_strong_branching(BCP_lp_prob& p,
                                BCP_vec<BCP_lp_branching_object*>& candidates,
                                BCP_presolved_lp_brobj*& best_presolved)
{
    OsiSolverInterface* lp = p.lp_solver;
    BCP_var_set& vars = p.node->vars;
    BCP_cut_set& cuts = p.node->cuts;

    const int orig_colnum = vars.size();

    const std::pair<int,int> added_object_num =
        BCP_add_branching_objects(p, candidates);
   
    const int added_colnum = added_object_num.first;
    const int added_rownum = added_object_num.second;

    const int colnum = vars.size();
    const int rownum = cuts.size();

    int i, j; // loop variable

    const CoinWarmStart * ws = p.lp_solver->getWarmStart();

    // prepare for strong branching
    lp->markHotStart();

    // save the lower/upper bounds of every var/cut
    BCP_vec<double> rowbounds(2 * rownum, 0.0);
    BCP_vec<double> colbounds(2 * colnum, 0.0);

    const int maxind = std::max<int>(rownum, colnum);
    BCP_vec<int> all_indices(maxind, 0);
    for (i = 0; i < maxind; ++i)
        all_indices[i] = i;

    const double * rlb_orig = lp->getRowLower();
    const double * rub_orig = lp->getRowUpper();
    for (j = -1, i = 0; i < rownum; ++i) {
        rowbounds[++j] = rlb_orig[i];
        rowbounds[++j] = rub_orig[i];
    }

    const double * clb_orig = lp->getColLower();
    const double * cub_orig = lp->getColUpper();
    for (j = -1, i = 0; i < colnum; ++i) {
        colbounds[++j] = clb_orig[i];
        colbounds[++j] = cub_orig[i];
    }

    best_presolved = 0;

    // Look at the candidates one-by-one and presolve them.
    BCP_vec<BCP_lp_branching_object*>::iterator cani;

    if (p.param(BCP_lp_par::MaxPresolveIter) > 0) {
        lp->setIntParam(OsiMaxNumIterationHotStart,
                        p.param(BCP_lp_par::MaxPresolveIter));
    }

    p.user->print(p.param(BCP_lp_par::LpVerb_StrongBranchResult),
                  "\nLP: Starting strong branching:\n\n");

    const OsiBabSolver* babSolver = p.user->getOsiBabSolver();

    int cand_ind = -1;
    for (cani = candidates.begin(); cani != candidates.end(); ++cani){
        // Create a temporary branching object to hold the current results
        BCP_presolved_lp_brobj* tmp_presolved =
            new BCP_presolved_lp_brobj(*cani);
        const BCP_lp_branching_object* can = *cani;
        ++cand_ind;
        for (i = 0; i < can->child_num; ++i){
            can->apply_child_bd(lp, i);
            // bound changes always imply that primal feasibility is lost.
            p.user->modify_lp_parameters(p.lp_solver, 1, true);
#if 0
            char fname[1000];
            sprintf(fname, "matrix-%i.%i.%i-child-%i.%i",
                    p.node->level, p.node->index, p.node->iteration_count,
                    cand_ind, i);
            lp->writeMps(fname, "mps");
#endif
            lp->solveFromHotStart();
            tmp_presolved->get_results(*lp, i);
            BCP_lp_test_feasibility(p, tmp_presolved->lpres(i));
            if (babSolver) {
                p.user->generate_cuts_in_lp(tmp_presolved->lpres(i),
                                            p.node->vars, p.node->cuts,
                                            tmp_presolved->get_new_cuts()[i],
                                            tmp_presolved->get_new_rows()[i]);
            }
        }
        // reset the bounds of the affected vars/cuts
        if (can->cuts_affected() > 0)
            lp->setRowSetBounds(all_indices.begin(), all_indices.entry(rownum),
                                rowbounds.begin());
        if (can->vars_affected() > 0)
            lp->setColSetBounds(all_indices.begin(), all_indices.entry(colnum),
                                colbounds.begin());

        if (p.param(BCP_lp_par::LpVerb_PresolveResult)) {
            p.user->print(true, "LP:   Presolving:");
            if (p.param(BCP_lp_par::LpVerb_PresolvePositions)) {
                can->print_branching_info(orig_colnum,
                                          p.lp_result->x(),
                                          p.lp_solver->getObjCoefficients());
            }
            for (i = 0; i < can->child_num; ++i) {
                const BCP_lp_result& res = tmp_presolved->lpres(i);
                const double lb = res.objval();
                p.user->print(true,
                              (lb>BCP_DBL_MAX/10 ? " [%e,%i,%i]":" [%.4f,%i,%i]"),
                              lb, res.termcode(), res.iternum());
            }
            p.user->print(true, "\n");
        }
        // Compare the current one with the best so far
        switch (p.user->compare_branching_candidates(tmp_presolved,
                                                     best_presolved)) {
        case BCP_OldPresolvedIsBetter:
            break;
        case BCP_NewPresolvedIsBetter:
            std::swap(tmp_presolved, best_presolved);
            break;
        case BCP_NewPresolvedIsBetter_BranchOnIt:
            // Free the remaining candidates if there are any. This also resets
            // candidates.end(), thus 
            purge_ptr_vector(candidates, cani + 1, candidates.end());
            std::swap(tmp_presolved, best_presolved);
            break;
        }
        delete tmp_presolved;
    }

    // indicate to the lp solver that strong branching is done
    lp->unmarkHotStart();
    p.lp_solver->setWarmStart(ws);

    // delete all the candidates but the selected one (candidates will just
    // silently go out of scope and we'll be left with a pointer to the final
    // candidate in best_presolved).
    BCP_lp_branching_object* can = best_presolved->candidate();
    int selected = 0;
    for (i=0, cani=candidates.begin(); cani != candidates.end(); ++cani, ++i) {
        if (*cani != can) {
            delete *cani;
        } else {
            selected = i;
        }
    }

    // Mark the cols/rows of the OTHER candidates as removable
    BCP_mark_result_of_strong_branching(p, can, added_colnum, added_rownum);
    // Delete whatever cols/rows we want to delete. This function also updates
    // var/cut_positions !!!
    BCP_lp_delete_cols_and_rows(p, can, added_colnum, added_rownum,
                                false /* not from fathom */,
                                true /* to force deletion */);
   
    delete ws;

    return selected;
}

//#############################################################################

static inline BCP_branching_decision
BCP_lp_select_branching_object(BCP_lp_prob& p,
                               BCP_presolved_lp_brobj*& best_presolved)
{
    BCP_var_set& vars = p.node->vars;
    BCP_cut_set& cuts = p.node->cuts;
    BCP_vec<BCP_lp_branching_object*> candidates;

    bool force_branch = (p.lp_result->termcode() & BCP_Abandoned) != 0;

    BCP_branching_decision do_branch = 
        p.user->select_branching_candidates(*p.lp_result,
                                            vars, cuts,
                                            *p.local_var_pool,
                                            *p.local_cut_pool,
                                            candidates,
                                            force_branch);
    switch (do_branch){
    case BCP_DoNotBranch_Fathomed:
        return BCP_DoNotBranch_Fathomed;
    case BCP_DoNotBranch:
        if (p.local_var_pool->size() == 0 && p.local_cut_pool->size() == 0) {
            /* Hmmm... check whether some magic was done and the former sol is
               now infeasible, so resolving is perfectly normal.
               NOTE: We only check whether the former primal sol and lhs
               values are within the bounds! */
            const double petol = p.lp_result->primalTolerance();
            const double * x = p.lp_result->x();
            for (int i = vars.size() - 1; i >= 0; --i) {
                const BCP_var* v = vars[i];
                if (x[i] + petol < v->lb() || x[i] - petol > v->ub()) {
                    return BCP_DoNotBranch; // YES...
                }
            }
            const double * lhs = p.lp_result->lhs();
            for (int i = cuts.size() - 1; i >= 0; --i) {
                const BCP_cut* c = cuts[i];
                if (lhs[i] + petol < c->lb() || lhs[i] - petol > c->ub()) {
                    return BCP_DoNotBranch; // YES...
                }
            }
            p.user->print(true, "\
LP: ***WARNING*** : BCP_DoNotBranch, but nothing can be added! ***WARNING***\n");
            //throw BCP_fatal_error("BCP_DoNotBranch, but nothing can be added!\n");
        }
        return BCP_DoNotBranch;
    case BCP_DoBranch:
        break;
    }

    // give error message if there are no branching candidates
    if (candidates.size() < 1) {
        throw BCP_fatal_error("\
BCP_lp_select_branching_object: branching forced but no candidates selected\n");
    }
   
    // ** OK, now we have to branch. **
    double time0 = CoinCpuTime();
    const int orig_colnum = p.node->vars.size();

    // if branching candidates are not presolved then choose the first
    // branching candidate as the best candidate.
    int selected = 0;
    if (p.param(BCP_lp_par::MaxPresolveIter) < 0) {
        if (candidates.size() > 1) {
            p.user->print(true, "\
LP: Strong branching is disabled but more than one candidate is selected.\n\
    Deleting all candidates but the first.\n");
            // delete all other candidates
            BCP_vec<BCP_lp_branching_object*>::iterator can =
                candidates.begin();
            for (++can; can != candidates.end(); ++can) {
                delete *can;
            }
            candidates.erase(candidates.begin()+1, candidates.end());
        }
        BCP_add_branching_objects(p, candidates);
        best_presolved = new BCP_presolved_lp_brobj(candidates[0]);
        if (candidates[0]->objval_) {
            best_presolved->set_objective_values(*candidates[0]->objval_,
                                                 *candidates[0]->termcode_,
                                                 p.node->true_lower_bound);
        } else {
            best_presolved->initialize_lower_bound(p.node->true_lower_bound);
        }
    } else {
        selected = BCP_lp_perform_strong_branching(p, candidates,
                                                   best_presolved);
    }

    const BCP_lp_branching_object* can = best_presolved->candidate();

    // decide what to do with each child
    p.user->set_actions_for_children(best_presolved);
    BCP_vec<BCP_child_action>& action = best_presolved->action();
    // override the set values if we won't dive
    if (p.node->dive == BCP_DoNotDive){
        bool needed_overriding = false;
        for (int i = can->child_num - 1; i >= 0; --i) {
            if (action[i] == BCP_KeepChild) {
                action[i] = BCP_ReturnChild;
                needed_overriding = true;
            }
        }
        p.user->print(needed_overriding &&
                      p.param(BCP_lp_par::LpVerb_StrongBranchResult),
                      "LP:  Every child is returned because of not diving.\n");
    }

    // We don't know what is fathomable! strong branching may give an approx
    // sol for the children's subproblems, but it may not be a lower
    // bound. Let the tree manager decide what to do with them.

    // now throw out the fathomable ones. This can be done only if nothing
    // needs to be priced, there already is an upper bound and strong branching
    // was enabled (otherwise we don't have the LPs solved)
    if (p.param(BCP_lp_par::MaxPresolveIter) >= 0) {
        BCP_print_brobj_stat(p, orig_colnum, candidates.size(), selected,
                             best_presolved);
    }

    // finally get the user data for the children
    p.user->set_user_data_for_children(best_presolved, selected);
   
    // Now just resolve the LP to get what'll be sent to the TM.
    // 2nd arg is 1, since only only bd changes happened which can afffect
    // only primal feasibility 
    p.user->modify_lp_parameters(p.lp_solver, 1, false);
    p.lp_solver->initialSolve();
    p.lp_result->get_results(*p.lp_solver);
    p.node->quality = p.lp_result->objval();

    p.stat.time_branching += CoinCpuTime() - time0;

    return BCP_DoBranch;
}

//#############################################################################

static inline void
BCP_lp_make_parent_from_node(BCP_lp_prob& p)
{
    BCP_lp_parent& parent = *p.parent;
    BCP_lp_node& node = *p.node;

    const int bvarnum = p.core->varnum();
    const int bcutnum = p.core->cutnum();

    // deal with parent's fields one-by-one

    // core_as_change has already been updated correctly in BCP_lp_pack_core()
    node.tm_storage.core_change = (bvarnum + bcutnum > 0 ?
                                   BCP_Storage_WrtParent : BCP_Storage_NoData);
    int i;

    const BCP_var_set& vars = node.vars;
    const int varnum = vars.size();
    BCP_obj_set_change& var_set = parent.var_set;
    BCP_vec<int>& var_ind = var_set._new_objs;
    BCP_vec<BCP_obj_change>& var_ch = var_set._change;
    var_ind.clear();
    var_ch.clear();
    var_ind.reserve(varnum - bvarnum);
    var_ch.reserve(varnum - bvarnum);
    for (i = bvarnum; i < varnum; ++i) {
        const BCP_var* var = vars[i];
        assert(var->bcpind() > 0);
        var_ind.unchecked_push_back(var->bcpind());
        var_ch.unchecked_push_back(BCP_obj_change(var->lb(), var->ub(),
                                                  var->status()));
    }
    node.tm_storage.var_change = BCP_Storage_WrtParent;

    const BCP_cut_set& cuts = node.cuts;
    const int cutnum = cuts.size();
    BCP_obj_set_change& cut_set = parent.cut_set;
    BCP_vec<int>& cut_ind = cut_set._new_objs;
    BCP_vec<BCP_obj_change>& cut_ch = cut_set._change;
    cut_ind.clear();
    cut_ch.clear();
    cut_ind.reserve(cutnum - bcutnum);
    cut_ch.reserve(cutnum - bcutnum);
    for (i = bcutnum; i < cutnum; ++i) {
        const BCP_cut* cut = cuts[i];
        assert(cut->bcpind() > 0);
        cut_ind.unchecked_push_back(cut->bcpind());
        cut_ch.unchecked_push_back(BCP_obj_change(cut->lb(), cut->ub(),
                                                  cut->status()));
    }
    node.tm_storage.cut_change = BCP_Storage_WrtParent;

    delete parent.warmstart;
    parent.warmstart = node.warmstart;
    node.warmstart = 0;
    node.tm_storage.warmstart = BCP_Storage_WrtParent;

    parent.index = node.index;

    delete node.user_data;
    node.user_data = 0;
}

//#############################################################################

BCP_branching_result
BCP_lp_branch(BCP_lp_prob& p)
{
    BCP_presolved_lp_brobj* best_presolved = 0;

    // this is needed to stop gcc complaining about uninitialized use of
    // do_branch (this complaint might arise from inlining)
    BCP_branching_decision do_branch = BCP_DoBranch;
    do_branch = BCP_lp_select_branching_object(p, best_presolved);

    switch (do_branch){
    case BCP_DoNotBranch_Fathomed:
        BCP_lp_send_cuts_to_cp(p, -1);
        BCP_lp_perform_fathom(p,"LP:   Forcibly fathoming node in branch().\n",
                              BCP_Msg_NodeDescription_Discarded);
        return BCP_BranchingFathomedThisNode;
    case BCP_DoNotBranch:
        BCP_lp_send_cuts_to_cp(p,
                               p.param(BCP_lp_par::CutEffectiveCountBeforePool));
        // the branching objects are already added and we will add from the
        // local pools as well.
        return BCP_BranchingContinueThisNode;
        break;
    case BCP_DoBranch:
        break;
    }

    // Now p.node has the final set of vars/cuts for this node, and this
    // routine will extract the final warmstart information. Send this all off
    // to the the TM. This function also sends off the branching info, and gets
    // diving info from TM. In case of diving it receives/updates the index of
    // the node and the internal indices of the not yet indexed vars/cuts.
    int keep = BCP_lp_send_node_description(p, best_presolved,
                                            BCP_Msg_NoMessage);

    // send out the cuts to be sent to the CP
    BCP_lp_send_cuts_to_cp(p, -1);

    if (keep < 0){ // if no diving then return quickly
        if (p.param(BCP_lp_par::LpVerb_FathomInfo)) {
            if (best_presolved->is_pruned())
                p.user->print(true, "LP:   Forcibly Pruning node\n");
            else
                p.user->print(true, "LP:   Returned children to TM. Waiting for new node.\n");
        }
        delete best_presolved->candidate();
        delete best_presolved;
        BCP_lp_clean_up_node(p);
        return BCP_BranchingFathomedThisNode;
    }

    // Otherwise we dive. start updating things.
    // first move the current node to be the parent
    BCP_lp_make_parent_from_node(p);

    // now apply the bounds of the kept child
    BCP_lp_branching_object* can = best_presolved->candidate();
    can->apply_child_bd(p.lp_solver, keep);
    if (can->vars_affected()) {
        BCP_var_set& vars = p.node->vars;
        if (can->forced_var_pos) {
            vars.set_lb_ub(*can->forced_var_pos, can->forced_var_bd_child(keep));
            const BCP_vec<int>& pos = *can->forced_var_pos;
            for (int p = pos.size() - 1; p >= 0; --p) {
                vars[pos[p]]->make_non_removable();
            }
        }
        if (can->implied_var_pos)
            vars.set_lb_ub(*can->implied_var_pos,can->implied_var_bd_child(keep));
    }
    if (can->cuts_affected()) {
        BCP_cut_set& cuts = p.node->cuts;
        if (can->forced_cut_pos) {
            cuts.set_lb_ub(*can->forced_cut_pos, can->forced_cut_bd_child(keep));
            const BCP_vec<int>& pos = *can->forced_cut_pos;
            for (int p = pos.size() - 1; p >= 0; --p) {
                cuts[pos[p]]->make_non_removable();
            }
        }
        if (can->implied_cut_pos)
            cuts.set_lb_ub(*can->implied_cut_pos,can->implied_cut_bd_child(keep));
    }
    // Delete the old user data before getting new
    delete p.node->user_data;
    p.node->user_data = best_presolved->user_data()[keep];
    best_presolved->user_data()[keep] = 0;

    // Get rid of best_presolved
    delete best_presolved->candidate();
    delete best_presolved;

    return BCP_BranchingDivedIntoNewNode;
}