/build/buildd/coinor-cbc-2.5.0/Cbc/src/CbcHeuristic.hpp
Go to the documentation of this file.
00001 /* $Id: CbcHeuristic.hpp 1432 2010-02-07 19:33:53Z bjarni $ */
00002 // Copyright (C) 2002, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 #ifndef CbcHeuristic_H
00005 #define CbcHeuristic_H
00006 
00007 #include <string>
00008 #include <vector>
00009 #include "CoinPackedMatrix.hpp"
00010 #include "OsiCuts.hpp"
00011 #include "CoinHelperFunctions.hpp"
00012 #include "OsiBranchingObject.hpp"
00013 
00014 class OsiSolverInterface;
00015 
00016 class CbcModel;
00017 
00018 //#############################################################################
00019 
00020 class CbcHeuristicNodeList;
00021 class CbcBranchingObject;
00022 
00026 class CbcHeuristicNode {
00027 private:
00028     void gutsOfConstructor(CbcModel& model);
00029     CbcHeuristicNode();
00030     CbcHeuristicNode& operator=(const CbcHeuristicNode&);
00031 private:
00033     int numObjects_;
00037     CbcBranchingObject** brObj_;
00038 public:
00039     CbcHeuristicNode(CbcModel& model);
00040 
00041     CbcHeuristicNode(const CbcHeuristicNode& rhs);
00042     ~CbcHeuristicNode();
00043     double distance(const CbcHeuristicNode* node) const;
00044     double minDistance(const CbcHeuristicNodeList& nodeList) const;
00045     bool minDistanceIsSmall(const CbcHeuristicNodeList& nodeList,
00046                             const double threshold) const;
00047     double avgDistance(const CbcHeuristicNodeList& nodeList) const;
00048 };
00049 
00050 class CbcHeuristicNodeList {
00051 private:
00052     void gutsOfDelete();
00053     void gutsOfCopy(const CbcHeuristicNodeList& rhs);
00054 private:
00055     std::vector<CbcHeuristicNode*> nodes_;
00056 public:
00057     CbcHeuristicNodeList() {}
00058     CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
00059     CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
00060     ~CbcHeuristicNodeList();
00061 
00062     void append(CbcHeuristicNode*& node);
00063     void append(const CbcHeuristicNodeList& nodes);
00064     inline const CbcHeuristicNode* node(int i) const {
00065         return nodes_[i];
00066     }
00067     inline int size() const {
00068         return nodes_.size();
00069     }
00070 };
00071 
00072 //#############################################################################
00075 class CbcHeuristic {
00076 private:
00077     void gutsOfDelete() {}
00078     void gutsOfCopy(const CbcHeuristic & rhs);
00079 
00080 public:
00081     // Default Constructor
00082     CbcHeuristic ();
00083 
00084     // Constructor with model - assumed before cuts
00085     CbcHeuristic (CbcModel & model);
00086 
00087     // Copy constructor
00088     CbcHeuristic ( const CbcHeuristic &);
00089 
00090     virtual ~CbcHeuristic();
00091 
00093     virtual CbcHeuristic * clone() const = 0;
00094 
00096     CbcHeuristic & operator=(const CbcHeuristic& rhs);
00097 
00099     virtual void setModel(CbcModel * model);
00100 
00102     virtual void resetModel(CbcModel * model) = 0;
00103 
00109     virtual int solution(double & objectiveValue,
00110                          double * newSolution) = 0;
00111 
00119     virtual int solution2(double & /*objectiveValue*/,
00120                           double * /*newSolution*/,
00121                           OsiCuts & /*cs*/) {
00122         return 0;
00123     }
00124 
00126     virtual void validate() {}
00127 
00132     inline void setWhen(int value) {
00133         when_ = value;
00134     }
00136     inline int when() const {
00137         return when_;
00138     }
00139 
00141     inline void setNumberNodes(int value) {
00142         numberNodes_ = value;
00143     }
00145     inline int numberNodes() const {
00146         return numberNodes_;
00147     }
00157     inline void setSwitches(int value) {
00158         switches_ = value;
00159     }
00169     inline int switches() const {
00170         return switches_;
00171     }
00173     bool exitNow(double bestObjective) const;
00175     inline void setFeasibilityPumpOptions(int value) {
00176         feasibilityPumpOptions_ = value;
00177     }
00179     inline int feasibilityPumpOptions() const {
00180         return feasibilityPumpOptions_;
00181     }
00183     inline void setModelOnly(CbcModel * model) {
00184         model_ = model;
00185     }
00186 
00187 
00189     inline void setFractionSmall(double value) {
00190         fractionSmall_ = value;
00191     }
00193     inline double fractionSmall() const {
00194         return fractionSmall_;
00195     }
00197     inline int numberSolutionsFound() const {
00198         return numberSolutionsFound_;
00199     }
00201     inline void incrementNumberSolutionsFound() {
00202         numberSolutionsFound_++;
00203     }
00204 
00214     int smallBranchAndBound(OsiSolverInterface * solver, int numberNodes,
00215                             double * newSolution, double & newSolutionValue,
00216                             double cutoff , std::string name) const;
00218     virtual void generateCpp( FILE * ) {}
00220     void generateCpp( FILE * fp, const char * heuristic) ;
00222     virtual bool canDealWithOdd() const {
00223         return false;
00224     }
00226     inline const char *heuristicName() const {
00227         return heuristicName_.c_str();
00228     }
00230     inline void setHeuristicName(const char *name) {
00231         heuristicName_ = name;
00232     }
00234     void setSeed(int value);
00236     inline void setDecayFactor(double value) {
00237         decayFactor_ = value;
00238     }
00240     void setInputSolution(const double * solution, double objValue);
00241     /* Runs if bit set
00242         0 - before cuts at root node (or from doHeuristics)
00243         1 - during cuts at root
00244         2 - after root node cuts
00245         3 - after cuts at other nodes
00246         4 - during cuts at other nodes
00247             8 added if previous heuristic in loop found solution
00248      */
00249     inline void setWhereFrom(int value) {
00250         whereFrom_ = value;
00251     }
00258     inline void setShallowDepth(int value) {
00259         shallowDepth_ = value;
00260     }
00262     inline void setHowOftenShallow(int value) {
00263         howOftenShallow_ = value;
00264     }
00268     inline void setMinDistanceToRun(int value) {
00269         minDistanceToRun_ = value;
00270     }
00271 
00280     virtual bool shouldHeurRun(int whereFrom);
00282     bool shouldHeurRun_randomChoice();
00283     void debugNodes();
00284     void printDistanceToNodes();
00286     inline int numRuns() const {
00287         return numRuns_;
00288     }
00289 
00291     inline int numCouldRun() const {
00292         return numCouldRun_;
00293     }
00298     OsiSolverInterface * cloneBut(int type);
00299 protected:
00300 
00302     CbcModel * model_;
00304     int when_;
00306     int numberNodes_;
00308     int feasibilityPumpOptions_;
00310     mutable double fractionSmall_;
00312     CoinThreadRandom randomNumberGenerator_;
00314     std::string heuristicName_;
00315 
00317     int howOften_;
00319     double decayFactor_;
00329     mutable int switches_;
00330     /* Runs if bit set
00331         0 - before cuts at root node (or from doHeuristics)
00332         1 - during cuts at root
00333         2 - after root node cuts
00334         3 - after cuts at other nodes
00335         4 - during cuts at other nodes
00336             8 added if previous heuristic in loop found solution
00337      */
00338     int whereFrom_;
00345     int shallowDepth_;
00347     int howOftenShallow_;
00350     int numInvocationsInShallow_;
00353     int numInvocationsInDeep_;
00355     int lastRunDeep_;
00357     int numRuns_;
00361     int minDistanceToRun_;
00362 
00364     CbcHeuristicNodeList runNodes_;
00365 
00367     int numCouldRun_;
00368 
00370     int numberSolutionsFound_;
00371 
00372     // Input solution - so can be used as seed
00373     double * inputSolution_;
00374 
00375 
00376 #ifdef JJF_ZERO
00377 
00378     double * lowerBoundLastNode_;
00380     double * upperBoundLastNode_;
00381 #endif
00382 };
00386 class CbcRounding : public CbcHeuristic {
00387 public:
00388 
00389     // Default Constructor
00390     CbcRounding ();
00391 
00392     // Constructor with model - assumed before cuts
00393     CbcRounding (CbcModel & model);
00394 
00395     // Copy constructor
00396     CbcRounding ( const CbcRounding &);
00397 
00398     // Destructor
00399     ~CbcRounding ();
00400 
00402     CbcRounding & operator=(const CbcRounding& rhs);
00403 
00405     virtual CbcHeuristic * clone() const;
00407     virtual void generateCpp( FILE * fp) ;
00408 
00410     virtual void resetModel(CbcModel * model);
00411 
00413     virtual void setModel(CbcModel * model);
00414 
00415     using CbcHeuristic::solution ;
00421     virtual int solution(double & objectiveValue,
00422                          double * newSolution);
00429     virtual int solution(double & objectiveValue,
00430                          double * newSolution,
00431                          double solutionValue);
00433     virtual void validate();
00434 
00435 
00437     void setSeed(int value) {
00438         seed_ = value;
00439     }
00440 
00441 protected:
00442     // Data
00443 
00444     // Original matrix by column
00445     CoinPackedMatrix matrix_;
00446 
00447     // Original matrix by
00448     CoinPackedMatrix matrixByRow_;
00449 
00450     // Down locks
00451     unsigned short * down_;
00452 
00453     // Up locks
00454     unsigned short * up_;
00455 
00456     // Equality locks
00457     unsigned short * equal_;
00458 
00459     // Seed for random stuff
00460     int seed_;
00461 };
00462 
00468 class CbcHeuristicPartial : public CbcHeuristic {
00469 public:
00470 
00471     // Default Constructor
00472     CbcHeuristicPartial ();
00473 
00478     CbcHeuristicPartial (CbcModel & model, int fixPriority = 10000, int numberNodes = 200);
00479 
00480     // Copy constructor
00481     CbcHeuristicPartial ( const CbcHeuristicPartial &);
00482 
00483     // Destructor
00484     ~CbcHeuristicPartial ();
00485 
00487     CbcHeuristicPartial & operator=(const CbcHeuristicPartial& rhs);
00488 
00490     virtual CbcHeuristic * clone() const;
00492     virtual void generateCpp( FILE * fp) ;
00493 
00495     virtual void resetModel(CbcModel * model);
00496 
00498     virtual void setModel(CbcModel * model);
00499 
00500     using CbcHeuristic::solution ;
00506     virtual int solution(double & objectiveValue,
00507                          double * newSolution);
00509     virtual void validate();
00510 
00511 
00513     void setFixPriority(int value) {
00514         fixPriority_ = value;
00515     }
00516 
00518     virtual bool shouldHeurRun(int whereFrom);
00519 
00520 protected:
00521     // Data
00522 
00523     // All variables with abs priority <= this will be fixed
00524     int fixPriority_;
00525 };
00526 
00531 class CbcSerendipity : public CbcHeuristic {
00532 public:
00533 
00534     // Default Constructor
00535     CbcSerendipity ();
00536 
00537     /* Constructor with model
00538     */
00539     CbcSerendipity (CbcModel & model);
00540 
00541     // Copy constructor
00542     CbcSerendipity ( const CbcSerendipity &);
00543 
00544     // Destructor
00545     ~CbcSerendipity ();
00546 
00548     CbcSerendipity & operator=(const CbcSerendipity& rhs);
00549 
00551     virtual CbcHeuristic * clone() const;
00553     virtual void generateCpp( FILE * fp) ;
00554 
00556     virtual void setModel(CbcModel * model);
00557 
00558     using CbcHeuristic::solution ;
00569     virtual int solution(double & objectiveValue,
00570                          double * newSolution);
00572     virtual void resetModel(CbcModel * model);
00573 
00574 protected:
00575 };
00576 
00580 class CbcHeuristicJustOne : public CbcHeuristic {
00581 public:
00582 
00583     // Default Constructor
00584     CbcHeuristicJustOne ();
00585 
00586     // Constructor with model - assumed before cuts
00587     CbcHeuristicJustOne (CbcModel & model);
00588 
00589     // Copy constructor
00590     CbcHeuristicJustOne ( const CbcHeuristicJustOne &);
00591 
00592     // Destructor
00593     ~CbcHeuristicJustOne ();
00594 
00596     virtual CbcHeuristicJustOne * clone() const;
00597 
00599     CbcHeuristicJustOne & operator=(const CbcHeuristicJustOne& rhs);
00600 
00602     virtual void generateCpp( FILE * fp) ;
00603 
00610     virtual int solution(double & objectiveValue,
00611                          double * newSolution);
00613     virtual void resetModel(CbcModel * model);
00614 
00616     virtual void setModel(CbcModel * model);
00618 
00624     virtual bool selectVariableToBranch(OsiSolverInterface* /*solver*/,
00625                                         const double* /*newSolution*/,
00626                                         int& /*bestColumn*/,
00627                                         int& /*bestRound*/) {
00628         return true;
00629     }
00631     virtual void validate();
00633     void addHeuristic(const CbcHeuristic * heuristic, double probability);
00635     void normalizeProbabilities();
00636 protected:
00637     // Data
00638 
00639     // Probability of running a heuristic
00640     double * probabilities_;
00641 
00642     // Heuristics
00643     CbcHeuristic ** heuristic_;
00644 
00645     // Number of heuristics
00646     int numberHeuristics_;
00647 
00648 };
00649 
00650 #endif
00651