00001
00002
00003
00004
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
00084 CbcHeuristic ();
00085
00086
00087 CbcHeuristic (CbcModel & model);
00088
00089
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 & ,
00122 double * ,
00123 OsiCuts & ) {
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
00246
00247
00248
00249
00250
00251
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
00347
00348
00349
00350
00351
00352
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
00392 double * inputSolution_;
00393
00394
00395 #ifdef JJF_ZERO
00397 double * lowerBoundLastNode_;
00399 double * upperBoundLastNode_;
00400 #endif
00401 };
00405 class CbcRounding : public CbcHeuristic {
00406 public:
00407
00408
00409 CbcRounding ();
00410
00411
00412 CbcRounding (CbcModel & model);
00413
00414
00415 CbcRounding ( const CbcRounding &);
00416
00417
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
00462
00463
00464 CoinPackedMatrix matrix_;
00465
00466
00467 CoinPackedMatrix matrixByRow_;
00468
00469
00470 unsigned short * down_;
00471
00472
00473 unsigned short * up_;
00474
00475
00476 unsigned short * equal_;
00477
00478
00479 int seed_;
00480 };
00481
00487 class CbcHeuristicPartial : public CbcHeuristic {
00488 public:
00489
00490
00491 CbcHeuristicPartial ();
00492
00497 CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00498
00499
00500 CbcHeuristicPartial ( const CbcHeuristicPartial &);
00501
00502
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
00541
00542
00543 int fixPriority_;
00544 };
00545
00550 class CbcSerendipity : public CbcHeuristic {
00551 public:
00552
00553
00554 CbcSerendipity ();
00555
00556
00557
00558 CbcSerendipity (CbcModel & model);
00559
00560
00561 CbcSerendipity ( const CbcSerendipity &);
00562
00563
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
00603 CbcHeuristicJustOne ();
00604
00605
00606 CbcHeuristicJustOne (CbcModel & model);
00607
00608
00609 CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00610
00611
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* ,
00644 const double* ,
00645 int& ,
00646 int& ) {
00647 return true;
00648 }
00650 virtual void validate();
00652 void addHeuristic(const CbcHeuristic * heuristic, double probability);
00654 void normalizeProbabilities();
00655 protected:
00656
00657
00658
00659 double * probabilities_;
00660
00661
00662 CbcHeuristic ** heuristic_;
00663
00664
00665 int numberHeuristics_;
00666
00667 };
00668
00669 #endif
00670