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