[185] | 1 | // Copyright (C) 2004, International Business Machines |
---|
| 2 | // Corporation and others. All Rights Reserved. |
---|
| 3 | #ifndef CbcTreeLocal_H |
---|
| 4 | #define CbcTreeLocal_H |
---|
| 5 | |
---|
| 6 | //############################################################################# |
---|
| 7 | /* This implements (approximately) local branching as in the 2002 paper by |
---|
| 8 | Matteo Fischetti and Andrea Lodi. |
---|
| 9 | |
---|
| 10 | The very simple version of the algorithm for problems with |
---|
| 11 | 0-1 variables and continuous is as follows: |
---|
| 12 | |
---|
| 13 | Obtain a feasible solution (one can be passed in). |
---|
| 14 | |
---|
| 15 | Add a cut which limits search to a k neighborhood of this solution. |
---|
| 16 | (At most k 0-1 variables may change value) |
---|
| 17 | Do branch and bound on this problem. |
---|
| 18 | |
---|
| 19 | If finished search and proven optimal then we can reverse cut so |
---|
| 20 | any solutions must be at least k+1 away from solution and we can |
---|
| 21 | add a new cut limiting search to a k neighborhood of new solution |
---|
| 22 | repeat. |
---|
| 23 | |
---|
| 24 | If finished search and no new solution then the simplest version |
---|
| 25 | would reverse last cut and complete search. The version implemented |
---|
| 26 | here can use time and node limits and can widen search (increase effective k) |
---|
| 27 | .... and more |
---|
| 28 | |
---|
| 29 | */ |
---|
| 30 | |
---|
| 31 | #include "CbcTree.hpp" |
---|
| 32 | #include "CbcNode.hpp" |
---|
| 33 | #include "OsiRowCut.hpp" |
---|
| 34 | class CbcModel; |
---|
| 35 | |
---|
| 36 | |
---|
| 37 | class CbcTreeLocal : public CbcTree { |
---|
| 38 | |
---|
| 39 | public: |
---|
| 40 | |
---|
| 41 | // Default Constructor |
---|
| 42 | CbcTreeLocal (); |
---|
| 43 | |
---|
| 44 | /* Constructor with solution. |
---|
| 45 | If solution NULL no solution, otherwise must be integer |
---|
| 46 | range is initial upper bound (k) on difference from given solution. |
---|
| 47 | typeCuts - |
---|
| 48 | 0 means just 0-1 cuts and will need to refine 0-1 solution |
---|
| 49 | 1 uses weaker cuts on all integer variables |
---|
| 50 | maxDiversification is maximum number of range widenings to try |
---|
| 51 | timeLimit is seconds in subTree |
---|
| 52 | nodeLimit is nodes in subTree |
---|
| 53 | refine is whether to see if we can prove current solution is optimal |
---|
| 54 | when we fix all 0-1 (in case typeCuts==0 and there are general integer variables) |
---|
| 55 | if false then no refinement but reverse cuts weaker |
---|
| 56 | */ |
---|
| 57 | CbcTreeLocal (CbcModel * model,const double * solution ,int range=10, |
---|
| 58 | int typeCuts=0,int maxDiversification=0, |
---|
| 59 | int timeLimit=1000000, int nodeLimit=1000000,bool refine=true); |
---|
| 60 | // Copy constructor |
---|
| 61 | CbcTreeLocal ( const CbcTreeLocal & rhs); |
---|
| 62 | |
---|
| 63 | // = operator |
---|
| 64 | CbcTreeLocal & operator=(const CbcTreeLocal & rhs); |
---|
| 65 | |
---|
| 66 | virtual ~CbcTreeLocal(); |
---|
| 67 | |
---|
| 68 | /// Clone |
---|
| 69 | virtual CbcTree * clone() const; |
---|
[511] | 70 | /// Create C++ lines to get to current state |
---|
| 71 | virtual void generateCpp( FILE * fp) ; |
---|
[185] | 72 | |
---|
| 73 | /*! \name Heap access and maintenance methods */ |
---|
| 74 | //@{ |
---|
| 75 | |
---|
| 76 | /// Return the top node of the heap |
---|
[511] | 77 | virtual CbcNode * top() const; |
---|
[185] | 78 | |
---|
| 79 | /// Add a node to the heap |
---|
| 80 | virtual void push(CbcNode * x); |
---|
| 81 | |
---|
| 82 | /// Remove the top node from the heap |
---|
| 83 | virtual void pop() ; |
---|
| 84 | |
---|
| 85 | //@} |
---|
| 86 | /*! \name Other stuff */ |
---|
| 87 | //@{ |
---|
| 88 | |
---|
| 89 | /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything |
---|
| 90 | int createCut(const double * solution, OsiRowCut & cut); |
---|
| 91 | |
---|
| 92 | /// Test if empty *** note may be overridden |
---|
| 93 | virtual bool empty() ; |
---|
| 94 | |
---|
| 95 | /// We may have got an intelligent tree so give it one more chance |
---|
| 96 | virtual void endSearch() ; |
---|
| 97 | /// Other side of last cut branch (if bias==rhs_ will be weakest possible) |
---|
| 98 | void reverseCut(int state, double bias=0.0); |
---|
| 99 | /// Delete last cut branch |
---|
| 100 | void deleteCut(OsiRowCut & cut); |
---|
[186] | 101 | /// Pass in solution (so can be used after heuristic) |
---|
| 102 | void passInSolution(const double * solution, double solutionValue); |
---|
[511] | 103 | // range i.e. k |
---|
| 104 | inline int range() const |
---|
[706] | 105 | { return range_;} |
---|
[511] | 106 | // setrange i.e. k |
---|
| 107 | inline void setRange(int value) |
---|
[706] | 108 | { range_ = value;} |
---|
[511] | 109 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 110 | inline int typeCuts() const |
---|
[706] | 111 | { return typeCuts_;} |
---|
[511] | 112 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 113 | inline void setTypeCuts(int value) |
---|
[706] | 114 | { typeCuts_ = value;} |
---|
[511] | 115 | // maximum number of diversifications |
---|
| 116 | inline int maxDiversification() const |
---|
[706] | 117 | { return maxDiversification_;} |
---|
[511] | 118 | // maximum number of diversifications |
---|
| 119 | inline void setMaxDiversification(int value) |
---|
[706] | 120 | { maxDiversification_ = value;} |
---|
[511] | 121 | // time limit per subtree |
---|
| 122 | inline int timeLimit() const |
---|
[706] | 123 | { return timeLimit_;} |
---|
[511] | 124 | // time limit per subtree |
---|
| 125 | inline void setTimeLimit(int value) |
---|
[706] | 126 | { timeLimit_ = value;} |
---|
[511] | 127 | // node limit for subtree |
---|
| 128 | inline int nodeLimit() const |
---|
[706] | 129 | { return nodeLimit_;} |
---|
[511] | 130 | // node limit for subtree |
---|
| 131 | inline void setNodeLimit(int value) |
---|
[706] | 132 | { nodeLimit_ = value;} |
---|
[511] | 133 | // Whether to do refinement step |
---|
| 134 | inline bool refine() const |
---|
[706] | 135 | { return refine_;} |
---|
[511] | 136 | // Whether to do refinement step |
---|
| 137 | inline void setRefine(bool yesNo) |
---|
[706] | 138 | { refine_ = yesNo;} |
---|
[185] | 139 | |
---|
| 140 | //@} |
---|
| 141 | private: |
---|
| 142 | // Node for local cuts |
---|
| 143 | CbcNode * localNode_; |
---|
| 144 | // best solution |
---|
| 145 | double * bestSolution_; |
---|
| 146 | // saved solution |
---|
| 147 | double * savedSolution_; |
---|
| 148 | // solution number at start of pass |
---|
| 149 | int saveNumberSolutions_; |
---|
| 150 | /* Cut. If zero size then no solution yet. Otherwise is left hand branch */ |
---|
| 151 | OsiRowCut cut_; |
---|
| 152 | // This cut fixes all 0-1 variables |
---|
| 153 | OsiRowCut fixedCut_; |
---|
| 154 | // Model |
---|
| 155 | CbcModel * model_; |
---|
| 156 | // Original lower bounds |
---|
| 157 | double * originalLower_; |
---|
| 158 | // Original upper bounds |
---|
| 159 | double * originalUpper_; |
---|
| 160 | // range i.e. k |
---|
| 161 | int range_; |
---|
| 162 | // Type of cuts - 0=just 0-1, 1=all |
---|
| 163 | int typeCuts_; |
---|
| 164 | // maximum number of diversifications |
---|
| 165 | int maxDiversification_; |
---|
| 166 | // current diversification |
---|
| 167 | int diversification_; |
---|
| 168 | // Whether next will be strong diversification |
---|
| 169 | bool nextStrong_; |
---|
| 170 | // Current rhs |
---|
| 171 | double rhs_; |
---|
| 172 | // Save allowable gap |
---|
| 173 | double savedGap_; |
---|
| 174 | // Best solution |
---|
| 175 | double bestCutoff_; |
---|
| 176 | // time limit per subtree |
---|
| 177 | int timeLimit_; |
---|
| 178 | // time when subtree started |
---|
| 179 | int startTime_; |
---|
| 180 | // node limit for subtree |
---|
| 181 | int nodeLimit_; |
---|
| 182 | // node count when subtree started |
---|
| 183 | int startNode_; |
---|
| 184 | // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step |
---|
| 185 | int searchType_; |
---|
| 186 | // Whether to do refinement step |
---|
| 187 | bool refine_; |
---|
| 188 | |
---|
| 189 | }; |
---|
| 190 | #endif |
---|
| 191 | |
---|