CbcTree.hpp

Go to the documentation of this file.

/* $Id: CbcTree.hpp 1943 2013-07-21 09:05:45Z forrest $ */
// Copyright (C) 2004, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
 
#ifndef CbcTree_H
#define CbcTree_H
 
#include <vector>
#include <algorithm>
#include <cmath>
 
#include "CoinHelperFunctions.hpp"
#include "CbcCompare.hpp"
 
//#define CBC_DUBIOUS_HEAP
#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
//#define CBC_DUBIOUS_HEAP
#endif
#if 1 //ndef CBC_DUBIOUS_HEAP
 
class CbcTree {
 
public:
    CbcTree ();
 
    CbcTree (const CbcTree &rhs);
 
    CbcTree & operator=(const CbcTree &rhs);
 
    virtual ~CbcTree();
 
    virtual CbcTree * clone() const;
 
    virtual void generateCpp(FILE *) {}
 
    void setComparison(CbcCompareBase &compare);
 
    virtual CbcNode * top() const;
 
    virtual void push(CbcNode *x);
 
    virtual void pop() ;
 
    virtual CbcNode * bestNode(double cutoff);
 
    virtual void rebuild() ;
 
    virtual bool empty() ;
 
    virtual int size() const { return static_cast<int>(nodes_.size()); }
 
    inline CbcNode * operator [] (int i) const { return nodes_[i]; }
 
    inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
    void realpop();
    void fixTop();
    void realpush(CbcNode * node);
 
    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
 
    CbcNode * bestAlternate();
 
    virtual void endSearch() {}
 
    virtual double getBestPossibleObjective();
 
    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
 
    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
 
    inline void setNumberBranching(int value) { numberBranching_ = value; }
 
    inline int getNumberBranching() const { return numberBranching_; }
 
    inline void setMaximumBranching(int value) { maximumBranching_ = value; }
 
    inline int getMaximumBranching() const { return maximumBranching_; }
 
    inline unsigned int * branched() const { return branched_; }
 
    inline int * newBounds() const { return newBound_; }
 
    inline double lastObjective() const {
        return lastObjective_;
    }
    inline int lastDepth() const {
        return lastDepth_;
    }
    inline int lastUnsatisfied() const {
        return lastUnsatisfied_;
    }
    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
                                 const double * currentLower,
                                 const double * currentUpper);
    void increaseSpace();
 
# if CBC_DEBUG_HEAP > 0
 
    void validateHeap() ;
# endif
 
protected:
    std::vector <CbcNode *> nodes_;
    CbcCompare comparison_;
    int maximumNodeNumber_;
    int numberBranching_;
    int maximumBranching_;
    double lastObjective_;
    int lastDepth_;
    int lastUnsatisfied_;
    unsigned int * branched_;
    int * newBound_;
};
 
#ifdef JJF_ZERO // not used
 
class CbcTreeArray : public CbcTree {
 
public:
 
    // Default Constructor
    CbcTreeArray ();
 
    // Copy constructor
    CbcTreeArray ( const CbcTreeArray & rhs);
    // = operator
    CbcTreeArray & operator=(const CbcTreeArray & rhs);
 
    virtual ~CbcTreeArray();
 
    virtual CbcTree * clone() const;
    virtual void generateCpp( FILE * ) {}
 
 
    void setComparison(CbcCompareBase  &compare);
 
    virtual void push(CbcNode * x);
 
    virtual CbcNode * bestNode(double cutoff);
 
 
 
    virtual bool empty() ;
 
 
 
    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    virtual double getBestPossibleObjective();
protected:
    CbcNode * lastNode_;
    CbcNode * lastNodePopped_;
    int switches_;
 
};
 
#include "CoinSearchTree.hpp"
class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
 
public:
 
    // Default Constructor
    CbcNewTree ();
 
    // Copy constructor
    CbcNewTree ( const CbcNewTree & rhs);
    // = operator
    CbcNewTree & operator=(const CbcNewTree & rhs);
 
    virtual ~CbcNewTree();
 
    virtual CbcNewTree * clone() const;
    virtual void generateCpp( FILE * ) {}
 
 
    void setComparison(CbcCompareBase  &compare);
 
    virtual CbcNode * top() const;
 
    virtual void push(CbcNode * x);
 
    virtual void pop() ;
    virtual CbcNode * bestNode(double cutoff);
 
 
 
    virtual bool empty() ;
 
    inline int size() const {
        return nodes_.size();
    }
 
    inline CbcNode * operator [] (int i) const {
        return nodes_[i];
    }
 
    inline CbcNode * nodePointer (int i) const {
        return nodes_[i];
    }
 
 
 
    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
 
    CbcNode * bestAlternate();
 
    virtual void endSearch() {}
protected:
 
 
};
#endif
#else
/* CBC_DUBIOUS_HEAP is defined
 
  See note at top of file. This code is highly suspect.
  -- lh, 100921 --
*/
class CbcTree {
 
public:
 
    // Default Constructor
    CbcTree ();
 
    // Copy constructor
    CbcTree ( const CbcTree & rhs);
    // = operator
    CbcTree & operator=(const CbcTree & rhs);
 
    virtual ~CbcTree();
 
    virtual CbcTree * clone() const;
    virtual void generateCpp( FILE * fp) {}
 
 
    void setComparison(CbcCompareBase  &compare);
 
    virtual CbcNode * top() const;
 
    virtual void push(CbcNode * x);
 
    virtual void pop() ;
    virtual CbcNode * bestNode(double cutoff);
 
 
 
    //virtual bool empty() ;
 
    inline int size() const {
        return nodes_.size();
    }
 
    inline CbcNode * operator [] (int i) const {
        return nodes_[i];
    }
 
    inline CbcNode * nodePointer (int i) const {
        return nodes_[i];
    }
 
    virtual bool empty();
    //inline int size() const { return size_; }
    void realpop();
    void fixTop();
    void realpush(CbcNode * node);
 
 
    void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
 
    CbcNode * bestAlternate();
 
    virtual void endSearch() {}
    inline void resetNodeNumbers() {
        maximumNodeNumber_ = 0;
    }
 
    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
protected:
    std::vector <CbcNode *> nodes_;
    CbcCompare comparison_;     
    int maximumNodeNumber_;
 
 
};
#endif
#endif