1 | // $Id: CbcHeuristicDW.hpp 1899 2013-04-09 18:12:08Z stefan $ |
---|
2 | // Copyright (C) 2006, International Business Machines |
---|
3 | // Corporation and others. All Rights Reserved. |
---|
4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
5 | |
---|
6 | |
---|
7 | #ifndef CbcHeuristicDW_H |
---|
8 | #define CbcHeuristicDW_H |
---|
9 | |
---|
10 | #include "CbcHeuristic.hpp" |
---|
11 | |
---|
12 | /** |
---|
13 | This is unlike the other heuristics in that it is very very compute intensive. |
---|
14 | It tries to find a DW structure and use that |
---|
15 | */ |
---|
16 | |
---|
17 | class CbcHeuristicDW : public CbcHeuristic { |
---|
18 | public: |
---|
19 | |
---|
20 | // Default Constructor |
---|
21 | CbcHeuristicDW (); |
---|
22 | |
---|
23 | /* Constructor with model - assumed before cuts |
---|
24 | */ |
---|
25 | CbcHeuristicDW (CbcModel & model, int keepContinuous=0); |
---|
26 | |
---|
27 | /* Constructor with model - assumed before cuts |
---|
28 | */ |
---|
29 | CbcHeuristicDW (CbcModel & model, |
---|
30 | int callBack(CbcHeuristicDW * currentHeuristic, |
---|
31 | CbcModel * thisModel, |
---|
32 | int whereFrom), |
---|
33 | int keepContinuous=0); |
---|
34 | |
---|
35 | // Copy constructor |
---|
36 | CbcHeuristicDW ( const CbcHeuristicDW &); |
---|
37 | |
---|
38 | // Destructor |
---|
39 | ~CbcHeuristicDW (); |
---|
40 | |
---|
41 | /// Clone |
---|
42 | virtual CbcHeuristic * clone() const; |
---|
43 | |
---|
44 | |
---|
45 | /// Assignment operator |
---|
46 | CbcHeuristicDW & operator=(const CbcHeuristicDW& rhs); |
---|
47 | |
---|
48 | /// Create C++ lines to get to current state |
---|
49 | virtual void generateCpp( FILE * fp) ; |
---|
50 | |
---|
51 | /// Resets stuff if model changes |
---|
52 | virtual void resetModel(CbcModel * model); |
---|
53 | |
---|
54 | /// update model (This is needed if cliques update matrix etc) |
---|
55 | virtual void setModel(CbcModel * model); |
---|
56 | using CbcHeuristic::solution ; |
---|
57 | /** returns 0 if no solution, 1 if valid solution. |
---|
58 | Sets solution values if good, sets objective value (only if good) |
---|
59 | This does Relaxation Induced Neighborhood Search |
---|
60 | */ |
---|
61 | virtual int solution(double & objectiveValue, |
---|
62 | double * newSolution); |
---|
63 | /** Return number of blocks |
---|
64 | <=0 - no usable structure */ |
---|
65 | inline int numberBlocks() const |
---|
66 | { return numberBlocks_;} |
---|
67 | /// Pass in a solution |
---|
68 | void passInSolution(const double * solution); |
---|
69 | /// Pass in continuous solution |
---|
70 | void passInContinuousSolution(const double * solution); |
---|
71 | /** DW Proposal actions |
---|
72 | fullDWEverySoOften - |
---|
73 | 0 - off |
---|
74 | k - every k times solution gets better |
---|
75 | */ |
---|
76 | void setProposalActions(int fullDWEverySoOften); |
---|
77 | /// Objective value when whichDw created |
---|
78 | double objectiveValueWhen(int whichDW) const; |
---|
79 | /// Number of columns in DW |
---|
80 | int numberColumnsDW(int whichDW) const; |
---|
81 | /// Solver |
---|
82 | inline OsiSolverInterface * solver() const |
---|
83 | { return solver_;} |
---|
84 | /// DW model (user must delete) |
---|
85 | OsiSolverInterface * DWModel(int whichDW) const; |
---|
86 | /// Best objective value |
---|
87 | inline double bestObjective() const |
---|
88 | { return bestObjective_;} |
---|
89 | /// Best solution found so far |
---|
90 | inline const double * bestSolution() const |
---|
91 | { return bestSolution_;} |
---|
92 | /// Continuous solution |
---|
93 | inline const double * continuousSolution() const |
---|
94 | { return continuousSolution_;} |
---|
95 | /// Reduced costs of fixed solution |
---|
96 | inline const double * fixedDj() const |
---|
97 | { return fixedDj_;} |
---|
98 | /// Objective at which DW updated |
---|
99 | inline const double * objectiveDW() const |
---|
100 | { return objectiveDW_;} |
---|
101 | /// Number of times we have added to DW model |
---|
102 | inline int numberDWTimes() const |
---|
103 | { return numberDWTimes_;} |
---|
104 | /// Number of columns in DW |
---|
105 | inline const int * numberColumnsDW() const |
---|
106 | { return numberColumnsDW_;} |
---|
107 | /// Set number of passes |
---|
108 | inline void setNumberPasses(int value) |
---|
109 | { numberPasses_ = value;} |
---|
110 | /// Set number of passes without better solution |
---|
111 | inline void setNumberBadPasses(int value) |
---|
112 | { numberBadPasses_ = value;} |
---|
113 | /// Set number free integers needed (Base value) |
---|
114 | inline void setNumberNeeded(int value) |
---|
115 | { nNeededBase_ = value;} |
---|
116 | /// Get number free integers needed (Base value) |
---|
117 | inline int getNumberNeeded() const |
---|
118 | {return nNeededBase_;} |
---|
119 | /// Set number free integers needed (Current value) |
---|
120 | inline void setCurrentNumberNeeded(int value) |
---|
121 | { nNeeded_ = value;} |
---|
122 | /// Get number free integers needed (Current value) |
---|
123 | inline int getCurrentNumberNeeded() const |
---|
124 | {return nNeeded_;} |
---|
125 | /// Set number nodes (could be done in callback) (Base value) |
---|
126 | inline void setNumberNodes(int value) |
---|
127 | { nNodesBase_ = value;} |
---|
128 | /// Get number nodes (could be done in callback) (Base value) |
---|
129 | inline int getNumberNodes() const |
---|
130 | {return nNodesBase_;} |
---|
131 | /// Set number nodes (could be done in callback) (Current value) |
---|
132 | inline void setCurrentNumberNodes(int value) |
---|
133 | { nNodes_ = value;} |
---|
134 | /// Get number nodes (could be done in callback) (Current value) |
---|
135 | inline int getCurrentNumberNodes() const |
---|
136 | {return nNodes_;} |
---|
137 | /// Set target objective |
---|
138 | inline void setTargetObjective(double value) |
---|
139 | { targetObjective_ = value;} |
---|
140 | /// Sets how often to do it |
---|
141 | inline void setHowOften(int value) { |
---|
142 | howOften_ = value; |
---|
143 | } |
---|
144 | /// Block for every row |
---|
145 | inline const int * whichRowBlock() const |
---|
146 | { return whichRowBlock_;} |
---|
147 | /// Block for every column |
---|
148 | inline const int * whichColumnBlock() const |
---|
149 | { return whichColumnBlock_;} |
---|
150 | /// Initial Lower bounds |
---|
151 | inline double * initialLower() const |
---|
152 | { return saveLower_;} |
---|
153 | /// Initial Upper bounds |
---|
154 | inline double * initialUpper() const |
---|
155 | { return saveUpper_;} |
---|
156 | /// Local integer arrays (each numberBlocks_ long) |
---|
157 | inline int * intArrays() const |
---|
158 | { return intArray_;} |
---|
159 | /// Local double arrays (each numberBlocks_ long) |
---|
160 | inline double * doubleArrays() const |
---|
161 | { return doubleArray_;} |
---|
162 | /// Phase of solution |
---|
163 | inline int phase() const |
---|
164 | { return phase_;} |
---|
165 | /// Pass number |
---|
166 | inline int pass() const |
---|
167 | { return pass_;} |
---|
168 | /// Which columns are in block |
---|
169 | inline const int * columnsInBlock() const |
---|
170 | { return columnsInBlock_;} |
---|
171 | /// Starts for columnsInBlock |
---|
172 | inline const int * startColumnBlock() const |
---|
173 | { return startColumnBlock_;} |
---|
174 | /// Number of integer variables in each block |
---|
175 | inline const int * intsInBlock() const |
---|
176 | { return intsInBlock_;} |
---|
177 | /// Objective value (could also check validity) |
---|
178 | double objectiveValue(const double * solution); |
---|
179 | private: |
---|
180 | /// Guts of copy |
---|
181 | void gutsOfCopy(const CbcHeuristicDW & rhs); |
---|
182 | /// Guts of delete |
---|
183 | void gutsOfDelete(); |
---|
184 | /// Set default values |
---|
185 | void setDefaults(); |
---|
186 | /// Find structure |
---|
187 | void findStructure(); |
---|
188 | /// Set up DW structure |
---|
189 | void setupDWStructures(); |
---|
190 | /// Add DW proposals |
---|
191 | int addDW(const double * solution,int numberBlocksUsed, |
---|
192 | const int * whichBlocks); |
---|
193 | protected: |
---|
194 | typedef int (*heuristicCallBack) (CbcHeuristicDW * ,CbcModel *, int) ; |
---|
195 | // Data |
---|
196 | /// Target objective |
---|
197 | double targetObjective_; |
---|
198 | /// Best objective value |
---|
199 | double bestObjective_; |
---|
200 | /// Objective value last time |
---|
201 | double lastObjective_; |
---|
202 | /** Call back |
---|
203 | whereFrom - |
---|
204 | 0 - after blocks found but before data setup |
---|
205 | 1 - after blocks sorted but before used |
---|
206 | 2 - just before normal branch and bound |
---|
207 | 3 - after DW has been updated |
---|
208 | 4 - if better solution found |
---|
209 | 5 - every time a block might be used |
---|
210 | next few for adjustment of nNeeded etc |
---|
211 | 6 - complete search done - no solution |
---|
212 | 7 - stopped on nodes - no improvement |
---|
213 | 8 - improving (same as 4 but after nNeeded changed |
---|
214 | Pointers to local data given by following pointers |
---|
215 | */ |
---|
216 | heuristicCallBack functionPointer_; |
---|
217 | /// Local integer arrays (each numberBlocks_ long) |
---|
218 | int * intArray_; |
---|
219 | /// Local double arrays (each numberBlocks_ long) |
---|
220 | double * doubleArray_; |
---|
221 | /// Base solver |
---|
222 | OsiSolverInterface * solver_; |
---|
223 | /// DW solver |
---|
224 | OsiSolverInterface * dwSolver_; |
---|
225 | /// Best solution found so far |
---|
226 | double * bestSolution_; |
---|
227 | /// Continuous solution |
---|
228 | double * continuousSolution_; |
---|
229 | /// Reduced costs of fixed solution |
---|
230 | double * fixedDj_; |
---|
231 | /// Original lower bounds |
---|
232 | double * saveLower_; |
---|
233 | /// Original Upper bounds |
---|
234 | double * saveUpper_; |
---|
235 | /// random numbers for master rows |
---|
236 | double * random_; |
---|
237 | /// Weights for each proposal |
---|
238 | double * weights_; |
---|
239 | /// Objective at which DW updated |
---|
240 | double * objectiveDW_; |
---|
241 | /// Number of columns in each DW |
---|
242 | int * numberColumnsDW_; |
---|
243 | /// Block for every row |
---|
244 | int * whichRowBlock_; |
---|
245 | /// Block for every column |
---|
246 | int * whichColumnBlock_; |
---|
247 | /// Block number for each proposal |
---|
248 | int * dwBlock_; |
---|
249 | /// Points back to master rows |
---|
250 | int * backwardRow_; |
---|
251 | /// Which rows are in blocke |
---|
252 | int * rowsInBlock_; |
---|
253 | /// Which columns are in block |
---|
254 | int * columnsInBlock_; |
---|
255 | /// Starts for rowsInBlock |
---|
256 | int * startRowBlock_; |
---|
257 | /// Starts for columnsInBlock |
---|
258 | int * startColumnBlock_; |
---|
259 | /// Number of integer variables in each block |
---|
260 | int * intsInBlock_; |
---|
261 | /// Bits set for 1 integers in each block |
---|
262 | unsigned int * fingerPrint_; |
---|
263 | /// Affinity each block has for other (will be triangular?) |
---|
264 | unsigned short * affinity_; |
---|
265 | /** DW Proposal actions |
---|
266 | fullDWEverySoOften - |
---|
267 | 0 - off |
---|
268 | k - every k times solution gets better |
---|
269 | */ |
---|
270 | int fullDWEverySoOften_; |
---|
271 | /// Number of passes |
---|
272 | int numberPasses_; |
---|
273 | /// How often to do (code can change) |
---|
274 | int howOften_; |
---|
275 | /// Current maximum number of DW proposals |
---|
276 | int maximumDW_; |
---|
277 | /// Number of DW proposals |
---|
278 | int numberDW_; |
---|
279 | /// Number of times we have added to DW model |
---|
280 | int numberDWTimes_; |
---|
281 | /// Number of unsigned ints needed for each block of fingerPrint |
---|
282 | int sizeFingerPrint_; |
---|
283 | /// Number of columns in master |
---|
284 | int numberMasterColumns_; |
---|
285 | /// Number of rows in master |
---|
286 | int numberMasterRows_; |
---|
287 | /// Number of blocks |
---|
288 | int numberBlocks_; |
---|
289 | /// Action on decomposition - 1 keep continuous, 0 don't |
---|
290 | int keepContinuous_; |
---|
291 | /// Phase of solution |
---|
292 | int phase_; |
---|
293 | /// Pass number |
---|
294 | int pass_; |
---|
295 | /// Base number of integers needed |
---|
296 | int nNeededBase_; |
---|
297 | /// Base number of nodes needed |
---|
298 | int nNodesBase_; |
---|
299 | /// Base number of integers needed |
---|
300 | int nNeeded_; |
---|
301 | /// Base number of nodes needed |
---|
302 | int nNodes_; |
---|
303 | /// Number of passes without better solution |
---|
304 | int numberBadPasses_; |
---|
305 | // 0 - fine, 1 can't be better, 2 max node |
---|
306 | int solveState_; |
---|
307 | }; |
---|
308 | |
---|
309 | #endif |
---|