Cbc  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
CbcHeuristic.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 // Copyright (C) 2002, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 // This code is licensed under the terms of the Eclipse Public License (EPL).
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     // Default Constructor
00084     CbcHeuristic ();
00085 
00086     // Constructor with model - assumed before cuts
00087     CbcHeuristic (CbcModel & model);
00088 
00089     // Copy constructor
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 & /*objectiveValue*/,
00122                           double * /*newSolution*/,
00123                           OsiCuts & /*cs*/) {
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     /* Runs if bit set
00246         0 - before cuts at root node (or from doHeuristics)
00247         1 - during cuts at root
00248         2 - after root node cuts
00249         3 - after cuts at other nodes
00250         4 - during cuts at other nodes
00251             8 added if previous heuristic in loop found solution
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     /* Runs if bit set
00347         0 - before cuts at root node (or from doHeuristics)
00348         1 - during cuts at root
00349         2 - after root node cuts
00350         3 - after cuts at other nodes
00351         4 - during cuts at other nodes
00352             8 added if previous heuristic in loop found solution
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     // Input solution - so can be used as seed
00392     double * inputSolution_;
00393 
00394 
00395 #ifdef JJF_ZERO
00396 
00397     double * lowerBoundLastNode_;
00399     double * upperBoundLastNode_;
00400 #endif
00401 };
00405 class CbcRounding : public CbcHeuristic {
00406 public:
00407 
00408     // Default Constructor
00409     CbcRounding ();
00410 
00411     // Constructor with model - assumed before cuts
00412     CbcRounding (CbcModel & model);
00413 
00414     // Copy constructor
00415     CbcRounding ( const CbcRounding &);
00416 
00417     // Destructor
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     // Data
00462 
00463     // Original matrix by column
00464     CoinPackedMatrix matrix_;
00465 
00466     // Original matrix by
00467     CoinPackedMatrix matrixByRow_;
00468 
00469     // Down locks
00470     unsigned short * down_;
00471 
00472     // Up locks
00473     unsigned short * up_;
00474 
00475     // Equality locks
00476     unsigned short * equal_;
00477 
00478     // Seed for random stuff
00479     int seed_;
00480 };
00481 
00487 class CbcHeuristicPartial : public CbcHeuristic {
00488 public:
00489 
00490     // Default Constructor
00491     CbcHeuristicPartial ();
00492 
00497     CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00498 
00499     // Copy constructor
00500     CbcHeuristicPartial ( const CbcHeuristicPartial &);
00501 
00502     // Destructor
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     // Data
00541 
00542     // All variables with abs priority <= this will be fixed
00543     int fixPriority_;
00544 };
00545 
00550 class CbcSerendipity : public CbcHeuristic {
00551 public:
00552 
00553     // Default Constructor
00554     CbcSerendipity ();
00555 
00556     /* Constructor with model
00557     */
00558     CbcSerendipity (CbcModel & model);
00559 
00560     // Copy constructor
00561     CbcSerendipity ( const CbcSerendipity &);
00562 
00563     // Destructor
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     // Default Constructor
00603     CbcHeuristicJustOne ();
00604 
00605     // Constructor with model - assumed before cuts
00606     CbcHeuristicJustOne (CbcModel & model);
00607 
00608     // Copy constructor
00609     CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00610 
00611     // Destructor
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* /*solver*/,
00644                                         const double* /*newSolution*/,
00645                                         int& /*bestColumn*/,
00646                                         int& /*bestRound*/) {
00647         return true;
00648     }
00650     virtual void validate();
00652     void addHeuristic(const CbcHeuristic * heuristic, double probability);
00654     void normalizeProbabilities();
00655 protected:
00656     // Data
00657 
00658     // Probability of running a heuristic
00659     double * probabilities_;
00660 
00661     // Heuristics
00662     CbcHeuristic ** heuristic_;
00663 
00664     // Number of heuristics
00665     int numberHeuristics_;
00666 
00667 };
00668 
00669 #endif
00670 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines