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