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-2022 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 visit scipopt.org. */
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 */
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 void SCIPhistoryFree(
51  SCIP_HISTORY** history, /**< pointer to branching and inference history */
52  BMS_BLKMEM* blkmem /**< block memory */
53  );
54 
55 /** resets history entry to zero */
56 void SCIPhistoryReset(
57  SCIP_HISTORY* history /**< branching and inference history */
58  );
59 
60 /** unites two history entries by adding the values of the second one to the first one */
61 void SCIPhistoryUnite(
62  SCIP_HISTORY* history, /**< branching and inference history */
63  SCIP_HISTORY* addhistory, /**< history values to add to history */
64  SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */
65  );
66 
67 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
68  * in the LP's objective value
69  */
71  SCIP_HISTORY* history, /**< branching and inference history */
72  SCIP_SET* set, /**< global SCIP settings */
73  SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */
74  SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */
75  SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */
76  );
77 
78 
79 /**@defgroup ValueHistory Value Based History
80  * @ingroup INTERNALAPI
81  * @brief Value based history methods
82  *
83  * @{
84  */
85 
86 /** creates an empty value history */
88  SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */
89  BMS_BLKMEM* blkmem /**< block memory */
90  );
91 
92 /** frees a value history */
94  SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */
95  BMS_BLKMEM* blkmem /**< block memory */
96  );
97 
98 /** finds for the given domain value the history if it does not exist yet it will be created */
100  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
101  BMS_BLKMEM* blkmem, /**< block memory */
102  SCIP_SET* set, /**< global SCIP settings */
103  SCIP_Real value, /**< domain value of interest */
104  SCIP_HISTORY** history /**< pointer to store the history for the given domain value */
105  );
106 
107 /** scales the conflict score values with the given scalar for each value history entry */
109  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
110  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
111  );
112 
113 /**@} */
114 
115 /** returns the opposite direction of the given branching direction */
117  SCIP_BRANCHDIR dir /**< branching direction */
118  );
119 
120 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
122  SCIP_HISTORY* history, /**< branching and inference history */
123  SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */
124  );
125 
126 /** returns the variance of pseudo costs about the mean. */
128  SCIP_HISTORY* history, /**< branching and inference history */
129  SCIP_BRANCHDIR direction /**< direction of variable: 1 for upwards history, 0 for downwards history */
130  );
131 
132 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in
133  * the given branching direction
134  */
136  SCIP_HISTORY* history, /**< branching and inference history */
137  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
138  );
139 
140 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
142  SCIP_HISTORY* history, /**< branching and inference history */
143  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
144  );
145 
146 /** increases the conflict score of the history entry by the given weight */
148  SCIP_HISTORY* history, /**< branching and inference history */
149  SCIP_BRANCHDIR dir, /**< branching direction */
150  SCIP_Real weight /**< weight of this update in conflict score */
151  );
152 
153  /** scales the conflict score values with the given scalar */
155  SCIP_HISTORY* history, /**< branching and inference history */
156  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
157  );
158 
159 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
161  SCIP_HISTORY* history, /**< branching and inference history */
162  SCIP_BRANCHDIR dir, /**< branching direction */
163  SCIP_Real length /**< length of the conflict */
164  );
165 
166 /** gets the number of active conflicts of the history entry */
168  SCIP_HISTORY* history, /**< branching and inference history */
169  SCIP_BRANCHDIR dir /**< branching direction */
170  );
171 
172 /** increases the number of branchings counter */
174  SCIP_HISTORY* history, /**< branching and inference history */
175  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
176  int depth /**< depth at which the bound change took place */
177  );
178 
179 /** increases the number of inferences counter */
181  SCIP_HISTORY* history, /**< branching and inference history */
182  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
183  SCIP_Real weight /**< weight of this update in cutoff score */
184  );
185 
186 
187 /** increases the number of cutoffs counter */
189  SCIP_HISTORY* history, /**< branching and inference history */
190  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
191  SCIP_Real weight /**< weight of this update in cutoff score */
192  );
193 
194 /** get number of branchings counter */
196  SCIP_HISTORY* history, /**< branching and inference history */
197  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
198  );
199 
200 /** returns the average number of inferences per branching */
202  SCIP_HISTORY* history, /**< branching and inference history */
203  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
204  );
205 
206 /** returns the average number of cutoffs per branching */
208  SCIP_HISTORY* history, /**< branching and inference history */
209  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
210  );
211 
212 /** returns the average depth of bound changes due to branching */
214  SCIP_HISTORY* history, /**< branching and inference history */
215  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
216  );
217 
218 /** returns true if the given history contains a valid ratio */
220  SCIP_HISTORY* history /**< branching and inference history */
221 );
222 
223 /** returns the most recent ratio computed given the variable history */
225  SCIP_HISTORY* history /**< branching and inference history */
226 );
227 
228 /** returns the most recent value of r/l used to compute this variable's ratio */
230  SCIP_HISTORY* history /**< branching and inference history */
231 );
232 
233 /** sets the ratio history for a particular variable */
235  SCIP_HISTORY* history, /**< branching and inference history */
236  SCIP_Bool valid, /**< True iff the ratio computed is valid */
237  SCIP_Real ratio, /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */
238  SCIP_Real balance /**< The value of rightgain/leftgain */
239 );
240 
241 #ifdef NDEBUG
242 
243 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
244  * speed up the algorithms.
245  */
246 
247 #define SCIPbranchdirOpposite(dir) \
248  ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \
249  : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
250 #define SCIPhistoryGetPseudocost(history,solvaldelta) \
251  ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
252  ? (history)->pscostweightedmean[1] : 1.0) \
253  : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \
254  ? (history)->pscostweightedmean[0] : 1.0) )
255 #define SCIPhistoryGetPseudocostVariance(history, dir) \
256  ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1) \
257  * ((history)->pscostvariance[dir]) \
258  : 0.0)
259 #define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
260 #define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0)
261 #define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
262 #define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \
263  (history)->vsids[1] *= (scalar); }
264 #define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
265  (history)->conflengthsum[dir] += length; }
266 #define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
267 #define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
268  (history)->branchdepthsum[dir] += depth; }
269 #define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight)
270 #define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight)
271 #define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir])
272 #define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \
273  ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
274 #define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \
275  ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
276 #define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \
277  ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
278 #define SCIPhistoryIsRatioValid(history) ((history)->ratiovalid)
279 #define SCIPhistoryGetLastRatio(history) ((history)->ratio)
280 #define SCIPhistorySetRatioHistory(history,newvalid,newratio,newbalance) (history)->ratiovalid = newvalid, \
281  (history)->ratio = newratio, (history)->balance = newbalance
282 #define SCIPhistoryGetLastBalance(history) ((history)->balance)
283 
284 #endif
285 
286 #ifdef __cplusplus
287 }
288 #endif
289 
290 #endif
void SCIPhistoryFree(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:57
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:231
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:494
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:607
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:42
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:701
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition: history.c:317
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:591
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for global SCIP settings
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition: history.c:69
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition: history.c:430
type definitions for return codes for SCIP methods
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:711
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:675
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:688
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition: history.c:272
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:508
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:250
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:533
SCIP_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition: history.c:444
void SCIPhistoryUnite(SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
Definition: history.c:101
SCIP_Real SCIPhistoryGetPseudocostCount(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:468
SCIP_Bool SCIPhistoryIsPseudocostEmpty(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:481
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:549
#define SCIP_Bool
Definition: def.h:84
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: history.c:162
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:623
datastructures for branching and inference history
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition: history.c:421
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:733
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:649
#define SCIP_Real
Definition: def.h:177
type definitions for branching and inference history
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:722
#define SCIP_Longint
Definition: def.h:162
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition: history.c:575
memory allocation routines