diff options
Diffstat (limited to 'newstructure/thirdparty/linux/include/coin/CbcTree.hpp')
| -rw-r--r-- | newstructure/thirdparty/linux/include/coin/CbcTree.hpp | 490 |
1 files changed, 0 insertions, 490 deletions
diff --git a/newstructure/thirdparty/linux/include/coin/CbcTree.hpp b/newstructure/thirdparty/linux/include/coin/CbcTree.hpp deleted file mode 100644 index 92ea2bf..0000000 --- a/newstructure/thirdparty/linux/include/coin/CbcTree.hpp +++ /dev/null @@ -1,490 +0,0 @@ -/* $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" - -/*! \brief Using MS heap implementation - - It's unclear if this is needed any longer, or even if it should be allowed. - Cbc occasionally tries to do things to the tree (typically tweaking the - comparison predicate) that can cause a violation of the heap property (parent better - than either child). In a debug build, Microsoft's heap implementation does checks that - detect this and fail. This symbol switched to an alternate implementation of CbcTree, - and there are clearly differences, but no explanation as to why or what for. - - As of 100921, the code is cleaned up to make it through `cbc -unitTest' without - triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can - be used for debugging if this turns up again. -*/ -//#define CBC_DUBIOUS_HEAP -#if defined(_MSC_VER) || defined(__MNO_CYGWIN) -//#define CBC_DUBIOUS_HEAP -#endif -#if 1 //ndef CBC_DUBIOUS_HEAP - -/*! \brief Controls search tree debugging - - In order to have validateHeap() available, set CBC_DEBUG_HEAP - to 1 or higher. - - - 1 calls validateHeap() after each change to the heap - - 2 will print a line for major operations (clean, set comparison, etc.) - - 3 will print information about each push and pop - -#define CBC_DEBUG_HEAP 1 -*/ - - -/*! \class CbcTree - \brief Implementation of the live set as a heap. - - This class is used to hold the set of live nodes in the search tree. -*/ -class CbcTree { - -public: - /*! \name Constructors and related */ -//@{ - /// Default Constructor - CbcTree (); - - /// Copy constructor - CbcTree (const CbcTree &rhs); - - /// = operator - CbcTree & operator=(const CbcTree &rhs); - - /// Destructor - virtual ~CbcTree(); - - /// Clone - virtual CbcTree * clone() const; - - /// Create C++ lines to get to current state - virtual void generateCpp(FILE *) {} -//@} - - /*! \name Heap access and maintenance methods */ -//@{ - /// Set comparison function and resort heap - void setComparison(CbcCompareBase &compare); - - /// Return the top node of the heap - virtual CbcNode * top() const; - - /// Add a node to the heap - virtual void push(CbcNode *x); - - /// Remove the top node from the heap - virtual void pop() ; - - /*! \brief Gets best node and takes off heap - - Before returning the node from the top of the heap, the node - is offered an opportunity to reevaluate itself. Callers should - be prepared to check that the node returned is suitable for use. - */ - virtual CbcNode * bestNode(double cutoff); - - /*! \brief Rebuild the heap */ - virtual void rebuild() ; -//@} - - /*! \name Direct node access methods */ -//@{ - /// Test for an empty tree - virtual bool empty() ; - - /// Return size - virtual int size() const { return static_cast<int>(nodes_.size()); } - - /// Return a node pointer - inline CbcNode * operator [] (int i) const { return nodes_[i]; } - - /// Return a node pointer - inline CbcNode * nodePointer (int i) const { return nodes_[i]; } - void realpop(); - /** After changing data in the top node, fix the heap */ - void fixTop(); - void realpush(CbcNode * node); -//@} - - /*! \name Search tree maintenance */ -//@{ - /*! \brief Prune the tree using an objective function cutoff - - This routine removes all nodes with objective worse than the - specified cutoff value. It also sets bestPossibleObjective to - the best objective over remaining nodes. - */ - virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); - - /// Get best on list using alternate method - CbcNode * bestAlternate(); - - /// We may have got an intelligent tree so give it one more chance - virtual void endSearch() {} - - /// Get best possible objective function in the tree - virtual double getBestPossibleObjective(); - - /// Reset maximum node number - inline void resetNodeNumbers() { maximumNodeNumber_ = 0; } - - /// Get maximum node number - inline int maximumNodeNumber() const { return maximumNodeNumber_; } - - /// Set number of branches - inline void setNumberBranching(int value) { numberBranching_ = value; } - - /// Get number of branches - inline int getNumberBranching() const { return numberBranching_; } - - /// Set maximum branches - inline void setMaximumBranching(int value) { maximumBranching_ = value; } - - /// Get maximum branches - inline int getMaximumBranching() const { return maximumBranching_; } - - /// Get branched variables - inline unsigned int * branched() const { return branched_; } - - /// Get bounds - inline int * newBounds() const { return newBound_; } - - /// Last objective in branch-and-cut search tree - inline double lastObjective() const { - return lastObjective_; - } - /// Last depth in branch-and-cut search tree - inline int lastDepth() const { - return lastDepth_; - } - /// Last number of objects unsatisfied - inline int lastUnsatisfied() const { - return lastUnsatisfied_; - } - /// Adds branching information to complete state - void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo, - const double * currentLower, - const double * currentUpper); - /// Increase space for data - void increaseSpace(); -//@} - -# if CBC_DEBUG_HEAP > 0 - /*! \name Debugging methods */ - //@{ - /*! \brief Check that the heap property is satisfied. */ - void validateHeap() ; - //@} -# endif - -protected: - /// Storage vector for the heap - std::vector <CbcNode *> nodes_; - /// Sort predicate for heap ordering. - CbcCompare comparison_; - /// Maximum "node" number so far to split ties - int maximumNodeNumber_; - /// Size of variable list - int numberBranching_; - /// Maximum size of variable list - int maximumBranching_; - /// Objective of last node pushed on tree - double lastObjective_; - /// Depth of last node pushed on tree - int lastDepth_; - /// Number unsatisfied of last node pushed on tree - int lastUnsatisfied_; - /** Integer variables branched or bounded - top bit set if new upper bound - next bit set if a branch - */ - unsigned int * branched_; - /// New bound - int * newBound_; -}; - -#ifdef JJF_ZERO // not used -/*! \brief Implementation of live set as a managed array. - - This class is used to hold the set of live nodes in the search tree. -*/ -class CbcTreeArray : public CbcTree { - -public: - - // Default Constructor - CbcTreeArray (); - - // Copy constructor - CbcTreeArray ( const CbcTreeArray & rhs); - // = operator - CbcTreeArray & operator=(const CbcTreeArray & rhs); - - virtual ~CbcTreeArray(); - - /// Clone - virtual CbcTree * clone() const; - /// Create C++ lines to get to current state - virtual void generateCpp( FILE * ) {} - - /*! \name Heap access and maintenance methods */ -//@{ - - /// Set comparison function and resort heap - void setComparison(CbcCompareBase &compare); - - /// Add a node to the heap - virtual void push(CbcNode * x); - - /// Gets best node and takes off heap - virtual CbcNode * bestNode(double cutoff); - -//@} - /*! \name vector methods */ -//@{ - - /// Test if empty *** note may be overridden - virtual bool empty() ; - -//@} - - /*! \name Search tree maintenance */ -//@{ - - /*! \brief Prune the tree using an objective function cutoff - - This routine removes all nodes with objective worst than the - specified cutoff value. - It also sets bestPossibleObjective to best - of all on tree before deleting. - */ - - void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); - /// Get best possible objective function in the tree - virtual double getBestPossibleObjective(); -//@} -protected: - /// Returns - /// Last node - CbcNode * lastNode_; - /// Last node popped - CbcNode * lastNodePopped_; - /// Not used yet - int switches_; - -}; - -/// New style -#include "CoinSearchTree.hpp" -/*! \class tree - \brief Implementation of live set as a heap. - - This class is used to hold the set of live nodes in the search tree. -*/ - -class CbcNewTree : public CbcTree, public CoinSearchTreeManager { - -public: - - // Default Constructor - CbcNewTree (); - - // Copy constructor - CbcNewTree ( const CbcNewTree & rhs); - // = operator - CbcNewTree & operator=(const CbcNewTree & rhs); - - virtual ~CbcNewTree(); - - /// Clone - virtual CbcNewTree * clone() const; - /// Create C++ lines to get to current state - virtual void generateCpp( FILE * ) {} - - /*! \name Heap access and maintenance methods */ -//@{ - - /// Set comparison function and resort heap - void setComparison(CbcCompareBase &compare); - - /// Return the top node of the heap - virtual CbcNode * top() const; - - /// Add a node to the heap - virtual void push(CbcNode * x); - - /// Remove the top node from the heap - virtual void pop() ; - /// Gets best node and takes off heap - virtual CbcNode * bestNode(double cutoff); - -//@} - /*! \name vector methods */ -//@{ - - /// Test if empty *** note may be overridden - virtual bool empty() ; - - /// Return size - inline int size() const { - return nodes_.size(); - } - - /// [] operator - inline CbcNode * operator [] (int i) const { - return nodes_[i]; - } - - /// Return a node pointer - inline CbcNode * nodePointer (int i) const { - return nodes_[i]; - } - -//@} - - /*! \name Search tree maintenance */ -//@{ - - /*! \brief Prune the tree using an objective function cutoff - - This routine removes all nodes with objective worst than the - specified cutoff value. - It also sets bestPossibleObjective to best - of all on tree before deleting. - */ - - void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); - - /// Get best on list using alternate method - CbcNode * bestAlternate(); - - /// We may have got an intelligent tree so give it one more chance - 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(); - - /// Clone - virtual CbcTree * clone() const; - /// Create C++ lines to get to current state - virtual void generateCpp( FILE * fp) {} - - /*! \name Heap access and maintenance methods */ -//@{ - - /// Set comparison function and resort heap - void setComparison(CbcCompareBase &compare); - - /// Return the top node of the heap - virtual CbcNode * top() const; - - /// Add a node to the heap - virtual void push(CbcNode * x); - - /// Remove the top node from the heap - virtual void pop() ; - /// Gets best node and takes off heap - virtual CbcNode * bestNode(double cutoff); - -//@} - /*! \name vector methods */ -//@{ - - /// Test if empty *** note may be overridden - //virtual bool empty() ; - - /// Return size - inline int size() const { - return nodes_.size(); - } - - /// [] operator - inline CbcNode * operator [] (int i) const { - return nodes_[i]; - } - - /// Return a node pointer - inline CbcNode * nodePointer (int i) const { - return nodes_[i]; - } - - virtual bool empty(); - //inline int size() const { return size_; } - void realpop(); - /** After changing data in the top node, fix the heap */ - void fixTop(); - void realpush(CbcNode * node); -//@} - - /*! \name Search tree maintenance */ -//@{ - - /*! \brief Prune the tree using an objective function cutoff - - This routine removes all nodes with objective worst than the - specified cutoff value. - It also sets bestPossibleObjective to best - of all on tree before deleting. - */ - - void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); - - /// Get best on list using alternate method - CbcNode * bestAlternate(); - - /// We may have got an intelligent tree so give it one more chance - virtual void endSearch() {} - /// Reset maximum node number - inline void resetNodeNumbers() { - maximumNodeNumber_ = 0; - } - - /// Get maximum node number - inline int maximumNodeNumber() const { return maximumNodeNumber_; } -//@} -protected: - std::vector <CbcNode *> nodes_; - CbcCompare comparison_; ///> Sort function for heap ordering. - /// Maximum "node" number so far to split ties - int maximumNodeNumber_; - - -}; -#endif -#endif - |