initial add

1 files changed, 490 insertions, 0 deletions

diff --git a/build/Bonmin/include/coin/CbcTree.hpp b/build/Bonmin/include/coin/CbcTree.hpp
new file mode 100644
index 0000000..92ea2bf
--- /dev/null
+++ b/build/Bonmin/include/coin/CbcTree.hpp
@@ -0,0 +1,490 @@
+/* $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
+