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 { return nodes_[i]; }
00065 inline int size() const { return nodes_.size(); }
00066 };
00067
00068
00071 class CbcHeuristic {
00072 private:
00073 void gutsOfDelete() {}
00074 void gutsOfCopy(const CbcHeuristic & rhs);
00075
00076 public:
00077
00078 CbcHeuristic ();
00079
00080
00081 CbcHeuristic (CbcModel & model);
00082
00083
00084 CbcHeuristic ( const CbcHeuristic &);
00085
00086 virtual ~CbcHeuristic();
00087
00089 virtual CbcHeuristic * clone() const=0;
00090
00092 CbcHeuristic & operator=(const CbcHeuristic& rhs);
00093
00095 virtual void setModel(CbcModel * model);
00096
00098 virtual void resetModel(CbcModel * model)=0;
00099
00105 virtual int solution(double & objectiveValue,
00106 double * newSolution)=0;
00107
00115 virtual int solution2(double & ,
00116 double * ,
00117 OsiCuts & ) {return 0;}
00118
00120 virtual void validate() {}
00121
00126 inline void setWhen(int value)
00127 { when_=value;}
00129 inline int when() const
00130 { return when_;}
00131
00133 inline void setNumberNodes(int value)
00134 { numberNodes_=value;}
00136 inline int numberNodes() const
00137 { return numberNodes_;}
00147 inline void setSwitches(int value)
00148 { switches_ = value;}
00158 inline int switches() const
00159 { return switches_;}
00161 bool exitNow(double bestObjective) const;
00163 inline void setFeasibilityPumpOptions(int value)
00164 { feasibilityPumpOptions_=value;}
00166 inline int feasibilityPumpOptions() const
00167 { return feasibilityPumpOptions_;}
00169 inline void setModelOnly(CbcModel * model)
00170 { model_ = model;}
00171
00172
00174 inline void setFractionSmall(double value)
00175 { fractionSmall_=value;}
00177 inline double fractionSmall() const
00178 { return fractionSmall_;}
00180 inline int numberSolutionsFound() const
00181 { return numberSolutionsFound_;}
00183 inline void incrementNumberSolutionsFound()
00184 { numberSolutionsFound_++;}
00185
00195 int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
00196 double * newSolution, double & newSolutionValue,
00197 double cutoff , std::string name) const;
00199 virtual void generateCpp( FILE * ) {}
00201 void generateCpp( FILE * fp,const char * heuristic) ;
00203 virtual bool canDealWithOdd() const
00204 { return false;}
00206 inline const char *heuristicName() const
00207 { return heuristicName_.c_str();}
00209 inline void setHeuristicName(const char *name)
00210 { heuristicName_ = name;}
00212 void setSeed(int value);
00214 inline void setDecayFactor(double value)
00215 { decayFactor_=value;}
00217 void setInputSolution(const double * solution, double objValue);
00218
00219
00220
00221
00222
00223
00224
00225
00226 inline void setWhereFrom(int value)
00227 { whereFrom_=value;}
00234 inline void setShallowDepth(int value)
00235 { shallowDepth_=value;}
00237 inline void setHowOftenShallow(int value)
00238 { howOftenShallow_=value;}
00242 inline void setMinDistanceToRun(int value)
00243 { minDistanceToRun_=value;}
00244
00253 virtual bool shouldHeurRun(int whereFrom);
00255 bool shouldHeurRun_randomChoice();
00256 void debugNodes();
00257 void printDistanceToNodes();
00259 inline int numRuns() const
00260 { return numRuns_;}
00261
00263 inline int numCouldRun() const
00264 { return numCouldRun_;}
00269 OsiSolverInterface * cloneBut(int type);
00270 protected:
00271
00273 CbcModel * model_;
00275 int when_;
00277 int numberNodes_;
00279 int feasibilityPumpOptions_;
00281 mutable double fractionSmall_;
00283 CoinThreadRandom randomNumberGenerator_;
00285 std::string heuristicName_;
00286
00288 int howOften_;
00290 double decayFactor_;
00300 mutable int switches_;
00301
00302
00303
00304
00305
00306
00307
00308
00309 int whereFrom_;
00316 int shallowDepth_;
00318 int howOftenShallow_;
00321 int numInvocationsInShallow_;
00324 int numInvocationsInDeep_;
00326 int lastRunDeep_;
00328 int numRuns_;
00332 int minDistanceToRun_;
00333
00335 CbcHeuristicNodeList runNodes_;
00336
00338 int numCouldRun_;
00339
00341 int numberSolutionsFound_;
00342
00343
00344 double * inputSolution_;
00345
00346
00347 #if 0
00348
00349 double * lowerBoundLastNode_;
00351 double * upperBoundLastNode_;
00352 #endif
00353 };
00357 class CbcRounding : public CbcHeuristic {
00358 public:
00359
00360
00361 CbcRounding ();
00362
00363
00364 CbcRounding (CbcModel & model);
00365
00366
00367 CbcRounding ( const CbcRounding &);
00368
00369
00370 ~CbcRounding ();
00371
00373 CbcRounding & operator=(const CbcRounding& rhs);
00374
00376 virtual CbcHeuristic * clone() const;
00378 virtual void generateCpp( FILE * fp) ;
00379
00381 virtual void resetModel(CbcModel * model);
00382
00384 virtual void setModel(CbcModel * model);
00385
00386 using CbcHeuristic::solution ;
00392 virtual int solution(double & objectiveValue,
00393 double * newSolution);
00400 virtual int solution(double & objectiveValue,
00401 double * newSolution,
00402 double solutionValue);
00404 virtual void validate();
00405
00406
00408 void setSeed(int value)
00409 { seed_ = value;}
00410
00411 protected:
00412
00413
00414
00415 CoinPackedMatrix matrix_;
00416
00417
00418 CoinPackedMatrix matrixByRow_;
00419
00420
00421 unsigned short * down_;
00422
00423
00424 unsigned short * up_;
00425
00426
00427 unsigned short * equal_;
00428
00429
00430 int seed_;
00431 };
00432
00438 class CbcHeuristicPartial : public CbcHeuristic {
00439 public:
00440
00441
00442 CbcHeuristicPartial ();
00443
00448 CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
00449
00450
00451 CbcHeuristicPartial ( const CbcHeuristicPartial &);
00452
00453
00454 ~CbcHeuristicPartial ();
00455
00457 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00458
00460 virtual CbcHeuristic * clone() const;
00462 virtual void generateCpp( FILE * fp) ;
00463
00465 virtual void resetModel(CbcModel * model);
00466
00468 virtual void setModel(CbcModel * model);
00469
00470 using CbcHeuristic::solution ;
00476 virtual int solution(double & objectiveValue,
00477 double * newSolution);
00479 virtual void validate();
00480
00481
00483 void setFixPriority(int value)
00484 { fixPriority_ = value;}
00485
00487 virtual bool shouldHeurRun(int whereFrom);
00488
00489 protected:
00490
00491
00492
00493 int fixPriority_;
00494 };
00495
00500 class CbcSerendipity : public CbcHeuristic {
00501 public:
00502
00503
00504 CbcSerendipity ();
00505
00506
00507
00508 CbcSerendipity (CbcModel & model);
00509
00510
00511 CbcSerendipity ( const CbcSerendipity &);
00512
00513
00514 ~CbcSerendipity ();
00515
00517 CbcSerendipity & operator=(const CbcSerendipity& rhs);
00518
00520 virtual CbcHeuristic * clone() const;
00522 virtual void generateCpp( FILE * fp) ;
00523
00525 virtual void setModel(CbcModel * model);
00526
00527 using CbcHeuristic::solution ;
00538 virtual int solution(double & objectiveValue,
00539 double * newSolution);
00541 virtual void resetModel(CbcModel * model);
00542
00543 protected:
00544 };
00545
00549 class CbcHeuristicJustOne : public CbcHeuristic {
00550 public:
00551
00552
00553 CbcHeuristicJustOne ();
00554
00555
00556 CbcHeuristicJustOne (CbcModel & model);
00557
00558
00559 CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00560
00561
00562 ~CbcHeuristicJustOne ();
00563
00565 virtual CbcHeuristicJustOne * clone() const;
00566
00568 CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00569
00571 virtual void generateCpp( FILE * fp) ;
00572
00579 virtual int solution(double & objectiveValue,
00580 double * newSolution);
00582 virtual void resetModel(CbcModel * model);
00583
00585 virtual void setModel(CbcModel * model);
00587
00593 virtual bool selectVariableToBranch(OsiSolverInterface* ,
00594 const double* ,
00595 int& ,
00596 int& )
00597 { return true;}
00599 virtual void validate();
00601 void addHeuristic(const CbcHeuristic * heuristic, double probability);
00603 void normalizeProbabilities();
00604 protected:
00605
00606
00607
00608 double * probabilities_;
00609
00610
00611 CbcHeuristic ** heuristic_;
00612
00613
00614 int numberHeuristics_;
00615
00616 };
00617
00618 #endif