Scippy

SCIP

Solving Constraint Integer Programs

history.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file history.h
17  * @brief internal methods for branching and inference history
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_HISTORY_H__
25 #define __SCIP_HISTORY_H__
26 
27 
28 #include "scip/def.h"
29 #include "blockmemshell/memory.h"
30 #include "scip/type_retcode.h"
31 #include "scip/type_set.h"
32 #include "scip/type_history.h"
33 
34 #ifdef NDEBUG
35 #include "scip/struct_history.h"
36 #endif
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 /** creates an empty history entry */
43 extern
44 SCIP_RETCODE SCIPhistoryCreate(
45  SCIP_HISTORY** history, /**< pointer to store branching and inference history */
46  BMS_BLKMEM* blkmem /**< block memory */
47  );
48 
49 /** frees a history entry */
50 extern
51 void SCIPhistoryFree(
52  SCIP_HISTORY** history, /**< pointer to branching and inference history */
53  BMS_BLKMEM* blkmem /**< block memory */
54  );
55 
56 /** resets history entry to zero */
57 extern
58 void SCIPhistoryReset(
59  SCIP_HISTORY* history /**< branching and inference history */
60  );
61 
62 /** unites two history entries by adding the values of the second one to the first one */
63 extern
64 void SCIPhistoryUnite(
65  SCIP_HISTORY* history, /**< branching and inference history */
66  SCIP_HISTORY* addhistory, /**< history values to add to history */
67  SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */
68  );
69 
70 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
71  * in the LP's objective value
72  */
73 extern
74 void SCIPhistoryUpdatePseudocost(
75  SCIP_HISTORY* history, /**< branching and inference history */
76  SCIP_SET* set, /**< global SCIP settings */
77  SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */
78  SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */
79  SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */
80  );
81 
82 
83 /**@defgroup ValueHistory Value based history
84  *
85  * Value based history methods
86  *
87  * @{
88  */
89 
90 /** creates an empty value history */
91 extern
92 SCIP_RETCODE SCIPvaluehistoryCreate(
93  SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */
94  BMS_BLKMEM* blkmem /**< block memory */
95  );
96 
97 /** frees a value history */
98 extern
99 void SCIPvaluehistoryFree(
100  SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */
101  BMS_BLKMEM* blkmem /**< block memory */
102  );
103 
104 /** finds for the given domain value the history if it does not exist yet it will be created */
105 extern
106 SCIP_RETCODE SCIPvaluehistoryFind(
107  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
108  BMS_BLKMEM* blkmem, /**< block memory */
109  SCIP_SET* set, /**< global SCIP settings */
110  SCIP_Real value, /**< domain value of interest */
111  SCIP_HISTORY** history /**< pointer to store the history for the given domain value */
112  );
113 
114 /** scales the conflict score values with the given scalar for each value history entry */
115 extern
116 void SCIPvaluehistoryScaleVSIDS(
117  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
118  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
119  );
120 
121 /**@} */
122 
123 /** returns the opposite direction of the given branching direction */
124 extern
125 SCIP_BRANCHDIR SCIPbranchdirOpposite(
126  SCIP_BRANCHDIR dir /**< branching direction */
127  );
128 
129 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
130 extern
131 SCIP_Real SCIPhistoryGetPseudocost(
132  SCIP_HISTORY* history, /**< branching and inference history */
133  SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */
134  );
135 
136 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in
137  * the given branching direction
138  */
139 extern
140 SCIP_Real SCIPhistoryGetPseudocostCount(
141  SCIP_HISTORY* history, /**< branching and inference history */
142  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
143  );
144 
145 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
146 extern
147 SCIP_Bool SCIPhistoryIsPseudocostEmpty(
148  SCIP_HISTORY* history, /**< branching and inference history */
149  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
150  );
151 
152 /** increases the conflict score of the history entry by the given weight */
153 extern
154 void SCIPhistoryIncVSIDS(
155  SCIP_HISTORY* history, /**< branching and inference history */
156  SCIP_BRANCHDIR dir, /**< branching direction */
157  SCIP_Real weight /**< weight of this update in conflict score */
158  );
159 
160  /** scales the conflict score values with the given scalar */
161 extern
162 void SCIPhistoryScaleVSIDS(
163  SCIP_HISTORY* history, /**< branching and inference history */
164  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
165  );
166 
167 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
168 extern
169 void SCIPhistoryIncNActiveConflicts(
170  SCIP_HISTORY* history, /**< branching and inference history */
171  SCIP_BRANCHDIR dir, /**< branching direction */
172  SCIP_Real length /**< length of the conflict */
173  );
174 
175 /** gets the number of active conflicts of the history entry */
176 extern
177 SCIP_Longint SCIPhistoryGetNActiveConflicts(
178  SCIP_HISTORY* history, /**< branching and inference history */
179  SCIP_BRANCHDIR dir /**< branching direction */
180  );
181 
182 /** gets the average conflict length of the history entry */
183 extern
184 SCIP_Real SCIPhistoryGetAvgConflictlength(
185  SCIP_HISTORY* history, /**< branching and inference history */
186  SCIP_BRANCHDIR dir /**< branching direction */
187  );
188 
189 /** increases the number of branchings counter */
190 extern
191 void SCIPhistoryIncNBranchings(
192  SCIP_HISTORY* history, /**< branching and inference history */
193  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
194  int depth /**< depth at which the bound change took place */
195  );
196 
197 /** increases the number of inferences counter */
198 extern
199 void SCIPhistoryIncInferenceSum(
200  SCIP_HISTORY* history, /**< branching and inference history */
201  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
202  SCIP_Real weight /**< weight of this update in cutoff score */
203  );
204 
205 
206 /** increases the number of cutoffs counter */
207 extern
208 void SCIPhistoryIncCutoffSum(
209  SCIP_HISTORY* history, /**< branching and inference history */
210  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
211  SCIP_Real weight /**< weight of this update in cutoff score */
212  );
213 
214 /** get number of branchings counter */
215 extern
216 SCIP_Longint SCIPhistoryGetNBranchings(
217  SCIP_HISTORY* history, /**< branching and inference history */
218  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
219  );
220 
221 /** get number of inferences counter */
222 extern
223 SCIP_Real SCIPhistoryGetInferenceSum(
224  SCIP_HISTORY* history, /**< branching and inference history */
225  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
226  );
227 
228 /** returns the average number of inferences per branching */
229 extern
230 SCIP_Real SCIPhistoryGetAvgInferences(
231  SCIP_HISTORY* history, /**< branching and inference history */
232  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
233  );
234 
235 /** returns the average number of cutoffs per branching */
236 extern
237 SCIP_Real SCIPhistoryGetAvgCutoffs(
238  SCIP_HISTORY* history, /**< branching and inference history */
239  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
240  );
241 
242 /** returns the average depth of bound changes due to branching */
243 extern
244 SCIP_Real SCIPhistoryGetAvgBranchdepth(
245  SCIP_HISTORY* history, /**< branching and inference history */
246  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
247  );
248 
249 #ifdef NDEBUG
250 
251 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
252  * speed up the algorithms.
253  */
254 
255 #define SCIPbranchdirOpposite(dir) \
256  ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \
257  : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
258 #define SCIPhistoryGetPseudocost(history,solvaldelta) \
259  ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
260  ? (history)->pscostsum[1] / (history)->pscostcount[1] : 1.0) \
261  : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \
262  ? (history)->pscostsum[0] / (history)->pscostcount[0] : 1.0) )
263 #define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
264 #define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0)
265 #define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
266 #define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \
267  (history)->vsids[1] *= (scalar); }
268 #define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
269  (history)->conflengthsum[dir] += length; }
270 #define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
271 #define SCIPhistoryGetAvgConflictlength(history,dir) ((history)->conflengthsum[dir] > 0.0 \
272  ? (SCIP_Real)(history)->nactiveconflicts[dir]/(SCIP_Real)(history)->conflengthsum[dir] : 0.0)
273 #define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
274  (history)->branchdepthsum[dir] += depth; }
275 #define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight)
276 #define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight)
277 #define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir])
278 #define SCIPhistoryGetInferenceSum(history,dir) ((history)->inferencesum[dir])
279 #define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \
280  ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
281 #define SCIPhistoryGetCutoffSum(history,dir) ((history)->cutoffsum[dir])
282 #define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \
283  ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
284 #define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \
285  ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
286 
287 #endif
288 
289 #ifdef __cplusplus
290 }
291 #endif
292 
293 #endif
294