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