# 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