Changeset 1573 for trunk/Cbc/src/CbcTree.cpp
 Timestamp:
 Jan 4, 2011 8:12:36 PM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Cbc/src/CbcTree.cpp
r1506 r1573 2 2 // Copyright (C) 2004, International Business Machines 3 3 // Corporation and others. All Rights Reserved. 4 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 5 6 6 #include "CbcModel.hpp" … … 18 18 19 19 /* 20 The next few methods test that the heap property (parent equal or better than either21 child) is maintained in the heap. Originally created to sort out why `cbc unitTest'22 triggered an `Invalid heap' error in a MSVS debug build.20 The next few methods test that the heap property (parent equal or better 21 than either child) is maintained in the heap. Originally created to sort out 22 why `cbc unitTest' triggered an `Invalid heap' error in a MSVS debug build. 23 23 */ 24 24 /* 25 Predicate test. The parent should be better or equal to the child. Since the predicate 26 comparison_(x,y) returns true if y (child) is strictly better, we want failure on the 27 initial test. Clearly, success for comparison(x,y) and comparison(y,x) is also a failure. 25 Predicate test. The parent should be better or equal to the child. Since the 26 predicate comparison_(x,y) returns true if y (child) is strictly better, 27 we want failure on the initial test. Clearly, success for comparison(x,y) 28 and comparison(y,x) is also a failure. 28 29 29 30 Returns true if the predicate passes, false if it fails. … … 43 44 44 45 /* 45 Check for the heap property: the parent is better than or equal to either child. 46 47 The heap is a binary tree, stored in the vector layer by layer. By advancing parent 48 at half the rate of child (aka curNode), we check both children of a given parent. 49 (Draw yourself a picture; it'll help.) An empty heap is trivially valid. A heap with 50 no predicate is trivially invalid. 51 52 TODO: The heap > vector mapping assumed here is valid for the MSVS heap implementation. 53 No guarantee it's valid elsewhere. 46 Check for the heap property: the parent is better than or equal to 47 either child. 48 49 The heap is a binary tree, stored in the vector layer by layer. By advancing 50 parent at half the rate of child (aka curNode), we check both children 51 of a given parent. (Draw yourself a picture; it'll help.) An empty heap 52 is trivially valid. A heap with no predicate is trivially invalid. 53 54 TODO: The heap > vector mapping assumed here is valid for the MSVS heap 55 implementation. No guarantee it's valid elsewhere. 54 56 */ 55 57 … … 84 86 if (*curNode == 0) { 85 87 std::cout 86 << " Invalid heap[" << curNdx << "] (left child null entry)!" << std::endl ; 88 << " Invalid heap[" << curNdx << "] (left child null entry)!" 89 << std::endl ; 87 90 } else { 88 91 if (!check_pred(*comparison_.test_,*parent,*child)) { … … 92 95 std::cout 93 96 << " Parent [" << parNdx << "] (" << std::hex << node << std::dec 94 << ") unsat " << node>numberUnsatisfied() << ", depth " << node>depth() 95 << ", obj " << node>objectiveValue() << "." << std::endl ; 97 << ") unsat " << node>numberUnsatisfied() << ", depth " 98 << node>depth() << ", obj " << node>objectiveValue() << "." 99 << std::endl ; 96 100 node = *child ; 97 101 std::cout 98 102 << " Child [" << curNdx << "] (" << std::hex << node << std::dec 99 << ") unsat " << node>numberUnsatisfied() << ", depth " << node>depth() 100 << ", obj " << node>objectiveValue() << "." << std::endl ; 103 << ") unsat " << node>numberUnsatisfied() << ", depth " 104 << node>depth() << ", obj " << node>objectiveValue() << "." 105 << std::endl ; 101 106 } 102 107 } … … 106 111 if (*curNode == 0) { 107 112 std::cout 108 << " Invalid heap[" << curNdx << "] (right child null entry)!" << std::endl ; 113 << " Invalid heap[" << curNdx << "] (right child null entry)!" 114 << std::endl ; 109 115 } else { 110 116 if (!check_pred(*comparison_.test_,*parent,*child)) { … … 114 120 std::cout 115 121 << " Parent [" << parNdx << "] (" << std::hex << node << std::dec 116 << ") unsat " << node>numberUnsatisfied() << ", depth " << node>depth() 117 << ", obj " << node>objectiveValue() << "." << std::endl ; 122 << ") unsat " << node>numberUnsatisfied() << ", depth " 123 << node>depth() << ", obj " << node>objectiveValue() << "." 124 << std::endl ; 118 125 node = *child ; 119 126 std::cout 120 127 << " Child [" << curNdx << "] (" << std::hex << node << std::dec 121 << ") unsat " << node>numberUnsatisfied() << ", depth " << node>depth() 122 << ", obj " << node>objectiveValue() << "." << std::endl ; 128 << ") unsat " << node>numberUnsatisfied() << ", depth " 129 << node>depth() << ", obj " << node>objectiveValue() << "." 130 << std::endl ; 123 131 } 124 132 } 125 133 } 126 return ;134 return ; 127 135 } 128 136 … … 612 620 are necessary. When reconstructing a node, these checks are used to skip 613 621 over loose cuts, excluding them from the reconstituted basis. But here 614 we're just interested in correcting the reference count. Tight/loose should615 make no difference.616 617 Arguably a separate routine should be used in place of addCuts1. It's doing618 more work than needed, modifying the model to match a subproblem at a node619 that will be discarded. Then again, we seem to need the basis.622 we're just interested in correcting the reference count. Tight/loose 623 should make no difference. 624 625 Arguably a separate routine should be used in place of addCuts1. It's 626 doing more work than needed, modifying the model to match a subproblem 627 at a node that will be discarded. Then again, we seem to need the basis. 620 628 */ 621 629 for (j = nNodes  1; j >= kDelete; j) { … … 1004 1012 are necessary. When reconstructing a node, these checks are used to skip 1005 1013 over loose cuts, excluding them from the reconstituted basis. But here 1006 we're just interested in correcting the reference count. Tight/loose should1007 make no difference.1008 1009 Arguably a separate routine should be used in place of addCuts1. It's doing1010 more work than needed, modifying the model to match a subproblem at a node1011 that will be discarded. Then again, we seem to need the basis.1014 we're just interested in correcting the reference count. Tight/loose 1015 should make no difference. 1016 1017 Arguably a separate routine should be used in place of addCuts1. It's 1018 doing more work than needed, modifying the model to match a subproblem 1019 at a node that will be discarded. Then again, we seem to need the basis. 1012 1020 */ 1013 1021 for (j = lastNode  1; j >= kDelete; j) { … … 1290 1298 are necessary. When reconstructing a node, these checks are used to skip 1291 1299 over loose cuts, excluding them from the reconstituted basis. But here 1292 we're just interested in correcting the reference count. Tight/loose should1293 make no difference.1294 1295 Arguably a separate routine should be used in place of addCuts1. It's doing1296 more work than needed, modifying the model to match a subproblem at a node1297 that will be discarded. Then again, we seem to need the basis.1300 we're just interested in correcting the reference count. Tight/loose 1301 should make no difference. 1302 1303 Arguably a separate routine should be used in place of addCuts1. It's 1304 doing more work than needed, modifying the model to match a subproblem 1305 at a node that will be discarded. Then again, we seem to need the basis. 1298 1306 */ 1299 1307 for (j = nNodes  1; j >= kDelete; j) {
Note: See TracChangeset
for help on using the changeset viewer.