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_;}
00138 inline void setFeasibilityPumpOptions(int value)
00139 { feasibilityPumpOptions_=value;}
00141 inline int feasibilityPumpOptions() const
00142 { return feasibilityPumpOptions_;}
00144 inline void setModelOnly(CbcModel * model)
00145 { model_ = model;}
00146
00147
00149 inline void setFractionSmall(double value)
00150 { fractionSmall_=value;}
00152 inline double fractionSmall() const
00153 { return fractionSmall_;}
00154
00162 int smallBranchAndBound(OsiSolverInterface * solver,int numberNodes,
00163 double * newSolution, double & newSolutionValue,
00164 double cutoff , std::string name) const;
00166 virtual void generateCpp( FILE * fp) {}
00168 void generateCpp( FILE * fp,const char * heuristic) ;
00170 virtual bool canDealWithOdd() const
00171 { return false;}
00173 inline const char *heuristicName() const
00174 { return heuristicName_.c_str();}
00176 inline void setHeuristicName(const char *name)
00177 { heuristicName_ = name;}
00179 void setSeed(int value);
00180
00182 bool shouldHeurRun();
00183 bool shouldHeurRun_randomChoice();
00184 void debugNodes();
00185 void printDistanceToNodes();
00186
00187 protected:
00188
00190 CbcModel * model_;
00192 int when_;
00194 int numberNodes_;
00196 int feasibilityPumpOptions_;
00198 double fractionSmall_;
00200 CoinThreadRandom randomNumberGenerator_;
00202 std::string heuristicName_;
00203
00205 int howOften_;
00207 double decayFactor_;
00214 int shallowDepth_;
00216 int howOftenShallow_;
00219 int numInvocationsInShallow_;
00222 int numInvocationsInDeep_;
00224 int lastRunDeep_;
00226 int numRuns_;
00230 int minDistanceToRun_;
00231
00233 CbcHeuristicNodeList runNodes_;
00234
00236 int numCouldRun_;
00237
00238
00239 #if 0
00241 double * lowerBoundLastNode_;
00243 double * upperBoundLastNode_;
00244 #endif
00245 };
00249 class CbcRounding : public CbcHeuristic {
00250 public:
00251
00252
00253 CbcRounding ();
00254
00255
00256 CbcRounding (CbcModel & model);
00257
00258
00259 CbcRounding ( const CbcRounding &);
00260
00261
00262 ~CbcRounding ();
00263
00265 CbcRounding & operator=(const CbcRounding& rhs);
00266
00268 virtual CbcHeuristic * clone() const;
00270 virtual void generateCpp( FILE * fp) ;
00271
00273 virtual void resetModel(CbcModel * model);
00274
00276 virtual void setModel(CbcModel * model);
00277
00278 using CbcHeuristic::solution ;
00284 virtual int solution(double & objectiveValue,
00285 double * newSolution);
00292 virtual int solution(double & objectiveValue,
00293 double * newSolution,
00294 double solutionValue);
00296 virtual void validate();
00297
00298
00300 void setSeed(int value)
00301 { seed_ = value;}
00302
00303 protected:
00304
00305
00306
00307 CoinPackedMatrix matrix_;
00308
00309
00310 CoinPackedMatrix matrixByRow_;
00311
00312
00313 unsigned short * down_;
00314
00315
00316 unsigned short * up_;
00317
00318
00319 unsigned short * equal_;
00320
00321
00322 int seed_;
00323 };
00324
00330 class CbcHeuristicPartial : public CbcHeuristic {
00331 public:
00332
00333
00334 CbcHeuristicPartial ();
00335
00340 CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
00341
00342
00343 CbcHeuristicPartial ( const CbcHeuristicPartial &);
00344
00345
00346 ~CbcHeuristicPartial ();
00347
00349 CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00350
00352 virtual CbcHeuristic * clone() const;
00354 virtual void generateCpp( FILE * fp) ;
00355
00357 virtual void resetModel(CbcModel * model);
00358
00360 virtual void setModel(CbcModel * model);
00361
00362 using CbcHeuristic::solution ;
00368 virtual int solution(double & objectiveValue,
00369 double * newSolution);
00371 virtual void validate();
00372
00373
00375 void setFixPriority(int value)
00376 { fixPriority_ = value;}
00377
00378 protected:
00379
00380
00381
00382 int fixPriority_;
00383 };
00384
00389 class CbcSerendipity : public CbcHeuristic {
00390 public:
00391
00392
00393 CbcSerendipity ();
00394
00395
00396
00397 CbcSerendipity (CbcModel & model);
00398
00399
00400 CbcSerendipity ( const CbcSerendipity &);
00401
00402
00403 ~CbcSerendipity ();
00404
00406 CbcSerendipity & operator=(const CbcSerendipity& rhs);
00407
00409 virtual CbcHeuristic * clone() const;
00411 virtual void generateCpp( FILE * fp) ;
00412
00414 virtual void setModel(CbcModel * model);
00415
00416 using CbcHeuristic::solution ;
00427 virtual int solution(double & objectiveValue,
00428 double * newSolution);
00430 virtual void resetModel(CbcModel * model);
00431
00432 protected:
00433 };
00434
00435 #endif