00001
00002
00003 #ifndef CbcHeuristic_H
00004 #define CbcHeuristic_H
00005
00006 #include <string>
00007 #include <vector>
00008 #include "CoinPackedMatrix.hpp"
00009 #include "OsiCuts.hpp"
00010 #include "CoinHelperFunctions.hpp"
00011 #include "OsiBranchingObject.hpp"
00012
00013 class OsiSolverInterface;
00014
00015 class CbcModel;
00016
00017
00018
00019 class CbcHeuristicNodeList;
00020 class CbcBranchingObject;
00021
00025 class CbcHeuristicNode {
00026 private:
00027 void gutsOfConstructor(CbcModel& model);
00028 CbcHeuristicNode();
00029 CbcHeuristicNode& operator=(const CbcHeuristicNode&);
00030 private:
00032 int numObjects_;
00036 CbcBranchingObject** brObj_;
00037 public:
00038 CbcHeuristicNode(CbcModel& model);
00039
00040 CbcHeuristicNode(const CbcHeuristicNode& rhs);
00041 ~CbcHeuristicNode();
00042 double distance(const CbcHeuristicNode* node) const;
00043 double minDistance(const CbcHeuristicNodeList& nodeList) const;
00044 bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
00045 const double threshold) const;
00046 double avgDistance(const CbcHeuristicNodeList& nodeList) const;
00047 };
00048
00049 class CbcHeuristicNodeList {
00050 private:
00051 void gutsOfDelete();
00052 void gutsOfCopy(const CbcHeuristicNodeList& rhs);
00053 private:
00054 std::vector<CbcHeuristicNode*> nodes_;
00055 public:
00056 CbcHeuristicNodeList() {}
00057 CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
00058 CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
00059 ~CbcHeuristicNodeList();
00060
00061 void append(CbcHeuristicNode*& node);
00062 void append(const CbcHeuristicNodeList& nodes);
00063 inline const CbcHeuristicNode* node(int i) const { return nodes_[i]; }
00064 inline int size() const { return nodes_.size(); }
00065 };
00066
00067
00070 class CbcHeuristic {
00071 private:
00072 void gutsOfDelete() {}
00073 void gutsOfCopy(const CbcHeuristic & rhs);
00074
00075 public:
00076
00077 CbcHeuristic ();
00078
00079
00080 CbcHeuristic (CbcModel & model);
00081
00082
00083 CbcHeuristic ( const CbcHeuristic &);
00084
00085 virtual ~CbcHeuristic();
00086
00088 virtual CbcHeuristic * clone() const=0;
00089
00091 CbcHeuristic & operator=(const CbcHeuristic& rhs);
00092
00094 virtual void setModel(CbcModel * model);
00095
00097 virtual void resetModel(CbcModel * model)=0;
00098
00104 virtual int solution(double & objectiveValue,
00105 double * newSolution)=0;
00106
00114 virtual int solution(double & objectiveValue,
00115 double * newSolution,
00116 OsiCuts & cs) {return 0;}
00117
00119 virtual void validate() {}
00120
00125 inline void setWhen(int value)
00126 { when_=value;}
00128 inline int when() const
00129 { return when_;}
00130
00132 inline void setNumberNodes(int value)
00133 { numberNodes_=value;}
00135 inline int numberNodes() const
00136 { return numberNodes_;}
00142 inline void setSwitches(int value)
00143 { switches_ = value;}
00149 inline int switches() const
00150 { return switches_;}
00152 bool exitNow(double bestObjective) const;
00154 inline void setFeasibilityPumpOptions(int value)
00155 { feasibilityPumpOptions_=value;}
00157 inline int feasibilityPumpOptions() const
00158 { return feasibilityPumpOptions_;}
00160 inline void setModelOnly(CbcModel * model)
00161 { model_ = model;}
00162
00163
00165 inline void setFractionSmall(double value)
00166 { fractionSmall_=value;}
00168 inline double fractionSmall() const
00169 { return fractionSmall_;}
00171 inline int numberSolutionsFound() const
00172 { return numberSolutionsFound_;}
00174 inline void incrementNumberSolutionsFound()
00175 { numberSolutionsFound_++;}
00176
00186 int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
00187 double * newSolution, double & newSolutionValue,
00188 double cutoff , std::string name) const;
00190 virtual void generateCpp( FILE * fp) {}
00192 void generateCpp( FILE * fp,const char * heuristic) ;
00194 virtual bool canDealWithOdd() const
00195 { return false;}
00197 inline const char *heuristicName() const
00198 { return heuristicName_.c_str();}
00200 inline void setHeuristicName(const char *name)
00201 { heuristicName_ = name;}
00203 void setSeed(int value);
00205 void setInputSolution(const double * solution, double objValue);
00206
00208 virtual bool shouldHeurRun();
00210 bool shouldHeurRun_randomChoice();
00211 void debugNodes();
00212 void printDistanceToNodes();
00214 inline int numRuns() const
00215 { return numRuns_;}
00216
00218 inline int numCouldRun() const
00219 { return numCouldRun_;}
00220
00221 protected:
00222
00224 CbcModel * model_;
00226 int when_;
00228 int numberNodes_;
00230 int feasibilityPumpOptions_;
00232 mutable double fractionSmall_;
00234 CoinThreadRandom randomNumberGenerator_;
00236 std::string heuristicName_;
00237
00239 int howOften_;
00241 double decayFactor_;
00250 int switches_;
00257 int shallowDepth_;
00259 int howOftenShallow_;
00262 int numInvocationsInShallow_;
00265 int numInvocationsInDeep_;
00267 int lastRunDeep_;
00269 int numRuns_;
00273 int minDistanceToRun_;
00274
00276 CbcHeuristicNodeList runNodes_;
00277
00279 int numCouldRun_;
00280
00282 int numberSolutionsFound_;
00283
00284
00285 double * inputSolution_;
00286
00287
00288 #if 0
00290 double * lowerBoundLastNode_;
00292 double * upperBoundLastNode_;
00293 #endif
00294 };
00298 class CbcRounding : public CbcHeuristic {
00299 public:
00300
00301
00302 CbcRounding ();
00303
00304
00305 CbcRounding (CbcModel & model);
00306
00307
00308 CbcRounding ( const CbcRounding &);
00309
00310
00311 ~CbcRounding ();
00312
00314 CbcRounding & operator=(const CbcRounding& rhs);
00315
00317 virtual CbcHeuristic * clone() const;
00319 virtual void generateCpp( FILE * fp) ;
00320
00322 virtual void resetModel(CbcModel * model);
00323
00325 virtual void setModel(CbcModel * model);
00326
00327 using CbcHeuristic::solution ;
00333 virtual int solution(double & objectiveValue,
00334 double * newSolution);
00341 virtual int solution(double & objectiveValue,
00342 double * newSolution,
00343 double solutionValue);
00345 virtual void validate();
00346
00347
00349 void setSeed(int value)
00350 { seed_ = value;}
00351
00352 protected:
00353
00354
00355
00356 CoinPackedMatrix matrix_;
00357
00358
00359 CoinPackedMatrix matrixByRow_;
00360
00361
00362 unsigned short * down_;
00363
00364
00365 unsigned short * up_;
00366
00367
00368 unsigned short * equal_;
00369
00370
00371 int seed_;
00372 };
00373
00379 class CbcHeuristicPartial : public CbcHeuristic {
00380 public:
00381
00382
00383 CbcHeuristicPartial ();
00384
00389 CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
00390
00391
00392 CbcHeuristicPartial ( const CbcHeuristicPartial &);
00393
00394
00395 ~CbcHeuristicPartial ();
00396
00398 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00399
00401 virtual CbcHeuristic * clone() const;
00403 virtual void generateCpp( FILE * fp) ;
00404
00406 virtual void resetModel(CbcModel * model);
00407
00409 virtual void setModel(CbcModel * model);
00410
00411 using CbcHeuristic::solution ;
00417 virtual int solution(double & objectiveValue,
00418 double * newSolution);
00420 virtual void validate();
00421
00422
00424 void setFixPriority(int value)
00425 { fixPriority_ = value;}
00426
00428 virtual bool shouldHeurRun();
00429
00430 protected:
00431
00432
00433
00434 int fixPriority_;
00435 };
00436
00441 class CbcSerendipity : public CbcHeuristic {
00442 public:
00443
00444
00445 CbcSerendipity ();
00446
00447
00448
00449 CbcSerendipity (CbcModel & model);
00450
00451
00452 CbcSerendipity ( const CbcSerendipity &);
00453
00454
00455 ~CbcSerendipity ();
00456
00458 CbcSerendipity & operator=(const CbcSerendipity& rhs);
00459
00461 virtual CbcHeuristic * clone() const;
00463 virtual void generateCpp( FILE * fp) ;
00464
00466 virtual void setModel(CbcModel * model);
00467
00468 using CbcHeuristic::solution ;
00479 virtual int solution(double & objectiveValue,
00480 double * newSolution);
00482 virtual void resetModel(CbcModel * model);
00483
00484 protected:
00485 };
00486
00490 class CbcHeuristicJustOne : public CbcHeuristic {
00491 public:
00492
00493
00494 CbcHeuristicJustOne ();
00495
00496
00497 CbcHeuristicJustOne (CbcModel & model);
00498
00499
00500 CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00501
00502
00503 ~CbcHeuristicJustOne ();
00504
00506 virtual CbcHeuristicJustOne * clone() const;
00507
00509 CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00510
00512 virtual void generateCpp( FILE * fp) ;
00513
00520 virtual int solution(double & objectiveValue,
00521 double * newSolution);
00523 virtual void resetModel(CbcModel * model);
00524
00526 virtual void setModel(CbcModel * model);
00528
00534 virtual bool selectVariableToBranch(OsiSolverInterface* solver,
00535 const double* newSolution,
00536 int& bestColumn,
00537 int& bestRound)
00538 { return true;}
00540 virtual void validate();
00542 void addHeuristic(const CbcHeuristic * heuristic, double probability);
00544 void normalizeProbabilities();
00545 protected:
00546
00547
00548
00549 double * probabilities_;
00550
00551
00552 CbcHeuristic ** heuristic_;
00553
00554
00555 int numberHeuristics_;
00556
00557 };
00558
00559 #endif