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
16class ClpFactorization;
17class ClpDualRowSteepest;
18class ClpNodeStuff;
19class ClpNode {
20
21public:
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
119protected:
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};
176class ClpNodeStuff {
177
178public:
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
214public:
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};
288class ClpHashValue {
289
290public:
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 //@}
320private:
321 /**@name private stuff */
322 //@{
323 /** returns hash */
324 int hash(double value) const;
325 /// Resizes
326 void resize(bool increaseMax);
327 //@}
328
329protected:
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
350