BCP_tm_functions.cpp

Go to the documentation of this file.

// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
#include <cstdio>
#include "BCP_os.hpp"
#include "BCP_error.hpp"
#include "BCP_node_change.hpp"
#include "BCP_enum_tm.hpp"
#include "BCP_tm.hpp"
#include "BCP_tm_functions.hpp"

static inline BCP_node_start_result BCP_tm_start_one_node(BCP_tm_prob& p);

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

BCP_vec< std::pair<int,int> >::iterator
BCP_tm_identify_process(BCP_vec< std::pair<int,int> >& proclist, int proc)
{
    BCP_vec< std::pair<int,int> >::iterator proci = proclist.begin();
    BCP_vec< std::pair<int,int> >::iterator lastproci = proclist.end();
    while (proci != lastproci) {
        if (proci->first == proc)
            break;
        ++proci;
    }
    return proci;
}

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

bool
BCP_tm_assign_processes(BCP_tm_prob& p, BCP_tm_node* node)
{
    int lp = -1;
    int cg = -1;
    int vg = -1;
    int cp = -1;
    int vp = -1;
    bool so_far_so_good = true;

    if (so_far_so_good) {
        lp = p.lp_scheduler.request_node_id();
        if (lp == -1)
            return false;
        if (! p.msg_env->alive(lp)) {
            BCP_tm_remove_lp(p, lp);
            return false;
        }
    }

#if ! defined(BCP_ONLY_LP_PROCESS_HANDLING_WORKS)
    if (so_far_so_good && p.slaves.cg) {
        cg = p.slaves.cg->get_free_proc();
        if (cg == -1)
            return false;
        if (! p.msg_env->alive(cg)) {
            BCP_tm_remove_cg(p, p.slaves.cg->index_of_proc(cg));
            so_far_so_good = false;
        }
    }

    if (so_far_so_good && p.slaves.vg) {
        vg = p.slaves.vg->get_free_proc();
        if (vg == -1)
            return false;
        if (! p.msg_env->alive(vg)) {
            BCP_tm_remove_vg(p, p.slaves.vg->index_of_proc(vg));
            so_far_so_good = false;
        }
    }

    if (so_far_so_good && p.slaves.cp) {
        while (true) {
            cp = p.slaves.cp->get_free_proc();
            if (cp == -1)
                break;
            if (p.msg_env->alive(cp))
                break;
            // *FIXME*
            throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
        }
        if (cp == -1) {
            // if there is no free CP, just keep the old one
            if (node->cp != -1 && ! p.msg_env->alive(node->cp)) {
                // *FIXME*
                throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
            }
        } else {
            if (node->cp != -1 && ! p.msg_env->alive(node->cp)) {
                // *FIXME*
                throw BCP_fatal_error("TM: A CP has died. Aborting...\n");
            }
        } 
    }

    if (so_far_so_good && p.slaves.vp) {
        while (true) {
            vp = p.slaves.vp->get_free_proc();
            if (vp == -1)
                break;
            if (p.msg_env->alive(vp))
                break;
            // *FIXME*
            throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
        }
        if (vp == -1) {
            // if there is no free VP, just keep the old one
            if (node->vp != -1 && ! p.msg_env->alive(node->vp)) {
                // *FIXME*
                throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
            }
        } else {
            if (node->vp != -1 && ! p.msg_env->alive(node->vp)) {
                // *FIXME*
                throw BCP_fatal_error("TM: A VP has died. Aborting...\n");
            }
        } 
    }
#endif

    if (! so_far_so_good)
        return BCP_tm_assign_processes(p, node);

    node->lp = lp;
    node->cg = cg;
    node->vg = vg;
    if (cp != -1) {
        // *LATER* : copy the old CP over to the free one and let node have
        // this new CP.
        node->cp = cp;
    }
    if (vp != -1) {
        // *LATER* : copy the old VP over to the free one and let node have
        // this new VP.
        node->vp = vp;
    }

    return true;
}

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

static void BCP_tm_free_nodes(BCP_tm_prob& p)
{
    for (int i = p.nodes_to_free.size() - 1; i >= 0; --i) {
        BCP_tm_modify_pool_counters(p, p.nodes_to_free[i]);
        BCP_tm_remove_explored(p, p.nodes_to_free[i]);
    }
    p.nodes_to_free.clear();
}

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

static inline BCP_node_start_result
BCP_tm_start_one_node(BCP_tm_prob& p)
{
    BCP_tm_node* next_node;

    while (true){
        if (p.candidate_list.empty()) {
            BCP_tm_free_nodes(p);
            return BCP_NodeStart_NoNode;
        }
        next_node = dynamic_cast<BCP_tm_node*>(p.candidate_list.top());
        p.candidate_list.pop();

        // if no UB yet or lb is lower than UB then go ahead
        if (! p.has_ub())
            break;

        bool process_this = true;

        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;

        if (process_this)
            break;

        // ok, so we do have an UB and true lb is "higher" than the UB.
        if (p.current_phase_colgen == BCP_DoNotGenerateColumns_Fathom) {
            // nothing is left to price or in this phase we just fathom the
            // over-the-bound nodes. in either case this node can be pruned
            // right here.
            next_node->status = BCP_PrunedNode_OverUB;
            if (p.param(BCP_tm_par::TmVerb_PrunedNodeInfo))
                printf("TM: Pruning NODE %i LEVEL %i instead of sending it.\n",
                       next_node->index(), next_node->getDepth());
            p.nodes_to_free.push_back(next_node);
            BCP_print_memusage(p);
            continue;
        }
        if (p.current_phase_colgen == BCP_DoNotGenerateColumns_Send) {
            // the node would be sent back from the LP right away. save the
            // trouble and don't even send it out
            p.next_phase_nodes.push_back(next_node);
            next_node->status = BCP_NextPhaseNode_OverUB;
            if (p.param(BCP_tm_par::TmVerb_PrunedNodeInfo))
                printf("\
TM: Moving NODE %i LEVEL %i into the next phase list \n\
    instead of sending it.\n",
                       next_node->index(), next_node->getDepth());
            continue;
        }
        // must be BCP_GenerateColumns
        // all right, we want to send it out anyway for pricing
        break;
    }

    // assign processes to the node and send it off
    if (! BCP_tm_assign_processes(p, next_node)) {
        // couldn't find free processes
        p.candidate_list.push(next_node, false);
        BCP_tm_free_nodes(p);
        return BCP_NodeStart_Error;
    }

    p.active_nodes[next_node->lp] = next_node;
    next_node->status = BCP_ActiveNode;
    if (p.param(BCP_tm_par::MessagePassingIsSerial)) {
        BCP_tm_free_nodes(p);
    }
    BCP_tm_node_to_send* node_to_send =
        new BCP_tm_node_to_send(p, next_node, BCP_Msg_ActiveNodeData);
    if (node_to_send->send()) {
        delete node_to_send;
    }

#ifdef BCP__DUMP_PROCINFO
#if (BCP__DUMP_PROCINFO == 1)
    dump_procinfo(p, "start_one_node()");
#endif
#endif
        
    return BCP_NodeStart_OK;
}

#ifdef BCP__DUMP_PROCINFO
#if (BCP__DUMP_PROCINFO == 1)
void dump_procinfo(BCP_tm_prob& p, const char* str)
{
    printf("TM: ***** dump_procinfo from %s *********\n", str);
    printf("TM: ********** Active nodes *********\n");
    for (int i = 0; i < p.slaves.lp->size(); ++i) {
        if (p.active_nodes[i])
            printf("TM:     %i, %i, %i\n",
                   i, p.active_nodes[i]->index(), p.active_nodes[i]->lp);
        else
            printf("TM:     %i, %i, %i\n",
                   i, -1, -1);
         
    }
    printf("TM: ********** All nodes *********\n");
    for (int i = 0; i < p.search_tree.size(); ++i) {
        printf("TM:     %i, %i\n", i, p.search_tree[i]->lp);
    }
}
#endif
#endif

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

BCP_node_start_result BCP_tm_start_new_nodes(BCP_tm_prob& p)
{
    while (p.lp_scheduler.has_free_node_id()) {
        switch (BCP_tm_start_one_node(p)){
        case BCP_NodeStart_NoNode:
            return BCP_NodeStart_NoNode;
        case BCP_NodeStart_Error:
            if (p.lp_scheduler.has_free_node_id()) {
                throw BCP_fatal_error("\
TM: couldn't start new node but there's a free LP ?!\n");
            }
            break;
        case BCP_NodeStart_OK:
            break;
        }
    }
    BCP_tm_free_nodes(p);
    return BCP_NodeStart_OK;
}

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

void BCP_tm_list_candidates(BCP_tm_prob& p)
{
    /* FIXME: must walk through the siblings... */
#if 0
    CoinSearchTreeBase& candidates = *p.candidate_list.getTree();
    const int n = candidates.size();
    const std::vector<CoinTreeNode*>& nodes = candidates.getNodes();
    for (int i = 0; i < n; ++i) {
        printf("%5i", dynamic_cast<BCP_tm_node*>(nodes[i])->index());
    }
    printf("\n");
#endif
}

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

void BCP_check_parameters(BCP_tm_prob& p)
{
    p.ub(p.param(BCP_tm_par::UpperBound));

    if (p.par.entry(BCP_tm_par::VerbosityShutUp)) {
        int i;
        BCP_parameter_set<BCP_tm_par>& tmpar = p.par;
        BCP_parameter_set<BCP_lp_par>& lppar = p.slave_pars.lp;
        BCP_parameter_set<BCP_cg_par>& cgpar = p.slave_pars.cg;
        BCP_parameter_set<BCP_vg_par>& vgpar = p.slave_pars.vg;
        char treestat = tmpar.entry(BCP_tm_par::TmVerb_FinalStatistics);
        char bestsol  = tmpar.entry(BCP_tm_par::TmVerb_BestFeasibleSolution);
        for (i = BCP_tm_par::TmVerb_First+1; i < BCP_tm_par::TmVerb_Last; ++i){
            if (tmpar.entry(static_cast<BCP_tm_par::chr_params>(i)) == 2) {
                tmpar.set_entry(static_cast<BCP_tm_par::chr_params>(i), true);
            } else {
                tmpar.set_entry(static_cast<BCP_tm_par::chr_params>(i), false);
            }
        }
        for (i = BCP_lp_par::LpVerb_First+1; i < BCP_lp_par::LpVerb_Last; ++i){
            if (lppar.entry(static_cast<BCP_lp_par::chr_params>(i)) == 2) {
                lppar.set_entry(static_cast<BCP_lp_par::chr_params>(i), true);
            } else {
                lppar.set_entry(static_cast<BCP_lp_par::chr_params>(i), false);
            }
        }
        for (i = BCP_cg_par::CgVerb_First+1; i < BCP_cg_par::CgVerb_Last; ++i){
            if (cgpar.entry(static_cast<BCP_cg_par::chr_params>(i)) == 2) {
                cgpar.set_entry(static_cast<BCP_cg_par::chr_params>(i), true);
            } else {
                cgpar.set_entry(static_cast<BCP_cg_par::chr_params>(i), false);
            }
        }
        /*
          for (i = BCP_vg_par::VgVerb_First+1; i < BCP_vg_par::VgVerb_Last; ++i){
          vgpar.set_entry(static_cast<BCP_vg_par::chr_params>(i), false);
          }
        */
        tmpar.set_entry(BCP_tm_par::TmVerb_FinalStatistics, treestat);
        tmpar.set_entry(BCP_tm_par::TmVerb_BestFeasibleSolution, bestsol);
        if (tmpar.entry(BCP_tm_par::ReportWhenDefaultIsExecuted) == 2) {
            tmpar.set_entry(BCP_tm_par::ReportWhenDefaultIsExecuted, true);
        } else {
            tmpar.set_entry(BCP_tm_par::ReportWhenDefaultIsExecuted, false);
        }
        if (lppar.entry(BCP_lp_par::ReportWhenDefaultIsExecuted) == 2) {
            lppar.set_entry(BCP_lp_par::ReportWhenDefaultIsExecuted, true);
        } else {
            lppar.set_entry(BCP_lp_par::ReportWhenDefaultIsExecuted, false);
        }
        if (cgpar.entry(BCP_cg_par::ReportWhenDefaultIsExecuted) == 2) {
            cgpar.set_entry(BCP_cg_par::ReportWhenDefaultIsExecuted, true);
        } else {
            cgpar.set_entry(BCP_cg_par::ReportWhenDefaultIsExecuted, false);
        }
        if (vgpar.entry(BCP_vg_par::ReportWhenDefaultIsExecuted) == 2) {
            vgpar.set_entry(BCP_vg_par::ReportWhenDefaultIsExecuted, true);
        } else {
            vgpar.set_entry(BCP_vg_par::ReportWhenDefaultIsExecuted, false);
        }
    }
    if (p.param(BCP_tm_par::MaxHeapSize) == 0) {
        long fm = BCP_free_mem();
        fm = fm == -1 ? 192 * (1<<20) /* 192M */ : fm;
        p.par.set_entry(BCP_tm_par::MaxHeapSize, fm);
        p.slave_pars.ts.set_entry(BCP_ts_par::MaxHeapSize, fm);
    }
}

//#############################################################################
// A little bit of sanity check

void BCP_sanity_checks(BCP_tm_prob& p)
{
}