[1271] | 1 | /* $Id: CbcTreeLocal.hpp 1573 2011-01-05 01:12:36Z stefan $ */ |
---|
[185] | 2 | // Copyright (C) 2004, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
[1573] | 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[185] | 6 | #ifndef CbcTreeLocal_H |
---|
| 7 | #define CbcTreeLocal_H |
---|
| 8 | |
---|
| 9 | //############################################################################# |
---|
| 10 | /* This implements (approximately) local branching as in the 2002 paper by |
---|
| 11 | Matteo Fischetti and Andrea Lodi. |
---|
| 12 | |
---|
[1286] | 13 | The very simple version of the algorithm for problems with |
---|
[185] | 14 | 0-1 variables and continuous is as follows: |
---|
| 15 | |
---|
| 16 | Obtain a feasible solution (one can be passed in). |
---|
| 17 | |
---|
| 18 | Add a cut which limits search to a k neighborhood of this solution. |
---|
| 19 | (At most k 0-1 variables may change value) |
---|
| 20 | Do branch and bound on this problem. |
---|
| 21 | |
---|
| 22 | If finished search and proven optimal then we can reverse cut so |
---|
[1286] | 23 | any solutions must be at least k+1 away from solution and we can |
---|
[185] | 24 | add a new cut limiting search to a k neighborhood of new solution |
---|
| 25 | repeat. |
---|
| 26 | |
---|
| 27 | If finished search and no new solution then the simplest version |
---|
[1286] | 28 | would reverse last cut and complete search. The version implemented |
---|
[185] | 29 | here can use time and node limits and can widen search (increase effective k) |
---|
| 30 | .... and more |
---|
| 31 | |
---|
| 32 | */ |
---|
| 33 | |
---|
| 34 | #include "CbcTree.hpp" |
---|
| 35 | #include "CbcNode.hpp" |
---|
| 36 | #include "OsiRowCut.hpp" |
---|
| 37 | class CbcModel; |
---|
| 38 | |
---|
| 39 | |
---|
| 40 | class CbcTreeLocal : public CbcTree { |
---|
| 41 | |
---|
| 42 | public: |
---|
| 43 | |
---|
[1286] | 44 | // Default Constructor |
---|
| 45 | CbcTreeLocal (); |
---|
[185] | 46 | |
---|
[1286] | 47 | /* Constructor with solution. |
---|
| 48 | If solution NULL no solution, otherwise must be integer |
---|
| 49 | range is initial upper bound (k) on difference from given solution. |
---|
| 50 | typeCuts - |
---|
| 51 | 0 means just 0-1 cuts and will need to refine 0-1 solution |
---|
| 52 | 1 uses weaker cuts on all integer variables |
---|
| 53 | maxDiversification is maximum number of range widenings to try |
---|
| 54 | timeLimit is seconds in subTree |
---|
| 55 | nodeLimit is nodes in subTree |
---|
| 56 | refine is whether to see if we can prove current solution is optimal |
---|
| 57 | when we fix all 0-1 (in case typeCuts==0 and there are general integer variables) |
---|
| 58 | if false then no refinement but reverse cuts weaker |
---|
| 59 | */ |
---|
| 60 | CbcTreeLocal (CbcModel * model, const double * solution , int range = 10, |
---|
| 61 | int typeCuts = 0, int maxDiversification = 0, |
---|
| 62 | int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true); |
---|
| 63 | // Copy constructor |
---|
| 64 | CbcTreeLocal ( const CbcTreeLocal & rhs); |
---|
[185] | 65 | |
---|
[1286] | 66 | // = operator |
---|
| 67 | CbcTreeLocal & operator=(const CbcTreeLocal & rhs); |
---|
[185] | 68 | |
---|
[1286] | 69 | virtual ~CbcTreeLocal(); |
---|
[185] | 70 | |
---|
[1286] | 71 | /// Clone |
---|
| 72 | virtual CbcTree * clone() const; |
---|
| 73 | /// Create C++ lines to get to current state |
---|
| 74 | virtual void generateCpp( FILE * fp) ; |
---|
| 75 | |
---|
| 76 | /*! \name Heap access and maintenance methods */ |
---|
[185] | 77 | //@{ |
---|
| 78 | |
---|
[1286] | 79 | /// Return the top node of the heap |
---|
| 80 | virtual CbcNode * top() const; |
---|
[185] | 81 | |
---|
[1286] | 82 | /// Add a node to the heap |
---|
| 83 | virtual void push(CbcNode * x); |
---|
[185] | 84 | |
---|
[1286] | 85 | /// Remove the top node from the heap |
---|
| 86 | virtual void pop() ; |
---|
[185] | 87 | |
---|
| 88 | //@} |
---|
[1286] | 89 | /*! \name Other stuff */ |
---|
[185] | 90 | //@{ |
---|
| 91 | |
---|
[1286] | 92 | /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything |
---|
| 93 | int createCut(const double * solution, OsiRowCut & cut); |
---|
[185] | 94 | |
---|
[1286] | 95 | /// Test if empty *** note may be overridden |
---|
| 96 | virtual bool empty() ; |
---|
[185] | 97 | |
---|
[1286] | 98 | /// We may have got an intelligent tree so give it one more chance |
---|
| 99 | virtual void endSearch() ; |
---|
| 100 | /// Other side of last cut branch (if bias==rhs_ will be weakest possible) |
---|
| 101 | void reverseCut(int state, double bias = 0.0); |
---|
| 102 | /// Delete last cut branch |
---|
| 103 | void deleteCut(OsiRowCut & cut); |
---|
| 104 | /// Pass in solution (so can be used after heuristic) |
---|
| 105 | void passInSolution(const double * solution, double solutionValue); |
---|
| 106 | // range i.e. k |
---|
| 107 | inline int range() const { |
---|
| 108 | return range_; |
---|
| 109 | } |
---|
| 110 | // setrange i.e. k |
---|
| 111 | inline void setRange(int value) { |
---|
| 112 | range_ = value; |
---|
| 113 | } |
---|
| 114 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 115 | inline int typeCuts() const { |
---|
| 116 | return typeCuts_; |
---|
| 117 | } |
---|
| 118 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 119 | inline void setTypeCuts(int value) { |
---|
| 120 | typeCuts_ = value; |
---|
| 121 | } |
---|
| 122 | // maximum number of diversifications |
---|
| 123 | inline int maxDiversification() const { |
---|
| 124 | return maxDiversification_; |
---|
| 125 | } |
---|
| 126 | // maximum number of diversifications |
---|
| 127 | inline void setMaxDiversification(int value) { |
---|
| 128 | maxDiversification_ = value; |
---|
| 129 | } |
---|
| 130 | // time limit per subtree |
---|
| 131 | inline int timeLimit() const { |
---|
| 132 | return timeLimit_; |
---|
| 133 | } |
---|
| 134 | // time limit per subtree |
---|
| 135 | inline void setTimeLimit(int value) { |
---|
| 136 | timeLimit_ = value; |
---|
| 137 | } |
---|
| 138 | // node limit for subtree |
---|
| 139 | inline int nodeLimit() const { |
---|
| 140 | return nodeLimit_; |
---|
| 141 | } |
---|
| 142 | // node limit for subtree |
---|
| 143 | inline void setNodeLimit(int value) { |
---|
| 144 | nodeLimit_ = value; |
---|
| 145 | } |
---|
| 146 | // Whether to do refinement step |
---|
| 147 | inline bool refine() const { |
---|
| 148 | return refine_; |
---|
| 149 | } |
---|
| 150 | // Whether to do refinement step |
---|
| 151 | inline void setRefine(bool yesNo) { |
---|
| 152 | refine_ = yesNo; |
---|
| 153 | } |
---|
[1271] | 154 | |
---|
| 155 | //@} |
---|
| 156 | private: |
---|
[1286] | 157 | // Node for local cuts |
---|
| 158 | CbcNode * localNode_; |
---|
| 159 | // best solution |
---|
| 160 | double * bestSolution_; |
---|
| 161 | // saved solution |
---|
| 162 | double * savedSolution_; |
---|
| 163 | // solution number at start of pass |
---|
| 164 | int saveNumberSolutions_; |
---|
| 165 | /* Cut. If zero size then no solution yet. Otherwise is left hand branch */ |
---|
| 166 | OsiRowCut cut_; |
---|
| 167 | // This cut fixes all 0-1 variables |
---|
| 168 | OsiRowCut fixedCut_; |
---|
| 169 | // Model |
---|
| 170 | CbcModel * model_; |
---|
| 171 | // Original lower bounds |
---|
| 172 | double * originalLower_; |
---|
| 173 | // Original upper bounds |
---|
| 174 | double * originalUpper_; |
---|
| 175 | // range i.e. k |
---|
| 176 | int range_; |
---|
| 177 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 178 | int typeCuts_; |
---|
| 179 | // maximum number of diversifications |
---|
| 180 | int maxDiversification_; |
---|
| 181 | // current diversification |
---|
| 182 | int diversification_; |
---|
| 183 | // Whether next will be strong diversification |
---|
| 184 | bool nextStrong_; |
---|
| 185 | // Current rhs |
---|
| 186 | double rhs_; |
---|
| 187 | // Save allowable gap |
---|
| 188 | double savedGap_; |
---|
| 189 | // Best solution |
---|
| 190 | double bestCutoff_; |
---|
| 191 | // time limit per subtree |
---|
| 192 | int timeLimit_; |
---|
| 193 | // time when subtree started |
---|
| 194 | int startTime_; |
---|
| 195 | // node limit for subtree |
---|
| 196 | int nodeLimit_; |
---|
| 197 | // node count when subtree started |
---|
| 198 | int startNode_; |
---|
| 199 | // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step |
---|
| 200 | int searchType_; |
---|
| 201 | // Whether to do refinement step |
---|
| 202 | bool refine_; |
---|
[1271] | 203 | |
---|
| 204 | }; |
---|
| 205 | |
---|
| 206 | class CbcTreeVariable : public CbcTree { |
---|
| 207 | |
---|
| 208 | public: |
---|
| 209 | |
---|
[1286] | 210 | // Default Constructor |
---|
| 211 | CbcTreeVariable (); |
---|
[1271] | 212 | |
---|
[1286] | 213 | /* Constructor with solution. |
---|
| 214 | If solution NULL no solution, otherwise must be integer |
---|
| 215 | range is initial upper bound (k) on difference from given solution. |
---|
| 216 | typeCuts - |
---|
| 217 | 0 means just 0-1 cuts and will need to refine 0-1 solution |
---|
| 218 | 1 uses weaker cuts on all integer variables |
---|
| 219 | maxDiversification is maximum number of range widenings to try |
---|
| 220 | timeLimit is seconds in subTree |
---|
| 221 | nodeLimit is nodes in subTree |
---|
| 222 | refine is whether to see if we can prove current solution is optimal |
---|
| 223 | when we fix all 0-1 (in case typeCuts==0 and there are general integer variables) |
---|
| 224 | if false then no refinement but reverse cuts weaker |
---|
| 225 | */ |
---|
| 226 | CbcTreeVariable (CbcModel * model, const double * solution , int range = 10, |
---|
| 227 | int typeCuts = 0, int maxDiversification = 0, |
---|
| 228 | int timeLimit = 1000000, int nodeLimit = 1000000, bool refine = true); |
---|
| 229 | // Copy constructor |
---|
| 230 | CbcTreeVariable ( const CbcTreeVariable & rhs); |
---|
[1271] | 231 | |
---|
[1286] | 232 | // = operator |
---|
| 233 | CbcTreeVariable & operator=(const CbcTreeVariable & rhs); |
---|
[1271] | 234 | |
---|
[1286] | 235 | virtual ~CbcTreeVariable(); |
---|
[1271] | 236 | |
---|
[1286] | 237 | /// Clone |
---|
| 238 | virtual CbcTree * clone() const; |
---|
| 239 | /// Create C++ lines to get to current state |
---|
| 240 | virtual void generateCpp( FILE * fp) ; |
---|
| 241 | |
---|
| 242 | /*! \name Heap access and maintenance methods */ |
---|
[1271] | 243 | //@{ |
---|
| 244 | |
---|
[1286] | 245 | /// Return the top node of the heap |
---|
| 246 | virtual CbcNode * top() const; |
---|
[1271] | 247 | |
---|
[1286] | 248 | /// Add a node to the heap |
---|
| 249 | virtual void push(CbcNode * x); |
---|
[1271] | 250 | |
---|
[1286] | 251 | /// Remove the top node from the heap |
---|
| 252 | virtual void pop() ; |
---|
[1271] | 253 | |
---|
| 254 | //@} |
---|
[1286] | 255 | /*! \name Other stuff */ |
---|
[1271] | 256 | //@{ |
---|
| 257 | |
---|
[1286] | 258 | /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything |
---|
| 259 | int createCut(const double * solution, OsiRowCut & cut); |
---|
[1271] | 260 | |
---|
[1286] | 261 | /// Test if empty *** note may be overridden |
---|
| 262 | virtual bool empty() ; |
---|
[1271] | 263 | |
---|
[1286] | 264 | /// We may have got an intelligent tree so give it one more chance |
---|
| 265 | virtual void endSearch() ; |
---|
| 266 | /// Other side of last cut branch (if bias==rhs_ will be weakest possible) |
---|
| 267 | void reverseCut(int state, double bias = 0.0); |
---|
| 268 | /// Delete last cut branch |
---|
| 269 | void deleteCut(OsiRowCut & cut); |
---|
| 270 | /// Pass in solution (so can be used after heuristic) |
---|
| 271 | void passInSolution(const double * solution, double solutionValue); |
---|
| 272 | // range i.e. k |
---|
| 273 | inline int range() const { |
---|
| 274 | return range_; |
---|
| 275 | } |
---|
| 276 | // setrange i.e. k |
---|
| 277 | inline void setRange(int value) { |
---|
| 278 | range_ = value; |
---|
| 279 | } |
---|
| 280 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 281 | inline int typeCuts() const { |
---|
| 282 | return typeCuts_; |
---|
| 283 | } |
---|
| 284 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 285 | inline void setTypeCuts(int value) { |
---|
| 286 | typeCuts_ = value; |
---|
| 287 | } |
---|
| 288 | // maximum number of diversifications |
---|
| 289 | inline int maxDiversification() const { |
---|
| 290 | return maxDiversification_; |
---|
| 291 | } |
---|
| 292 | // maximum number of diversifications |
---|
| 293 | inline void setMaxDiversification(int value) { |
---|
| 294 | maxDiversification_ = value; |
---|
| 295 | } |
---|
| 296 | // time limit per subtree |
---|
| 297 | inline int timeLimit() const { |
---|
| 298 | return timeLimit_; |
---|
| 299 | } |
---|
| 300 | // time limit per subtree |
---|
| 301 | inline void setTimeLimit(int value) { |
---|
| 302 | timeLimit_ = value; |
---|
| 303 | } |
---|
| 304 | // node limit for subtree |
---|
| 305 | inline int nodeLimit() const { |
---|
| 306 | return nodeLimit_; |
---|
| 307 | } |
---|
| 308 | // node limit for subtree |
---|
| 309 | inline void setNodeLimit(int value) { |
---|
| 310 | nodeLimit_ = value; |
---|
| 311 | } |
---|
| 312 | // Whether to do refinement step |
---|
| 313 | inline bool refine() const { |
---|
| 314 | return refine_; |
---|
| 315 | } |
---|
| 316 | // Whether to do refinement step |
---|
| 317 | inline void setRefine(bool yesNo) { |
---|
| 318 | refine_ = yesNo; |
---|
| 319 | } |
---|
[185] | 320 | |
---|
| 321 | //@} |
---|
| 322 | private: |
---|
[1286] | 323 | // Node for local cuts |
---|
| 324 | CbcNode * localNode_; |
---|
| 325 | // best solution |
---|
| 326 | double * bestSolution_; |
---|
| 327 | // saved solution |
---|
| 328 | double * savedSolution_; |
---|
| 329 | // solution number at start of pass |
---|
| 330 | int saveNumberSolutions_; |
---|
| 331 | /* Cut. If zero size then no solution yet. Otherwise is left hand branch */ |
---|
| 332 | OsiRowCut cut_; |
---|
| 333 | // This cut fixes all 0-1 variables |
---|
| 334 | OsiRowCut fixedCut_; |
---|
| 335 | // Model |
---|
| 336 | CbcModel * model_; |
---|
| 337 | // Original lower bounds |
---|
| 338 | double * originalLower_; |
---|
| 339 | // Original upper bounds |
---|
| 340 | double * originalUpper_; |
---|
| 341 | // range i.e. k |
---|
| 342 | int range_; |
---|
| 343 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 344 | int typeCuts_; |
---|
| 345 | // maximum number of diversifications |
---|
| 346 | int maxDiversification_; |
---|
| 347 | // current diversification |
---|
| 348 | int diversification_; |
---|
| 349 | // Whether next will be strong diversification |
---|
| 350 | bool nextStrong_; |
---|
| 351 | // Current rhs |
---|
| 352 | double rhs_; |
---|
| 353 | // Save allowable gap |
---|
| 354 | double savedGap_; |
---|
| 355 | // Best solution |
---|
| 356 | double bestCutoff_; |
---|
| 357 | // time limit per subtree |
---|
| 358 | int timeLimit_; |
---|
| 359 | // time when subtree started |
---|
| 360 | int startTime_; |
---|
| 361 | // node limit for subtree |
---|
| 362 | int nodeLimit_; |
---|
| 363 | // node count when subtree started |
---|
| 364 | int startNode_; |
---|
| 365 | // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step |
---|
| 366 | int searchType_; |
---|
| 367 | // Whether to do refinement step |
---|
| 368 | bool refine_; |
---|
[185] | 369 | |
---|
| 370 | }; |
---|
| 371 | #endif |
---|
| 372 | |
---|