Changeset 1286 for branches/sandbox/Cbc/src/CbcHeuristicDivePseudoCost.cpp
 Timestamp:
 Nov 9, 2009 6:33:07 PM (12 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/sandbox/Cbc/src/CbcHeuristicDivePseudoCost.cpp
r1271 r1286 12 12 13 13 // Default Constructor 14 CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost() 15 :CbcHeuristicDive()14 CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost() 15 : CbcHeuristicDive() 16 16 { 17 17 } … … 19 19 // Constructor from model 20 20 CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(CbcModel & model) 21 :CbcHeuristicDive(model)22 { 23 } 24 25 // Destructor 21 : CbcHeuristicDive(model) 22 { 23 } 24 25 // Destructor 26 26 CbcHeuristicDivePseudoCost::~CbcHeuristicDivePseudoCost () 27 27 { … … 32 32 CbcHeuristicDivePseudoCost::clone() const 33 33 { 34 return new CbcHeuristicDivePseudoCost(*this);34 return new CbcHeuristicDivePseudoCost(*this); 35 35 } 36 36 37 37 // Create C++ lines to get to current state 38 void 39 CbcHeuristicDivePseudoCost::generateCpp( FILE * fp) 40 { 41 CbcHeuristicDivePseudoCost other;42 fprintf(fp,"0#include \"CbcHeuristicDivePseudoCost.hpp\"\n");43 fprintf(fp,"3 CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n");44 CbcHeuristic::generateCpp(fp,"heuristicDivePseudoCost");45 fprintf(fp,"3 cbcModel>addHeuristic(&heuristicDivePseudoCost);\n");46 } 47 48 // Copy constructor 38 void 39 CbcHeuristicDivePseudoCost::generateCpp( FILE * fp) 40 { 41 CbcHeuristicDivePseudoCost other; 42 fprintf(fp, "0#include \"CbcHeuristicDivePseudoCost.hpp\"\n"); 43 fprintf(fp, "3 CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n"); 44 CbcHeuristic::generateCpp(fp, "heuristicDivePseudoCost"); 45 fprintf(fp, "3 cbcModel>addHeuristic(&heuristicDivePseudoCost);\n"); 46 } 47 48 // Copy constructor 49 49 CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(const CbcHeuristicDivePseudoCost & rhs) 50 :51 CbcHeuristicDive(rhs)52 { 53 } 54 55 // Assignment operator 56 CbcHeuristicDivePseudoCost & 57 CbcHeuristicDivePseudoCost::operator=( const CbcHeuristicDivePseudoCost & rhs)58 { 59 if (this!=&rhs) {60 CbcHeuristicDive::operator=(rhs);61 }62 return *this;50 : 51 CbcHeuristicDive(rhs) 52 { 53 } 54 55 // Assignment operator 56 CbcHeuristicDivePseudoCost & 57 CbcHeuristicDivePseudoCost::operator=( const CbcHeuristicDivePseudoCost & rhs) 58 { 59 if (this != &rhs) { 60 CbcHeuristicDive::operator=(rhs); 61 } 62 return *this; 63 63 } 64 64 65 65 bool 66 66 CbcHeuristicDivePseudoCost::selectVariableToBranch(OsiSolverInterface* solver, 67 68 69 70 { 71 int numberIntegers = model_>numberIntegers();72 const int * integerVariable = model_>integerVariable();73 double integerTolerance = model_>getDblParam(CbcModel::CbcIntegerTolerance);74 75 // get the LP relaxation solution at the root node76 double * rootNodeLPSol = model_>continuousSolution();77 78 // get pseudo costs79 double * pseudoCostDown = downArray_;80 double * pseudoCostUp = upArray_;81 82 bestColumn = 1;83 bestRound = 1; // 1 rounds down, +1 rounds up84 double bestScore = 1.0;85 bool allTriviallyRoundableSoFar = true;86 for (int i=0; i<numberIntegers; i++) {87 int iColumn = integerVariable[i];88 double rootValue=rootNodeLPSol[iColumn];89 double value=newSolution[iColumn];90 double fraction=valuefloor(value);91 int round = 0;92 if (fabs(floor(value+0.5)value)>integerTolerance) {93 if (allTriviallyRoundableSoFar(downLocks_[i]>0&&upLocks_[i]>0)) {94 95 if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {96 97 98 99 100 101 102 103 104 if(allTriviallyRoundableSoFar&&downLocks_[i]==0&&upLocks_[i]>0)105 106 else if(allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]==0)107 108 else if(value  rootValue < 0.4)109 110 else if(value  rootValue > 0.4)111 112 else if(fraction < 0.3)113 114 else if(fraction > 0.7)115 116 else if(pCostDown < pCostUp)117 118 119 120 121 122 123 if(round == 1)124 125 126 127 128 129 if(solver>isBinary(iColumn))130 131 132 if(score > bestScore) {133 134 135 136 137 }138 }139 }140 141 return allTriviallyRoundableSoFar;67 const double* newSolution, 68 int& bestColumn, 69 int& bestRound) 70 { 71 int numberIntegers = model_>numberIntegers(); 72 const int * integerVariable = model_>integerVariable(); 73 double integerTolerance = model_>getDblParam(CbcModel::CbcIntegerTolerance); 74 75 // get the LP relaxation solution at the root node 76 double * rootNodeLPSol = model_>continuousSolution(); 77 78 // get pseudo costs 79 double * pseudoCostDown = downArray_; 80 double * pseudoCostUp = upArray_; 81 82 bestColumn = 1; 83 bestRound = 1; // 1 rounds down, +1 rounds up 84 double bestScore = 1.0; 85 bool allTriviallyRoundableSoFar = true; 86 for (int i = 0; i < numberIntegers; i++) { 87 int iColumn = integerVariable[i]; 88 double rootValue = rootNodeLPSol[iColumn]; 89 double value = newSolution[iColumn]; 90 double fraction = value  floor(value); 91 int round = 0; 92 if (fabs(floor(value + 0.5)  value) > integerTolerance) { 93 if (allTriviallyRoundableSoFar  (downLocks_[i] > 0 && upLocks_[i] > 0)) { 94 95 if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) { 96 allTriviallyRoundableSoFar = false; 97 bestScore = 1.0; 98 } 99 100 double pCostDown = pseudoCostDown[i]; 101 double pCostUp = pseudoCostUp[i]; 102 assert(pCostDown >= 0.0 && pCostUp >= 0.0); 103 104 if (allTriviallyRoundableSoFar && downLocks_[i] == 0 && upLocks_[i] > 0) 105 round = 1; 106 else if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] == 0) 107 round = 1; 108 else if (value  rootValue < 0.4) 109 round = 1; 110 else if (value  rootValue > 0.4) 111 round = 1; 112 else if (fraction < 0.3) 113 round = 1; 114 else if (fraction > 0.7) 115 round = 1; 116 else if (pCostDown < pCostUp) 117 round = 1; 118 else 119 round = 1; 120 121 // calculate score 122 double score; 123 if (round == 1) 124 score = fraction * (pCostDown + 1.0) / (pCostUp + 1.0); 125 else 126 score = (1.0  fraction) * (pCostUp + 1.0) / (pCostDown + 1.0); 127 128 // if variable is binary, increase its chance of being selected 129 if (solver>isBinary(iColumn)) 130 score *= 1000.0; 131 132 if (score > bestScore) { 133 bestColumn = iColumn; 134 bestScore = score; 135 bestRound = round; 136 } 137 } 138 } 139 } 140 141 return allTriviallyRoundableSoFar; 142 142 } 143 143 void 144 144 CbcHeuristicDivePseudoCost::initializeData() 145 145 { 146 int numberIntegers = model_>numberIntegers();147 if (!downArray_) {148 downArray_ = new double [numberIntegers];149 upArray_ = new double [numberIntegers];150 }151 // get pseudo costs152 model_>fillPseudoCosts(downArray_, upArray_);153 int diveOptions = when_/100;154 if (diveOptions) {155 // pseudo shadow prices156 int k = diveOptions%100;157 if (diveOptions>=100)158 k +=32;159 model_>pseudoShadow(k1);160 int numberInts=CoinMin(model_>numberObjects(),numberIntegers);161 OsiObject ** objects = model_>objects();162 for (int i=0;i<numberInts;i++) {163 CbcSimpleIntegerDynamicPseudoCost * obj1 =164 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(objects[i]) ;165 if (obj1) {166 //int iColumn = obj1>columnNumber();167 double downPseudoCost = 1.0e2*obj1>downDynamicPseudoCost();168 169 double upPseudoCost = 1.0e2*obj1>upDynamicPseudoCost();170 171 downPseudoCost = CoinMax(downPseudoCost,downShadow);172 downPseudoCost = CoinMax(downPseudoCost,0.001*upShadow);173 downArray_[i]=downPseudoCost;174 upPseudoCost = CoinMax(upPseudoCost,upShadow);175 upPseudoCost = CoinMax(upPseudoCost,0.001*downShadow);176 upArray_[i]=upPseudoCost;177 }178 }179 }146 int numberIntegers = model_>numberIntegers(); 147 if (!downArray_) { 148 downArray_ = new double [numberIntegers]; 149 upArray_ = new double [numberIntegers]; 150 } 151 // get pseudo costs 152 model_>fillPseudoCosts(downArray_, upArray_); 153 int diveOptions = when_ / 100; 154 if (diveOptions) { 155 // pseudo shadow prices 156 int k = diveOptions % 100; 157 if (diveOptions >= 100) 158 k += 32; 159 model_>pseudoShadow(k  1); 160 int numberInts = CoinMin(model_>numberObjects(), numberIntegers); 161 OsiObject ** objects = model_>objects(); 162 for (int i = 0; i < numberInts; i++) { 163 CbcSimpleIntegerDynamicPseudoCost * obj1 = 164 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(objects[i]) ; 165 if (obj1) { 166 //int iColumn = obj1>columnNumber(); 167 double downPseudoCost = 1.0e2 * obj1>downDynamicPseudoCost(); 168 double downShadow = obj1>downShadowPrice(); 169 double upPseudoCost = 1.0e2 * obj1>upDynamicPseudoCost(); 170 double upShadow = obj1>upShadowPrice(); 171 downPseudoCost = CoinMax(downPseudoCost, downShadow); 172 downPseudoCost = CoinMax(downPseudoCost, 0.001 * upShadow); 173 downArray_[i] = downPseudoCost; 174 upPseudoCost = CoinMax(upPseudoCost, upShadow); 175 upPseudoCost = CoinMax(upPseudoCost, 0.001 * downShadow); 176 upArray_[i] = upPseudoCost; 177 } 178 } 179 } 180 180 } 181 181 // Fix other variables at bounds 182 int 182 int 183 183 CbcHeuristicDivePseudoCost::fixOtherVariables(OsiSolverInterface * solver, 184 185 186 187 { 188 const double * lower = solver>getColLower();189 const double * upper = solver>getColUpper();190 double integerTolerance = model_>getDblParam(CbcModel::CbcIntegerTolerance);191 double primalTolerance;192 solver>getDblParam(OsiPrimalTolerance,primalTolerance);193 194 int numberIntegers = model_>numberIntegers();195 const int * integerVariable = model_>integerVariable();196 const double* reducedCost = solver>getReducedCost();197 // fix other integer variables that are at their bounds198 int cnt=0;199 int numberFree=0;200 int numberFixedAlready=0;201 for (int i=0; i<numberIntegers; i++) {202 int iColumn = integerVariable[i];203 if (upper[iColumn]>lower[iColumn]) {204 numberFree++;205 double value=solution[iColumn];206 if(valuelower[iColumn]<=integerTolerance) {207 208 candidate[cnt++].pseudoRedCost = CoinMax(1.0e2*reducedCost[iColumn],209 downArray_[i])*random[i];210 } else if(upper[iColumn]value<=integerTolerance) {211 212 candidate[cnt++].pseudoRedCost = CoinMax(1.0e2*reducedCost[iColumn],213 downArray_[i])*random[i];214 }215 } else {216 numberFixedAlready++;217 }218 }184 const double * solution, 185 PseudoReducedCost * candidate, 186 const double * random) 187 { 188 const double * lower = solver>getColLower(); 189 const double * upper = solver>getColUpper(); 190 double integerTolerance = model_>getDblParam(CbcModel::CbcIntegerTolerance); 191 double primalTolerance; 192 solver>getDblParam(OsiPrimalTolerance, primalTolerance); 193 194 int numberIntegers = model_>numberIntegers(); 195 const int * integerVariable = model_>integerVariable(); 196 const double* reducedCost = solver>getReducedCost(); 197 // fix other integer variables that are at their bounds 198 int cnt = 0; 199 int numberFree = 0; 200 int numberFixedAlready = 0; 201 for (int i = 0; i < numberIntegers; i++) { 202 int iColumn = integerVariable[i]; 203 if (upper[iColumn] > lower[iColumn]) { 204 numberFree++; 205 double value = solution[iColumn]; 206 if (value  lower[iColumn] <= integerTolerance) { 207 candidate[cnt].var = iColumn; 208 candidate[cnt++].pseudoRedCost = CoinMax(1.0e2 * reducedCost[iColumn], 209 downArray_[i]) * random[i]; 210 } else if (upper[iColumn]  value <= integerTolerance) { 211 candidate[cnt].var = iColumn; 212 candidate[cnt++].pseudoRedCost = CoinMax(1.0e2 * reducedCost[iColumn], 213 downArray_[i]) * random[i]; 214 } 215 } else { 216 numberFixedAlready++; 217 } 218 } 219 219 #ifdef CLP_INVESTIGATE 220 printf("cutoff %g obj %g  %d free, %d fixed\n",221 model_>getCutoff(),solver>getObjValue(),numberFree,222 220 printf("cutoff %g obj %g  %d free, %d fixed\n", 221 model_>getCutoff(), solver>getObjValue(), numberFree, 222 numberFixedAlready); 223 223 #endif 224 return cnt;225 //return CbcHeuristicDive::fixOtherVariables(solver, solution,226 // candidate, random);227 } 224 return cnt; 225 //return CbcHeuristicDive::fixOtherVariables(solver, solution, 226 // candidate, random); 227 }
Note: See TracChangeset
for help on using the changeset viewer.