/home/coin/SVN-release/Cbc-2.4.0/Cbc/src/CbcHeuristic.hpp

Go to the documentation of this file.
00001 /* $Id: CbcHeuristic.hpp 1271 2009-11-05 15:57:25Z forrest $ */
00002 // Copyright (C) 2002, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
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   // Default Constructor 
00078   CbcHeuristic ();
00079 
00080   // Constructor with model - assumed before cuts
00081   CbcHeuristic (CbcModel & model);
00082 
00083   // Copy constructor 
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 & /*objectiveValue*/,
00116                        double * /*newSolution*/,
00117                        OsiCuts & /*cs*/) {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   /* Runs if bit set
00219       0 - before cuts at root node (or from doHeuristics)
00220       1 - during cuts at root 
00221       2 - after root node cuts
00222       3 - after cuts at other nodes
00223       4 - during cuts at other nodes
00224           8 added if previous heuristic in loop found solution
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   /* Runs if bit set
00302       0 - before cuts at root node (or from doHeuristics)
00303       1 - during cuts at root 
00304       2 - after root node cuts
00305       3 - after cuts at other nodes
00306       4 - during cuts at other nodes
00307           8 added if previous heuristic in loop found solution
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   // Input solution - so can be used as seed
00344   double * inputSolution_;
00345 
00346 
00347 #if 0
00349   double * lowerBoundLastNode_;
00351   double * upperBoundLastNode_;
00352 #endif
00353 };
00357 class CbcRounding : public CbcHeuristic {
00358 public:
00359 
00360   // Default Constructor 
00361   CbcRounding ();
00362 
00363   // Constructor with model - assumed before cuts
00364   CbcRounding (CbcModel & model);
00365   
00366   // Copy constructor 
00367   CbcRounding ( const CbcRounding &);
00368    
00369   // Destructor 
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   // Data
00413 
00414   // Original matrix by column
00415   CoinPackedMatrix matrix_;
00416 
00417   // Original matrix by 
00418   CoinPackedMatrix matrixByRow_;
00419 
00420   // Down locks
00421   unsigned short * down_;
00422 
00423   // Up locks
00424   unsigned short * up_;
00425 
00426   // Equality locks
00427   unsigned short * equal_;
00428 
00429   // Seed for random stuff
00430   int seed_;
00431 };
00432 
00438 class CbcHeuristicPartial : public CbcHeuristic {
00439 public:
00440 
00441   // Default Constructor 
00442   CbcHeuristicPartial ();
00443 
00448   CbcHeuristicPartial (CbcModel & model, int fixPriority=10000, int numberNodes=200);
00449   
00450   // Copy constructor 
00451   CbcHeuristicPartial ( const CbcHeuristicPartial &);
00452    
00453   // Destructor 
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   // Data
00491 
00492   // All variables with abs priority <= this will be fixed
00493   int fixPriority_;
00494 };
00495 
00500 class CbcSerendipity : public CbcHeuristic {
00501 public:
00502 
00503   // Default Constructor 
00504   CbcSerendipity ();
00505 
00506   /* Constructor with model
00507   */
00508   CbcSerendipity (CbcModel & model);
00509   
00510   // Copy constructor 
00511   CbcSerendipity ( const CbcSerendipity &);
00512    
00513   // Destructor 
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   // Default Constructor 
00553   CbcHeuristicJustOne ();
00554 
00555   // Constructor with model - assumed before cuts
00556   CbcHeuristicJustOne (CbcModel & model);
00557   
00558   // Copy constructor 
00559   CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00560    
00561   // Destructor 
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* /*solver*/,
00594                                       const double* /*newSolution*/,
00595                                       int& /*bestColumn*/,
00596                                       int& /*bestRound*/) 
00597   { return true;}
00599   virtual void validate();
00601   void addHeuristic(const CbcHeuristic * heuristic, double probability);
00603   void normalizeProbabilities();
00604 protected:
00605   // Data
00606 
00607   // Probability of running a heuristic
00608   double * probabilities_;
00609 
00610   // Heuristics
00611   CbcHeuristic ** heuristic_;
00612 
00613   // Number of heuristics
00614   int numberHeuristics_;
00615 
00616 };
00617 
00618 #endif

Generated on Tue Jan 19 03:02:15 2010 by  doxygen 1.4.7