Cbc trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2002, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef CbcHeuristic_H 00007 #define CbcHeuristic_H 00008 00009 #include <string> 00010 #include <vector> 00011 #include "CoinPackedMatrix.hpp" 00012 #include "OsiCuts.hpp" 00013 #include "CoinHelperFunctions.hpp" 00014 #include "OsiBranchingObject.hpp" 00015 00016 class OsiSolverInterface; 00017 00018 class CbcModel; 00019 00020 //############################################################################# 00021 00022 class CbcHeuristicNodeList; 00023 class CbcBranchingObject; 00024 00028 class CbcHeuristicNode { 00029 private: 00030 void gutsOfConstructor(CbcModel& model); 00031 CbcHeuristicNode(); 00032 CbcHeuristicNode& operator=(const CbcHeuristicNode&); 00033 private: 00035 int numObjects_; 00039 CbcBranchingObject** brObj_; 00040 public: 00041 CbcHeuristicNode(CbcModel& model); 00042 00043 CbcHeuristicNode(const CbcHeuristicNode& rhs); 00044 ~CbcHeuristicNode(); 00045 double distance(const CbcHeuristicNode* node) const; 00046 double minDistance(const CbcHeuristicNodeList& nodeList) const; 00047 bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList, 00048 const double threshold) const; 00049 double avgDistance(const CbcHeuristicNodeList& nodeList) const; 00050 }; 00051 00052 class CbcHeuristicNodeList { 00053 private: 00054 void gutsOfDelete(); 00055 void gutsOfCopy(const CbcHeuristicNodeList& rhs); 00056 private: 00057 std::vector<CbcHeuristicNode*> nodes_; 00058 public: 00059 CbcHeuristicNodeList() {} 00060 CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs); 00061 CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs); 00062 ~CbcHeuristicNodeList(); 00063 00064 void append(CbcHeuristicNode*& node); 00065 void append(const CbcHeuristicNodeList& nodes); 00066 inline const CbcHeuristicNode* node(int i) const { 00067 return nodes_[i]; 00068 } 00069 inline int size() const { 00070 return static_cast<int>(nodes_.size()); 00071 } 00072 }; 00073 00074 //############################################################################# 00077 class CbcHeuristic { 00078 private: 00079 void gutsOfDelete() {} 00080 void gutsOfCopy(const CbcHeuristic & rhs); 00081 00082 public: 00083 // Default Constructor 00084 CbcHeuristic (); 00085 00086 // Constructor with model - assumed before cuts 00087 CbcHeuristic (CbcModel & model); 00088 00089 // Copy constructor 00090 CbcHeuristic ( const CbcHeuristic &); 00091 00092 virtual ~CbcHeuristic(); 00093 00095 virtual CbcHeuristic * clone() const = 0; 00096 00098 CbcHeuristic & operator=(const CbcHeuristic& rhs); 00099 00101 virtual void setModel(CbcModel * model); 00102 00104 virtual void resetModel(CbcModel * model) = 0; 00105 00111 virtual int solution(double & objectiveValue, 00112 double * newSolution) = 0; 00113 00121 virtual int solution2(double & /*objectiveValue*/, 00122 double * /*newSolution*/, 00123 OsiCuts & /*cs*/) { 00124 return 0; 00125 } 00126 00128 virtual void validate() {} 00129 00134 inline void setWhen(int value) { 00135 when_ = value; 00136 } 00138 inline int when() const { 00139 return when_; 00140 } 00141 00143 inline void setNumberNodes(int value) { 00144 numberNodes_ = value; 00145 } 00147 inline int numberNodes() const { 00148 return numberNodes_; 00149 } 00159 inline void setSwitches(int value) { 00160 switches_ = value; 00161 } 00171 inline int switches() const { 00172 return switches_; 00173 } 00175 bool exitNow(double bestObjective) const; 00177 inline void setFeasibilityPumpOptions(int value) { 00178 feasibilityPumpOptions_ = value; 00179 } 00181 inline int feasibilityPumpOptions() const { 00182 return feasibilityPumpOptions_; 00183 } 00185 inline void setModelOnly(CbcModel * model) { 00186 model_ = model; 00187 } 00188 00189 00191 inline void setFractionSmall(double value) { 00192 fractionSmall_ = value; 00193 } 00195 inline double fractionSmall() const { 00196 return fractionSmall_; 00197 } 00199 inline int numberSolutionsFound() const { 00200 return numberSolutionsFound_; 00201 } 00203 inline void incrementNumberSolutionsFound() { 00204 numberSolutionsFound_++; 00205 } 00206 00216 int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes, 00217 double * newSolution, double & newSolutionValue, 00218 double cutoff , std::string name) const; 00220 virtual void generateCpp( FILE * ) {} 00222 void generateCpp( FILE * fp, const char * heuristic) ; 00224 virtual bool canDealWithOdd() const { 00225 return false; 00226 } 00228 inline const char *heuristicName() const { 00229 return heuristicName_.c_str(); 00230 } 00232 inline void setHeuristicName(const char *name) { 00233 heuristicName_ = name; 00234 } 00236 void setSeed(int value); 00238 inline void setDecayFactor(double value) { 00239 decayFactor_ = value; 00240 } 00242 void setInputSolution(const double * solution, double objValue); 00243 /* Runs if bit set 00244 0 - before cuts at root node (or from doHeuristics) 00245 1 - during cuts at root 00246 2 - after root node cuts 00247 3 - after cuts at other nodes 00248 4 - during cuts at other nodes 00249 8 added if previous heuristic in loop found solution 00250 */ 00251 inline void setWhereFrom(int value) { 00252 whereFrom_ = value; 00253 } 00254 inline int whereFrom() const { 00255 return whereFrom_; 00256 } 00263 inline void setShallowDepth(int value) { 00264 shallowDepth_ = value; 00265 } 00267 inline void setHowOftenShallow(int value) { 00268 howOftenShallow_ = value; 00269 } 00273 inline void setMinDistanceToRun(int value) { 00274 minDistanceToRun_ = value; 00275 } 00276 00285 virtual bool shouldHeurRun(int whereFrom); 00287 bool shouldHeurRun_randomChoice(); 00288 void debugNodes(); 00289 void printDistanceToNodes(); 00291 inline int numRuns() const { 00292 return numRuns_; 00293 } 00294 00296 inline int numCouldRun() const { 00297 return numCouldRun_; 00298 } 00307 OsiSolverInterface * cloneBut(int type); 00308 protected: 00309 00311 CbcModel * model_; 00313 int when_; 00315 int numberNodes_; 00317 int feasibilityPumpOptions_; 00319 mutable double fractionSmall_; 00321 CoinThreadRandom randomNumberGenerator_; 00323 std::string heuristicName_; 00324 00326 int howOften_; 00328 double decayFactor_; 00338 mutable int switches_; 00339 /* Runs if bit set 00340 0 - before cuts at root node (or from doHeuristics) 00341 1 - during cuts at root 00342 2 - after root node cuts 00343 3 - after cuts at other nodes 00344 4 - during cuts at other nodes 00345 8 added if previous heuristic in loop found solution 00346 */ 00347 int whereFrom_; 00354 int shallowDepth_; 00356 int howOftenShallow_; 00359 int numInvocationsInShallow_; 00362 int numInvocationsInDeep_; 00364 int lastRunDeep_; 00366 int numRuns_; 00370 int minDistanceToRun_; 00371 00373 CbcHeuristicNodeList runNodes_; 00374 00376 int numCouldRun_; 00377 00379 int numberSolutionsFound_; 00380 00381 // Input solution - so can be used as seed 00382 double * inputSolution_; 00383 00384 00385 #ifdef JJF_ZERO 00386 00387 double * lowerBoundLastNode_; 00389 double * upperBoundLastNode_; 00390 #endif 00391 }; 00395 class CbcRounding : public CbcHeuristic { 00396 public: 00397 00398 // Default Constructor 00399 CbcRounding (); 00400 00401 // Constructor with model - assumed before cuts 00402 CbcRounding (CbcModel & model); 00403 00404 // Copy constructor 00405 CbcRounding ( const CbcRounding &); 00406 00407 // Destructor 00408 ~CbcRounding (); 00409 00411 CbcRounding & operator=(const CbcRounding& rhs); 00412 00414 virtual CbcHeuristic * clone() const; 00416 virtual void generateCpp( FILE * fp) ; 00417 00419 virtual void resetModel(CbcModel * model); 00420 00422 virtual void setModel(CbcModel * model); 00423 00424 using CbcHeuristic::solution ; 00430 virtual int solution(double & objectiveValue, 00431 double * newSolution); 00438 virtual int solution(double & objectiveValue, 00439 double * newSolution, 00440 double solutionValue); 00442 virtual void validate(); 00443 00444 00446 void setSeed(int value) { 00447 seed_ = value; 00448 } 00449 00450 protected: 00451 // Data 00452 00453 // Original matrix by column 00454 CoinPackedMatrix matrix_; 00455 00456 // Original matrix by 00457 CoinPackedMatrix matrixByRow_; 00458 00459 // Down locks 00460 unsigned short * down_; 00461 00462 // Up locks 00463 unsigned short * up_; 00464 00465 // Equality locks 00466 unsigned short * equal_; 00467 00468 // Seed for random stuff 00469 int seed_; 00470 }; 00471 00477 class CbcHeuristicPartial : public CbcHeuristic { 00478 public: 00479 00480 // Default Constructor 00481 CbcHeuristicPartial (); 00482 00487 CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200); 00488 00489 // Copy constructor 00490 CbcHeuristicPartial ( const CbcHeuristicPartial &); 00491 00492 // Destructor 00493 ~CbcHeuristicPartial (); 00494 00496 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs); 00497 00499 virtual CbcHeuristic * clone() const; 00501 virtual void generateCpp( FILE * fp) ; 00502 00504 virtual void resetModel(CbcModel * model); 00505 00507 virtual void setModel(CbcModel * model); 00508 00509 using CbcHeuristic::solution ; 00515 virtual int solution(double & objectiveValue, 00516 double * newSolution); 00518 virtual void validate(); 00519 00520 00522 void setFixPriority(int value) { 00523 fixPriority_ = value; 00524 } 00525 00527 virtual bool shouldHeurRun(int whereFrom); 00528 00529 protected: 00530 // Data 00531 00532 // All variables with abs priority <= this will be fixed 00533 int fixPriority_; 00534 }; 00535 00540 class CbcSerendipity : public CbcHeuristic { 00541 public: 00542 00543 // Default Constructor 00544 CbcSerendipity (); 00545 00546 /* Constructor with model 00547 */ 00548 CbcSerendipity (CbcModel & model); 00549 00550 // Copy constructor 00551 CbcSerendipity ( const CbcSerendipity &); 00552 00553 // Destructor 00554 ~CbcSerendipity (); 00555 00557 CbcSerendipity & operator=(const CbcSerendipity& rhs); 00558 00560 virtual CbcHeuristic * clone() const; 00562 virtual void generateCpp( FILE * fp) ; 00563 00565 virtual void setModel(CbcModel * model); 00566 00567 using CbcHeuristic::solution ; 00578 virtual int solution(double & objectiveValue, 00579 double * newSolution); 00581 virtual void resetModel(CbcModel * model); 00582 00583 protected: 00584 }; 00585 00589 class CbcHeuristicJustOne : public CbcHeuristic { 00590 public: 00591 00592 // Default Constructor 00593 CbcHeuristicJustOne (); 00594 00595 // Constructor with model - assumed before cuts 00596 CbcHeuristicJustOne (CbcModel & model); 00597 00598 // Copy constructor 00599 CbcHeuristicJustOne ( const CbcHeuristicJustOne &); 00600 00601 // Destructor 00602 ~CbcHeuristicJustOne (); 00603 00605 virtual CbcHeuristicJustOne * clone() const; 00606 00608 CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs); 00609 00611 virtual void generateCpp( FILE * fp) ; 00612 00619 virtual int solution(double & objectiveValue, 00620 double * newSolution); 00622 virtual void resetModel(CbcModel * model); 00623 00625 virtual void setModel(CbcModel * model); 00627 00633 virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/, 00634 const double* /*newSolution*/, 00635 int& /*bestColumn*/, 00636 int& /*bestRound*/) { 00637 return true; 00638 } 00640 virtual void validate(); 00642 void addHeuristic(const CbcHeuristic * heuristic, double probability); 00644 void normalizeProbabilities(); 00645 protected: 00646 // Data 00647 00648 // Probability of running a heuristic 00649 double * probabilities_; 00650 00651 // Heuristics 00652 CbcHeuristic ** heuristic_; 00653 00654 // Number of heuristics 00655 int numberHeuristics_; 00656 00657 }; 00658 00659 #endif 00660