BCP_tm_node.hpp

Go to the documentation of this file.

// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef _BCP_TM_NODE
#define _BCP_TM_NODE

//#include <cfloat>

#include <map>

#include "CoinSearchTree.hpp"
#include "CoinSmartPtr.hpp"

#include "BCP_math.hpp"
#include "BCP_vector.hpp"

#include "BCP_message_tag.hpp"
#include "BCP_obj_change.hpp"
#include "BCP_node_change.hpp"
#include "BCP_USER.hpp"

enum BCP_tm_node_status{
    BCP_DefaultNode,
    BCP_ProcessedNode,
    BCP_ActiveNode,
    BCP_PrunedNode_OverUB,
    BCP_PrunedNode_Infeas,
    BCP_PrunedNode_Discarded,
    BCP_CandidateNode,
    BCP_NextPhaseNode_OverUB,
    BCP_NextPhaseNode_Infeas
};

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

class BCP_tm_node;
class BCP_tm_prob;

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

class BCP_tm_node_data {
public:
    Coin::SmartPtr<BCP_node_change> _desc;
    Coin::SmartPtr<BCP_user_data>   _user;
    BCP_tm_node_data(BCP_node_change* d = NULL) : _desc(d), _user(0) {}
};

//=============================================================================

class BCP_tm_node : public CoinTreeNode {
private:
    BCP_tm_node(const BCP_tm_node&);
    BCP_tm_node& operator=(const BCP_tm_node&);
    // NOTE: deleting a tree_node deletes the whole subtree below!
public:
    static int num_local_nodes;
    static int num_remote_nodes;
    // *FIXME* break into groups 
    BCP_tm_node_status status;
    int _index;
    BCP_tm_node* _parent;

    int _birth_index;
    BCP_vec<BCP_tm_node*> _children;
    int lp, cg, cp, vg, vp;
    int _processed_leaf_num;
    int _pruned_leaf_num;
    int _tobepriced_leaf_num;
    int _leaf_num;

    int _core_storage:4;
    int _var_storage:4;
    int _cut_storage:4;
    int _ws_storage:4;

    int _locally_stored:2;
    // Exactly one of the next two is always irrelevant */
    int _data_location:30;
    BCP_tm_node_data _data;
        
public:
    BCP_tm_node(int level, BCP_node_change* desc);

//     BCP_tm_node(int level, BCP_node_change* desc,
//              BCP_tm_node* parent, int index);
    ~BCP_tm_node()
    {
      if (_locally_stored) {
        --num_local_nodes;
      } else {
        --num_remote_nodes;
      }
    }
    inline int index() const { return _index; }
    inline int child_num() const { return _children.size(); }
    inline int birth_index() const { return _birth_index; }

    //    inline BCP_user_data* user_data() { return _data._user; }
    inline BCP_tm_node* child(int ind) { return _children[ind]; }
    inline BCP_tm_node* parent() { return _parent; }

    //    inline const BCP_user_data* user_data() const { return _data._user; }
    inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
    inline const BCP_tm_node* parent() const { return _parent; }
    // Marking the descendants for deletion means that their _index fields are
    // set to -1. The reason is that some book-keeping must be one with the CP,
    // VP processes; with the next phase list, with the priority queue of the
    // current phase (and maybe sthing else?). So this function only marks, and
    // the data will be deleted later.
    int mark_descendants_for_deletion();
    void remove_child(BCP_tm_node* node);
    inline void reserve_child_num(int num) { _children.reserve(num); }
    inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
};

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

class BCP_tree {
private:
    BCP_vec<BCP_tm_node*> _tree;
    int maxdepth_;
    int processed_;

public:
    BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
    ~BCP_tree() {
        for (int i = _tree.size() - 1; i >= 0; --i) {
            delete _tree[i];
        }
    }
    inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
    inline BCP_vec<BCP_tm_node*>::iterator end()   { return _tree.end(); }

    inline BCP_tm_node* root() { return _tree.front(); }
    inline BCP_tm_node* operator[](int index) { return _tree[index]; }
    inline size_t size() const { return _tree.size(); }
    inline int maxdepth() const { return maxdepth_; }
    inline int processed() const { return processed_; }
    inline void increase_processed() { ++processed_; }
    double true_lower_bound(const BCP_tm_node* node) const;
    void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
    inline void insert(BCP_tm_node* node) {
        node->_index = _tree.size();
        _tree.push_back(node);
        if (node->getDepth() > maxdepth_)
            maxdepth_ = node->getDepth();
    }
    inline void remove(int index) {
        _tree[index] = 0;
    }
};

//#############################################################################
class BCP_tm_node_to_send;

class BCP_tm_node_to_send
{
public:
    static std::map<int, BCP_tm_node_to_send*> waiting;

private:
    BCP_tm_prob& p;

    BCP_message_tag msgtag;

    const int ID;

    const BCP_tm_node* node;
    const BCP_tm_node** root_path;
    int* child_index;
    BCP_tm_node_data* node_data_on_root_path;

    int level;

    int explicit_core_level;
    int explicit_var_level;
    int explicit_cut_level;
    int explicit_ws_level;
    int explicit_all_level;

    int missing_desc_num;
    int missing_var_num;
    int missing_cut_num;

    BCP_obj_set_change var_set;
    BCP_obj_set_change cut_set;
    BCP_vec<Coin::SmartPtr<BCP_var> > vars;
    BCP_vec<Coin::SmartPtr<BCP_cut> > cuts;

public:

    BCP_tm_node_to_send(BCP_tm_prob& p, const BCP_tm_node* node,
                        const BCP_message_tag tag);
    ~BCP_tm_node_to_send();

    bool send();

    bool receive_node_desc(BCP_buffer& buf);
    bool receive_vars(BCP_buffer& buf);
    bool receive_cuts(BCP_buffer& buf);
};

#endif