# CbcHeuristic.hpp

Go to the documentation of this file.

    00001 /* $Id: CbcHeuristic.hpp 1675 2011-06-19 17:23:14Z 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     }
    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
    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