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 } 00160 inline void setSwitches(int value) { 00161 switches_ = value; 00162 } 00173 inline int switches() const { 00174 return switches_; 00175 } 00177 bool exitNow(double bestObjective) const; 00179 inline void setFeasibilityPumpOptions(int value) { 00180 feasibilityPumpOptions_ = value; 00181 } 00183 inline int feasibilityPumpOptions() const { 00184 return feasibilityPumpOptions_; 00185 } 00187 inline void setModelOnly(CbcModel * model) { 00188 model_ = model; 00189 } 00190 00191 00193 inline void setFractionSmall(double value) { 00194 fractionSmall_ = value; 00195 } 00197 inline double fractionSmall() const { 00198 return fractionSmall_; 00199 } 00201 inline int numberSolutionsFound() const { 00202 return numberSolutionsFound_; 00203 } 00205 inline void incrementNumberSolutionsFound() { 00206 numberSolutionsFound_++; 00207 } 00208 00218 int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes, 00219 double * newSolution, double & newSolutionValue, 00220 double cutoff , std::string name) const; 00222 virtual void generateCpp( FILE * ) {} 00224 void generateCpp( FILE * fp, const char * heuristic) ; 00226 virtual bool canDealWithOdd() const { 00227 return false; 00228 } 00230 inline const char *heuristicName() const { 00231 return heuristicName_.c_str(); 00232 } 00234 inline void setHeuristicName(const char *name) { 00235 heuristicName_ = name; 00236 } 00238 void setSeed(int value); 00240 inline void setDecayFactor(double value) { 00241 decayFactor_ = value; 00242 } 00244 void setInputSolution(const double * solution, double objValue); 00245 /* Runs if bit set 00246 0 - before cuts at root node (or from doHeuristics) 00247 1 - during cuts at root 00248 2 - after root node cuts 00249 3 - after cuts at other nodes 00250 4 - during cuts at other nodes 00251 8 added if previous heuristic in loop found solution 00252 */ 00253 inline void setWhereFrom(int value) { 00254 whereFrom_ = value; 00255 } 00256 inline int whereFrom() const { 00257 return whereFrom_; 00258 } 00265 inline void setShallowDepth(int value) { 00266 shallowDepth_ = value; 00267 } 00269 inline void setHowOftenShallow(int value) { 00270 howOftenShallow_ = value; 00271 } 00275 inline void setMinDistanceToRun(int value) { 00276 minDistanceToRun_ = value; 00277 } 00278 00287 virtual bool shouldHeurRun(int whereFrom); 00289 bool shouldHeurRun_randomChoice(); 00290 void debugNodes(); 00291 void printDistanceToNodes(); 00293 inline int numRuns() const { 00294 return numRuns_; 00295 } 00296 00298 inline int numCouldRun() const { 00299 return numCouldRun_; 00300 } 00309 OsiSolverInterface * cloneBut(int type); 00310 protected: 00311 00313 CbcModel * model_; 00315 int when_; 00317 int numberNodes_; 00323 int feasibilityPumpOptions_; 00325 mutable double fractionSmall_; 00327 CoinThreadRandom randomNumberGenerator_; 00329 std::string heuristicName_; 00330 00332 int howOften_; 00334 double decayFactor_; 00345 mutable int switches_; 00346 /* Runs if bit set 00347 0 - before cuts at root node (or from doHeuristics) 00348 1 - during cuts at root 00349 2 - after root node cuts 00350 3 - after cuts at other nodes 00351 4 - during cuts at other nodes 00352 8 added if previous heuristic in loop found solution 00353 */ 00354 int whereFrom_; 00361 int shallowDepth_; 00363 int howOftenShallow_; 00366 int numInvocationsInShallow_; 00369 int numInvocationsInDeep_; 00371 int lastRunDeep_; 00373 int numRuns_; 00377 int minDistanceToRun_; 00378 00380 CbcHeuristicNodeList runNodes_; 00381 00383 int numCouldRun_; 00384 00386 int numberSolutionsFound_; 00387 00389 mutable int numberNodesDone_; 00390 00391 // Input solution - so can be used as seed 00392 double * inputSolution_; 00393 00394 00395 #ifdef JJF_ZERO 00396 00397 double * lowerBoundLastNode_; 00399 double * upperBoundLastNode_; 00400 #endif 00401 }; 00405 class CbcRounding : public CbcHeuristic { 00406 public: 00407 00408 // Default Constructor 00409 CbcRounding (); 00410 00411 // Constructor with model - assumed before cuts 00412 CbcRounding (CbcModel & model); 00413 00414 // Copy constructor 00415 CbcRounding ( const CbcRounding &); 00416 00417 // Destructor 00418 ~CbcRounding (); 00419 00421 CbcRounding & operator=(const CbcRounding& rhs); 00422 00424 virtual CbcHeuristic * clone() const; 00426 virtual void generateCpp( FILE * fp) ; 00427 00429 virtual void resetModel(CbcModel * model); 00430 00432 virtual void setModel(CbcModel * model); 00433 00434 using CbcHeuristic::solution ; 00440 virtual int solution(double & objectiveValue, 00441 double * newSolution); 00448 virtual int solution(double & objectiveValue, 00449 double * newSolution, 00450 double solutionValue); 00452 virtual void validate(); 00453 00454 00456 void setSeed(int value) { 00457 seed_ = value; 00458 } 00459 00460 protected: 00461 // Data 00462 00463 // Original matrix by column 00464 CoinPackedMatrix matrix_; 00465 00466 // Original matrix by 00467 CoinPackedMatrix matrixByRow_; 00468 00469 // Down locks 00470 unsigned short * down_; 00471 00472 // Up locks 00473 unsigned short * up_; 00474 00475 // Equality locks 00476 unsigned short * equal_; 00477 00478 // Seed for random stuff 00479 int seed_; 00480 }; 00481 00487 class CbcHeuristicPartial : public CbcHeuristic { 00488 public: 00489 00490 // Default Constructor 00491 CbcHeuristicPartial (); 00492 00497 CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200); 00498 00499 // Copy constructor 00500 CbcHeuristicPartial ( const CbcHeuristicPartial &); 00501 00502 // Destructor 00503 ~CbcHeuristicPartial (); 00504 00506 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs); 00507 00509 virtual CbcHeuristic * clone() const; 00511 virtual void generateCpp( FILE * fp) ; 00512 00514 virtual void resetModel(CbcModel * model); 00515 00517 virtual void setModel(CbcModel * model); 00518 00519 using CbcHeuristic::solution ; 00525 virtual int solution(double & objectiveValue, 00526 double * newSolution); 00528 virtual void validate(); 00529 00530 00532 void setFixPriority(int value) { 00533 fixPriority_ = value; 00534 } 00535 00537 virtual bool shouldHeurRun(int whereFrom); 00538 00539 protected: 00540 // Data 00541 00542 // All variables with abs priority <= this will be fixed 00543 int fixPriority_; 00544 }; 00545 00550 class CbcSerendipity : public CbcHeuristic { 00551 public: 00552 00553 // Default Constructor 00554 CbcSerendipity (); 00555 00556 /* Constructor with model 00557 */ 00558 CbcSerendipity (CbcModel & model); 00559 00560 // Copy constructor 00561 CbcSerendipity ( const CbcSerendipity &); 00562 00563 // Destructor 00564 ~CbcSerendipity (); 00565 00567 CbcSerendipity & operator=(const CbcSerendipity& rhs); 00568 00570 virtual CbcHeuristic * clone() const; 00572 virtual void generateCpp( FILE * fp) ; 00573 00575 virtual void setModel(CbcModel * model); 00576 00577 using CbcHeuristic::solution ; 00588 virtual int solution(double & objectiveValue, 00589 double * newSolution); 00591 virtual void resetModel(CbcModel * model); 00592 00593 protected: 00594 }; 00595 00599 class CbcHeuristicJustOne : public CbcHeuristic { 00600 public: 00601 00602 // Default Constructor 00603 CbcHeuristicJustOne (); 00604 00605 // Constructor with model - assumed before cuts 00606 CbcHeuristicJustOne (CbcModel & model); 00607 00608 // Copy constructor 00609 CbcHeuristicJustOne ( const CbcHeuristicJustOne &); 00610 00611 // Destructor 00612 ~CbcHeuristicJustOne (); 00613 00615 virtual CbcHeuristicJustOne * clone() const; 00616 00618 CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs); 00619 00621 virtual void generateCpp( FILE * fp) ; 00622 00629 virtual int solution(double & objectiveValue, 00630 double * newSolution); 00632 virtual void resetModel(CbcModel * model); 00633 00635 virtual void setModel(CbcModel * model); 00637 00643 virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/, 00644 const double* /*newSolution*/, 00645 int& /*bestColumn*/, 00646 int& /*bestRound*/) { 00647 return true; 00648 } 00650 virtual void validate(); 00652 void addHeuristic(const CbcHeuristic * heuristic, double probability); 00654 void normalizeProbabilities(); 00655 protected: 00656 // Data 00657 00658 // Probability of running a heuristic 00659 double * probabilities_; 00660 00661 // Heuristics 00662 CbcHeuristic ** heuristic_; 00663 00664 // Number of heuristics 00665 int numberHeuristics_; 00666 00667 }; 00668 00669 #endif 00670