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; |
---|
70 | |
---|
71 | /*! \name Heap access and maintenance methods */ |
---|
72 | //@{ |
---|
73 | |
---|
74 | /// Return the top node of the heap |
---|
75 | virtual CbcNode * top() const; |
---|
76 | |
---|
77 | /// Add a node to the heap |
---|
78 | virtual void push(CbcNode * x); |
---|
79 | |
---|
80 | /// Remove the top node from the heap |
---|
81 | virtual void pop() ; |
---|
82 | |
---|
83 | //@} |
---|
84 | /*! \name Other stuff */ |
---|
85 | //@{ |
---|
86 | |
---|
87 | /// Create cut - return -1 if bad, 0 if okay and 1 if cut is everything |
---|
88 | int createCut(const double * solution, OsiRowCut & cut); |
---|
89 | |
---|
90 | /// Test if empty *** note may be overridden |
---|
91 | virtual bool empty() ; |
---|
92 | |
---|
93 | /// We may have got an intelligent tree so give it one more chance |
---|
94 | virtual void endSearch() ; |
---|
95 | /// Other side of last cut branch (if bias==rhs_ will be weakest possible) |
---|
96 | void reverseCut(int state, double bias=0.0); |
---|
97 | /// Delete last cut branch |
---|
98 | void deleteCut(OsiRowCut & cut); |
---|
99 | /// Pass in solution (so can be used after heuristic) |
---|
100 | void passInSolution(const double * solution, double solutionValue); |
---|
101 | |
---|
102 | //@} |
---|
103 | private: |
---|
104 | // Node for local cuts |
---|
105 | CbcNode * localNode_; |
---|
106 | // best solution |
---|
107 | double * bestSolution_; |
---|
108 | // saved solution |
---|
109 | double * savedSolution_; |
---|
110 | // solution number at start of pass |
---|
111 | int saveNumberSolutions_; |
---|
112 | /* Cut. If zero size then no solution yet. Otherwise is left hand branch */ |
---|
113 | OsiRowCut cut_; |
---|
114 | // This cut fixes all 0-1 variables |
---|
115 | OsiRowCut fixedCut_; |
---|
116 | // Model |
---|
117 | CbcModel * model_; |
---|
118 | // Original lower bounds |
---|
119 | double * originalLower_; |
---|
120 | // Original upper bounds |
---|
121 | double * originalUpper_; |
---|
122 | // range i.e. k |
---|
123 | int range_; |
---|
124 | // Type of cuts - 0=just 0-1, 1=all |
---|
125 | int typeCuts_; |
---|
126 | // maximum number of diversifications |
---|
127 | int maxDiversification_; |
---|
128 | // current diversification |
---|
129 | int diversification_; |
---|
130 | // Whether next will be strong diversification |
---|
131 | bool nextStrong_; |
---|
132 | // Current rhs |
---|
133 | double rhs_; |
---|
134 | // Save allowable gap |
---|
135 | double savedGap_; |
---|
136 | // Best solution |
---|
137 | double bestCutoff_; |
---|
138 | // time limit per subtree |
---|
139 | int timeLimit_; |
---|
140 | // time when subtree started |
---|
141 | int startTime_; |
---|
142 | // node limit for subtree |
---|
143 | int nodeLimit_; |
---|
144 | // node count when subtree started |
---|
145 | int startNode_; |
---|
146 | // -1 not started, 0 == stop on first solution, 1 don't stop on first, 2 refinement step |
---|
147 | int searchType_; |
---|
148 | // Whether to do refinement step |
---|
149 | bool refine_; |
---|
150 | |
---|
151 | }; |
---|
152 | #endif |
---|
153 | |
---|