/home/coin/SVN-release/Cbc-2.4.2/Cbc/src/CbcTreeLocal.hpp

Go to the documentation of this file.
00001 /* $Id: CbcTreeLocal.hpp 1271 2009-11-05 15:57:25Z forrest $ */
00002 // Copyright (C) 2004, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 #ifndef CbcTreeLocal_H
00005 #define CbcTreeLocal_H
00006 
00007 //#############################################################################
00008 /*  This implements (approximately) local branching as in the 2002 paper by
00009     Matteo Fischetti and Andrea Lodi.
00010 
00011     The very simple version of the algorithm for problems with 
00012     0-1 variables and continuous is as follows:
00013 
00014     Obtain a feasible solution (one can be passed in).
00015 
00016     Add a cut which limits search to a k neighborhood of this solution.
00017     (At most k 0-1 variables may change value)
00018     Do branch and bound on this problem.
00019 
00020     If finished search and proven optimal then we can reverse cut so
00021     any solutions must be at least k+1 away from solution and we can 
00022     add a new cut limiting search to a k neighborhood of new solution
00023     repeat.
00024 
00025     If finished search and no new solution then the simplest version
00026     would reverse last cut and complete search.  The version implemented 
00027     here can use time and node limits and can widen search (increase effective k)
00028     .... and more
00029 
00030 */
00031 
00032 #include "CbcTree.hpp"
00033 #include "CbcNode.hpp"
00034 #include "OsiRowCut.hpp"
00035 class CbcModel;
00036 
00037 
00038 class CbcTreeLocal : public CbcTree {
00039 
00040 public:
00041 
00042   // Default Constructor 
00043   CbcTreeLocal ();
00044 
00045   /* Constructor with solution.
00046      If solution NULL no solution, otherwise must be integer
00047      range is initial upper bound (k) on difference from given solution.
00048      typeCuts -
00049               0 means just 0-1 cuts and will need to refine 0-1 solution
00050               1 uses weaker cuts on all integer variables
00051      maxDiversification is maximum number of range widenings to try
00052      timeLimit is seconds in subTree
00053      nodeLimit is nodes in subTree
00054      refine is whether to see if we can prove current solution is optimal
00055      when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
00056      if false then no refinement but reverse cuts weaker
00057   */
00058   CbcTreeLocal (CbcModel * model,const double * solution ,int range=10,
00059                    int typeCuts=0,int maxDiversification=0,
00060                    int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
00061   // Copy constructor 
00062   CbcTreeLocal ( const CbcTreeLocal & rhs);
00063 
00064   // = operator
00065   CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
00066    
00067   virtual ~CbcTreeLocal();
00068 
00070   virtual CbcTree * clone() const;
00072   virtual void generateCpp( FILE * fp) ;
00073 
00076 
00078   virtual CbcNode * top() const;
00079 
00081   virtual void push(CbcNode * x);
00082 
00084   virtual void pop() ;
00085 
00087 
00089 
00091   int createCut(const double * solution, OsiRowCut & cut);
00092 
00094   virtual bool empty() ;
00095 
00097   virtual void endSearch() ;
00099   void reverseCut(int state, double bias=0.0);
00101   void deleteCut(OsiRowCut & cut);
00103   void passInSolution(const double * solution, double solutionValue);
00104   // range i.e. k
00105   inline int range() const
00106   { return range_;}
00107   // setrange i.e. k
00108   inline void setRange(int value)
00109   { range_ = value;}
00110   // Type of cuts - 0=just 0-1, 1=all
00111   inline int typeCuts() const
00112   { return typeCuts_;}
00113   // Type of cuts - 0=just 0-1, 1=all
00114   inline void setTypeCuts(int value)
00115   { typeCuts_ = value;}
00116   // maximum number of diversifications
00117   inline int maxDiversification() const
00118   { return maxDiversification_;}
00119   // maximum number of diversifications
00120   inline void setMaxDiversification(int value)
00121   { maxDiversification_ = value;}
00122   // time limit per subtree
00123   inline int timeLimit() const
00124   { return timeLimit_;}
00125   // time limit per subtree
00126   inline void setTimeLimit(int value)
00127   { timeLimit_ = value;}
00128   // node limit for subtree
00129   inline int nodeLimit() const
00130   { return nodeLimit_;}
00131   // node limit for subtree
00132   inline void setNodeLimit(int value)
00133   { nodeLimit_ = value;}
00134   // Whether to do refinement step
00135   inline bool refine() const
00136   { return refine_;}
00137   // Whether to do refinement step
00138   inline void setRefine(bool yesNo)
00139     { refine_ = yesNo;}
00140 
00142 private:
00143   // Node for local cuts
00144   CbcNode * localNode_;
00145   // best solution
00146   double * bestSolution_;
00147   // saved solution
00148   double * savedSolution_;
00149   // solution number at start of pass
00150   int saveNumberSolutions_;
00151   /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
00152   OsiRowCut cut_;
00153   // This cut fixes all 0-1 variables
00154   OsiRowCut fixedCut_;
00155   // Model
00156   CbcModel * model_;
00157   // Original lower bounds
00158   double * originalLower_;
00159   // Original upper bounds
00160   double * originalUpper_;
00161   // range i.e. k
00162   int range_;
00163   // Type of cuts - 0=just 0-1, 1=all
00164   int typeCuts_;
00165   // maximum number of diversifications
00166   int maxDiversification_;
00167   // current diversification
00168   int diversification_;
00169   // Whether next will be strong diversification
00170   bool nextStrong_;
00171   // Current rhs
00172   double rhs_;
00173   // Save allowable gap
00174   double savedGap_;
00175   // Best solution
00176   double bestCutoff_;
00177   // time limit per subtree
00178   int timeLimit_;
00179   // time when subtree started
00180   int startTime_;
00181   // node limit for subtree
00182   int nodeLimit_;
00183   // node count when subtree started
00184   int startNode_;
00185   // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
00186   int searchType_;
00187   // Whether to do refinement step
00188   bool refine_;
00189 
00190 };
00191 
00192 class CbcTreeVariable : public CbcTree {
00193 
00194 public:
00195 
00196   // Default Constructor 
00197   CbcTreeVariable ();
00198 
00199   /* Constructor with solution.
00200      If solution NULL no solution, otherwise must be integer
00201      range is initial upper bound (k) on difference from given solution.
00202      typeCuts -
00203               0 means just 0-1 cuts and will need to refine 0-1 solution
00204               1 uses weaker cuts on all integer variables
00205      maxDiversification is maximum number of range widenings to try
00206      timeLimit is seconds in subTree
00207      nodeLimit is nodes in subTree
00208      refine is whether to see if we can prove current solution is optimal
00209      when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
00210      if false then no refinement but reverse cuts weaker
00211   */
00212   CbcTreeVariable (CbcModel * model,const double * solution ,int range=10,
00213                    int typeCuts=0,int maxDiversification=0,
00214                    int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
00215   // Copy constructor 
00216   CbcTreeVariable ( const CbcTreeVariable & rhs);
00217 
00218   // = operator
00219   CbcTreeVariable & operator=(const CbcTreeVariable & rhs);
00220    
00221   virtual ~CbcTreeVariable();
00222 
00224   virtual CbcTree * clone() const;
00226   virtual void generateCpp( FILE * fp) ;
00227 
00230 
00232   virtual CbcNode * top() const;
00233 
00235   virtual void push(CbcNode * x);
00236 
00238   virtual void pop() ;
00239 
00241 
00243 
00245   int createCut(const double * solution, OsiRowCut & cut);
00246 
00248   virtual bool empty() ;
00249 
00251   virtual void endSearch() ;
00253   void reverseCut(int state, double bias=0.0);
00255   void deleteCut(OsiRowCut & cut);
00257   void passInSolution(const double * solution, double solutionValue);
00258   // range i.e. k
00259   inline int range() const
00260   { return range_;}
00261   // setrange i.e. k
00262   inline void setRange(int value)
00263   { range_ = value;}
00264   // Type of cuts - 0=just 0-1, 1=all
00265   inline int typeCuts() const
00266   { return typeCuts_;}
00267   // Type of cuts - 0=just 0-1, 1=all
00268   inline void setTypeCuts(int value)
00269   { typeCuts_ = value;}
00270   // maximum number of diversifications
00271   inline int maxDiversification() const
00272   { return maxDiversification_;}
00273   // maximum number of diversifications
00274   inline void setMaxDiversification(int value)
00275   { maxDiversification_ = value;}
00276   // time limit per subtree
00277   inline int timeLimit() const
00278   { return timeLimit_;}
00279   // time limit per subtree
00280   inline void setTimeLimit(int value)
00281   { timeLimit_ = value;}
00282   // node limit for subtree
00283   inline int nodeLimit() const
00284   { return nodeLimit_;}
00285   // node limit for subtree
00286   inline void setNodeLimit(int value)
00287   { nodeLimit_ = value;}
00288   // Whether to do refinement step
00289   inline bool refine() const
00290   { return refine_;}
00291   // Whether to do refinement step
00292   inline void setRefine(bool yesNo)
00293     { refine_ = yesNo;}
00294 
00296 private:
00297   // Node for local cuts
00298   CbcNode * localNode_;
00299   // best solution
00300   double * bestSolution_;
00301   // saved solution
00302   double * savedSolution_;
00303   // solution number at start of pass
00304   int saveNumberSolutions_;
00305   /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
00306   OsiRowCut cut_;
00307   // This cut fixes all 0-1 variables
00308   OsiRowCut fixedCut_;
00309   // Model
00310   CbcModel * model_;
00311   // Original lower bounds
00312   double * originalLower_;
00313   // Original upper bounds
00314   double * originalUpper_;
00315   // range i.e. k
00316   int range_;
00317   // Type of cuts - 0=just 0-1, 1=all
00318   int typeCuts_;
00319   // maximum number of diversifications
00320   int maxDiversification_;
00321   // current diversification
00322   int diversification_;
00323   // Whether next will be strong diversification
00324   bool nextStrong_;
00325   // Current rhs
00326   double rhs_;
00327   // Save allowable gap
00328   double savedGap_;
00329   // Best solution
00330   double bestCutoff_;
00331   // time limit per subtree
00332   int timeLimit_;
00333   // time when subtree started
00334   int startTime_;
00335   // node limit for subtree
00336   int nodeLimit_;
00337   // node count when subtree started
00338   int startNode_;
00339   // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
00340   int searchType_;
00341   // Whether to do refinement step
00342   bool refine_;
00343 
00344 };
00345 #endif
00346 

Generated on Sat May 22 03:07:44 2010 by  doxygen 1.4.7