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

Go to the documentation of this file.
00001 // Copyright (C) 2004, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef CbcTreeLocal_H
00004 #define CbcTreeLocal_H
00005 
00006 //#############################################################################
00007 /*  This implements (approximately) local branching as in the 2002 paper by
00008     Matteo Fischetti and Andrea Lodi.
00009 
00010     The very simple version of the algorithm for problems with 
00011     0-1 variables and continuous is as follows:
00012 
00013     Obtain a feasible solution (one can be passed in).
00014 
00015     Add a cut which limits search to a k neighborhood of this solution.
00016     (At most k 0-1 variables may change value)
00017     Do branch and bound on this problem.
00018 
00019     If finished search and proven optimal then we can reverse cut so
00020     any solutions must be at least k+1 away from solution and we can 
00021     add a new cut limiting search to a k neighborhood of new solution
00022     repeat.
00023 
00024     If finished search and no new solution then the simplest version
00025     would reverse last cut and complete search.  The version implemented 
00026     here can use time and node limits and can widen search (increase effective k)
00027     .... and more
00028 
00029 */
00030 
00031 #include "CbcTree.hpp"
00032 #include "CbcNode.hpp"
00033 #include "OsiRowCut.hpp"
00034 class CbcModel;
00035 
00036 
00037 class CbcTreeLocal : public CbcTree {
00038 
00039 public:
00040 
00041   // Default Constructor 
00042   CbcTreeLocal ();
00043 
00044   /* Constructor with solution.
00045      If solution NULL no solution, otherwise must be integer
00046      range is initial upper bound (k) on difference from given solution.
00047      typeCuts -
00048               0 means just 0-1 cuts and will need to refine 0-1 solution
00049               1 uses weaker cuts on all integer variables
00050      maxDiversification is maximum number of range widenings to try
00051      timeLimit is seconds in subTree
00052      nodeLimit is nodes in subTree
00053      refine is whether to see if we can prove current solution is optimal
00054      when we fix all 0-1 (in case typeCuts==0 and there are general integer variables)
00055      if false then no refinement but reverse cuts weaker
00056   */
00057   CbcTreeLocal (CbcModel * model,const double * solution ,int range=10,
00058                    int typeCuts=0,int maxDiversification=0,
00059                    int timeLimit=1000000, int nodeLimit=1000000,bool refine=true);
00060   // Copy constructor 
00061   CbcTreeLocal ( const CbcTreeLocal & rhs);
00062 
00063   // = operator
00064   CbcTreeLocal & operator=(const CbcTreeLocal & rhs);
00065    
00066   virtual ~CbcTreeLocal();
00067 
00069   virtual CbcTree * clone() const;
00070 
00073 
00075   virtual CbcNode * top();
00076 
00078   virtual void push(CbcNode * x);
00079 
00081   virtual void pop() ;
00082 
00084 
00086 
00088   int createCut(const double * solution, OsiRowCut & cut);
00089 
00091   virtual bool empty() ;
00092 
00094   virtual void endSearch() ;
00096   void reverseCut(int state, double bias=0.0);
00098   void deleteCut(OsiRowCut & cut);
00100   void passInSolution(const double * solution, double solutionValue);
00101 
00103 private:
00104   // Node for local cuts
00105   CbcNode * localNode_;
00106   // best solution
00107   double * bestSolution_;
00108   // saved solution
00109   double * savedSolution_;
00110   // solution number at start of pass
00111   int saveNumberSolutions_;
00112   /* Cut.  If zero size then no solution yet.  Otherwise is left hand branch */
00113   OsiRowCut cut_;
00114   // This cut fixes all 0-1 variables
00115   OsiRowCut fixedCut_;
00116   // Model
00117   CbcModel * model_;
00118   // Original lower bounds
00119   double * originalLower_;
00120   // Original upper bounds
00121   double * originalUpper_;
00122   // range i.e. k
00123   int range_;
00124   // Type of cuts - 0=just 0-1, 1=all
00125   int typeCuts_;
00126   // maximum number of diversifications
00127   int maxDiversification_;
00128   // current diversification
00129   int diversification_;
00130   // Whether next will be strong diversification
00131   bool nextStrong_;
00132   // Current rhs
00133   double rhs_;
00134   // Save allowable gap
00135   double savedGap_;
00136   // Best solution
00137   double bestCutoff_;
00138   // time limit per subtree
00139   int timeLimit_;
00140   // time when subtree started
00141   int startTime_;
00142   // node limit for subtree
00143   int nodeLimit_;
00144   // node count when subtree started
00145   int startNode_;
00146   // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step
00147   int searchType_;
00148   // Whether to do refinement step
00149   bool refine_;
00150 
00151 };
00152 #endif
00153 

Generated on Thu May 15 21:59:04 2008 by  doxygen 1.4.7