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 | inline void setProposalActions(int fullDWEverySoOften) |
---|
77 | { fullDWEverySoOften_=fullDWEverySoOften;} |
---|
78 | /// Objective value when whichDw created |
---|
79 | double objectiveValueWhen(int whichDW) const; |
---|
80 | /// Number of columns in DW |
---|
81 | int numberColumnsDW(int whichDW) const; |
---|
82 | /// Solver |
---|
83 | inline OsiSolverInterface * solver() const |
---|
84 | { return solver_;} |
---|
85 | /// DW model (user must delete) |
---|
86 | OsiSolverInterface * DWModel(int whichDW) const; |
---|
87 | /// Best objective value |
---|
88 | inline double bestObjective() const |
---|
89 | { return bestObjective_;} |
---|
90 | /// Best solution found so far |
---|
91 | inline const double * bestSolution() const |
---|
92 | { return bestSolution_;} |
---|
93 | /// Objective at which DW updated |
---|
94 | inline const double * objectiveDW() const |
---|
95 | { return objectiveDW_;} |
---|
96 | /// Number of times we have added to DW model |
---|
97 | inline int numberDWTimes() const |
---|
98 | { return numberDWTimes_;} |
---|
99 | /// Number of columns in DW |
---|
100 | inline const int * numberColumnsDW() const |
---|
101 | { return numberColumnsDW_;} |
---|
102 | /// Set number of passes |
---|
103 | inline void setNumberPasses(int value) |
---|
104 | { numberPasses_ = value;} |
---|
105 | /// Set number free integers needed |
---|
106 | inline void setNumberNeeded(int value) |
---|
107 | { nNeededBase_ = value;} |
---|
108 | /// Set target objective |
---|
109 | inline void setTargetObjective(double value) |
---|
110 | { targetObjective_ = value;} |
---|
111 | /// Sets how often to do it |
---|
112 | inline void setHowOften(int value) { |
---|
113 | howOften_ = value; |
---|
114 | } |
---|
115 | /// Block for every row |
---|
116 | inline const int * whichRowBlock() const |
---|
117 | { return whichRowBlock_;} |
---|
118 | /// Block for every column |
---|
119 | inline const int * whichColumnBlock() const |
---|
120 | { return whichColumnBlock_;} |
---|
121 | /// Initial Lower bounds |
---|
122 | inline const double * initialLower() const |
---|
123 | { return saveLower_;} |
---|
124 | /// Initial Upper bounds |
---|
125 | inline const double * initialUpper() const |
---|
126 | { return saveUpper_;} |
---|
127 | /// Objective value (could also check validity) |
---|
128 | double objectiveValue(const double * solution); |
---|
129 | private: |
---|
130 | /// Guts of copy |
---|
131 | void gutsOfCopy(const CbcHeuristicDW & rhs); |
---|
132 | /// Guts of delete |
---|
133 | void gutsOfDelete(); |
---|
134 | /// Set default values |
---|
135 | void setDefaults(); |
---|
136 | /// Find structure |
---|
137 | void findStructure(); |
---|
138 | /// Add DW proposals |
---|
139 | int addDW(const double * solution,int numberBlocksUsed, |
---|
140 | const int * whichBlocks); |
---|
141 | protected: |
---|
142 | typedef int (*heuristicCallBack) (CbcHeuristicDW * ,CbcModel *, int) ; |
---|
143 | // Data |
---|
144 | /// Target objective |
---|
145 | double targetObjective_; |
---|
146 | /// Best objective value |
---|
147 | double bestObjective_; |
---|
148 | /// Objective value last time |
---|
149 | double lastObjective_; |
---|
150 | /** Call back |
---|
151 | whereFrom - |
---|
152 | 0 - after blocks found but before data setup |
---|
153 | 1 - after blocks sorted but before used |
---|
154 | 2 - just before normal branch and bound |
---|
155 | 3 - after DW has been updated |
---|
156 | 4 - if better solution found |
---|
157 | Pointers to local data given by following pointers |
---|
158 | */ |
---|
159 | heuristicCallBack functionPointer_; |
---|
160 | /// Local integer arrays (each numberBlocks_ long) |
---|
161 | int * intArray_; |
---|
162 | /// Local double arrays (each numberBlocks_ long) |
---|
163 | double * doubleArray_; |
---|
164 | /// Base solver |
---|
165 | OsiSolverInterface * solver_; |
---|
166 | /// DW solver |
---|
167 | OsiSolverInterface * dwSolver_; |
---|
168 | /// Best solution found so far |
---|
169 | double * bestSolution_; |
---|
170 | /// Continuous solution |
---|
171 | double * continuousSolution_; |
---|
172 | /// Original lower bounds |
---|
173 | double * saveLower_; |
---|
174 | /// Original Upper bounds |
---|
175 | double * saveUpper_; |
---|
176 | /// random numbers for master rows |
---|
177 | double * random_; |
---|
178 | /// Weights for each proposal |
---|
179 | double * weights_; |
---|
180 | /// Objective at which DW updated |
---|
181 | double * objectiveDW_; |
---|
182 | /// Number of columns in each DW |
---|
183 | int * numberColumnsDW_; |
---|
184 | /// Block for every row |
---|
185 | int * whichRowBlock_; |
---|
186 | /// Block for every column |
---|
187 | int * whichColumnBlock_; |
---|
188 | /// Block number for each proposal |
---|
189 | int * dwBlock_; |
---|
190 | /// Points back to master rows |
---|
191 | int * backwardRow_; |
---|
192 | /// Which rows are in blocke |
---|
193 | int * rowsInBlock_; |
---|
194 | /// Which columns are in block |
---|
195 | int * columnsInBlock_; |
---|
196 | /// Starts for rowsInBlock |
---|
197 | int * startRowBlock_; |
---|
198 | /// Starts for columnsInBlock |
---|
199 | int * startColumnBlock_; |
---|
200 | /// Number of integer variables in each block |
---|
201 | int * intsInBlock_; |
---|
202 | /// Bits set for 1 integers in each block |
---|
203 | unsigned int * fingerPrint_; |
---|
204 | /// Affinity each block has for other (will be triangular?) |
---|
205 | unsigned short * affinity_; |
---|
206 | /** DW Proposal actions |
---|
207 | fullDWEverySoOften - |
---|
208 | 0 - off |
---|
209 | k - every k times solution gets better |
---|
210 | */ |
---|
211 | int fullDWEverySoOften_; |
---|
212 | /// Number of passes |
---|
213 | int numberPasses_; |
---|
214 | /// How often to do (code can change) |
---|
215 | int howOften_; |
---|
216 | /// Current maximum number of DW proposals |
---|
217 | int maximumDW_; |
---|
218 | /// Number of DW proposals |
---|
219 | int numberDW_; |
---|
220 | /// Number of times we have added to DW model |
---|
221 | int numberDWTimes_; |
---|
222 | /// Number of unsigned ints needed for each block of fingerPrint |
---|
223 | int sizeFingerPrint_; |
---|
224 | /// Number of columns in master |
---|
225 | int numberMasterColumns_; |
---|
226 | /// Number of rows in master |
---|
227 | int numberMasterRows_; |
---|
228 | /// Number of blocks |
---|
229 | int numberBlocks_; |
---|
230 | /// Action on decomposition - 1 keep continuous, 0 don't |
---|
231 | int keepContinuous_; |
---|
232 | /// Phase of solution |
---|
233 | int phase_; |
---|
234 | /// Base number of integers needed |
---|
235 | int nNeededBase_; |
---|
236 | /// Base number of nodes needed |
---|
237 | int nNodesBase_; |
---|
238 | /// Base number of integers needed |
---|
239 | int nNeeded_; |
---|
240 | /// Base number of nodes needed |
---|
241 | int nNodes_; |
---|
242 | // 0 - fine, 1 can't be better, 2 max node |
---|
243 | int solveState_; |
---|
244 | }; |
---|
245 | |
---|
246 | #endif |
---|