CbcHeuristic.hpp

Go to the documentation of this file.
00001 /* $Id: CbcHeuristic.hpp 1883 2013-04-06 13:33:15Z stefan $ */
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     int getSeed() const;
00242     inline void setDecayFactor(double value) {
00243         decayFactor_ = value;
00244     }
00246     void setInputSolution(const double * solution, double objValue);
00247     /* Runs if bit set
00248         0 - before cuts at root node (or from doHeuristics)
00249         1 - during cuts at root
00250         2 - after root node cuts
00251         3 - after cuts at other nodes
00252         4 - during cuts at other nodes
00253             8 added if previous heuristic in loop found solution
00254      */
00255     inline void setWhereFrom(int value) {
00256         whereFrom_ = value;
00257     }
00258     inline int whereFrom() const {
00259         return whereFrom_;
00260     }
00267     inline void setShallowDepth(int value) {
00268         shallowDepth_ = value;
00269     }
00271     inline void setHowOftenShallow(int value) {
00272         howOftenShallow_ = value;
00273     }
00277     inline void setMinDistanceToRun(int value) {
00278         minDistanceToRun_ = value;
00279     }
00280 
00289     virtual bool shouldHeurRun(int whereFrom);
00291     bool shouldHeurRun_randomChoice();
00292     void debugNodes();
00293     void printDistanceToNodes();
00295     inline int numRuns() const {
00296         return numRuns_;
00297     }
00298 
00300     inline int numCouldRun() const {
00301         return numCouldRun_;
00302     }
00311     OsiSolverInterface * cloneBut(int type);
00312 protected:
00313 
00315     CbcModel * model_;
00317     int when_;
00319     int numberNodes_;
00325     int feasibilityPumpOptions_;
00327     mutable double fractionSmall_;
00329     CoinThreadRandom randomNumberGenerator_;
00331     std::string heuristicName_;
00332 
00334     int howOften_;
00336     double decayFactor_;
00347     mutable int switches_;
00348     /* Runs if bit set
00349         0 - before cuts at root node (or from doHeuristics)
00350         1 - during cuts at root
00351         2 - after root node cuts
00352         3 - after cuts at other nodes
00353         4 - during cuts at other nodes
00354             8 added if previous heuristic in loop found solution
00355      */
00356     int whereFrom_;
00363     int shallowDepth_;
00365     int howOftenShallow_;
00368     int numInvocationsInShallow_;
00371     int numInvocationsInDeep_;
00373     int lastRunDeep_;
00375     int numRuns_;
00379     int minDistanceToRun_;
00380 
00382     CbcHeuristicNodeList runNodes_;
00383 
00385     int numCouldRun_;
00386 
00388     int numberSolutionsFound_;
00389 
00391     mutable int numberNodesDone_;
00392 
00393     // Input solution - so can be used as seed
00394     double * inputSolution_;
00395 
00396 
00397 #ifdef JJF_ZERO
00399     double * lowerBoundLastNode_;
00401     double * upperBoundLastNode_;
00402 #endif
00403 };
00407 class CbcRounding : public CbcHeuristic {
00408 public:
00409 
00410     // Default Constructor
00411     CbcRounding ();
00412 
00413     // Constructor with model - assumed before cuts
00414     CbcRounding (CbcModel & model);
00415 
00416     // Copy constructor
00417     CbcRounding ( const CbcRounding &);
00418 
00419     // Destructor
00420     ~CbcRounding ();
00421 
00423     CbcRounding & operator=(const CbcRounding& rhs);
00424 
00426     virtual CbcHeuristic * clone() const;
00428     virtual void generateCpp( FILE * fp) ;
00429 
00431     virtual void resetModel(CbcModel * model);
00432 
00434     virtual void setModel(CbcModel * model);
00435 
00436     using CbcHeuristic::solution ;
00442     virtual int solution(double & objectiveValue,
00443                          double * newSolution);
00450     virtual int solution(double & objectiveValue,
00451                          double * newSolution,
00452                          double solutionValue);
00454     virtual void validate();
00455 
00456 
00458     void setSeed(int value) {
00459         seed_ = value;
00460     }
00461 
00462 protected:
00463     // Data
00464 
00465     // Original matrix by column
00466     CoinPackedMatrix matrix_;
00467 
00468     // Original matrix by
00469     CoinPackedMatrix matrixByRow_;
00470 
00471     // Down locks
00472     unsigned short * down_;
00473 
00474     // Up locks
00475     unsigned short * up_;
00476 
00477     // Equality locks
00478     unsigned short * equal_;
00479 
00480     // Seed for random stuff
00481     int seed_;
00482 };
00483 
00489 class CbcHeuristicPartial : public CbcHeuristic {
00490 public:
00491 
00492     // Default Constructor
00493     CbcHeuristicPartial ();
00494 
00499     CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00500 
00501     // Copy constructor
00502     CbcHeuristicPartial ( const CbcHeuristicPartial &);
00503 
00504     // Destructor
00505     ~CbcHeuristicPartial ();
00506 
00508     CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00509 
00511     virtual CbcHeuristic * clone() const;
00513     virtual void generateCpp( FILE * fp) ;
00514 
00516     virtual void resetModel(CbcModel * model);
00517 
00519     virtual void setModel(CbcModel * model);
00520 
00521     using CbcHeuristic::solution ;
00527     virtual int solution(double & objectiveValue,
00528                          double * newSolution);
00530     virtual void validate();
00531 
00532 
00534     void setFixPriority(int value) {
00535         fixPriority_ = value;
00536     }
00537 
00539     virtual bool shouldHeurRun(int whereFrom);
00540 
00541 protected:
00542     // Data
00543 
00544     // All variables with abs priority <= this will be fixed
00545     int fixPriority_;
00546 };
00547 
00552 class CbcSerendipity : public CbcHeuristic {
00553 public:
00554 
00555     // Default Constructor
00556     CbcSerendipity ();
00557 
00558     /* Constructor with model
00559     */
00560     CbcSerendipity (CbcModel & model);
00561 
00562     // Copy constructor
00563     CbcSerendipity ( const CbcSerendipity &);
00564 
00565     // Destructor
00566     ~CbcSerendipity ();
00567 
00569     CbcSerendipity & operator=(const CbcSerendipity& rhs);
00570 
00572     virtual CbcHeuristic * clone() const;
00574     virtual void generateCpp( FILE * fp) ;
00575 
00577     virtual void setModel(CbcModel * model);
00578 
00579     using CbcHeuristic::solution ;
00590     virtual int solution(double & objectiveValue,
00591                          double * newSolution);
00593     virtual void resetModel(CbcModel * model);
00594 
00595 protected:
00596 };
00597 
00601 class CbcHeuristicJustOne : public CbcHeuristic {
00602 public:
00603 
00604     // Default Constructor
00605     CbcHeuristicJustOne ();
00606 
00607     // Constructor with model - assumed before cuts
00608     CbcHeuristicJustOne (CbcModel & model);
00609 
00610     // Copy constructor
00611     CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00612 
00613     // Destructor
00614     ~CbcHeuristicJustOne ();
00615 
00617     virtual CbcHeuristicJustOne * clone() const;
00618 
00620     CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00621 
00623     virtual void generateCpp( FILE * fp) ;
00624 
00631     virtual int solution(double & objectiveValue,
00632                          double * newSolution);
00634     virtual void resetModel(CbcModel * model);
00635 
00637     virtual void setModel(CbcModel * model);
00639 
00645     virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
00646                                         const double* /*newSolution*/,
00647                                         int& /*bestColumn*/,
00648                                         int& /*bestRound*/) {
00649         return true;
00650     }
00652     virtual void validate();
00654     void addHeuristic(const CbcHeuristic * heuristic, double probability);
00656     void normalizeProbabilities();
00657 protected:
00658     // Data
00659 
00660     // Probability of running a heuristic
00661     double * probabilities_;
00662 
00663     // Heuristics
00664     CbcHeuristic ** heuristic_;
00665 
00666     // Number of heuristics
00667     int numberHeuristics_;
00668 
00669 };
00670 
00671 #endif
00672 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on 27 Apr 2013 for Cbc by  doxygen 1.6.1