Go to the documentation of this file.00001
00002
00003
00004 #ifndef CbcHeuristic_H
00005 #define CbcHeuristic_H
00006
00007 #include <string>
00008 #include <vector>
00009 #include "CoinPackedMatrix.hpp"
00010 #include "OsiCuts.hpp"
00011 #include "CoinHelperFunctions.hpp"
00012 #include "OsiBranchingObject.hpp"
00013
00014 class OsiSolverInterface;
00015
00016 class CbcModel;
00017
00018
00019
00020 class CbcHeuristicNodeList;
00021 class CbcBranchingObject;
00022
00026 class CbcHeuristicNode {
00027 private:
00028 void gutsOfConstructor(CbcModel& model);
00029 CbcHeuristicNode();
00030 CbcHeuristicNode& operator=(const CbcHeuristicNode&);
00031 private:
00033 int numObjects_;
00037 CbcBranchingObject** brObj_;
00038 public:
00039 CbcHeuristicNode(CbcModel& model);
00040
00041 CbcHeuristicNode(const CbcHeuristicNode& rhs);
00042 ~CbcHeuristicNode();
00043 double distance(const CbcHeuristicNode* node) const;
00044 double minDistance(const CbcHeuristicNodeList& nodeList) const;
00045 bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
00046 const double threshold) const;
00047 double avgDistance(const CbcHeuristicNodeList& nodeList) const;
00048 };
00049
00050 class CbcHeuristicNodeList {
00051 private:
00052 void gutsOfDelete();
00053 void gutsOfCopy(const CbcHeuristicNodeList& rhs);
00054 private:
00055 std::vector<CbcHeuristicNode*> nodes_;
00056 public:
00057 CbcHeuristicNodeList() {}
00058 CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
00059 CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
00060 ~CbcHeuristicNodeList();
00061
00062 void append(CbcHeuristicNode*& node);
00063 void append(const CbcHeuristicNodeList& nodes);
00064 inline const CbcHeuristicNode* node(int i) const {
00065 return nodes_[i];
00066 }
00067 inline int size() const {
00068 return nodes_.size();
00069 }
00070 };
00071
00072
00075 class CbcHeuristic {
00076 private:
00077 void gutsOfDelete() {}
00078 void gutsOfCopy(const CbcHeuristic & rhs);
00079
00080 public:
00081
00082 CbcHeuristic ();
00083
00084
00085 CbcHeuristic (CbcModel & model);
00086
00087
00088 CbcHeuristic ( const CbcHeuristic &);
00089
00090 virtual ~CbcHeuristic();
00091
00093 virtual CbcHeuristic * clone() const = 0;
00094
00096 CbcHeuristic & operator=(const CbcHeuristic& rhs);
00097
00099 virtual void setModel(CbcModel * model);
00100
00102 virtual void resetModel(CbcModel * model) = 0;
00103
00109 virtual int solution(double & objectiveValue,
00110 double * newSolution) = 0;
00111
00119 virtual int solution2(double & ,
00120 double * ,
00121 OsiCuts & ) {
00122 return 0;
00123 }
00124
00126 virtual void validate() {}
00127
00132 inline void setWhen(int value) {
00133 when_ = value;
00134 }
00136 inline int when() const {
00137 return when_;
00138 }
00139
00141 inline void setNumberNodes(int value) {
00142 numberNodes_ = value;
00143 }
00145 inline int numberNodes() const {
00146 return numberNodes_;
00147 }
00157 inline void setSwitches(int value) {
00158 switches_ = value;
00159 }
00169 inline int switches() const {
00170 return switches_;
00171 }
00173 bool exitNow(double bestObjective) const;
00175 inline void setFeasibilityPumpOptions(int value) {
00176 feasibilityPumpOptions_ = value;
00177 }
00179 inline int feasibilityPumpOptions() const {
00180 return feasibilityPumpOptions_;
00181 }
00183 inline void setModelOnly(CbcModel * model) {
00184 model_ = model;
00185 }
00186
00187
00189 inline void setFractionSmall(double value) {
00190 fractionSmall_ = value;
00191 }
00193 inline double fractionSmall() const {
00194 return fractionSmall_;
00195 }
00197 inline int numberSolutionsFound() const {
00198 return numberSolutionsFound_;
00199 }
00201 inline void incrementNumberSolutionsFound() {
00202 numberSolutionsFound_++;
00203 }
00204
00214 int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
00215 double * newSolution, double & newSolutionValue,
00216 double cutoff , std::string name) const;
00218 virtual void generateCpp( FILE * ) {}
00220 void generateCpp( FILE * fp, const char * heuristic) ;
00222 virtual bool canDealWithOdd() const {
00223 return false;
00224 }
00226 inline const char *heuristicName() const {
00227 return heuristicName_.c_str();
00228 }
00230 inline void setHeuristicName(const char *name) {
00231 heuristicName_ = name;
00232 }
00234 void setSeed(int value);
00236 inline void setDecayFactor(double value) {
00237 decayFactor_ = value;
00238 }
00240 void setInputSolution(const double * solution, double objValue);
00241
00242
00243
00244
00245
00246
00247
00248
00249 inline void setWhereFrom(int value) {
00250 whereFrom_ = value;
00251 }
00258 inline void setShallowDepth(int value) {
00259 shallowDepth_ = value;
00260 }
00262 inline void setHowOftenShallow(int value) {
00263 howOftenShallow_ = value;
00264 }
00268 inline void setMinDistanceToRun(int value) {
00269 minDistanceToRun_ = value;
00270 }
00271
00280 virtual bool shouldHeurRun(int whereFrom);
00282 bool shouldHeurRun_randomChoice();
00283 void debugNodes();
00284 void printDistanceToNodes();
00286 inline int numRuns() const {
00287 return numRuns_;
00288 }
00289
00291 inline int numCouldRun() const {
00292 return numCouldRun_;
00293 }
00298 OsiSolverInterface * cloneBut(int type);
00299 protected:
00300
00302 CbcModel * model_;
00304 int when_;
00306 int numberNodes_;
00308 int feasibilityPumpOptions_;
00310 mutable double fractionSmall_;
00312 CoinThreadRandom randomNumberGenerator_;
00314 std::string heuristicName_;
00315
00317 int howOften_;
00319 double decayFactor_;
00329 mutable int switches_;
00330
00331
00332
00333
00334
00335
00336
00337
00338 int whereFrom_;
00345 int shallowDepth_;
00347 int howOftenShallow_;
00350 int numInvocationsInShallow_;
00353 int numInvocationsInDeep_;
00355 int lastRunDeep_;
00357 int numRuns_;
00361 int minDistanceToRun_;
00362
00364 CbcHeuristicNodeList runNodes_;
00365
00367 int numCouldRun_;
00368
00370 int numberSolutionsFound_;
00371
00372
00373 double * inputSolution_;
00374
00375
00376 #ifdef JJF_ZERO
00377
00378 double * lowerBoundLastNode_;
00380 double * upperBoundLastNode_;
00381 #endif
00382 };
00386 class CbcRounding : public CbcHeuristic {
00387 public:
00388
00389
00390 CbcRounding ();
00391
00392
00393 CbcRounding (CbcModel & model);
00394
00395
00396 CbcRounding ( const CbcRounding &);
00397
00398
00399 ~CbcRounding ();
00400
00402 CbcRounding & operator=(const CbcRounding& rhs);
00403
00405 virtual CbcHeuristic * clone() const;
00407 virtual void generateCpp( FILE * fp) ;
00408
00410 virtual void resetModel(CbcModel * model);
00411
00413 virtual void setModel(CbcModel * model);
00414
00415 using CbcHeuristic::solution ;
00421 virtual int solution(double & objectiveValue,
00422 double * newSolution);
00429 virtual int solution(double & objectiveValue,
00430 double * newSolution,
00431 double solutionValue);
00433 virtual void validate();
00434
00435
00437 void setSeed(int value) {
00438 seed_ = value;
00439 }
00440
00441 protected:
00442
00443
00444
00445 CoinPackedMatrix matrix_;
00446
00447
00448 CoinPackedMatrix matrixByRow_;
00449
00450
00451 unsigned short * down_;
00452
00453
00454 unsigned short * up_;
00455
00456
00457 unsigned short * equal_;
00458
00459
00460 int seed_;
00461 };
00462
00468 class CbcHeuristicPartial : public CbcHeuristic {
00469 public:
00470
00471
00472 CbcHeuristicPartial ();
00473
00478 CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00479
00480
00481 CbcHeuristicPartial ( const CbcHeuristicPartial &);
00482
00483
00484 ~CbcHeuristicPartial ();
00485
00487 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00488
00490 virtual CbcHeuristic * clone() const;
00492 virtual void generateCpp( FILE * fp) ;
00493
00495 virtual void resetModel(CbcModel * model);
00496
00498 virtual void setModel(CbcModel * model);
00499
00500 using CbcHeuristic::solution ;
00506 virtual int solution(double & objectiveValue,
00507 double * newSolution);
00509 virtual void validate();
00510
00511
00513 void setFixPriority(int value) {
00514 fixPriority_ = value;
00515 }
00516
00518 virtual bool shouldHeurRun(int whereFrom);
00519
00520 protected:
00521
00522
00523
00524 int fixPriority_;
00525 };
00526
00531 class CbcSerendipity : public CbcHeuristic {
00532 public:
00533
00534
00535 CbcSerendipity ();
00536
00537
00538
00539 CbcSerendipity (CbcModel & model);
00540
00541
00542 CbcSerendipity ( const CbcSerendipity &);
00543
00544
00545 ~CbcSerendipity ();
00546
00548 CbcSerendipity & operator=(const CbcSerendipity& rhs);
00549
00551 virtual CbcHeuristic * clone() const;
00553 virtual void generateCpp( FILE * fp) ;
00554
00556 virtual void setModel(CbcModel * model);
00557
00558 using CbcHeuristic::solution ;
00569 virtual int solution(double & objectiveValue,
00570 double * newSolution);
00572 virtual void resetModel(CbcModel * model);
00573
00574 protected:
00575 };
00576
00580 class CbcHeuristicJustOne : public CbcHeuristic {
00581 public:
00582
00583
00584 CbcHeuristicJustOne ();
00585
00586
00587 CbcHeuristicJustOne (CbcModel & model);
00588
00589
00590 CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00591
00592
00593 ~CbcHeuristicJustOne ();
00594
00596 virtual CbcHeuristicJustOne * clone() const;
00597
00599 CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00600
00602 virtual void generateCpp( FILE * fp) ;
00603
00610 virtual int solution(double & objectiveValue,
00611 double * newSolution);
00613 virtual void resetModel(CbcModel * model);
00614
00616 virtual void setModel(CbcModel * model);
00618
00624 virtual bool selectVariableToBranch(OsiSolverInterface* ,
00625 const double* ,
00626 int& ,
00627 int& ) {
00628 return true;
00629 }
00631 virtual void validate();
00633 void addHeuristic(const CbcHeuristic * heuristic, double probability);
00635 void normalizeProbabilities();
00636 protected:
00637
00638
00639
00640 double * probabilities_;
00641
00642
00643 CbcHeuristic ** heuristic_;
00644
00645
00646 int numberHeuristics_;
00647
00648 };
00649
00650 #endif
00651