Changeset 259
- Timestamp:
- Feb 18, 2006 3:46:11 PM (15 years ago)
- Location:
- trunk
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/CbcCutGenerator.cpp
r249 r259 33 33 numberTimes_(0), 34 34 numberCuts_(0), 35 numberColumnCuts_(0), 35 36 numberCutsActive_(0) 36 37 { … … 50 51 numberTimes_(0), 51 52 numberCuts_(0), 53 numberColumnCuts_(0), 52 54 numberCutsActive_(0) 53 55 { … … 86 88 numberTimes_ = rhs.numberTimes_; 87 89 numberCuts_ = rhs.numberCuts_; 90 numberColumnCuts_ = rhs.numberColumnCuts_; 88 91 numberCutsActive_ = rhs.numberCutsActive_; 89 92 } … … 112 115 numberTimes_ = rhs.numberTimes_; 113 116 numberCuts_ = rhs.numberCuts_; 117 numberColumnCuts_ = rhs.numberColumnCuts_; 114 118 numberCutsActive_ = rhs.numberCutsActive_; 115 119 } … … 203 207 int numberColumns = solver->getNumCols(); 204 208 double primalTolerance = 1.0e-8; 209 #if 0 210 int numberChanged=0,ifCut=0; 211 CoinPackedVector lbs; 212 CoinPackedVector ubs; 205 213 for (j=0;j<numberColumns;j++) { 206 if (tightUpper[j]==tightLower[j]&& 207 upper[j]>lower[j]) { 208 // fix 209 solver->setColLower(j,tightLower[j]); 210 solver->setColUpper(j,tightUpper[j]); 211 if (tightLower[j]>solution[j]+primalTolerance|| 212 tightUpper[j]<solution[j]-primalTolerance) 213 returnCode=true; 214 if (solver->isInteger(j)) { 215 if (tightUpper[j]<upper[j]) { 216 numberChanged++; 217 assert (tightUpper[j]==floor(tightUpper[j]+0.5)); 218 ubs.insert(j,tightUpper[j]); 219 if (tightUpper[j]<solution[j]-primalTolerance) 220 ifCut=1; 221 } 222 if (tightLower[j]>lower[j]) { 223 numberChanged++; 224 assert (tightLower[j]==floor(tightLower[j]+0.5)); 225 lbs.insert(j,tightLower[j]); 226 if (tightLower[j]>solution[j]+primalTolerance) 227 ifCut=1; 228 } 229 } else { 230 if (tightUpper[j]==tightLower[j]&& 231 upper[j]>lower[j]) { 232 // fix 233 //solver->setColLower(j,tightLower[j]); 234 //solver->setColUpper(j,tightUpper[j]); 235 double value = tightUpper[j]; 236 numberChanged++; 237 if (value<upper[j]) 238 ubs.insert(j,value); 239 if (value>lower[j]) 240 lbs.insert(j,value); 241 } 214 242 } 215 243 } 216 //returnCode = !solver->basisIsAvailable(); 244 if (numberChanged) { 245 OsiColCut cc; 246 cc.setUbs(ubs); 247 cc.setLbs(lbs); 248 if (ifCut) { 249 cc.setEffectiveness(100.0); 250 } else { 251 cc.setEffectiveness(1.0e-5); 252 } 253 cs.insert(cc); 254 } 255 // need to resolve if some bounds changed 256 returnCode = !solver->basisIsAvailable(); 257 assert (!returnCode); 258 #else 259 for (j=0;j<numberColumns;j++) { 260 if (solver->isInteger(j)) { 261 if (tightUpper[j]<upper[j]) { 262 double nearest = floor(tightUpper[j]+0.5); 263 assert (fabs(tightUpper[j]-nearest)<1.0e-7); 264 solver->setColUpper(j,nearest); 265 if (nearest<solution[j]-primalTolerance) 266 returnCode=true; 267 } 268 if (tightLower[j]>lower[j]) { 269 double nearest = floor(tightLower[j]+0.5); 270 assert (fabs(tightLower[j]-nearest)<1.0e-7); 271 solver->setColLower(j,nearest); 272 if (nearest>solution[j]+primalTolerance) 273 returnCode=true; 274 } 275 } else { 276 if (tightUpper[j]==tightLower[j]&& 277 upper[j]>lower[j]) { 278 // fix 279 solver->setColLower(j,tightLower[j]); 280 solver->setColUpper(j,tightUpper[j]); 281 if (tightLower[j]>solution[j]+primalTolerance|| 282 tightUpper[j]<solution[j]-primalTolerance) 283 returnCode=true; 284 } 285 } 286 } 287 //if (!solver->basisIsAvailable()) 288 //returnCode=true; 289 #endif 217 290 } 218 291 if (timing_) -
trunk/CbcModel.cpp
r257 r259 3406 3406 numberNewCuts_(0), 3407 3407 sizeMiniTree_(0), 3408 searchStrategy_(-1), 3409 numberStrongIterations_(0), 3408 3410 resolveAfterTakeOffCuts_(true) 3409 3411 { … … 3521 3523 numberNewCuts_(0), 3522 3524 sizeMiniTree_(0), 3525 searchStrategy_(-1), 3526 numberStrongIterations_(0), 3523 3527 resolveAfterTakeOffCuts_(true) 3524 3528 { … … 3710 3714 numberNewCuts_(rhs.numberNewCuts_), 3711 3715 sizeMiniTree_(rhs.sizeMiniTree_), 3716 searchStrategy_(rhs.searchStrategy_), 3717 numberStrongIterations_(rhs.numberStrongIterations_), 3712 3718 resolveAfterTakeOffCuts_(rhs.resolveAfterTakeOffCuts_) 3713 3719 { … … 4011 4017 resolveAfterTakeOffCuts_=rhs.resolveAfterTakeOffCuts_; 4012 4018 sizeMiniTree_ = rhs.sizeMiniTree_; 4019 searchStrategy_ = rhs.searchStrategy_; 4020 numberStrongIterations_ = rhs.numberStrongIterations_; 4013 4021 lastHeuristic_ = NULL; 4014 4022 numberCutGenerators_ = rhs.numberCutGenerators_; … … 4243 4251 numberOldActiveCuts_=0; 4244 4252 numberNewCuts_=0; 4253 searchStrategy_=-1; 4254 numberStrongIterations_=0; 4245 4255 // Parameters which need to be reset 4246 4256 dblParam_[CbcCutoffIncrement] = 1e-5; … … 6226 6236 return this; 6227 6237 } 6238 } 6239 // Fill in useful estimates 6240 void 6241 CbcModel::pseudoShadow(double * down, double * up) 6242 { 6243 // Column copy of matrix 6244 const double * element = solver_->getMatrixByCol()->getElements(); 6245 const int * row = solver_->getMatrixByCol()->getIndices(); 6246 const CoinBigIndex * columnStart = solver_->getMatrixByCol()->getVectorStarts(); 6247 const int * columnLength = solver_->getMatrixByCol()->getVectorLengths(); 6248 const double *objective = solver_->getObjCoefficients() ; 6249 int numberColumns = solver_->getNumCols() ; 6250 double direction = solver_->getObjSense(); 6251 int iColumn; 6252 const double * dual = cbcRowPrice_; 6253 down = new double[numberColumns]; 6254 up = new double[numberColumns]; 6255 double upSum=1.0e-20; 6256 double downSum = 1.0e-20; 6257 int numberIntegers=0; 6258 for (iColumn=0;iColumn<numberColumns;iColumn++) { 6259 CoinBigIndex start = columnStart[iColumn]; 6260 CoinBigIndex end = start + columnLength[iColumn]; 6261 double upValue = 0.0; 6262 double downValue = 0.0; 6263 double value = direction*objective[iColumn]; 6264 if (value) { 6265 if (value>0.0) 6266 upValue += value; 6267 else 6268 downValue -= value; 6269 } 6270 for (CoinBigIndex j=start;j<end;j++) { 6271 int iRow = row[j]; 6272 value = -dual[iRow]; 6273 if (value) { 6274 value *= element[j]; 6275 if (value>0.0) 6276 upValue += value; 6277 else 6278 downValue -= value; 6279 } 6280 } 6281 // use dj if bigger 6282 double dj = cbcReducedCost_[iColumn]; 6283 upValue = CoinMax(upValue,dj); 6284 downValue = CoinMax(downValue,-dj); 6285 up[iColumn]=upValue; 6286 down[iColumn]=downValue; 6287 if (solver_->isInteger(iColumn)) { 6288 if (!numberNodes_) 6289 printf("%d - dj %g up %g down %g cost %g\n", 6290 iColumn,dj,upValue,downValue,objective[iColumn]); 6291 upSum += upValue; 6292 downSum += downValue; 6293 numberIntegers++; 6294 } 6295 } 6296 if (numberIntegers) { 6297 double smallDown = 0.01*(downSum/((double) numberIntegers)); 6298 double smallUp = 0.01*(upSum/((double) numberIntegers)); 6299 for (int i=0;i<numberObjects_;i++) { 6300 CbcSimpleIntegerDynamicPseudoCost * obj1 = 6301 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[i]) ; 6302 if (obj1) { 6303 iColumn = obj1->columnNumber(); 6304 double upPseudoCost = obj1->upDynamicPseudoCost(); 6305 double saveUp = upPseudoCost; 6306 upPseudoCost = CoinMax(upPseudoCost,smallUp); 6307 upPseudoCost = CoinMax(upPseudoCost,up[iColumn]); 6308 upPseudoCost = CoinMax(upPseudoCost,0.1*down[iColumn]); 6309 obj1->setUpDynamicPseudoCost(upPseudoCost); 6310 if (upPseudoCost>saveUp&&!numberNodes_) 6311 printf("For %d up went from %g to %g\n", 6312 iColumn,saveUp,upPseudoCost); 6313 double downPseudoCost = obj1->downDynamicPseudoCost(); 6314 double saveDown = downPseudoCost; 6315 downPseudoCost = CoinMax(downPseudoCost,smallDown); 6316 downPseudoCost = CoinMax(downPseudoCost,down[iColumn]); 6317 downPseudoCost = CoinMax(downPseudoCost,0.1*down[iColumn]); 6318 obj1->setDownDynamicPseudoCost(downPseudoCost); 6319 if (downPseudoCost>saveDown&&!numberNodes_) 6320 printf("For %d down went from %g to %g\n", 6321 iColumn,saveDown,downPseudoCost); 6322 } 6323 } 6324 } 6325 delete [] down; 6326 delete [] up; 6228 6327 } 6229 6328 -
trunk/CbcNode.cpp
r231 r259 18 18 #include "CbcModel.hpp" 19 19 #include "CbcNode.hpp" 20 #include "CbcStatistics.hpp" 20 21 #include "CbcBranchActual.hpp" 21 22 #include "CbcBranchDynamic.hpp" … … 883 884 if (model->hotstartSolution()) 884 885 numberStrong=0; 886 int numberStrongDone=0; 887 int numberUnfinished=0; 888 int numberStrongInfeasible=0; 889 int numberStrongIterations=0; 885 890 int saveNumberStrong=numberStrong; 886 891 int numberObjects = model->numberObjects(); … … 917 922 estimatedDegradation=0.0; 918 923 //int numberIntegerInfeasibilities=0; // without odd ones 924 numberStrongDone=0; 925 numberUnfinished=0; 926 numberStrongInfeasible=0; 927 numberStrongIterations=0; 919 928 920 929 // We may go round this loop twice (only if we think we have solution) … … 926 935 // numberIntegerInfeasibilities, 927 936 // numberObjectInfeasibilities); 928 // If forcePriority > 0 then we want best solution929 937 const double * hotstartSolution = model->hotstartSolution(); 930 938 const int * hotstartPriorities = model->hotstartPriorities(); … … 1079 1087 } 1080 1088 } 1081 if (roundAgain ) {1089 if (roundAgain&&saveNumberStrong) { 1082 1090 // restore basis 1083 1091 solver->setWarmStart(ws); … … 1348 1356 if (feasible) { 1349 1357 solver->solveFromHotStart() ; 1358 numberStrongDone++; 1359 numberStrongIterations += solver->getIterationCount(); 1350 1360 /* 1351 1361 We now have an estimate of objective degradation that we can use for strong … … 1373 1383 iStatus = outputStuff[2*i]; 1374 1384 choice[i].numItersDown = outputStuff[2*numberStrong+2*i]; 1385 numberStrongDone++; 1386 numberStrongIterations += choice[i].numItersDown; 1375 1387 newObjectiveValue = objectiveValue+newUpper[i]; 1376 1388 solver->setColSolution(outputSolution[2*i]); … … 1381 1393 if (newObjectiveValue>=model->getCutoff()) { 1382 1394 objectiveChange = 1.0e100; // say infeasible 1395 numberStrongInfeasible++; 1383 1396 } else { 1384 1397 // See if integer solution … … 1391 1404 model->setLastHeuristic(NULL); 1392 1405 model->incrementUsed(solver->getColSolution()); 1393 if (newObjectiveValue >= model->getCutoff()) // *new* cutoff1406 if (newObjectiveValue >= model->getCutoff()) { // *new* cutoff 1394 1407 objectiveChange = 1.0e100 ; 1408 numberStrongInfeasible++; 1409 } 1395 1410 } 1396 1411 } 1397 1412 } else if (iStatus==1) { 1398 1413 objectiveChange = 1.0e100 ; 1414 numberStrongInfeasible++; 1399 1415 } else { 1400 1416 // Can't say much as we did not finish 1401 1417 choice[i].finishedDown = false ; 1418 numberUnfinished++; 1402 1419 } 1403 1420 choice[i].downMovement = objectiveChange ; … … 1440 1457 if (feasible) { 1441 1458 solver->solveFromHotStart() ; 1459 numberStrongDone++; 1460 numberStrongIterations += solver->getIterationCount(); 1442 1461 /* 1443 1462 We now have an estimate of objective degradation that we can use for strong … … 1465 1484 iStatus = outputStuff[2*i+1]; 1466 1485 choice[i].numItersUp = outputStuff[2*numberStrong+2*i+1]; 1486 numberStrongDone++; 1487 numberStrongIterations += choice[i].numItersUp; 1467 1488 newObjectiveValue = objectiveValue+newLower[i]; 1468 1489 solver->setColSolution(outputSolution[2*i+1]); … … 1473 1494 if (newObjectiveValue>=model->getCutoff()) { 1474 1495 objectiveChange = 1.0e100; // say infeasible 1496 numberStrongInfeasible++; 1475 1497 } else { 1476 1498 // See if integer solution … … 1483 1505 model->setLastHeuristic(NULL); 1484 1506 model->incrementUsed(solver->getColSolution()); 1485 if (newObjectiveValue >= model->getCutoff()) // *new* cutoff1507 if (newObjectiveValue >= model->getCutoff()) { // *new* cutoff 1486 1508 objectiveChange = 1.0e100 ; 1509 numberStrongInfeasible++; 1510 } 1487 1511 } 1488 1512 } 1489 1513 } else if (iStatus==1) { 1490 1514 objectiveChange = 1.0e100 ; 1515 numberStrongInfeasible++; 1491 1516 } else { 1492 1517 // Can't say much as we did not finish 1493 1518 choice[i].finishedUp = false ; 1519 numberUnfinished++; 1494 1520 } 1495 1521 choice[i].upMovement = objectiveChange ; … … 1654 1680 } 1655 1681 delete ws; 1682 int numberNodes = model->getNodeCount(); 1683 // update number of strong iterations 1684 model->setNumberStrongIterations(model->numberStrongIterations()+numberStrongIterations); 1656 1685 1657 1686 /* … … 1665 1694 if (anyAction>=0) { 1666 1695 1667 int numberNodes = model->getNodeCount();1668 1696 // get average cost per iteration and assume stopped ones 1669 1697 // would stop after 50% more iterations at average cost??? !!! ??? … … 1807 1835 //assert(objectiveValue_ == solver->getObjSense()*solver->getObjValue()); 1808 1836 double cutoff =model->getCutoff(); 1837 double distanceToCutoff=cutoff-objectiveValue_; 1809 1838 const double * lower = solver->getColLower(); 1810 1839 const double * upper = solver->getColUpper(); … … 1831 1860 if (model->hotstartSolution()) 1832 1861 return -3; 1862 #define RANGING 1863 #ifdef RANGING 1833 1864 // Pass number 1834 1865 int kPass=0; 1866 int numberRows = solver->getNumRows(); 1867 #endif 1835 1868 int numberColumns = model->getNumCols(); 1836 int numberRows = solver->getNumRows();1837 1869 double * saveUpper = new double[numberColumns]; 1838 1870 double * saveLower = new double[numberColumns]; … … 1851 1883 decision = new CbcBranchDynamicDecision(); 1852 1884 int numberMini=0; 1853 int xStrong=0;1854 int xIters=0;1855 1885 int xPen=0; 1856 1886 int xMark=0; … … 1888 1918 osiclp->setSpecialOptions(saveClpOptions|1024); 1889 1919 } 1920 int saveSearchStrategy2 = model->searchStrategy(); 1921 if (saveSearchStrategy2<999) { 1922 // Get average up and down costs 1923 double averageUp=0.0; 1924 double averageDown=0.0; 1925 { 1926 int numberUp=0; 1927 int numberDown=0; 1928 int i; 1929 for ( i=0;i<numberObjects;i++) { 1930 CbcObject * object = model->modifiableObject(i); 1931 CbcSimpleIntegerDynamicPseudoCost * dynamicObject = 1932 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ; 1933 assert(dynamicObject); 1934 if (dynamicObject->numberTimesUp()) { 1935 numberUp++; 1936 averageUp += dynamicObject->upDynamicPseudoCost(); 1937 } 1938 if (dynamicObject->numberTimesDown()) { 1939 numberDown++; 1940 averageDown += dynamicObject->downDynamicPseudoCost(); 1941 } 1942 } 1943 if (numberUp) 1944 averageUp /= (double) numberUp; 1945 else 1946 averageUp=1.0; 1947 if (numberDown) 1948 averageDown /= (double) numberDown; 1949 else 1950 averageDown=1.0; 1951 for ( i=0;i<numberObjects;i++) { 1952 CbcObject * object = model->modifiableObject(i); 1953 CbcSimpleIntegerDynamicPseudoCost * dynamicObject = 1954 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ; 1955 assert(dynamicObject); 1956 if (!dynamicObject->numberTimesUp()) 1957 dynamicObject->setUpDynamicPseudoCost(averageUp); 1958 if (!dynamicObject->numberTimesDown()) 1959 dynamicObject->setDownDynamicPseudoCost(averageDown); 1960 } 1961 } 1962 } else if (saveSearchStrategy2<1999) { 1963 // pseudo shadow prices 1964 model->pseudoShadow(NULL,NULL); 1965 } else if (saveSearchStrategy2<2999) { 1966 // leave old ones 1967 } else if (saveSearchStrategy2<3999) { 1968 // pseudo shadow prices at root 1969 if (!numberNodes) 1970 model->pseudoShadow(NULL,NULL); 1971 } else { 1972 abort(); 1973 } 1974 if (saveSearchStrategy2>=0) 1975 saveSearchStrategy2 = saveSearchStrategy2 % 1000; 1976 if (saveSearchStrategy2==999) 1977 saveSearchStrategy2=-1; 1978 int px[4]={-1,-1,-1,-1}; 1979 int saveSearchStrategy = saveSearchStrategy2<99 ? saveSearchStrategy2 : saveSearchStrategy2-100; 1980 bool newWay = saveSearchStrategy2>98; 1981 int numberNotTrusted=0; 1982 int numberStrongDone; 1983 int numberUnfinished; 1984 int numberStrongInfeasible; 1985 int numberStrongIterations; 1890 1986 while(!finished) { 1891 1987 finished=true; … … 1896 1992 int numberIntegerInfeasibilities=0; // without odd ones 1897 1993 int numberToDo=0; 1898 double averageDown=0.0;1899 int numberDown=0;1900 double averageUp=0.0;1901 int numberUp=0;1902 1994 int iBestNot=-1; 1903 1995 int iBestGot=-1; 1904 1996 double best=0.0; 1905 int numberNotTrusted=0; 1997 numberNotTrusted=0; 1998 numberStrongDone=0; 1999 numberUnfinished=0; 2000 numberStrongInfeasible=0; 2001 numberStrongIterations=0; 1906 2002 int * which = objectMark+numberObjects+1; 1907 2003 int neededPenalties; … … 1931 2027 numberToDo=0; 1932 2028 neededPenalties=0; 1933 averageDown=0.0;1934 numberDown=0;1935 averageUp=0.0;1936 numberUp=0;1937 2029 iBestNot=-1; 1938 2030 double bestNot=0.0; … … 1948 2040 double infeasibility = object->infeasibility(preferredWay); 1949 2041 int priorityLevel = object->priority(); 2042 #define ZERO_ONE 0 2043 #define ZERO_FAKE 1.0e20; 2044 #if ZERO_ONE==1 2045 // branch on 0-1 first (temp) 2046 if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0) 2047 priorityLevel--; 2048 #endif 2049 #if ZERO_ONE==2 2050 if (fabs(saveSolution[dynamicObject->columnNumber()])<1.0) 2051 infeasibility *= ZERO_FAKE; 2052 #endif 1950 2053 if (infeasibility) { 2054 int iColumn = dynamicObject->columnNumber(); 2055 double gap = saveUpper[iColumn]-saveLower[iColumn]; 2056 // Give precedence to ones with gap of 1.0 2057 assert(gap>0.0); 2058 infeasibility /= CoinMin(gap,100.0); 1951 2059 if (!depth_&&false) { 1952 2060 // try closest to 0.5 1953 int iColumn = dynamicObject->columnNumber();1954 2061 double part =saveSolution[iColumn]-floor(saveSolution[iColumn]); 1955 2062 infeasibility = fabs(0.5-part); … … 1957 2064 bool gotDown=false; 1958 2065 int numberThisDown = dynamicObject->numberTimesDown(); 1959 if (numberThisDown) { 1960 averageDown += dynamicObject->downDynamicPseudoCost(); 1961 numberDown++; 1962 if (numberThisDown>=numberBeforeTrust) 1963 gotDown=true; 1964 } 2066 if (numberThisDown>=numberBeforeTrust) 2067 gotDown=true; 1965 2068 bool gotUp=false; 1966 2069 int numberThisUp = dynamicObject->numberTimesUp(); 1967 if (numberThisUp) { 1968 averageUp += dynamicObject->upDynamicPseudoCost(); 1969 numberUp++; 1970 if (numberThisUp>=numberBeforeTrust) 1971 gotUp=true; 1972 } 2070 if (numberThisUp>=numberBeforeTrust) 2071 gotUp=true; 1973 2072 if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0) 1974 2073 printf("%d down %d %g up %d %g - infeas %g\n", … … 2004 2103 int iColumn = dynamicObject->columnNumber(); 2005 2104 double part =saveSolution[iColumn]-floor(saveSolution[iColumn]); 2006 sort[numberToDo]=-infeasibility; 2105 sort[numberToDo]=-10.0*infeasibility; 2106 if (!(numberThisUp+numberThisDown)) 2107 sort[numberToDo] *= 100.0; // make even more likely 2007 2108 if (1.0-fabs(part-0.5)>bestNot) { 2008 2109 iBestNot=numberToDo; … … 2085 2186 //bool skipAll = (numberBeforeTrust>20&&numberNodes>20000&&numberNotTrusted==0); 2086 2187 bool skipAll = numberNotTrusted==0; 2188 bool doneHotStart=false; 2189 #ifndef CBC_WEAK_STRONG 2087 2190 if ((numberNodes%20)==0||(model->specialOptions()&8)!=0) 2088 2191 skipAll=false; 2192 #endif 2193 int searchStrategy = saveSearchStrategy>=0 ? (saveSearchStrategy%10) : -1; 2194 if (!newWay) { 2195 // 10 up always use %10, 20 up as 10 and allow penalties 2196 // But adjust depending on ratio of iterations 2197 if (searchStrategy>0&&saveSearchStrategy<10) { 2198 if (numberBeforeTrust>=5&&numberBeforeTrust<=10) { 2199 if (searchStrategy!=2) { 2200 int numberIterations = model->getIterationCount(); 2201 int numberStrongIterations = model->numberStrongIterations(); 2202 if (numberStrongIterations>numberIterations+10000) { 2203 searchStrategy=2; 2204 //skipAll=true; 2205 } else if (numberStrongIterations*4+1000<numberIterations||depth_<5) { 2206 searchStrategy=3; 2207 skipAll=false; 2208 } 2209 } else { 2210 skipAll=true; 2211 } 2212 } 2213 } 2214 } else { 2215 // But adjust depending on ratio of iterations 2216 if (saveSearchStrategy<0) { 2217 // unset 2218 if ((numberNodes%20)==0||(model->specialOptions()&8)!=0) { 2219 // Do numberStrong 2220 searchStrategy=3; 2221 } else if (depth_<5) { 2222 // Do numberStrong 2223 searchStrategy=2; 2224 } else { 2225 int numberIterations = model->getIterationCount(); 2226 int numberStrongIterations = model->numberStrongIterations(); 2227 int numberRows = solver->getNumRows(); 2228 if (numberStrongIterations>numberIterations+CoinMin(10000,10*numberRows)) { 2229 // off 2230 searchStrategy=0; 2231 } else if (numberStrongIterations*4+1000<numberIterations) { 2232 // Do numberStrong if not trusted 2233 searchStrategy=2; 2234 } else { 2235 searchStrategy=1; 2236 } 2237 } 2238 } 2239 if (searchStrategy<3&&(!numberNotTrusted||!searchStrategy)) 2240 skipAll=true; 2241 else 2242 skipAll=false; 2243 } 2089 2244 // worth trying if too many times 2090 2245 // Save basis … … 2092 2247 // save limit 2093 2248 int saveLimit=0; 2249 solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit); 2094 2250 if (!skipAll) { 2095 2251 ws = solver->getWarmStart(); 2096 solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit); 2097 if (!saveStateOfSearch&&saveLimit<100) 2098 solver->setIntParam(OsiMaxNumIterationHotStart,100); 2252 int limit=100; 2253 #if 0 2254 int averageBranchIterations = model->getIterationCount()/(model->getNodeCount()+1); 2255 if (numberNodes) 2256 limit = CoinMin(CoinMax(limit,2*averageBranchIterations),500); 2257 else 2258 limit = 500; 2259 #endif 2260 if ((!saveStateOfSearch||searchStrategy>3)&&saveLimit<limit&&saveLimit==100) 2261 solver->setIntParam(OsiMaxNumIterationHotStart,limit); 2099 2262 } 2100 2263 // Say which one will be best … … 2126 2289 solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ; 2127 2290 int iDo; 2128 #define RANGING2129 2291 #ifdef RANGING 2130 if ( skipAll&&numberBeforeTrust)2292 if ((skipAll&&numberBeforeTrust&&saveSearchStrategy<20)||saveSearchStrategy<10) 2131 2293 numberPenalties=0; 2132 2294 { … … 2134 2296 double needed = neededPenalties; 2135 2297 needed *= numberRows; 2136 if (needed>1.0e6 ) {2298 if (needed>1.0e6&&numberNodes&&saveSearchStrategy<20) { 2137 2299 numberPenalties=0; 2138 2300 neededPenalties=0; … … 2154 2316 solver->markHotStart(); 2155 2317 } 2318 doneHotStart=true; 2156 2319 xMark++; 2157 2320 kPass++; … … 2159 2322 const double * downCost=osiclp->upRange(); 2160 2323 const double * upCost=osiclp->downRange(); 2161 //printf("numberTodo %d needed %d numberpenalties %d\n",numberToDo,needed ,numberPenalties);2324 //printf("numberTodo %d needed %d numberpenalties %d\n",numberToDo,neededPenalties,numberPenalties); 2162 2325 double invTrust = 1.0/((double) numberBeforeTrust); 2163 2326 for (int i=0;i<neededPenalties;i++) { … … 2189 2352 } 2190 2353 sort[j] = - CoinMin(downEstimate[iObject],upEstimate[iObject]); 2191 if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0) 2354 #ifdef CBC_WEAK_STRONG 2355 sort[j] -= 1.0e10; // make more likely to be chosen 2356 #endif 2357 //if ((numberNodes%PRINT_STUFF)==0&&PRINT_STUFF>0) 2358 if (!numberNodes) 2192 2359 printf("%d pen down ps %g -> %g up ps %g -> %g\n", 2193 2360 iObject,downCost[i],downPenalty,upCost[i],upPenalty); … … 2197 2364 // Mark hot start 2198 2365 solver->markHotStart(); 2366 doneHotStart=true; 2199 2367 xMark++; 2200 2368 //if (solver->isProvenPrimalInfeasible()) … … 2206 2374 } 2207 2375 #else 2208 // Mark hot start 2209 solver->markHotStart(); 2210 xMark++; 2376 if (!skipAll) { 2377 // Mark hot start 2378 doneHotStart=true; 2379 solver->markHotStart(); 2380 xMark++; 2381 } 2211 2382 // make sure best will be first 2212 2383 if (iBestGot>=0) … … 2232 2403 //printf("todo %d, strong %d\n",numberToDo,numberStrong); 2233 2404 int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2; 2234 int numberTest2 = CoinMax(2*numberStrong,10)+1000000; 2405 int numberTest2 = 2*numberStrong; 2406 if (!newWay) { 2407 if (searchStrategy==3) { 2408 // Previously decided we need strong 2409 doQuickly=false; 2410 numberTest = numberStrong; 2411 //numberTest2 = 1000000; 2412 } 2413 if (searchStrategy<0||searchStrategy==1) 2414 //numberTest2 = 1000000; 2235 2415 #if 0 2236 2416 if (numberBeforeTrust>20&&(numberNodes>20000||(numberNodes>200&&numberNotTrusted==0))) { … … 2242 2422 #else 2243 2423 // Try nearly always off 2244 if ((numberNodes%20)!=0) { 2245 numberTest=0; 2424 if (searchStrategy<2) { 2425 if ((numberNodes%20)!=0) { 2426 if ((model->specialOptions()&8)==0) { 2427 numberTest=0; 2428 doQuickly=true; 2429 } 2430 } else { 2431 doQuickly=false; 2432 numberTest=2*numberStrong; 2433 } 2434 } else if (searchStrategy!=3) { 2246 2435 doQuickly=true; 2247 } else { 2248 doQuickly=true; 2249 numberTest=2*numberStrong; 2436 numberTest=numberStrong; 2250 2437 } 2251 2438 #endif 2252 2439 if (depth_<10&&numberStrong) { 2253 doQuickly=false; 2254 if (depth_<7) 2255 numberStrong *=3; 2256 if (!depth_) 2257 numberStrong=CoinMin(6*numberStrong,numberToDo); 2258 numberTest=numberStrong; 2440 if (searchStrategy!=2) { 2441 doQuickly=false; 2442 if (depth_<7) 2443 numberStrong *=3; 2444 if (!depth_) 2445 numberStrong=CoinMin(6*numberStrong,numberToDo); 2446 numberTest=numberStrong; 2447 } 2259 2448 model->setStateOfSearch(2); // use min min 2260 2449 } … … 2264 2453 // if too many and big then just do 10 its 2265 2454 if (!skipAll&&saveStateOfSearch) { 2266 //if (numberNotTrusted>3*numberStrong&&numberRows>250&&numberColumns>1000 )2455 //if (numberNotTrusted>3*numberStrong&&numberRows>250&&numberColumns>1000&&saveLimit==100) 2267 2456 // off solver->setIntParam(OsiMaxNumIterationHotStart,10); 2268 2457 } 2269 double distanceToCutoff=model->getCutoff()-objectiveValue_;2270 2458 // make negative for test 2271 2459 distanceToCutoff = - distanceToCutoff; … … 2287 2475 numberTest = CoinMax(numberTest,5); 2288 2476 } 2477 } else { 2478 int numberTest=numberNotTrusted>0 ? numberStrong : (numberStrong+1)/2; 2479 int numberTest2 = 2*numberStrong; 2480 if (searchStrategy>=3) { 2481 // Previously decided we need strong 2482 doQuickly=false; 2483 if (depth_<7) 2484 numberStrong *=3; 2485 if (!depth_) 2486 numberStrong=CoinMin(6*numberStrong,numberToDo); 2487 numberTest = numberStrong; 2488 numberTest2 *= 2; 2489 } else if (searchStrategy==2||(searchStrategy==1&&depth_<6)) { 2490 numberStrong *=2; 2491 if (!depth_) 2492 numberStrong=CoinMin(2*numberStrong,numberToDo); 2493 numberTest = numberStrong; 2494 } else if (searchStrategy==1&&numberNotTrusted) { 2495 numberTest = numberStrong; 2496 } else { 2497 numberTest=0; 2498 skipAll=true; 2499 } 2500 distanceToCutoff=model->getCutoff()-objectiveValue_; 2501 // make negative for test 2502 distanceToCutoff = - distanceToCutoff; 2503 if (numberObjects>-100) { 2504 // larger 2505 distanceToCutoff *= 100.0; 2506 } 2507 distanceToCutoff = -COIN_DBL_MAX; 2508 if (skipAll) { 2509 numberTest=0; 2510 doQuickly=true; 2511 } 2512 } 2513 px[0]=numberTest; 2514 px[1]=numberTest2; 2515 px[2]= doQuickly ? 1 : -1; 2516 px[3]=numberStrong; 2517 //printf("skipAll %c doQuickly %c numberTest %d numberTest2 %d numberNot %d\n", 2518 // skipAll ? 'Y' : 'N',doQuickly ? 'Y' : 'N',numberTest,numberTest2,numberNotTrusted); 2289 2519 // See if we want mini tree 2290 2520 bool wantMiniTree=false; … … 2313 2543 // see if can skip strong branching 2314 2544 int canSkip = choice.possibleBranch->fillStrongInfo(choice); 2315 if (!doQuickly||numberTest>0) 2545 if (!newWay) { 2546 if (!doQuickly||(numberTest>0&&searchStrategy!=2)) 2316 2547 canSkip=0; 2548 } else { 2549 if (skipAll) 2550 canSkip=1; 2551 else if (numberTest>0&&searchStrategy>=3) 2552 canSkip=0; 2553 } 2317 2554 if (!numberBeforeTrust) { 2318 2555 canSkip=1; … … 2320 2557 if (sort[iDo]<distanceToCutoff) 2321 2558 canSkip=0; 2322 if ( numberTest2<=0&&sort[iDo]>distanceToCutoff)2559 if (((numberTest2<=0&&numberTest<=0)||skipAll)&&sort[iDo]>distanceToCutoff) { 2323 2560 canSkip=1; // always skip 2561 if (iDo>20) 2562 break; // give up anyway 2563 } 2324 2564 if (model->messageHandler()->logLevel()>3&&numberBeforeTrust) 2325 2565 dynamicObject->print(1,choice.possibleBranch->value()); 2326 2566 // was if (!canSkip) 2567 if (newWay) 2568 numberTest2--; 2327 2569 if (!canSkip) { 2328 2570 numberTest--; 2571 if (!newWay) 2329 2572 numberTest2--; 2330 2573 // just do a few 2331 if (canSkip)2332 2574 //if (canSkip) 2575 //solver->setIntParam(OsiMaxNumIterationHotStart,10); 2333 2576 double objectiveChange ; 2334 2577 double newObjectiveValue=1.0e100; … … 2346 2589 choice.possibleBranch->branch() ; 2347 2590 solver->solveFromHotStart() ; 2348 xStrong++;2349 xIters += solver->getIterationCount();2591 numberStrongDone++; 2592 numberStrongIterations += solver->getIterationCount(); 2350 2593 /* 2351 2594 We now have an estimate of objective degradation that we can use for strong … … 2370 2613 if (newObjectiveValue>=cutoff) { 2371 2614 objectiveChange = 1.0e100; // say infeasible 2615 numberStrongInfeasible++; 2372 2616 } else { 2373 2617 // See if integer solution … … 2381 2625 model->incrementUsed(solver->getColSolution()); 2382 2626 cutoff =model->getCutoff(); 2383 if (newObjectiveValue >= cutoff) // *new* cutoff2627 if (newObjectiveValue >= cutoff) { // *new* cutoff 2384 2628 objectiveChange = 1.0e100 ; 2629 numberStrongInfeasible++; 2630 } 2385 2631 } 2386 2632 } 2387 2633 } else if (iStatus==1) { 2388 2634 objectiveChange = 1.0e100 ; 2635 numberStrongInfeasible++; 2389 2636 } else { 2390 2637 // Can't say much as we did not finish 2391 2638 choice.finishedDown = false ; 2639 numberUnfinished++; 2392 2640 } 2393 2641 choice.downMovement = objectiveChange ; … … 2409 2657 choice.possibleBranch->branch(); 2410 2658 solver->solveFromHotStart() ; 2411 xStrong++;2412 xIters += solver->getIterationCount();2659 numberStrongDone++; 2660 numberStrongIterations += solver->getIterationCount(); 2413 2661 /* 2414 2662 We now have an estimate of objective degradation that we can use for strong … … 2433 2681 if (newObjectiveValue>=cutoff) { 2434 2682 objectiveChange = 1.0e100; // say infeasible 2683 numberStrongInfeasible++; 2435 2684 } else { 2436 2685 // See if integer solution … … 2444 2693 model->incrementUsed(solver->getColSolution()); 2445 2694 cutoff =model->getCutoff(); 2446 if (newObjectiveValue >= cutoff) // *new* cutoff2695 if (newObjectiveValue >= cutoff) { // *new* cutoff 2447 2696 objectiveChange = 1.0e100 ; 2697 numberStrongInfeasible++; 2698 } 2448 2699 } 2449 2700 } 2450 2701 } else if (iStatus==1) { 2451 2702 objectiveChange = 1.0e100 ; 2703 numberStrongInfeasible++; 2452 2704 } else { 2453 2705 // Can't say much as we did not finish 2454 2706 choice.finishedUp = false ; 2707 numberUnfinished++; 2455 2708 } 2456 2709 choice.upMovement = objectiveChange ; … … 2488 2741 choice.upMovement = CoinMax(0.0,choice.upMovement); 2489 2742 choice.downMovement = CoinMax(0.0,choice.downMovement); 2743 #if ZERO_ONE==2 2744 // branch on 0-1 first (temp) 2745 if (fabs(choice.possibleBranch->value())<1.0) { 2746 choice.upMovement *= ZERO_FAKE; 2747 choice.downMovement *= ZERO_FAKE; 2748 } 2749 #endif 2490 2750 // feasible - see which best 2491 2751 if (!canSkip) { 2752 if (iColumn==-46) { 2753 printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject], 2754 upEstimate[iObject]); 2755 printf("downMove %g upMove %g value %g current pseudo %g %g\n", 2756 choice.downMovement,choice.upMovement,choice.possibleBranch->value(), 2757 dynamicObject->downDynamicPseudoCost(),dynamicObject->upDynamicPseudoCost()); 2758 } 2492 2759 if (model->messageHandler()->logLevel()>3) 2493 2760 printf("sort %g downest %g upest %g ",sort[iDo],downEstimate[iObject], … … 2505 2772 decision->setBestCriterion(-1.0); 2506 2773 double bestCriterion = -1.0; 2774 double gap = saveUpper[iColumn]-saveLower[iColumn]; 2775 // Give precedence to ones with gap of 1.0 2776 assert(gap>0.0); 2777 double factor = changeFactor/CoinMin(gap,100.0); 2507 2778 int betterWay = decision->betterBranch(choice.possibleBranch, 2508 2779 branch_, 2509 choice.upMovement* changeFactor,2780 choice.upMovement*factor, 2510 2781 choice.numIntInfeasUp , 2511 choice.downMovement* changeFactor,2782 choice.downMovement*factor, 2512 2783 choice.numIntInfeasDown ); 2513 2784 if (wantMiniTree) { … … 2578 2849 saveLower[iColumn]=value; 2579 2850 solver->setColLower(iColumn,value); 2851 assert(doneHotStart); 2852 solver->unmarkHotStart(); 2853 solver->markHotStart(); 2580 2854 #endif 2581 2855 } … … 2602 2876 saveUpper[iColumn]=value; 2603 2877 solver->setColUpper(iColumn,value); 2878 assert(doneHotStart); 2879 solver->unmarkHotStart(); 2880 solver->markHotStart(); 2604 2881 #endif 2605 2882 } … … 2648 2925 iDo,whichChoice,numberToDo); 2649 2926 } 2650 if ( !skipAll) {2927 if (doneHotStart) { 2651 2928 // Delete the snapshot 2652 2929 solver->unmarkHotStart(); 2653 2930 // back to normal 2654 2931 solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ; 2655 solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);2656 2932 // restore basis 2657 2933 solver->setWarmStart(ws); 2658 2934 } 2935 solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit); 2659 2936 // Unless infeasible we will carry on 2660 2937 // But we could fix anyway … … 2726 3003 } 2727 3004 if (model->messageHandler()->logLevel()>2) 2728 printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d\n", 2729 xStrong,xIters,xPen,xMark,numberToFix,anyAction); 3005 printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d nnott %d nt %d, %d dq %s ns %d\n", 3006 numberStrongDone,numberStrongIterations,xPen,xMark, 3007 numberToFix,anyAction,numberNotTrusted,px[0],px[1],px[2]>0 ? "y" : "n",px[3]); 3008 // update number of strong iterations 3009 model->setNumberStrongIterations(model->numberStrongIterations()+numberStrongIterations); 3010 if (!newWay) { 3011 if (((model->searchStrategy()+1)%1000)==0) { 3012 if (solver->messageHandler()->logLevel()>1) 3013 printf("%d strong, %d iters, %d inf, %d not finished, %d not trusted\n", 3014 numberStrongDone,numberStrongIterations,numberStrongInfeasible,numberUnfinished, 3015 numberNotTrusted); 3016 // decide what to do 3017 int strategy=1; 3018 if (numberUnfinished*4>numberStrongDone&&numberStrongInfeasible*10<numberStrongDone) { 3019 strategy=2; 3020 if (model->logLevel()>1) 3021 printf("going to strategy 2\n"); 3022 } 3023 if (numberNodes) 3024 strategy=1; // should only happen after hot start 3025 model->setSearchStrategy(strategy); 3026 } 3027 } 2730 3028 //if (numberToFix&&depth_<5) 2731 3029 //printf("%d fixed by strong at depth %d\n",numberToFix,depth_); -
trunk/Test/Makefile.solve
r246 r259 55 55 ifneq (,$(filter COIN_HAS_OSICLP, $(Define))) 56 56 # add in USE 57 CXXFLAGS += $(addprefix -D,COIN_USE_CLP)57 #CXXFLAGS += $(addprefix -D,COIN_USE_CLP) 58 58 else 59 59 $(error COIN_HAS_CLP is not defined in Makefiles/Makefile.location. Probably the line 'CoinLibsDefined += COIN_libClp' is commented out.) -
trunk/include/CbcCutGenerator.hpp
r238 r259 183 183 inline int numberTimesEntered() const 184 184 { return numberTimes_;}; 185 void setNumberTimesEntered(int value)185 inline void setNumberTimesEntered(int value) 186 186 { numberTimes_ = value;}; 187 void incrementNumberTimesEntered(int value=1)187 inline void incrementNumberTimesEntered(int value=1) 188 188 { numberTimes_ += value;}; 189 189 /// Total number of cuts added 190 190 inline int numberCutsInTotal() const 191 191 { return numberCuts_;}; 192 void setNumberCutsInTotal(int value)192 inline void setNumberCutsInTotal(int value) 193 193 { numberCuts_ = value;}; 194 void incrementNumberCutsInTotal(int value=1)194 inline void incrementNumberCutsInTotal(int value=1) 195 195 { numberCuts_ += value;}; 196 /// Total number of column cuts 197 inline int numberColumnCuts() const 198 { return numberColumnCuts_;}; 199 inline void setNumberColumnCuts(int value) 200 { numberColumnCuts_ = value;}; 201 inline void incrementNumberColumnCuts(int value=1) 202 { numberColumnCuts_ += value;}; 196 203 /// Total number of cuts active after (at end of n cut passes at each node) 197 204 inline int numberCutsActive() const 198 205 { return numberCutsActive_;}; 199 void setNumberCutsActive(int value)206 inline void setNumberCutsActive(int value) 200 207 { numberCutsActive_ = value;}; 201 void incrementNumberCutsActive(int value=1)208 inline void incrementNumberCutsActive(int value=1) 202 209 { numberCutsActive_ += value;}; 203 210 inline void setSwitchOffIfLessThan(int value) … … 260 267 /// Total number of cuts added 261 268 int numberCuts_; 269 /// Total number of column cuts added 270 int numberColumnCuts_; 262 271 /// Total number of cuts active after (at end of n cut passes at each node) 263 272 int numberCutsActive_; -
trunk/include/CbcModel.hpp
r246 r259 366 366 void findIntegers(bool startAgain); 367 367 368 /** If numberBeforeTrust >0 then we are going to use CbcBranchDynamic.369 Scan and convert CbcSimpleInteger objects370 */371 void convertToDynamic();372 373 368 //@} 374 369 … … 1115 1110 inline void setStateOfSearch(int state) 1116 1111 { stateOfSearch_=state;}; 1112 /// Strategy worked out - mainly at root node for use by CbcNode 1113 inline int searchStrategy() const 1114 { return searchStrategy_;}; 1117 1115 /// Set strategy worked out - mainly at root node for use by CbcNode 1118 1116 inline void setSearchStrategy(int value) 1119 { /*searchStrategy_ = value; for compatibility*/};1117 { searchStrategy_ = value; }; 1120 1118 1121 1119 /// Get the number of cut generators … … 1396 1394 void addCuts1(CbcNode * node, CoinWarmStartBasis *&lastws); 1397 1395 1396 /** If numberBeforeTrust >0 then we are going to use CbcBranchDynamic. 1397 Scan and convert CbcSimpleInteger objects 1398 */ 1399 void convertToDynamic(); 1400 /// Use cliques for pseudocost information - return nonzero if infeasible 1401 int cliquePseudoCosts(int doStatistics); 1402 /// Fill in useful estimates 1403 void pseudoShadow(double * down, double * up); 1404 1398 1405 /// Get the hotstart solution 1399 1406 inline const double * hotstartSolution() const … … 1417 1424 inline CbcNode * currentNode() const 1418 1425 { return currentNode_;}; 1426 /// Set the number of iterations done in strong branching. 1427 inline void setNumberStrongIterations(int number) 1428 { numberStrongIterations_ = number;}; 1429 /// Get the number of iterations done in strong branching. 1430 inline int numberStrongIterations() const 1431 { return numberStrongIterations_;}; 1419 1432 //@} 1420 1433 … … 1740 1753 /// Size of mini - tree 1741 1754 int sizeMiniTree_; 1755 /// Strategy worked out - mainly at root node 1756 int searchStrategy_; 1757 /// Number of iterations in strong branching 1758 int numberStrongIterations_; 1742 1759 /// Whether to force a resolve after takeOffCuts 1743 1760 bool resolveAfterTakeOffCuts_;
Note: See TracChangeset
for help on using the changeset viewer.