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-2018 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  * @ingroup INTERNALAPI
18  * @brief internal methods for branching and inference history
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_HISTORY_H__
26 #define __SCIP_HISTORY_H__
27 
28 
29 #include "scip/def.h"
30 #include "blockmemshell/memory.h"
31 #include "scip/type_retcode.h"
32 #include "scip/type_set.h"
33 #include "scip/type_history.h"
34 
35 #ifdef NDEBUG
36 #include "scip/struct_history.h"
37 #endif
38 
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42 
43 /** creates an empty history entry */
44 extern
46  SCIP_HISTORY** history, /**< pointer to store branching and inference history */
47  BMS_BLKMEM* blkmem /**< block memory */
48  );
49 
50 /** frees a history entry */
51 extern
52 void SCIPhistoryFree(
53  SCIP_HISTORY** history, /**< pointer to branching and inference history */
54  BMS_BLKMEM* blkmem /**< block memory */
55  );
56 
57 /** resets history entry to zero */
58 extern
59 void SCIPhistoryReset(
60  SCIP_HISTORY* history /**< branching and inference history */
61  );
62 
63 /** unites two history entries by adding the values of the second one to the first one */
64 extern
65 void SCIPhistoryUnite(
66  SCIP_HISTORY* history, /**< branching and inference history */
67  SCIP_HISTORY* addhistory, /**< history values to add to history */
68  SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */
69  );
70 
71 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
72  * in the LP's objective value
73  */
74 extern
76  SCIP_HISTORY* history, /**< branching and inference history */
77  SCIP_SET* set, /**< global SCIP settings */
78  SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */
79  SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */
80  SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */
81  );
82 
83 
84 /**@defgroup ValueHistory Value Based History
85  * @ingroup INTERNALAPI
86  * @brief Value based history methods
87  *
88  * @{
89  */
90 
91 /** creates an empty value history */
92 extern
94  SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */
95  BMS_BLKMEM* blkmem /**< block memory */
96  );
97 
98 /** frees a value history */
99 extern
101  SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */
102  BMS_BLKMEM* blkmem /**< block memory */
103  );
104 
105 /** finds for the given domain value the history if it does not exist yet it will be created */
106 extern
108  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
109  BMS_BLKMEM* blkmem, /**< block memory */
110  SCIP_SET* set, /**< global SCIP settings */
111  SCIP_Real value, /**< domain value of interest */
112  SCIP_HISTORY** history /**< pointer to store the history for the given domain value */
113  );
114 
115 /** scales the conflict score values with the given scalar for each value history entry */
116 extern
118  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
119  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
120  );
121 
122 /**@} */
123 
124 /** returns the opposite direction of the given branching direction */
125 extern
127  SCIP_BRANCHDIR dir /**< branching direction */
128  );
129 
130 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
131 extern
133  SCIP_HISTORY* history, /**< branching and inference history */
134  SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */
135  );
136 
137 /** returns the variance of pseudo costs about the mean. */
138 extern
140  SCIP_HISTORY* history, /**< branching and inference history */
141  SCIP_BRANCHDIR direction /**< direction of variable: 1 for upwards history, 0 for downwards history */
142  );
143 
144 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in
145  * the given branching direction
146  */
147 extern
149  SCIP_HISTORY* history, /**< branching and inference history */
150  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
151  );
152 
153 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
154 extern
156  SCIP_HISTORY* history, /**< branching and inference history */
157  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
158  );
159 
160 /** increases the conflict score of the history entry by the given weight */
161 extern
163  SCIP_HISTORY* history, /**< branching and inference history */
164  SCIP_BRANCHDIR dir, /**< branching direction */
165  SCIP_Real weight /**< weight of this update in conflict score */
166  );
167 
168  /** scales the conflict score values with the given scalar */
169 extern
171  SCIP_HISTORY* history, /**< branching and inference history */
172  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
173  );
174 
175 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
176 extern
178  SCIP_HISTORY* history, /**< branching and inference history */
179  SCIP_BRANCHDIR dir, /**< branching direction */
180  SCIP_Real length /**< length of the conflict */
181  );
182 
183 /** gets the number of active conflicts of the history entry */
184 extern
186  SCIP_HISTORY* history, /**< branching and inference history */
187  SCIP_BRANCHDIR dir /**< branching direction */
188  );
189 
190 /** gets the average conflict length of the history entry */
191 extern
193  SCIP_HISTORY* history, /**< branching and inference history */
194  SCIP_BRANCHDIR dir /**< branching direction */
195  );
196 
197 /** increases the number of branchings counter */
198 extern
200  SCIP_HISTORY* history, /**< branching and inference history */
201  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
202  int depth /**< depth at which the bound change took place */
203  );
204 
205 /** increases the number of inferences counter */
206 extern
208  SCIP_HISTORY* history, /**< branching and inference history */
209  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
210  SCIP_Real weight /**< weight of this update in cutoff score */
211  );
212 
213 
214 /** increases the number of cutoffs counter */
215 extern
217  SCIP_HISTORY* history, /**< branching and inference history */
218  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
219  SCIP_Real weight /**< weight of this update in cutoff score */
220  );
221 
222 /** get number of branchings counter */
223 extern
225  SCIP_HISTORY* history, /**< branching and inference history */
226  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
227  );
228 
229 /** get number of inferences counter */
230 extern
232  SCIP_HISTORY* history, /**< branching and inference history */
233  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
234  );
235 
236 /** returns the average number of inferences per branching */
237 extern
239  SCIP_HISTORY* history, /**< branching and inference history */
240  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
241  );
242 
243 /** returns the average number of cutoffs per branching */
244 extern
246  SCIP_HISTORY* history, /**< branching and inference history */
247  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
248  );
249 
250 /** returns the average depth of bound changes due to branching */
251 extern
253  SCIP_HISTORY* history, /**< branching and inference history */
254  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
255  );
256 
257 #ifdef NDEBUG
258 
259 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
260  * speed up the algorithms.
261  */
262 
263 #define SCIPbranchdirOpposite(dir) \
264  ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \
265  : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
266 #define SCIPhistoryGetPseudocost(history,solvaldelta) \
267  ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
268  ? (history)->pscostweightedmean[1] : 1.0) \
269  : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \
270  ? (history)->pscostweightedmean[0] : 1.0) )
271 #define SCIPhistoryGetPseudocostVariance(history, dir) \
272  ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1) \
273  * ((history)->pscostvariance[dir]) \
274  : 0.0)
275 #define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
276 #define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0)
277 #define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
278 #define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \
279  (history)->vsids[1] *= (scalar); }
280 #define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
281  (history)->conflengthsum[dir] += length; }
282 #define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
283 #define SCIPhistoryGetAvgConflictlength(history,dir) ((history)->conflengthsum[dir] > 0.0 \
284  ? (SCIP_Real)(history)->nactiveconflicts[dir]/(SCIP_Real)(history)->conflengthsum[dir] : 0.0)
285 #define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
286  (history)->branchdepthsum[dir] += depth; }
287 #define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight)
288 #define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight)
289 #define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir])
290 #define SCIPhistoryGetInferenceSum(history,dir) ((history)->inferencesum[dir])
291 #define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \
292  ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
293 #define SCIPhistoryGetCutoffSum(history,dir) ((history)->cutoffsum[dir])
294 #define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \
295  ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
296 #define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \
297  ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
298 
299 #endif
300 
301 #ifdef __cplusplus
302 }
303 #endif
304 
305 #endif
void SCIPhistoryFree(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:55
SCIP_Real SCIPhistoryGetAvgConflictlength(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:555
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:228
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:487
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:600
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:40
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition: history.c:314
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:584
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for global SCIP settings
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition: history.c:67
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition: history.c:423
type definitions for return codes for SCIP methods
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:668
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:681
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition: history.c:269
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:501
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:247
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:526
SCIP_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition: history.c:437
void SCIPhistoryUnite(SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
Definition: history.c:96
SCIP_Real SCIPhistoryGetPseudocostCount(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:461
SCIP_Bool SCIPhistoryIsPseudocostEmpty(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:474
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:542
#define SCIP_Bool
Definition: def.h:61
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: history.c:159
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:616
datastructures for branching and inference history
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition: history.c:414
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:642
#define SCIP_Real
Definition: def.h:149
type definitions for branching and inference history
SCIP_Real SCIPhistoryGetInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:629
#define SCIP_Longint
Definition: def.h:134
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition: history.c:568
memory allocation routines