[1271] | 1 | /* $Id: CbcTree.hpp 1573 2011-01-05 01:12:36Z lou $ */ |
---|
[2] | 2 | // Copyright (C) 2004, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
[1573] | 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[2] | 6 | #ifndef CbcTree_H |
---|
| 7 | #define CbcTree_H |
---|
| 8 | |
---|
| 9 | #include <vector> |
---|
[724] | 10 | #include <algorithm> |
---|
| 11 | #include <cmath> |
---|
[2] | 12 | |
---|
[724] | 13 | #include "CoinFinite.hpp" |
---|
| 14 | #include "CoinHelperFunctions.hpp" |
---|
[1315] | 15 | #include "CbcCompare.hpp" |
---|
[724] | 16 | |
---|
[1506] | 17 | /*! \brief Using MS heap implementation |
---|
[2] | 18 | |
---|
[1506] | 19 | It's unclear if this is needed any longer, or even if it should be allowed. |
---|
| 20 | Cbc occasionally tries to do things to the tree (typically tweaking the |
---|
| 21 | comparison predicate) that can cause a violation of the heap property (parent better |
---|
| 22 | than either child). In a debug build, Microsoft's heap implementation does checks that |
---|
| 23 | detect this and fail. This symbol switched to an alternate implementation of CbcTree, |
---|
| 24 | and there are clearly differences, but no explanation as to why or what for. |
---|
| 25 | |
---|
| 26 | As of 100921, the code is cleaned up to make it through `cbc -unitTest' without |
---|
| 27 | triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can |
---|
| 28 | be used for debugging if this turns up again. |
---|
[2] | 29 | */ |
---|
[724] | 30 | //#define CBC_DUBIOUS_HEAP |
---|
| 31 | #if defined(_MSC_VER) || defined(__MNO_CYGWIN) |
---|
| 32 | //#define CBC_DUBIOUS_HEAP |
---|
| 33 | #endif |
---|
[1286] | 34 | #ifndef CBC_DUBIOUS_HEAP |
---|
[1506] | 35 | |
---|
| 36 | /*! \brief Controls search tree debugging |
---|
| 37 | |
---|
| 38 | In order to have validateHeap() available, set CBC_DEBUG_HEAP |
---|
| 39 | to 1 or higher. |
---|
| 40 | |
---|
| 41 | - 1 calls validateHeap() after each change to the heap |
---|
| 42 | - 2 will print a line for major operations (clean, set comparison, etc.) |
---|
| 43 | - 3 will print information about each push and pop |
---|
| 44 | |
---|
| 45 | #define CBC_DEBUG_HEAP 1 |
---|
| 46 | */ |
---|
| 47 | |
---|
| 48 | |
---|
| 49 | /*! \class CbcTree |
---|
| 50 | \brief Implementation of the live set as a heap. |
---|
| 51 | |
---|
| 52 | This class is used to hold the set of live nodes in the search tree. |
---|
| 53 | */ |
---|
[2] | 54 | class CbcTree { |
---|
| 55 | |
---|
| 56 | public: |
---|
[1506] | 57 | /*! \name Constructors and related */ |
---|
| 58 | //@{ |
---|
| 59 | /// Default Constructor |
---|
[1286] | 60 | CbcTree (); |
---|
[2] | 61 | |
---|
[1506] | 62 | /// Copy constructor |
---|
| 63 | CbcTree (const CbcTree &rhs); |
---|
[2] | 64 | |
---|
[1506] | 65 | /// = operator |
---|
| 66 | CbcTree & operator=(const CbcTree &rhs); |
---|
| 67 | |
---|
| 68 | /// Destructor |
---|
[1286] | 69 | virtual ~CbcTree(); |
---|
[2] | 70 | |
---|
[1286] | 71 | /// Clone |
---|
| 72 | virtual CbcTree * clone() const; |
---|
[1506] | 73 | |
---|
[1286] | 74 | /// Create C++ lines to get to current state |
---|
[1506] | 75 | virtual void generateCpp(FILE *) {} |
---|
| 76 | //@} |
---|
[1286] | 77 | |
---|
| 78 | /*! \name Heap access and maintenance methods */ |
---|
[2] | 79 | //@{ |
---|
[1286] | 80 | /// Set comparison function and resort heap |
---|
[1506] | 81 | void setComparison(CbcCompareBase &compare); |
---|
[2] | 82 | |
---|
[1286] | 83 | /// Return the top node of the heap |
---|
| 84 | virtual CbcNode * top() const; |
---|
[2] | 85 | |
---|
[1286] | 86 | /// Add a node to the heap |
---|
[1506] | 87 | virtual void push(CbcNode *x); |
---|
[2] | 88 | |
---|
[1286] | 89 | /// Remove the top node from the heap |
---|
| 90 | virtual void pop() ; |
---|
[1506] | 91 | |
---|
| 92 | /*! \brief Gets best node and takes off heap |
---|
| 93 | |
---|
| 94 | Before returning the node from the top of the heap, the node |
---|
| 95 | is offered an opportunity to reevaluate itself. Callers should |
---|
| 96 | be prepared to check that the node returned is suitable for use. |
---|
| 97 | */ |
---|
[1286] | 98 | virtual CbcNode * bestNode(double cutoff); |
---|
[2] | 99 | |
---|
[1506] | 100 | /*! \brief Rebuild the heap */ |
---|
| 101 | virtual void rebuild() ; |
---|
[2] | 102 | //@} |
---|
[1506] | 103 | |
---|
| 104 | /*! \name Direct node access methods */ |
---|
[2] | 105 | //@{ |
---|
[1506] | 106 | /// Test for an empty tree |
---|
[1286] | 107 | virtual bool empty() ; |
---|
[2] | 108 | |
---|
[1286] | 109 | /// Return size |
---|
[1506] | 110 | virtual int size() const { return static_cast<int>(nodes_.size()); } |
---|
[2] | 111 | |
---|
[1286] | 112 | /// Return a node pointer |
---|
[1506] | 113 | inline CbcNode * operator [] (int i) const { return nodes_[i]; } |
---|
[931] | 114 | |
---|
[1506] | 115 | /// Return a node pointer |
---|
| 116 | inline CbcNode * nodePointer (int i) const { return nodes_[i]; } |
---|
[2] | 117 | //@} |
---|
| 118 | |
---|
[1286] | 119 | /*! \name Search tree maintenance */ |
---|
[2] | 120 | //@{ |
---|
[1286] | 121 | /*! \brief Prune the tree using an objective function cutoff |
---|
[2] | 122 | |
---|
[1506] | 123 | This routine removes all nodes with objective worse than the |
---|
| 124 | specified cutoff value. It also sets bestPossibleObjective to |
---|
| 125 | the best objective over remaining nodes. |
---|
[1286] | 126 | */ |
---|
| 127 | virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); |
---|
[2] | 128 | |
---|
[1286] | 129 | /// Get best on list using alternate method |
---|
| 130 | CbcNode * bestAlternate(); |
---|
[135] | 131 | |
---|
[1286] | 132 | /// We may have got an intelligent tree so give it one more chance |
---|
| 133 | virtual void endSearch() {} |
---|
[777] | 134 | |
---|
[1286] | 135 | /// Get best possible objective function in the tree |
---|
| 136 | virtual double getBestPossibleObjective(); |
---|
[1506] | 137 | |
---|
[1286] | 138 | /// Reset maximum node number |
---|
[1506] | 139 | inline void resetNodeNumbers() { maximumNodeNumber_ = 0; } |
---|
| 140 | |
---|
[1315] | 141 | /// Get maximum node number |
---|
[1506] | 142 | inline int maximumNodeNumber() const { return maximumNodeNumber_; } |
---|
| 143 | |
---|
[1286] | 144 | /// Set number of branches |
---|
[1506] | 145 | inline void setNumberBranching(int value) { numberBranching_ = value; } |
---|
| 146 | |
---|
[1286] | 147 | /// Get number of branches |
---|
[1506] | 148 | inline int getNumberBranching() const { return numberBranching_; } |
---|
| 149 | |
---|
[1286] | 150 | /// Set maximum branches |
---|
[1506] | 151 | inline void setMaximumBranching(int value) { maximumBranching_ = value; } |
---|
| 152 | |
---|
[1286] | 153 | /// Get maximum branches |
---|
[1506] | 154 | inline int getMaximumBranching() const { return maximumBranching_; } |
---|
| 155 | |
---|
[1286] | 156 | /// Get branched variables |
---|
[1506] | 157 | inline unsigned int * branched() const { return branched_; } |
---|
| 158 | |
---|
[1286] | 159 | /// Get bounds |
---|
[1506] | 160 | inline int * newBounds() const { return newBound_; } |
---|
| 161 | |
---|
[1286] | 162 | /// Adds branching information to complete state |
---|
| 163 | void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo, |
---|
| 164 | const double * currentLower, |
---|
| 165 | const double * currentUpper); |
---|
| 166 | /// Increase space for data |
---|
| 167 | void increaseSpace(); |
---|
[2] | 168 | //@} |
---|
[1506] | 169 | |
---|
| 170 | # if CBC_DEBUG_HEAP > 0 |
---|
| 171 | /*! \name Debugging methods */ |
---|
| 172 | //@{ |
---|
| 173 | /*! \brief Check that the heap property is satisfied. */ |
---|
| 174 | void validateHeap() ; |
---|
| 175 | //@} |
---|
| 176 | # endif |
---|
| 177 | |
---|
[2] | 178 | protected: |
---|
[1506] | 179 | /// Storage vector for the heap |
---|
[1286] | 180 | std::vector <CbcNode *> nodes_; |
---|
[1506] | 181 | /// Sort predicate for heap ordering. |
---|
| 182 | CbcCompare comparison_; |
---|
[1286] | 183 | /// Maximum "node" number so far to split ties |
---|
| 184 | int maximumNodeNumber_; |
---|
| 185 | /// Size of variable list |
---|
| 186 | int numberBranching_; |
---|
| 187 | /// Maximum size of variable list |
---|
| 188 | int maximumBranching_; |
---|
| 189 | /** Integer variables branched or bounded |
---|
| 190 | top bit set if new upper bound |
---|
| 191 | next bit set if a branch |
---|
| 192 | */ |
---|
| 193 | unsigned int * branched_; |
---|
| 194 | /// New bound |
---|
| 195 | int * newBound_; |
---|
[2] | 196 | }; |
---|
[640] | 197 | |
---|
[1506] | 198 | #ifdef JJF_ZERO // not used |
---|
| 199 | /*! \brief Implementation of live set as a managed array. |
---|
| 200 | |
---|
[1132] | 201 | This class is used to hold the set of live nodes in the search tree. |
---|
| 202 | */ |
---|
| 203 | class CbcTreeArray : public CbcTree { |
---|
| 204 | |
---|
| 205 | public: |
---|
| 206 | |
---|
[1286] | 207 | // Default Constructor |
---|
| 208 | CbcTreeArray (); |
---|
[1132] | 209 | |
---|
[1286] | 210 | // Copy constructor |
---|
| 211 | CbcTreeArray ( const CbcTreeArray & rhs); |
---|
| 212 | // = operator |
---|
| 213 | CbcTreeArray & operator=(const CbcTreeArray & rhs); |
---|
[1132] | 214 | |
---|
[1286] | 215 | virtual ~CbcTreeArray(); |
---|
[1132] | 216 | |
---|
[1286] | 217 | /// Clone |
---|
| 218 | virtual CbcTree * clone() const; |
---|
| 219 | /// Create C++ lines to get to current state |
---|
| 220 | virtual void generateCpp( FILE * ) {} |
---|
| 221 | |
---|
| 222 | /*! \name Heap access and maintenance methods */ |
---|
[1132] | 223 | //@{ |
---|
| 224 | |
---|
[1286] | 225 | /// Set comparison function and resort heap |
---|
| 226 | void setComparison(CbcCompareBase &compare); |
---|
[1132] | 227 | |
---|
[1286] | 228 | /// Add a node to the heap |
---|
| 229 | virtual void push(CbcNode * x); |
---|
[1132] | 230 | |
---|
[1286] | 231 | /// Gets best node and takes off heap |
---|
| 232 | virtual CbcNode * bestNode(double cutoff); |
---|
[1132] | 233 | |
---|
| 234 | //@} |
---|
[1286] | 235 | /*! \name vector methods */ |
---|
[1132] | 236 | //@{ |
---|
| 237 | |
---|
[1286] | 238 | /// Test if empty *** note may be overridden |
---|
| 239 | virtual bool empty() ; |
---|
[1132] | 240 | |
---|
| 241 | //@} |
---|
| 242 | |
---|
[1286] | 243 | /*! \name Search tree maintenance */ |
---|
[1132] | 244 | //@{ |
---|
| 245 | |
---|
[1286] | 246 | /*! \brief Prune the tree using an objective function cutoff |
---|
[1132] | 247 | |
---|
[1286] | 248 | This routine removes all nodes with objective worst than the |
---|
| 249 | specified cutoff value. |
---|
| 250 | It also sets bestPossibleObjective to best |
---|
| 251 | of all on tree before deleting. |
---|
| 252 | */ |
---|
[1132] | 253 | |
---|
[1286] | 254 | void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); |
---|
| 255 | /// Get best possible objective function in the tree |
---|
| 256 | virtual double getBestPossibleObjective(); |
---|
[1132] | 257 | //@} |
---|
| 258 | protected: |
---|
[1286] | 259 | /// Returns |
---|
| 260 | /// Last node |
---|
| 261 | CbcNode * lastNode_; |
---|
| 262 | /// Last node popped |
---|
| 263 | CbcNode * lastNodePopped_; |
---|
| 264 | /// Not used yet |
---|
| 265 | int switches_; |
---|
[1132] | 266 | |
---|
| 267 | }; |
---|
| 268 | |
---|
[640] | 269 | /// New style |
---|
| 270 | #include "CoinSearchTree.hpp" |
---|
| 271 | /*! \class tree |
---|
| 272 | \brief Implementation of live set as a heap. |
---|
| 273 | |
---|
| 274 | This class is used to hold the set of live nodes in the search tree. |
---|
| 275 | */ |
---|
| 276 | |
---|
| 277 | class CbcNewTree : public CbcTree, public CoinSearchTreeManager { |
---|
| 278 | |
---|
| 279 | public: |
---|
| 280 | |
---|
[1286] | 281 | // Default Constructor |
---|
| 282 | CbcNewTree (); |
---|
[640] | 283 | |
---|
[1286] | 284 | // Copy constructor |
---|
| 285 | CbcNewTree ( const CbcNewTree & rhs); |
---|
| 286 | // = operator |
---|
| 287 | CbcNewTree & operator=(const CbcNewTree & rhs); |
---|
[640] | 288 | |
---|
[1286] | 289 | virtual ~CbcNewTree(); |
---|
[640] | 290 | |
---|
[1286] | 291 | /// Clone |
---|
| 292 | virtual CbcNewTree * clone() const; |
---|
| 293 | /// Create C++ lines to get to current state |
---|
| 294 | virtual void generateCpp( FILE * ) {} |
---|
| 295 | |
---|
| 296 | /*! \name Heap access and maintenance methods */ |
---|
[640] | 297 | //@{ |
---|
| 298 | |
---|
[1286] | 299 | /// Set comparison function and resort heap |
---|
| 300 | void setComparison(CbcCompareBase &compare); |
---|
[640] | 301 | |
---|
[1286] | 302 | /// Return the top node of the heap |
---|
| 303 | virtual CbcNode * top() const; |
---|
[640] | 304 | |
---|
[1286] | 305 | /// Add a node to the heap |
---|
| 306 | virtual void push(CbcNode * x); |
---|
[640] | 307 | |
---|
[1286] | 308 | /// Remove the top node from the heap |
---|
| 309 | virtual void pop() ; |
---|
| 310 | /// Gets best node and takes off heap |
---|
| 311 | virtual CbcNode * bestNode(double cutoff); |
---|
[640] | 312 | |
---|
| 313 | //@} |
---|
[1286] | 314 | /*! \name vector methods */ |
---|
[640] | 315 | //@{ |
---|
| 316 | |
---|
[1286] | 317 | /// Test if empty *** note may be overridden |
---|
| 318 | virtual bool empty() ; |
---|
[640] | 319 | |
---|
[1286] | 320 | /// Return size |
---|
| 321 | inline int size() const { |
---|
| 322 | return nodes_.size(); |
---|
| 323 | } |
---|
[640] | 324 | |
---|
[1286] | 325 | /// [] operator |
---|
| 326 | inline CbcNode * operator [] (int i) const { |
---|
| 327 | return nodes_[i]; |
---|
| 328 | } |
---|
[640] | 329 | |
---|
[1286] | 330 | /// Return a node pointer |
---|
| 331 | inline CbcNode * nodePointer (int i) const { |
---|
| 332 | return nodes_[i]; |
---|
| 333 | } |
---|
[640] | 334 | |
---|
| 335 | //@} |
---|
| 336 | |
---|
[1286] | 337 | /*! \name Search tree maintenance */ |
---|
[640] | 338 | //@{ |
---|
| 339 | |
---|
[1286] | 340 | /*! \brief Prune the tree using an objective function cutoff |
---|
[640] | 341 | |
---|
[1286] | 342 | This routine removes all nodes with objective worst than the |
---|
| 343 | specified cutoff value. |
---|
| 344 | It also sets bestPossibleObjective to best |
---|
| 345 | of all on tree before deleting. |
---|
| 346 | */ |
---|
[640] | 347 | |
---|
[1286] | 348 | void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); |
---|
[640] | 349 | |
---|
[1286] | 350 | /// Get best on list using alternate method |
---|
| 351 | CbcNode * bestAlternate(); |
---|
[640] | 352 | |
---|
[1286] | 353 | /// We may have got an intelligent tree so give it one more chance |
---|
| 354 | virtual void endSearch() {} |
---|
[640] | 355 | //@} |
---|
| 356 | protected: |
---|
| 357 | |
---|
| 358 | |
---|
| 359 | }; |
---|
[1343] | 360 | #endif |
---|
[724] | 361 | #else |
---|
[1506] | 362 | /* CBC_DUBIOUS_HEAP is defined |
---|
| 363 | |
---|
| 364 | See note at top of file. This code is highly suspect. |
---|
| 365 | -- lh, 100921 -- |
---|
| 366 | */ |
---|
[724] | 367 | class CbcTree { |
---|
| 368 | |
---|
| 369 | public: |
---|
| 370 | |
---|
[1286] | 371 | // Default Constructor |
---|
| 372 | CbcTree (); |
---|
[724] | 373 | |
---|
[1286] | 374 | // Copy constructor |
---|
| 375 | CbcTree ( const CbcTree & rhs); |
---|
| 376 | // = operator |
---|
| 377 | CbcTree & operator=(const CbcTree & rhs); |
---|
[724] | 378 | |
---|
[1286] | 379 | virtual ~CbcTree(); |
---|
[724] | 380 | |
---|
[1286] | 381 | /// Clone |
---|
| 382 | virtual CbcTree * clone() const; |
---|
| 383 | /// Create C++ lines to get to current state |
---|
| 384 | virtual void generateCpp( FILE * fp) {} |
---|
| 385 | |
---|
| 386 | /*! \name Heap access and maintenance methods */ |
---|
[724] | 387 | //@{ |
---|
| 388 | |
---|
[1286] | 389 | /// Set comparison function and resort heap |
---|
| 390 | void setComparison(CbcCompareBase &compare); |
---|
[724] | 391 | |
---|
[1286] | 392 | /// Return the top node of the heap |
---|
| 393 | virtual CbcNode * top() const; |
---|
[724] | 394 | |
---|
[1286] | 395 | /// Add a node to the heap |
---|
| 396 | virtual void push(CbcNode * x); |
---|
[724] | 397 | |
---|
[1286] | 398 | /// Remove the top node from the heap |
---|
| 399 | virtual void pop() ; |
---|
| 400 | /// Gets best node and takes off heap |
---|
| 401 | virtual CbcNode * bestNode(double cutoff); |
---|
[724] | 402 | |
---|
| 403 | //@} |
---|
[1286] | 404 | /*! \name vector methods */ |
---|
[724] | 405 | //@{ |
---|
| 406 | |
---|
[1286] | 407 | /// Test if empty *** note may be overridden |
---|
| 408 | //virtual bool empty() ; |
---|
[724] | 409 | |
---|
[1286] | 410 | /// Return size |
---|
| 411 | inline int size() const { |
---|
| 412 | return nodes_.size(); |
---|
| 413 | } |
---|
[724] | 414 | |
---|
[1286] | 415 | /// [] operator |
---|
| 416 | inline CbcNode * operator [] (int i) const { |
---|
| 417 | return nodes_[i]; |
---|
| 418 | } |
---|
[724] | 419 | |
---|
[1286] | 420 | /// Return a node pointer |
---|
| 421 | inline CbcNode * nodePointer (int i) const { |
---|
| 422 | return nodes_[i]; |
---|
| 423 | } |
---|
| 424 | |
---|
| 425 | virtual bool empty(); |
---|
| 426 | //inline int size() const { return size_; } |
---|
| 427 | void realpop(); |
---|
| 428 | /** After changing data in the top node, fix the heap */ |
---|
| 429 | void fixTop(); |
---|
| 430 | void realpush(CbcNode * node); |
---|
[724] | 431 | //@} |
---|
| 432 | |
---|
[1286] | 433 | /*! \name Search tree maintenance */ |
---|
[724] | 434 | //@{ |
---|
| 435 | |
---|
[1286] | 436 | /*! \brief Prune the tree using an objective function cutoff |
---|
[724] | 437 | |
---|
[1286] | 438 | This routine removes all nodes with objective worst than the |
---|
| 439 | specified cutoff value. |
---|
| 440 | It also sets bestPossibleObjective to best |
---|
| 441 | of all on tree before deleting. |
---|
| 442 | */ |
---|
[724] | 443 | |
---|
[1286] | 444 | void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); |
---|
[724] | 445 | |
---|
[1286] | 446 | /// Get best on list using alternate method |
---|
| 447 | CbcNode * bestAlternate(); |
---|
[724] | 448 | |
---|
[1286] | 449 | /// We may have got an intelligent tree so give it one more chance |
---|
| 450 | virtual void endSearch() {} |
---|
| 451 | /// Reset maximum node number |
---|
| 452 | inline void resetNodeNumbers() { |
---|
| 453 | maximumNodeNumber_ = 0; |
---|
| 454 | } |
---|
[724] | 455 | //@} |
---|
| 456 | protected: |
---|
[1286] | 457 | std::vector <CbcNode *> nodes_; |
---|
| 458 | CbcCompare comparison_; ///> Sort function for heap ordering. |
---|
| 459 | /// Maximum "node" number so far to split ties |
---|
| 460 | int maximumNodeNumber_; |
---|
[724] | 461 | |
---|
| 462 | |
---|
| 463 | }; |
---|
[2] | 464 | #endif |
---|
[724] | 465 | #endif |
---|
[2] | 466 | |
---|