Changeset 912 for trunk/Cbc/src/CbcHeuristic.cpp
 Timestamp:
 Apr 10, 2008 1:55:10 PM (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Cbc/src/CbcHeuristic.cpp
r904 r912 13 13 #include <cfloat> 14 14 15 //#define PRINT_DEBUG 15 16 #ifdef COIN_HAS_CLP 16 17 #include "OsiClpSolverInterface.hpp" … … 24 25 #include "OsiAuxInfo.hpp" 25 26 #include "OsiPresolve.hpp" 27 #include "CbcBranchActual.hpp" 28 //============================================================================== 29 30 CbcHeuristicNode::CbcHeuristicNode(const CbcHeuristicNode& rhs) 31 { 32 numObjects_ = rhs.numObjects_; 33 brObj_ = new CbcBranchingObject*[numObjects_]; 34 for (int i = 0; i < numObjects_; ++i) { 35 brObj_[i] = rhs.brObj_[i]>clone(); 36 } 37 } 38 39 void 40 CbcHeuristicNodeList::gutsOfDelete() 41 { 42 for (int i = nodes_.size()  1; i >= 0; i) { 43 delete nodes_[i]; 44 } 45 } 46 47 void 48 CbcHeuristicNodeList::gutsOfCopy(const CbcHeuristicNodeList& rhs) 49 { 50 append(rhs); 51 } 52 53 CbcHeuristicNodeList::CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs) 54 { 55 gutsOfCopy(rhs); 56 } 57 58 CbcHeuristicNodeList& CbcHeuristicNodeList::operator= 59 (const CbcHeuristicNodeList& rhs) 60 { 61 if (this != &rhs) { 62 gutsOfDelete(); 63 gutsOfCopy(rhs); 64 } 65 return *this; 66 } 67 68 CbcHeuristicNodeList::~CbcHeuristicNodeList() 69 { 70 gutsOfDelete(); 71 } 72 73 void 74 CbcHeuristicNodeList::append(CbcHeuristicNode*& node) 75 { 76 nodes_.push_back(node); 77 node = NULL; 78 } 79 80 void 81 CbcHeuristicNodeList::append(const CbcHeuristicNodeList& nodes) 82 { 83 nodes_.reserve(nodes_.size() + nodes.size()); 84 for (int i = 0; i < nodes.size(); ++i) { 85 CbcHeuristicNode* node = new CbcHeuristicNode(*nodes.node(i)); 86 append(node); 87 } 88 } 89 90 //============================================================================== 26 91 27 92 // Default Constructor 28 CbcHeuristic::CbcHeuristic() 29 :model_(NULL), 30 when_(2), 31 numberNodes_(200), 32 feasibilityPumpOptions_(1), 33 fractionSmall_(1.0), 34 heuristicName_("Unknown") 93 CbcHeuristic::CbcHeuristic() : 94 model_(NULL), 95 when_(2), 96 numberNodes_(200), 97 feasibilityPumpOptions_(1), 98 fractionSmall_(1.0), 99 heuristicName_("Unknown"), 100 howOften_(1), 101 decayFactor_(0.0), 102 shallowDepth_(1), 103 howOftenShallow_(1), 104 numInvocationsInShallow_(0), 105 numInvocationsInDeep_(0), 106 lastRunDeep_(0), 107 numRuns_(0), 108 minDistanceToRun_(1), 109 runNodes_(), 110 numCouldRun_(0) 35 111 { 36 112 // As CbcHeuristic virtual need to modify .cpp if above change … … 38 114 39 115 // Constructor from model 40 CbcHeuristic::CbcHeuristic(CbcModel & model) 41 : 116 CbcHeuristic::CbcHeuristic(CbcModel & model) : 42 117 model_(&model), 43 118 when_(2), … … 45 120 feasibilityPumpOptions_(1), 46 121 fractionSmall_(1.0), 47 heuristicName_("Unknown") 48 { 49 // As CbcHeuristic virtual need to modify .cpp if above change 122 heuristicName_("Unknown"), 123 howOften_(1), 124 decayFactor_(0.0), 125 shallowDepth_(1), 126 howOftenShallow_(1), 127 numInvocationsInShallow_(0), 128 numInvocationsInDeep_(0), 129 lastRunDeep_(0), 130 numRuns_(0), 131 minDistanceToRun_(1), 132 runNodes_(), 133 numCouldRun_(0) 134 {} 135 136 void 137 CbcHeuristic::gutsOfCopy(const CbcHeuristic & rhs) 138 { 139 model_ = rhs.model_; 140 when_ = rhs.when_; 141 numberNodes_ = rhs.numberNodes_; 142 feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_; 143 fractionSmall_ = rhs.fractionSmall_; 144 randomNumberGenerator_ = rhs.randomNumberGenerator_; 145 heuristicName_ = rhs.heuristicName_; 146 howOften_ = rhs.howOften_; 147 decayFactor_ = rhs.howOften_; 148 shallowDepth_= rhs.shallowDepth_; 149 howOftenShallow_= rhs.howOftenShallow_; 150 numInvocationsInShallow_ = rhs.numInvocationsInShallow_; 151 numInvocationsInDeep_ = rhs.numInvocationsInDeep_; 152 lastRunDeep_ = rhs.lastRunDeep_; 153 numRuns_ = rhs.numRuns_; 154 numCouldRun_ = rhs.numCouldRun_; 155 minDistanceToRun_ = rhs.minDistanceToRun_; 156 runNodes_ = rhs.runNodes_; 50 157 } 51 158 // Copy constructor 52 159 CbcHeuristic::CbcHeuristic(const CbcHeuristic & rhs) 53 : 54 model_(rhs.model_), 55 when_(rhs.when_), 56 numberNodes_(rhs.numberNodes_), 57 feasibilityPumpOptions_(rhs.feasibilityPumpOptions_), 58 fractionSmall_(rhs.fractionSmall_), 59 randomNumberGenerator_(rhs.randomNumberGenerator_), 60 heuristicName_(rhs.heuristicName_) 61 { 62 } 160 { 161 gutsOfCopy(rhs); 162 } 163 63 164 // Assignment operator 64 165 CbcHeuristic & … … 66 167 { 67 168 if (this!=&rhs) { 68 model_ = rhs.model_; 69 when_ = rhs.when_; 70 numberNodes_ = rhs.numberNodes_; 71 feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_; 72 fractionSmall_ = rhs.fractionSmall_; 73 randomNumberGenerator_ = rhs.randomNumberGenerator_; 74 heuristicName_ = rhs.heuristicName_ ; 169 gutsOfDelete(); 170 gutsOfCopy(rhs); 75 171 } 76 172 return *this; 173 } 174 175 void CbcHeurDebugNodes(CbcModel* model_) 176 { 177 CbcNode* node = model_>currentNode(); 178 CbcNodeInfo* nodeInfo = node>nodeInfo(); 179 std::cout << "===============================================================\n"; 180 while (nodeInfo) { 181 const CbcNode* node = nodeInfo>owner(); 182 printf("nodeinfo: node %i\n", nodeInfo>nodeNumber()); 183 { 184 const CbcIntegerBranchingObject* brPrint = 185 dynamic_cast<const CbcIntegerBranchingObject*>(nodeInfo>parentBranch()); 186 if (!brPrint) { 187 printf(" parentBranch: NULL\n"); 188 } else { 189 const double* downBounds = brPrint>downBounds(); 190 const double* upBounds = brPrint>upBounds(); 191 int variable = brPrint>variable(); 192 int way = brPrint>way(); 193 printf(" parentBranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", 194 variable, (int)downBounds[0], (int)downBounds[1], 195 (int)upBounds[0], (int)upBounds[1], way); 196 } 197 } 198 if (! node) { 199 printf(" owner: NULL\n"); 200 } else { 201 printf(" owner: node %i depth %i onTree %i active %i", 202 node>nodeNumber(), node>depth(), node>onTree(), node>active()); 203 const OsiBranchingObject* osibr = 204 nodeInfo>owner()>branchingObject(); 205 const CbcBranchingObject* cbcbr = 206 dynamic_cast<const CbcBranchingObject*>(osibr); 207 const CbcIntegerBranchingObject* brPrint = 208 dynamic_cast<const CbcIntegerBranchingObject*>(cbcbr); 209 if (!brPrint) { 210 printf(" ownerBranch: NULL\n"); 211 } else { 212 const double* downBounds = brPrint>downBounds(); 213 const double* upBounds = brPrint>upBounds(); 214 int variable = brPrint>variable(); 215 int way = brPrint>way(); 216 printf(" ownerbranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", 217 variable, (int)downBounds[0], (int)downBounds[1], 218 (int)upBounds[0], (int)upBounds[1], way); 219 } 220 } 221 nodeInfo = nodeInfo>parent(); 222 } 223 } 224 225 void 226 CbcHeuristic::debugNodes() 227 { 228 CbcHeurDebugNodes(model_); 229 } 230 231 void 232 CbcHeuristic::printDistanceToNodes() 233 { 234 const CbcNode* currentNode = model_>currentNode(); 235 if (currentNode != NULL) { 236 CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); 237 for (int i = runNodes_.size()  1; i >= 0; i) { 238 nodeDesc>distance(runNodes_.node(i)); 239 } 240 runNodes_.append(nodeDesc); 241 } 242 } 243 244 bool 245 CbcHeuristic::shouldHeurRun() 246 { 247 248 #if 0 249 const CbcNode* currentNode = model_>currentNode(); 250 if (currentNode == NULL) { 251 return false; 252 } 253 254 debugNodes(); 255 // return false; 256 257 const int depth = currentNode>depth(); 258 #else 259 int depth = 0; 260 const CbcNode* currentNode = model_>currentNode(); 261 if (currentNode != NULL) { 262 depth = currentNode>depth(); 263 #ifdef PRINT_DEBUG 264 debugNodes(); 265 #endif 266 } 267 #endif 268 269 const int nodeCount = model_>getNodeCount(); // FIXME: check that this is 270 // correct in parallel 271 272 if (nodeCount == 0  depth <= shallowDepth_) { 273 // what to do when we are in the shallow part of the tree 274 if (model_>getCurrentPassNumber() == 1) { 275 // first time in the node... 276 numInvocationsInShallow_ = 0; 277 } 278 ++numInvocationsInShallow_; 279 // Very large howOftenShallow_ will give the original test: 280 // (model_>getCurrentPassNumber() != 1) 281 // if ((numInvocationsInShallow_ % howOftenShallow_) != 1) { 282 if ((numInvocationsInShallow_ % howOftenShallow_) != 0) { 283 return false; 284 } 285 // LL: should we save these nodes in the list of nodes where the heur was 286 // LL: run? 287 #if 1 288 if (currentNode != NULL) { 289 // Get where we are and create the appropriate CbcHeuristicNode object 290 CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); 291 runNodes_.append(nodeDesc); 292 } 293 #endif 294 } else { 295 // deeper in the tree 296 if (model_>getCurrentPassNumber() == 1) { 297 // first time in the node... 298 ++numInvocationsInDeep_; 299 } 300 if (numInvocationsInDeep_  lastRunDeep_ < howOften_) { 301 return false; 302 } 303 if (model_>getCurrentPassNumber() != 1) { 304 // Run the heuristic only when first entering the node. 305 // LL: I don't think this is right. It should run just before strong 306 // LL: branching, I believe. 307 return false; 308 } 309 // Get where we are and create the appropriate CbcHeuristicNode object 310 CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); 311 //#ifdef PRINT_DEBUG 312 #if 1 313 double minDistance = nodeDesc>minDistance(runNodes_); 314 double minDistanceToRun = 1.5 * log((double)depth) / log((double)2); 315 std::cout<<"minDistance = "<<minDistance 316 <<", minDistanceToRun = "<<minDistanceToRun<<std::endl; 317 if (minDistance < minDistanceToRun) { 318 #else 319 if (nodeDesc>minDistance(runNodes_) < minDistanceToRun_) { 320 #endif 321 delete nodeDesc; 322 return false; 323 } 324 runNodes_.append(nodeDesc); 325 lastRunDeep_ = numInvocationsInDeep_; 326 // ++lastRunDeep_; 327 } 328 ++numRuns_; 329 return true; 330 } 331 332 bool 333 CbcHeuristic::shouldHeurRun_randomChoice() 334 { 335 int depth = 0; 336 const CbcNode* currentNode = model_>currentNode(); 337 if (currentNode != NULL) { 338 depth = currentNode>depth(); 339 } 340 341 if(depth != 0) { 342 const double numerator = depth * depth; 343 const double denominator = exp(depth * log((double)2)); 344 double probability = numerator / denominator; 345 double randomNumber = randomNumberGenerator_.randomDouble(); 346 if (randomNumber>probability) 347 return false; 348 349 if (model_>getCurrentPassNumber() > 1) 350 return false; 351 } 352 ++numRuns_; 353 return true; 77 354 } 78 355 … … 82 359 { 83 360 model_=model; 84 }361 } 85 362 // Set seed 86 363 void … … 460 737 return returnCode; 461 738 } 739 740 //############################################################################## 741 742 inline int compare3BranchingObjects(const CbcBranchingObject* br0, 743 const CbcBranchingObject* br1) 744 { 745 const int t0 = br0>type(); 746 const int t1 = br1>type(); 747 if (t0 < t1) { 748 return 1; 749 } 750 if (t0 > t1) { 751 return 1; 752 } 753 return br0>compareOriginalObject(br1); 754 } 755 756 //============================================================================== 757 758 inline bool compareBranchingObjects(const CbcBranchingObject* br0, 759 const CbcBranchingObject* br1) 760 { 761 return compare3BranchingObjects(br0, br1) < 0; 762 } 763 764 //============================================================================== 765 766 void 767 CbcHeuristicNode::gutsOfConstructor(CbcModel& model) 768 { 769 // CbcHeurDebugNodes(&model); 770 CbcNode* node = model.currentNode(); 771 brObj_ = new CbcBranchingObject*[node>depth()]; 772 CbcNodeInfo* nodeInfo = node>nodeInfo(); 773 int cnt = 0; 774 while (nodeInfo>parentBranch() != NULL) { 775 brObj_[cnt++] = nodeInfo>parentBranch()>clone(); 776 nodeInfo = nodeInfo>parent(); 777 } 778 std::sort(brObj_, brObj_+cnt, compareBranchingObjects); 779 if (cnt <= 1) { 780 numObjects_ = cnt; 781 } else { 782 numObjects_ = 0; 783 CbcBranchingObject* br; 784 for (int i = 1; i < cnt; ++i) { 785 if (compare3BranchingObjects(brObj_[numObjects_], brObj_[i]) == 0) { 786 int comp = brObj_[numObjects_]>compareBranchingObject(brObj_[i], &br); 787 switch (comp) { 788 case CbcRangeSame: // the same range 789 case CbcRangeDisjoint: // disjoint decisions 790 // should not happen! we are on a chain! 791 abort(); 792 case CbcRangeSubset: // brObj_[numObjects_] is a subset of brObj_[i] 793 delete brObj_[i]; 794 break; 795 case CbcRangeSuperset: // brObj_[i] is a subset of brObj_[numObjects_] 796 delete brObj_[numObjects_]; 797 brObj_[numObjects_] = brObj_[i]; 798 break; 799 case CbcRangeOverlap: // overlap 800 delete brObj_[i]; 801 delete brObj_[numObjects_]; 802 brObj_[numObjects_] = br; 803 break; 804 } 805 continue; 806 } else { 807 brObj_[++numObjects_] = brObj_[i]; 808 } 809 } 810 ++numObjects_; 811 } 812 } 813 814 //============================================================================== 815 816 CbcHeuristicNode::CbcHeuristicNode(CbcModel& model) 817 { 818 gutsOfConstructor(model); 819 } 820 821 //============================================================================== 822 823 double 824 CbcHeuristicNode::distance(const CbcHeuristicNode* node) const 825 { 826 827 const double disjointWeight = 1; 828 const double overlapWeight = 0.4; 829 const double subsetWeight = 0.2; 830 int countDisjointWeight = 0; 831 int countOverlapWeight = 0; 832 int countSubsetWeight = 0; 833 int i = 0; 834 int j = 0; 835 double dist = 0.0; 836 #ifdef PRINT_DEBUG 837 printf(" numObjects_ = %i, node>numObjects_ = %i\n", 838 numObjects_, node>numObjects_); 839 #endif 840 while( i < numObjects_ && j < node>numObjects_) { 841 CbcBranchingObject* br0 = brObj_[i]; 842 const CbcBranchingObject* br1 = node>brObj_[j]; 843 #ifdef PRINT_DEBUG 844 const CbcIntegerBranchingObject* brPrint0 = 845 dynamic_cast<const CbcIntegerBranchingObject*>(br0); 846 const double* downBounds = brPrint0>downBounds(); 847 const double* upBounds = brPrint0>upBounds(); 848 int variable = brPrint0>variable(); 849 int way = brPrint0>way(); 850 printf(" br0: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", 851 variable, (int)downBounds[0], (int)downBounds[1], 852 (int)upBounds[0], (int)upBounds[1], way); 853 const CbcIntegerBranchingObject* brPrint1 = 854 dynamic_cast<const CbcIntegerBranchingObject*>(br1); 855 downBounds = brPrint1>downBounds(); 856 upBounds = brPrint1>upBounds(); 857 variable = brPrint1>variable(); 858 way = brPrint1>way(); 859 printf(" br1: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", 860 variable, (int)downBounds[0], (int)downBounds[1], 861 (int)upBounds[0], (int)upBounds[1], way); 862 #endif 863 const int brComp = compare3BranchingObjects(br0, br1); 864 if (brComp < 0) { 865 dist += subsetWeight; 866 countSubsetWeight++; 867 ++i; 868 } 869 else if (brComp > 0) { 870 dist += subsetWeight; 871 countSubsetWeight++; 872 ++j; 873 } 874 else { 875 const int comp = br0>compareBranchingObject(br1, false); 876 switch (comp) { 877 case CbcRangeSame: 878 // do nothing 879 break; 880 case CbcRangeDisjoint: // disjoint decisions 881 dist += disjointWeight; 882 countDisjointWeight++; 883 break; 884 case CbcRangeSubset: // subset one way or another 885 case CbcRangeSuperset: 886 dist += subsetWeight; 887 countSubsetWeight++; 888 break; 889 case CbcRangeOverlap: // overlap 890 dist += overlapWeight; 891 countOverlapWeight++; 892 break; 893 } 894 ++i; 895 ++j; 896 } 897 } 898 dist += subsetWeight * (numObjects_  i + node>numObjects_  j); 899 countSubsetWeight += (numObjects_  i + node>numObjects_  j); 900 printf("subset = %i, overlap = %i, disjoint = %i\n", countSubsetWeight, 901 countOverlapWeight, countDisjointWeight); 902 return dist; 903 } 904 905 //============================================================================== 906 907 CbcHeuristicNode::~CbcHeuristicNode() 908 { 909 for (int i = 0; i < numObjects_; ++i) { 910 delete brObj_[i]; 911 } 912 delete [] brObj_; 913 } 914 915 //============================================================================== 916 917 double 918 CbcHeuristicNode::minDistance(const CbcHeuristicNodeList& nodeList) 919 { 920 double minDist = COIN_DBL_MAX; 921 for (int i = nodeList.size()  1; i >= 0; i) { 922 minDist = CoinMin(minDist, distance(nodeList.node(i))); 923 } 924 return minDist; 925 } 926 927 //============================================================================== 928 929 double 930 CbcHeuristicNode::avgDistance(const CbcHeuristicNodeList& nodeList) 931 { 932 if (nodeList.size() == 0) { 933 return COIN_DBL_MAX; 934 } 935 double sumDist = 0; 936 for (int i = nodeList.size()  1; i >= 0; i) { 937 sumDist += distance(nodeList.node(i)); 938 } 939 return sumDist/nodeList.size(); 940 } 941 942 //############################################################################## 462 943 463 944 // Default Constructor
Note: See TracChangeset
for help on using the changeset viewer.