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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file history.h
26  * @ingroup INTERNALAPI
27  * @brief internal methods for branching and inference history
28  * @author Tobias Achterberg
29  * @author Timo Berthold
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #ifndef __SCIP_HISTORY_H__
35 #define __SCIP_HISTORY_H__
36 
37 
38 #include "scip/def.h"
39 #include "blockmemshell/memory.h"
40 #include "scip/type_retcode.h"
41 #include "scip/type_set.h"
42 #include "scip/type_history.h"
43 
44 #ifdef NDEBUG
45 #include "scip/struct_history.h"
46 #endif
47 
48 #ifdef __cplusplus
49 extern "C" {
50 #endif
51 
52 /** creates an empty history entry */
54  SCIP_HISTORY** history, /**< pointer to store branching and inference history */
55  BMS_BLKMEM* blkmem /**< block memory */
56  );
57 
58 /** frees a history entry */
59 void SCIPhistoryFree(
60  SCIP_HISTORY** history, /**< pointer to branching and inference history */
61  BMS_BLKMEM* blkmem /**< block memory */
62  );
63 
64 /** resets history entry to zero */
65 void SCIPhistoryReset(
66  SCIP_HISTORY* history /**< branching and inference history */
67  );
68 
69 /** unites two history entries by adding the values of the second one to the first one */
70 void SCIPhistoryUnite(
71  SCIP_HISTORY* history, /**< branching and inference history */
72  SCIP_HISTORY* addhistory, /**< history values to add to history */
73  SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */
74  );
75 
76 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
77  * in the LP's objective value
78  */
80  SCIP_HISTORY* history, /**< branching and inference history */
81  SCIP_SET* set, /**< global SCIP settings */
82  SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */
83  SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */
84  SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */
85  );
86 
87 
88 /**@defgroup ValueHistory Value Based History
89  * @ingroup INTERNALAPI
90  * @brief Value based history methods
91  *
92  * @{
93  */
94 
95 /** creates an empty value history */
97  SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */
98  BMS_BLKMEM* blkmem /**< block memory */
99  );
100 
101 /** frees a value history */
103  SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */
104  BMS_BLKMEM* blkmem /**< block memory */
105  );
106 
107 /** finds for the given domain value the history if it does not exist yet it will be created */
109  SCIP_VALUEHISTORY* valuehistory, /**< value based history */
110  BMS_BLKMEM* blkmem, /**< block memory */
111  SCIP_SET* set, /**< global SCIP settings */
112  SCIP_Real value, /**< domain value of interest */
113  SCIP_HISTORY** history /**< pointer to store the history for the given domain value */
114  );
115 
116 /** scales the conflict score values with the given scalar for each value history entry */
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 */
126  SCIP_BRANCHDIR dir /**< branching direction */
127  );
128 
129 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
131  SCIP_HISTORY* history, /**< branching and inference history */
132  SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */
133  );
134 
135 /** returns the variance of pseudo costs about the mean. */
137  SCIP_HISTORY* history, /**< branching and inference history */
138  SCIP_BRANCHDIR direction /**< direction of variable: 1 for upwards history, 0 for downwards history */
139  );
140 
141 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in
142  * the given branching direction
143  */
145  SCIP_HISTORY* history, /**< branching and inference history */
146  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
147  );
148 
149 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
151  SCIP_HISTORY* history, /**< branching and inference history */
152  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
153  );
154 
155 /** increases the conflict score of the history entry by the given weight */
157  SCIP_HISTORY* history, /**< branching and inference history */
158  SCIP_BRANCHDIR dir, /**< branching direction */
159  SCIP_Real weight /**< weight of this update in conflict score */
160  );
161 
162  /** scales the conflict score values with the given scalar */
164  SCIP_HISTORY* history, /**< branching and inference history */
165  SCIP_Real scalar /**< scalar to multiply the conflict scores with */
166  );
167 
168 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
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 */
177  SCIP_HISTORY* history, /**< branching and inference history */
178  SCIP_BRANCHDIR dir /**< branching direction */
179  );
180 
181 /** increases the number of branchings counter */
183  SCIP_HISTORY* history, /**< branching and inference history */
184  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
185  int depth /**< depth at which the bound change took place */
186  );
187 
188 /** increases the number of inferences counter */
190  SCIP_HISTORY* history, /**< branching and inference history */
191  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
192  SCIP_Real weight /**< weight of this update in cutoff score */
193  );
194 
195 
196 /** increases the number of cutoffs counter */
198  SCIP_HISTORY* history, /**< branching and inference history */
199  SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */
200  SCIP_Real weight /**< weight of this update in cutoff score */
201  );
202 
203 /** get number of branchings counter */
205  SCIP_HISTORY* history, /**< branching and inference history */
206  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
207  );
208 
209 /** returns the average number of inferences per branching */
211  SCIP_HISTORY* history, /**< branching and inference history */
212  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
213  );
214 
215 /** returns the average number of cutoffs per branching */
217  SCIP_HISTORY* history, /**< branching and inference history */
218  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
219  );
220 
221 /** returns the average depth of bound changes due to branching */
223  SCIP_HISTORY* history, /**< branching and inference history */
224  SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */
225  );
226 
227 /** returns true if the given history contains a valid ratio */
229  SCIP_HISTORY* history /**< branching and inference history */
230 );
231 
232 /** returns the most recent ratio computed given the variable history */
234  SCIP_HISTORY* history /**< branching and inference history */
235 );
236 
237 /** returns the most recent value of r/l used to compute this variable's ratio */
239  SCIP_HISTORY* history /**< branching and inference history */
240 );
241 
242 /** sets the ratio history for a particular variable */
244  SCIP_HISTORY* history, /**< branching and inference history */
245  SCIP_Bool valid, /**< True iff the ratio computed is valid */
246  SCIP_Real ratio, /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */
247  SCIP_Real balance /**< The value of rightgain/leftgain */
248 );
249 
250 #ifdef NDEBUG
251 
252 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
253  * speed up the algorithms.
254  */
255 
256 #define SCIPbranchdirOpposite(dir) \
257  ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \
258  : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
259 #define SCIPhistoryGetPseudocost(history,solvaldelta) \
260  ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
261  ? (history)->pscostweightedmean[1] : 1.0) \
262  : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \
263  ? (history)->pscostweightedmean[0] : 1.0) )
264 #define SCIPhistoryGetPseudocostVariance(history, dir) \
265  ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1) \
266  * ((history)->pscostvariance[dir]) \
267  : 0.0)
268 #define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
269 #define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0)
270 #define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
271 #define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \
272  (history)->vsids[1] *= (scalar); }
273 #define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
274  (history)->conflengthsum[dir] += length; }
275 #define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
276 #define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
277  (history)->branchdepthsum[dir] += depth; }
278 #define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight)
279 #define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight)
280 #define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir])
281 #define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \
282  ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
283 #define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \
284  ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
285 #define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \
286  ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
287 #define SCIPhistoryIsRatioValid(history) ((history)->ratiovalid)
288 #define SCIPhistoryGetLastRatio(history) ((history)->ratio)
289 #define SCIPhistorySetRatioHistory(history,newvalid,newratio,newbalance) (history)->ratiovalid = newvalid, \
290  (history)->ratio = newratio, (history)->balance = newbalance
291 #define SCIPhistoryGetLastBalance(history) ((history)->balance)
292 
293 #endif
294 
295 #ifdef __cplusplus
296 }
297 #endif
298 
299 #endif
void SCIPhistoryFree(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:66
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:240
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:503
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:616
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:51
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:710
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition: history.c:326
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:600
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for global SCIP settings
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition: history.c:78
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition: history.c:439
type definitions for return codes for SCIP methods
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:720
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:684
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:697
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition: history.c:281
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:517
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:259
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:542
SCIP_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition: history.c:453
void SCIPhistoryUnite(SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
Definition: history.c:110
SCIP_Real SCIPhistoryGetPseudocostCount(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:477
SCIP_Bool SCIPhistoryIsPseudocostEmpty(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:490
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:558
#define SCIP_Bool
Definition: def.h:93
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: history.c:171
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:632
datastructures for branching and inference history
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition: history.c:430
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:742
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:658
#define SCIP_Real
Definition: def.h:186
type definitions for branching and inference history
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:731
#define SCIP_Longint
Definition: def.h:171
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition: history.c:584
memory allocation routines