Cbc trunk
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     }
00159     inline void setSwitches(int value) {
00160         switches_ = value;
00161     }
00171     inline int switches() const {
00172         return switches_;
00173     }
00175     bool exitNow(double bestObjective) const;
00177     inline void setFeasibilityPumpOptions(int value) {
00178         feasibilityPumpOptions_ = value;
00179     }
00181     inline int feasibilityPumpOptions() const {
00182         return feasibilityPumpOptions_;
00183     }
00185     inline void setModelOnly(CbcModel * model) {
00186         model_ = model;
00187     }
00188 
00189 
00191     inline void setFractionSmall(double value) {
00192         fractionSmall_ = value;
00193     }
00195     inline double fractionSmall() const {
00196         return fractionSmall_;
00197     }
00199     inline int numberSolutionsFound() const {
00200         return numberSolutionsFound_;
00201     }
00203     inline void incrementNumberSolutionsFound() {
00204         numberSolutionsFound_++;
00205     }
00206 
00216     int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
00217                             double * newSolution, double & newSolutionValue,
00218                             double cutoff , std::string name) const;
00220     virtual void generateCpp( FILE * ) {}
00222     void generateCpp( FILE * fp, const char * heuristic) ;
00224     virtual bool canDealWithOdd() const {
00225         return false;
00226     }
00228     inline const char *heuristicName() const {
00229         return heuristicName_.c_str();
00230     }
00232     inline void setHeuristicName(const char *name) {
00233         heuristicName_ = name;
00234     }
00236     void setSeed(int value);
00238     inline void setDecayFactor(double value) {
00239         decayFactor_ = value;
00240     }
00242     void setInputSolution(const double * solution, double objValue);
00243     /* Runs if bit set
00244         0 - before cuts at root node (or from doHeuristics)
00245         1 - during cuts at root
00246         2 - after root node cuts
00247         3 - after cuts at other nodes
00248         4 - during cuts at other nodes
00249             8 added if previous heuristic in loop found solution
00250      */
00251     inline void setWhereFrom(int value) {
00252         whereFrom_ = value;
00253     }
00254     inline int whereFrom() const {
00255         return whereFrom_;
00256     }
00263     inline void setShallowDepth(int value) {
00264         shallowDepth_ = value;
00265     }
00267     inline void setHowOftenShallow(int value) {
00268         howOftenShallow_ = value;
00269     }
00273     inline void setMinDistanceToRun(int value) {
00274         minDistanceToRun_ = value;
00275     }
00276 
00285     virtual bool shouldHeurRun(int whereFrom);
00287     bool shouldHeurRun_randomChoice();
00288     void debugNodes();
00289     void printDistanceToNodes();
00291     inline int numRuns() const {
00292         return numRuns_;
00293     }
00294 
00296     inline int numCouldRun() const {
00297         return numCouldRun_;
00298     }
00307     OsiSolverInterface * cloneBut(int type);
00308 protected:
00309 
00311     CbcModel * model_;
00313     int when_;
00315     int numberNodes_;
00317     int feasibilityPumpOptions_;
00319     mutable double fractionSmall_;
00321     CoinThreadRandom randomNumberGenerator_;
00323     std::string heuristicName_;
00324 
00326     int howOften_;
00328     double decayFactor_;
00338     mutable int switches_;
00339     /* Runs if bit set
00340         0 - before cuts at root node (or from doHeuristics)
00341         1 - during cuts at root
00342         2 - after root node cuts
00343         3 - after cuts at other nodes
00344         4 - during cuts at other nodes
00345             8 added if previous heuristic in loop found solution
00346      */
00347     int whereFrom_;
00354     int shallowDepth_;
00356     int howOftenShallow_;
00359     int numInvocationsInShallow_;
00362     int numInvocationsInDeep_;
00364     int lastRunDeep_;
00366     int numRuns_;
00370     int minDistanceToRun_;
00371 
00373     CbcHeuristicNodeList runNodes_;
00374 
00376     int numCouldRun_;
00377 
00379     int numberSolutionsFound_;
00380 
00381     // Input solution - so can be used as seed
00382     double * inputSolution_;
00383 
00384 
00385 #ifdef JJF_ZERO
00386 
00387     double * lowerBoundLastNode_;
00389     double * upperBoundLastNode_;
00390 #endif
00391 };
00395 class CbcRounding : public CbcHeuristic {
00396 public:
00397 
00398     // Default Constructor
00399     CbcRounding ();
00400 
00401     // Constructor with model - assumed before cuts
00402     CbcRounding (CbcModel & model);
00403 
00404     // Copy constructor
00405     CbcRounding ( const CbcRounding &);
00406 
00407     // Destructor
00408     ~CbcRounding ();
00409 
00411     CbcRounding & operator=(const CbcRounding& rhs);
00412 
00414     virtual CbcHeuristic * clone() const;
00416     virtual void generateCpp( FILE * fp) ;
00417 
00419     virtual void resetModel(CbcModel * model);
00420 
00422     virtual void setModel(CbcModel * model);
00423 
00424     using CbcHeuristic::solution ;
00430     virtual int solution(double & objectiveValue,
00431                          double * newSolution);
00438     virtual int solution(double & objectiveValue,
00439                          double * newSolution,
00440                          double solutionValue);
00442     virtual void validate();
00443 
00444 
00446     void setSeed(int value) {
00447         seed_ = value;
00448     }
00449 
00450 protected:
00451     // Data
00452 
00453     // Original matrix by column
00454     CoinPackedMatrix matrix_;
00455 
00456     // Original matrix by
00457     CoinPackedMatrix matrixByRow_;
00458 
00459     // Down locks
00460     unsigned short * down_;
00461 
00462     // Up locks
00463     unsigned short * up_;
00464 
00465     // Equality locks
00466     unsigned short * equal_;
00467 
00468     // Seed for random stuff
00469     int seed_;
00470 };
00471 
00477 class CbcHeuristicPartial : public CbcHeuristic {
00478 public:
00479 
00480     // Default Constructor
00481     CbcHeuristicPartial ();
00482 
00487     CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00488 
00489     // Copy constructor
00490     CbcHeuristicPartial ( const CbcHeuristicPartial &);
00491 
00492     // Destructor
00493     ~CbcHeuristicPartial ();
00494 
00496     CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00497 
00499     virtual CbcHeuristic * clone() const;
00501     virtual void generateCpp( FILE * fp) ;
00502 
00504     virtual void resetModel(CbcModel * model);
00505 
00507     virtual void setModel(CbcModel * model);
00508 
00509     using CbcHeuristic::solution ;
00515     virtual int solution(double & objectiveValue,
00516                          double * newSolution);
00518     virtual void validate();
00519 
00520 
00522     void setFixPriority(int value) {
00523         fixPriority_ = value;
00524     }
00525 
00527     virtual bool shouldHeurRun(int whereFrom);
00528 
00529 protected:
00530     // Data
00531 
00532     // All variables with abs priority <= this will be fixed
00533     int fixPriority_;
00534 };
00535 
00540 class CbcSerendipity : public CbcHeuristic {
00541 public:
00542 
00543     // Default Constructor
00544     CbcSerendipity ();
00545 
00546     /* Constructor with model
00547     */
00548     CbcSerendipity (CbcModel & model);
00549 
00550     // Copy constructor
00551     CbcSerendipity ( const CbcSerendipity &);
00552 
00553     // Destructor
00554     ~CbcSerendipity ();
00555 
00557     CbcSerendipity & operator=(const CbcSerendipity& rhs);
00558 
00560     virtual CbcHeuristic * clone() const;
00562     virtual void generateCpp( FILE * fp) ;
00563 
00565     virtual void setModel(CbcModel * model);
00566 
00567     using CbcHeuristic::solution ;
00578     virtual int solution(double & objectiveValue,
00579                          double * newSolution);
00581     virtual void resetModel(CbcModel * model);
00582 
00583 protected:
00584 };
00585 
00589 class CbcHeuristicJustOne : public CbcHeuristic {
00590 public:
00591 
00592     // Default Constructor
00593     CbcHeuristicJustOne ();
00594 
00595     // Constructor with model - assumed before cuts
00596     CbcHeuristicJustOne (CbcModel & model);
00597 
00598     // Copy constructor
00599     CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00600 
00601     // Destructor
00602     ~CbcHeuristicJustOne ();
00603 
00605     virtual CbcHeuristicJustOne * clone() const;
00606 
00608     CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00609 
00611     virtual void generateCpp( FILE * fp) ;
00612 
00619     virtual int solution(double & objectiveValue,
00620                          double * newSolution);
00622     virtual void resetModel(CbcModel * model);
00623 
00625     virtual void setModel(CbcModel * model);
00627 
00633     virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
00634                                         const double* /*newSolution*/,
00635                                         int& /*bestColumn*/,
00636                                         int& /*bestRound*/) {
00637         return true;
00638     }
00640     virtual void validate();
00642     void addHeuristic(const CbcHeuristic * heuristic, double probability);
00644     void normalizeProbabilities();
00645 protected:
00646     // Data
00647 
00648     // Probability of running a heuristic
00649     double * probabilities_;
00650 
00651     // Heuristics
00652     CbcHeuristic ** heuristic_;
00653 
00654     // Number of heuristics
00655     int numberHeuristics_;
00656 
00657 };
00658 
00659 #endif
00660 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines