1 | /* $Id: ClpNode.hpp 1753 2011-06-19 16:27:26Z stefan $ */ |
---|
2 | // Copyright (C) 2008, 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 | #ifndef ClpNode_H |
---|
7 | #define ClpNode_H |
---|
8 | |
---|
9 | #include "CoinPragma.hpp" |
---|
10 | |
---|
11 | // This implements all stuff for Clp fathom |
---|
12 | /** This contains what is in a Clp "node" |
---|
13 | |
---|
14 | */ |
---|
15 | |
---|
16 | class ClpFactorization; |
---|
17 | class ClpDualRowSteepest; |
---|
18 | class ClpNodeStuff; |
---|
19 | class ClpNode { |
---|
20 | |
---|
21 | public: |
---|
22 | /**@name Useful methods */ |
---|
23 | //@{ |
---|
24 | /** Applies node to model |
---|
25 | 0 - just tree bounds |
---|
26 | 1 - tree bounds and basis etc |
---|
27 | 2 - saved bounds and basis etc |
---|
28 | */ |
---|
29 | void applyNode(ClpSimplex * model, int doBoundsEtc ); |
---|
30 | /// Choose a new variable |
---|
31 | void chooseVariable(ClpSimplex * model, ClpNodeStuff * info); |
---|
32 | /// Fix on reduced costs |
---|
33 | int fixOnReducedCosts(ClpSimplex * model); |
---|
34 | /// Create odd arrays |
---|
35 | void createArrays(ClpSimplex * model); |
---|
36 | /// Clean up as crunch is different model |
---|
37 | void cleanUpForCrunch(); |
---|
38 | //@} |
---|
39 | |
---|
40 | /**@name Gets and sets */ |
---|
41 | //@{ |
---|
42 | /// Objective value |
---|
43 | inline double objectiveValue() const { |
---|
44 | return objectiveValue_; |
---|
45 | } |
---|
46 | /// Set objective value |
---|
47 | inline void setObjectiveValue(double value) { |
---|
48 | objectiveValue_ = value; |
---|
49 | } |
---|
50 | /// Primal solution |
---|
51 | inline const double * primalSolution() const { |
---|
52 | return primalSolution_; |
---|
53 | } |
---|
54 | /// Dual solution |
---|
55 | inline const double * dualSolution() const { |
---|
56 | return dualSolution_; |
---|
57 | } |
---|
58 | /// Initial value of integer variable |
---|
59 | inline double branchingValue() const { |
---|
60 | return branchingValue_; |
---|
61 | } |
---|
62 | /// Sum infeasibilities |
---|
63 | inline double sumInfeasibilities() const { |
---|
64 | return sumInfeasibilities_; |
---|
65 | } |
---|
66 | /// Number infeasibilities |
---|
67 | inline int numberInfeasibilities() const { |
---|
68 | return numberInfeasibilities_; |
---|
69 | } |
---|
70 | /// Relative depth |
---|
71 | inline int depth() const { |
---|
72 | return depth_; |
---|
73 | } |
---|
74 | /// Estimated solution value |
---|
75 | inline double estimatedSolution() const { |
---|
76 | return estimatedSolution_; |
---|
77 | } |
---|
78 | /** Way for integer variable -1 down , +1 up */ |
---|
79 | int way() const; |
---|
80 | /// Return true if branch exhausted |
---|
81 | bool fathomed() const; |
---|
82 | /// Change state of variable i.e. go other way |
---|
83 | void changeState(); |
---|
84 | /// Sequence number of integer variable (-1 if none) |
---|
85 | inline int sequence() const { |
---|
86 | return sequence_; |
---|
87 | } |
---|
88 | /// If odd arrays exist |
---|
89 | inline bool oddArraysExist() const { |
---|
90 | return lower_ != NULL; |
---|
91 | } |
---|
92 | /// Status array |
---|
93 | inline const unsigned char * statusArray() const { |
---|
94 | return status_; |
---|
95 | } |
---|
96 | //@} |
---|
97 | |
---|
98 | /**@name Constructors, destructor */ |
---|
99 | //@{ |
---|
100 | /** Default constructor. */ |
---|
101 | ClpNode(); |
---|
102 | /// Constructor from model |
---|
103 | ClpNode (ClpSimplex * model, const ClpNodeStuff * stuff, int depth); |
---|
104 | /// Does work of constructor (partly so gdb will work) |
---|
105 | void gutsOfConstructor(ClpSimplex * model, const ClpNodeStuff * stuff, |
---|
106 | int arraysExist, int depth); |
---|
107 | /** Destructor */ |
---|
108 | virtual ~ClpNode(); |
---|
109 | //@} |
---|
110 | |
---|
111 | /**@name Copy methods (at present illegal - will abort) */ |
---|
112 | //@{ |
---|
113 | /** The copy constructor. */ |
---|
114 | ClpNode(const ClpNode&); |
---|
115 | /// Operator = |
---|
116 | ClpNode& operator=(const ClpNode&); |
---|
117 | //@} |
---|
118 | |
---|
119 | protected: |
---|
120 | // For state of branch |
---|
121 | typedef struct { |
---|
122 | unsigned int firstBranch: 1; // nonzero if first branch on variable is up |
---|
123 | unsigned int branch: 2; // 0 means do first branch next, 1 second, 2 finished |
---|
124 | unsigned int spare: 29; |
---|
125 | } branchState; |
---|
126 | /**@name Data */ |
---|
127 | //@{ |
---|
128 | /// Initial value of integer variable |
---|
129 | double branchingValue_; |
---|
130 | /// Value of objective |
---|
131 | double objectiveValue_; |
---|
132 | /// Sum of infeasibilities |
---|
133 | double sumInfeasibilities_; |
---|
134 | /// Estimated solution value |
---|
135 | double estimatedSolution_; |
---|
136 | /// Factorization |
---|
137 | ClpFactorization * factorization_; |
---|
138 | /// Steepest edge weights |
---|
139 | ClpDualRowSteepest * weights_; |
---|
140 | /// Status vector |
---|
141 | unsigned char * status_; |
---|
142 | /// Primal solution |
---|
143 | double * primalSolution_; |
---|
144 | /// Dual solution |
---|
145 | double * dualSolution_; |
---|
146 | /// Integer lower bounds (only used in fathomMany) |
---|
147 | int * lower_; |
---|
148 | /// Integer upper bounds (only used in fathomMany) |
---|
149 | int * upper_; |
---|
150 | /// Pivot variables for factorization |
---|
151 | int * pivotVariables_; |
---|
152 | /// Variables fixed by reduced costs (at end of branch) 0x10000000 added if fixed to UB |
---|
153 | int * fixed_; |
---|
154 | /// State of branch |
---|
155 | branchState branchState_; |
---|
156 | /// Sequence number of integer variable (-1 if none) |
---|
157 | int sequence_; |
---|
158 | /// Number of infeasibilities |
---|
159 | int numberInfeasibilities_; |
---|
160 | /// Relative depth |
---|
161 | int depth_; |
---|
162 | /// Number fixed by reduced cost |
---|
163 | int numberFixed_; |
---|
164 | /// Flags - 1 duals scaled |
---|
165 | int flags_; |
---|
166 | /// Maximum number fixed by reduced cost |
---|
167 | int maximumFixed_; |
---|
168 | /// Maximum rows so far |
---|
169 | int maximumRows_; |
---|
170 | /// Maximum columns so far |
---|
171 | int maximumColumns_; |
---|
172 | /// Maximum Integers so far |
---|
173 | int maximumIntegers_; |
---|
174 | //@} |
---|
175 | }; |
---|
176 | class ClpNodeStuff { |
---|
177 | |
---|
178 | public: |
---|
179 | /**@name Constructors, destructor */ |
---|
180 | //@{ |
---|
181 | /** Default constructor. */ |
---|
182 | ClpNodeStuff(); |
---|
183 | /** Destructor */ |
---|
184 | virtual ~ClpNodeStuff(); |
---|
185 | //@} |
---|
186 | |
---|
187 | /**@name Copy methods (only copies ints etc, nulls arrays) */ |
---|
188 | //@{ |
---|
189 | /** The copy constructor. */ |
---|
190 | ClpNodeStuff(const ClpNodeStuff&); |
---|
191 | /// Operator = |
---|
192 | ClpNodeStuff& operator=(const ClpNodeStuff&); |
---|
193 | /// Zaps stuff 1 - arrays, 2 ints, 3 both |
---|
194 | void zap(int type); |
---|
195 | //@} |
---|
196 | |
---|
197 | |
---|
198 | /**@name Fill methods */ |
---|
199 | //@{ |
---|
200 | /** Fill with pseudocosts */ |
---|
201 | void fillPseudoCosts(const double * down, const double * up, |
---|
202 | const int * priority, |
---|
203 | const int * numberDown, const int * numberUp, |
---|
204 | const int * numberDownInfeasible, const int * numberUpInfeasible, |
---|
205 | int number); |
---|
206 | /// Update pseudo costs |
---|
207 | void update(int way, int sequence, double change, bool feasible); |
---|
208 | /// Return maximum number of nodes |
---|
209 | int maximumNodes() const; |
---|
210 | /// Return maximum space for nodes |
---|
211 | int maximumSpace() const; |
---|
212 | //@} |
---|
213 | |
---|
214 | public: |
---|
215 | /**@name Data */ |
---|
216 | //@{ |
---|
217 | /// Integer tolerance |
---|
218 | double integerTolerance_; |
---|
219 | /// Integer increment |
---|
220 | double integerIncrement_; |
---|
221 | /// Small change in branch |
---|
222 | double smallChange_; |
---|
223 | /// Down pseudo costs |
---|
224 | double * downPseudo_; |
---|
225 | /// Up pseudo costs |
---|
226 | double * upPseudo_; |
---|
227 | /// Priority |
---|
228 | int * priority_; |
---|
229 | /// Number of times down |
---|
230 | int * numberDown_; |
---|
231 | /// Number of times up |
---|
232 | int * numberUp_; |
---|
233 | /// Number of times down infeasible |
---|
234 | int * numberDownInfeasible_; |
---|
235 | /// Number of times up infeasible |
---|
236 | int * numberUpInfeasible_; |
---|
237 | /// Copy of costs (local) |
---|
238 | double * saveCosts_; |
---|
239 | /// Array of ClpNodes |
---|
240 | ClpNode ** nodeInfo_; |
---|
241 | /// Large model if crunched |
---|
242 | ClpSimplex * large_; |
---|
243 | /// Which rows in large model |
---|
244 | int * whichRow_; |
---|
245 | /// Which columns in large model |
---|
246 | int * whichColumn_; |
---|
247 | #ifndef NO_FATHOM_PRINT |
---|
248 | /// Cbc's message handler |
---|
249 | CoinMessageHandler * handler_; |
---|
250 | #endif |
---|
251 | /// Number bounds in large model |
---|
252 | int nBound_; |
---|
253 | /// Save of specialOptions_ (local) |
---|
254 | int saveOptions_; |
---|
255 | /** Options to pass to solver |
---|
256 | 1 - create external reduced costs for columns |
---|
257 | 2 - create external reduced costs for rows |
---|
258 | 4 - create external row activity (columns always done) |
---|
259 | Above only done if feasible |
---|
260 | 32 - just create up to nDepth_+1 nodes |
---|
261 | 65536 - set if activated |
---|
262 | */ |
---|
263 | int solverOptions_; |
---|
264 | /// Maximum number of nodes to do |
---|
265 | int maximumNodes_; |
---|
266 | /// Number before trust from CbcModel |
---|
267 | int numberBeforeTrust_; |
---|
268 | /// State of search from CbcModel |
---|
269 | int stateOfSearch_; |
---|
270 | /// Number deep |
---|
271 | int nDepth_; |
---|
272 | /// Number nodes returned (-1 if fathom aborted) |
---|
273 | int nNodes_; |
---|
274 | /// Number of nodes explored |
---|
275 | int numberNodesExplored_; |
---|
276 | /// Number of iterations |
---|
277 | int numberIterations_; |
---|
278 | /// Type of presolve - 0 none, 1 crunch |
---|
279 | int presolveType_; |
---|
280 | #ifndef NO_FATHOM_PRINT |
---|
281 | /// Depth passed in |
---|
282 | int startingDepth_; |
---|
283 | /// Node at which called |
---|
284 | int nodeCalled_; |
---|
285 | #endif |
---|
286 | //@} |
---|
287 | }; |
---|
288 | class ClpHashValue { |
---|
289 | |
---|
290 | public: |
---|
291 | /**@name Useful methods */ |
---|
292 | //@{ |
---|
293 | /// Return index or -1 if not found |
---|
294 | int index(double value) const; |
---|
295 | /// Add value to list and return index |
---|
296 | int addValue(double value) ; |
---|
297 | /// Number of different entries |
---|
298 | inline int numberEntries() const { |
---|
299 | return numberHash_; |
---|
300 | } |
---|
301 | //@} |
---|
302 | |
---|
303 | /**@name Constructors, destructor */ |
---|
304 | //@{ |
---|
305 | /** Default constructor. */ |
---|
306 | ClpHashValue(); |
---|
307 | /** Useful constructor. */ |
---|
308 | ClpHashValue(ClpSimplex * model); |
---|
309 | /** Destructor */ |
---|
310 | virtual ~ClpHashValue(); |
---|
311 | //@} |
---|
312 | |
---|
313 | /**@name Copy method */ |
---|
314 | //@{ |
---|
315 | /** The copy constructor. */ |
---|
316 | ClpHashValue(const ClpHashValue&); |
---|
317 | /// = |
---|
318 | ClpHashValue& operator=(const ClpHashValue&); |
---|
319 | //@} |
---|
320 | private: |
---|
321 | /**@name private stuff */ |
---|
322 | //@{ |
---|
323 | /** returns hash */ |
---|
324 | int hash(double value) const; |
---|
325 | /// Resizes |
---|
326 | void resize(bool increaseMax); |
---|
327 | //@} |
---|
328 | |
---|
329 | protected: |
---|
330 | /**@name Data members |
---|
331 | The data members are protected to allow access for derived classes. */ |
---|
332 | //@{ |
---|
333 | /// Data |
---|
334 | // for hashing |
---|
335 | typedef struct { |
---|
336 | double value; |
---|
337 | int index, next; |
---|
338 | } CoinHashLink; |
---|
339 | /// Hash table |
---|
340 | mutable CoinHashLink *hash_; |
---|
341 | /// Number of entries in hash table |
---|
342 | int numberHash_; |
---|
343 | /// Maximum number of entries in hash table i.e. size |
---|
344 | int maxHash_; |
---|
345 | /// Last used space |
---|
346 | int lastUsed_; |
---|
347 | //@} |
---|
348 | }; |
---|
349 | #endif |
---|