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