Changeset 1271 for stable/2.4/Cbc/src/CbcHeuristicLocal.cpp
 Timestamp:
 Nov 5, 2009 10:57:25 AM (10 years ago)
 Location:
 stable/2.4
 Files:

 1 edited
 1 copied
Legend:
 Unmodified
 Added
 Removed

stable/2.4
 Property svn:externals

old new 7 7 CoinUtils https://projects.coinor.org/svn/CoinUtils/stable/2.5/CoinUtils 8 8 Cgl https://projects.coinor.org/svn/Cgl/stable/0.54/Cgl 9 Clp https://projects.coinor.org/svn/Clp/stable/1.1 0/Clp9 Clp https://projects.coinor.org/svn/Clp/stable/1.11/Clp 10 10 Osi https://projects.coinor.org/svn/Osi/stable/0.100/Osi 11 11 Vol https://projects.coinor.org/svn/Vol/stable/1.1/Vol

 Property svn:externals

stable/2.4/Cbc/src/CbcHeuristicLocal.cpp
r1132 r1271 1 /* $Id$ */ 1 2 // Copyright (C) 2002, International Business Machines 2 3 // Corporation and others. All Rights Reserved. … … 36 37 // Get a copy of original matrix 37 38 assert(model.solver()); 38 matrix_ = *model.solver()>getMatrixByCol(); 39 if (model.solver()>getNumRows()) { 40 matrix_ = *model.solver()>getMatrixByCol(); 41 } 39 42 int numberColumns = model.solver()>getNumCols(); 40 used_ = new char[numberColumns];41 memset(used_,0,numberColumns );43 used_ = new int[numberColumns]; 44 memset(used_,0,numberColumns*sizeof(int)); 42 45 } 43 46 … … 79 82 if (model_&&rhs.used_) { 80 83 int numberColumns = model_>solver()>getNumCols(); 81 used_ = new char[numberColumns]; 82 memcpy(used_,rhs.used_,numberColumns); 84 used_ = CoinCopyOfArray(rhs.used_,numberColumns); 83 85 } else { 84 86 used_=NULL; … … 98 100 if (model_&&rhs.used_) { 99 101 int numberColumns = model_>solver()>getNumCols(); 100 used_ = new char[numberColumns]; 101 memcpy(used_,rhs.used_,numberColumns); 102 used_ = CoinCopyOfArray(rhs.used_,numberColumns); 102 103 } else { 103 104 used_=NULL; … … 109 110 // Resets stuff if model changes 110 111 void 111 CbcHeuristicLocal::resetModel(CbcModel * model)112 CbcHeuristicLocal::resetModel(CbcModel * /*model*/) 112 113 { 113 114 //CbcHeuristic::resetModel(model); … … 115 116 if (model_&&used_) { 116 117 int numberColumns = model_>solver()>getNumCols(); 117 used_ = new char[numberColumns];118 memset(used_,0,numberColumns );118 used_ = new int[numberColumns]; 119 memset(used_,0,numberColumns*sizeof(int)); 119 120 } else { 120 121 used_=NULL; … … 125 126 CbcHeuristicLocal::solutionFix(double & objectiveValue, 126 127 double * newSolution, 127 const int * keep)128 const int * /*keep*/) 128 129 { 129 130 numCouldRun_++; … … 156 157 } 157 158 } 158 int returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,objectiveValue, 159 objectiveValue,"CbcHeuristicLocal"); 160 if (returnCode<0) 161 returnCode=0; // returned on size 159 int returnCode = 0; 160 if (nFix*10>numberIntegers) { 161 returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,objectiveValue, 162 objectiveValue,"CbcHeuristicLocal"); 163 if (returnCode<0) { 164 returnCode=0; // returned on size 165 int numberColumns=newSolver>getNumCols(); 166 int numberContinuous = numberColumnsnumberIntegers; 167 if (numberContinuous>2*numberIntegers&& 168 nFix*10<numberColumns) { 169 #define LOCAL_FIX_CONTINUOUS 170 #ifdef LOCAL_FIX_CONTINUOUS 171 //const double * colUpper = newSolver>getColUpper(); 172 const double * colLower = newSolver>getColLower(); 173 int nAtLb=0; 174 //double sumDj=0.0; 175 const double * dj = newSolver>getReducedCost(); 176 double direction=newSolver>getObjSense(); 177 for (int iColumn=0;iColumn<numberColumns;iColumn++) { 178 if (!newSolver>isInteger(iColumn)) { 179 if (!used_[iColumn]) { 180 //double djValue = dj[iColumn]*direction; 181 nAtLb++; 182 //sumDj += djValue; 183 } 184 } 185 } 186 if (nAtLb) { 187 // fix some continuous 188 double * sort = new double[nAtLb]; 189 int * which = new int [nAtLb]; 190 //double threshold = CoinMax((0.01*sumDj)/static_cast<double>(nAtLb),1.0e6); 191 int nFix2=0; 192 for (int iColumn=0;iColumn<numberColumns;iColumn++) { 193 if (!newSolver>isInteger(iColumn)) { 194 if (!used_[iColumn]) { 195 double djValue = dj[iColumn]*direction; 196 if (djValue>1.0e6) { 197 sort[nFix2]=djValue; 198 which[nFix2++]=iColumn; 199 } 200 } 201 } 202 } 203 CoinSort_2(sort,sort+nFix2,which); 204 int divisor=2; 205 nFix2=CoinMin(nFix2,(numberColumnsnFix)/divisor); 206 for (int i=0;i<nFix2;i++) { 207 int iColumn = which[i]; 208 newSolver>setColUpper(iColumn,colLower[iColumn]); 209 } 210 delete [] sort; 211 delete [] which; 212 #ifdef CLP_INVESTIGATE2 213 printf("%d integers have zero value, and %d continuous fixed at lb\n", 214 nFix,nFix2); 215 #endif 216 returnCode = smallBranchAndBound(newSolver, 217 numberNodes_,newSolution, 218 objectiveValue, 219 objectiveValue,"CbcHeuristicLocal"); 220 if (returnCode<0) 221 returnCode=0; // returned on size 222 } 223 #endif 224 } 225 } 226 } 162 227 if ((returnCode&2)!=0) { 163 228 // could add cut … … 216 281 double * newSolution = new double [numberColumns]; 217 282 memcpy(newSolution,solution,numberColumns*sizeof(double)); 283 #ifdef LOCAL_FIX_CONTINUOUS 284 // mark continuous used 285 const double * columnLower = solver>getColLower(); 286 for (int iColumn=0;iColumn<numberColumns;iColumn++) { 287 if (!solver>isInteger(iColumn)) { 288 if (solution[iColumn]>columnLower[iColumn]+1.0e8) 289 used_[iColumn]=numberSolutions_; 290 } 291 } 292 #endif 218 293 219 294 // way is 1 if down possible, 2 if up possible, 3 if both possible … … 249 324 // if away from lower bound mark that fact 250 325 if (nearest>originalLower) { 251 used_[iColumn]= 1;326 used_[iColumn]=numberSolutions_; 252 327 } 253 328 cost[i] = direction*objective[iColumn]; … … 258 333 if (value<originalUpper0.5) 259 334 iway = 2; 260 way[i]= iway;335 way[i]=static_cast<char>(iway); 261 336 } 262 337 // get row activities … … 503 578 if (value<originalUpper0.5) 504 579 iway = 2; 505 way[goodK]= iway;580 way[goodK]=static_cast<char>(iway); 506 581 } 507 582 } … … 547 622 // if away from lower bound mark that fact 548 623 if (value>originalLower) { 549 used_[iColumn]= 1;624 used_[iColumn]=numberSolutions_; 550 625 } 551 626 } … … 574 649 delete [] mark; 575 650 if (numberSolutions_>1&&swap_==1) { 576 int i;577 for ( i=0;i<numberColumns;i++) {578 if (used_[i]>1)579 break;580 }581 if (i==numberColumns) {582 // modify used_ if just one583 const int * used = model_>usedInSolution();584 for (int i=0;i<numberColumns;i++)585 used_[i]= CoinMin(used[i],255);586 }587 651 // try merge 588 652 int returnCode2=solutionFix( solutionValue, betterSolution,NULL); … … 598 662 // Get a copy of original matrix 599 663 assert(model_>solver()); 600 matrix_ = *model_>solver()>getMatrixByCol(); 664 if (model_>solver()>getNumRows()) { 665 matrix_ = *model_>solver()>getMatrixByCol(); 666 } 601 667 delete [] used_; 602 668 int numberColumns = model>solver()>getNumCols(); 603 used_ = new char[numberColumns];604 memset(used_,0,numberColumns );669 used_ = new int[numberColumns]; 670 memset(used_,0,numberColumns*sizeof(int)); 605 671 } 606 672 // Default Constructor … … 635 701 { 636 702 CbcHeuristicNaive other; 637 fprintf(fp,"0#include \"CbcHeuristic Naive.hpp\"\n");703 fprintf(fp,"0#include \"CbcHeuristicLocal.hpp\"\n"); 638 704 fprintf(fp,"3 CbcHeuristicNaive naive(*cbcModel);\n"); 639 705 CbcHeuristic::generateCpp(fp,"naive"); … … 710 776 } 711 777 // First just fix all integers as close to zero as possible 712 OsiSolverInterface * newSolver = solver>clone();778 OsiSolverInterface * newSolver = cloneBut(7); // wassolver>clone(); 713 779 for (i=0;i<numberIntegers;i++) { 714 780 int iColumn=integerVariable[i]; … … 755 821 newSolver>setColLower(iColumn,value); 756 822 newSolver>setColUpper(iColumn,value); 823 } else { 824 // set back to original 825 newSolver>setColLower(iColumn,lower); 826 newSolver>setColUpper(iColumn,upper); 757 827 } 758 828 } … … 871 941 model_ = model; 872 942 } 943 // Default Constructor 944 CbcHeuristicCrossover::CbcHeuristicCrossover() 945 :CbcHeuristic(), 946 numberSolutions_(0), 947 useNumber_(3) 948 { 949 setWhen(1); 950 } 951 952 // Constructor with model  assumed before cuts 953 954 CbcHeuristicCrossover::CbcHeuristicCrossover(CbcModel & model) 955 :CbcHeuristic(model), 956 numberSolutions_(0), 957 useNumber_(3) 958 { 959 setWhen(1); 960 for (int i=0;i<10;i++) 961 random_[i]=model.randomNumberGenerator()>randomDouble(); 962 } 963 964 // Destructor 965 CbcHeuristicCrossover::~CbcHeuristicCrossover () 966 { 967 } 968 969 // Clone 970 CbcHeuristic * 971 CbcHeuristicCrossover::clone() const 972 { 973 return new CbcHeuristicCrossover(*this); 974 } 975 // Create C++ lines to get to current state 976 void 977 CbcHeuristicCrossover::generateCpp( FILE * fp) 978 { 979 CbcHeuristicCrossover other; 980 fprintf(fp,"0#include \"CbcHeuristicLocal.hpp\"\n"); 981 fprintf(fp,"3 CbcHeuristicCrossover crossover(*cbcModel);\n"); 982 CbcHeuristic::generateCpp(fp,"crossover"); 983 if (useNumber_!=other.useNumber_) 984 fprintf(fp,"3 crossover.setNumberSolutions(%d);\n",useNumber_); 985 else 986 fprintf(fp,"4 crossover.setNumberSolutions(%d);\n",useNumber_); 987 fprintf(fp,"3 cbcModel>addHeuristic(&crossover);\n"); 988 } 989 990 // Copy constructor 991 CbcHeuristicCrossover::CbcHeuristicCrossover(const CbcHeuristicCrossover & rhs) 992 : 993 CbcHeuristic(rhs), 994 attempts_(rhs.attempts_), 995 numberSolutions_(rhs.numberSolutions_), 996 useNumber_(rhs.useNumber_) 997 { 998 memcpy(random_,rhs.random_,10*sizeof(double)); 999 } 1000 1001 // Assignment operator 1002 CbcHeuristicCrossover & 1003 CbcHeuristicCrossover::operator=( const CbcHeuristicCrossover& rhs) 1004 { 1005 if (this!=&rhs) { 1006 CbcHeuristic::operator=(rhs); 1007 useNumber_ = rhs.useNumber_; 1008 attempts_ = rhs.attempts_; 1009 numberSolutions_ = rhs.numberSolutions_; 1010 memcpy(random_,rhs.random_,10*sizeof(double)); 1011 } 1012 return *this; 1013 } 1014 1015 // Resets stuff if model changes 1016 void 1017 CbcHeuristicCrossover::resetModel(CbcModel * model) 1018 { 1019 CbcHeuristic::resetModel(model); 1020 } 1021 int 1022 CbcHeuristicCrossover::solution(double & solutionValue, 1023 double * betterSolution) 1024 { 1025 if (when_==0) 1026 return 0; 1027 numCouldRun_++; 1028 bool useBest=(numberSolutions_!=model_>getSolutionCount()); 1029 if (!useBest&&(when_%10)==1) 1030 return 0; 1031 numberSolutions_=model_>getSolutionCount(); 1032 OsiSolverInterface * continuousSolver = model_>continuousSolver(); 1033 int useNumber =CoinMin(model_>numberSavedSolutions(),useNumber_); 1034 if (useNumber<2!continuousSolver) 1035 return 0; 1036 // Fix later 1037 if (!useBest) 1038 abort(); 1039 numRuns_++; 1040 double cutoff; 1041 model_>solver()>getDblParam(OsiDualObjectiveLimit,cutoff); 1042 double direction = model_>solver()>getObjSense(); 1043 cutoff *= direction; 1044 cutoff = CoinMin(cutoff,solutionValue); 1045 OsiSolverInterface * solver = cloneBut(2); 1046 // But reset bounds 1047 solver>setColLower(continuousSolver>getColLower()); 1048 solver>setColUpper(continuousSolver>getColUpper()); 1049 int numberColumns = solver>getNumCols(); 1050 // Fixed 1051 double * fixed =new double [numberColumns]; 1052 for (int i=0;i<numberColumns;i++) 1053 fixed[i]=COIN_DBL_MAX; 1054 int whichSolution[10]; 1055 for (int i=0;i<useNumber;i++) 1056 whichSolution[i]=i; 1057 for (int i=0;i<useNumber;i++) { 1058 int k = whichSolution[i]; 1059 const double * solution = model_>savedSolution(k); 1060 for (int j=0;j<numberColumns;j++) { 1061 if (solver>isInteger(j)) { 1062 if (fixed[j]==COIN_DBL_MAX) 1063 fixed[j]=floor(solution[j]+0.5); 1064 else if (fabs(fixed[j]solution[j])>1.0e7) 1065 fixed[j]=COIN_DBL_MAX; 1066 } 1067 } 1068 } 1069 const double * colLower = solver>getColLower(); 1070 for (int i=0;i<numberColumns;i++) { 1071 if (solver>isInteger(i)) { 1072 double value=fixed[i]; 1073 if (value!=COIN_DBL_MAX) { 1074 if (when_<10) { 1075 solver>setColLower(i,value); 1076 solver>setColUpper(i,value); 1077 } else if (value==colLower[i]) { 1078 solver>setColUpper(i,value); 1079 } 1080 } 1081 } 1082 } 1083 int returnCode = smallBranchAndBound(solver,numberNodes_,betterSolution, 1084 solutionValue, 1085 solutionValue,"CbcHeuristicCrossover"); 1086 if (returnCode<0) 1087 returnCode=0; // returned on size 1088 if ((returnCode&2)!=0) { 1089 // could add cut 1090 returnCode &= ~2; 1091 } 1092 1093 delete solver; 1094 return returnCode; 1095 } 1096 // update model 1097 void CbcHeuristicCrossover::setModel(CbcModel * model) 1098 { 1099 model_ = model; 1100 if (model) { 1101 for (int i=0;i<10;i++) 1102 random_[i]=model>randomNumberGenerator()>randomDouble(); 1103 } 1104 } 873 1105 874 1106
Note: See TracChangeset
for help on using the changeset viewer.