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-2024 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"
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
49extern "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 */
60 SCIP_HISTORY** history, /**< pointer to branching and inference history */
61 BMS_BLKMEM* blkmem /**< block memory */
62 );
63
64/** resets history entry to zero */
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 */
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/** returns the average efficacy value for the GMI cut produced by this variable */
244 SCIP_HISTORY* history /**< branching and inference history */
245 );
246
247/** increases the average efficacy value for the GMI cut produced by this variable */
249 SCIP_HISTORY* history, /**< branching and inference history */
250 SCIP_Real gmieff /**< normalized efficacy value of a cut which will increase gmieff */
251 );
252
253/** returns the most recent efficacy value for the GMI cut produced by this variable */
255 SCIP_HISTORY* history /**< branching and inference history */
256 );
257
258/** sets the new most recent efficacy value for the GMI cut produced by this variable */
260 SCIP_HISTORY* history, /**< branching and inference history */
261 SCIP_Real gmieff /**< Efficacy of GMI cut produced from simplex tableau row of this var */
262 );
263
264/** sets the ratio history for a particular variable */
266 SCIP_HISTORY* history, /**< branching and inference history */
267 SCIP_Bool valid, /**< True iff the ratio computed is valid */
268 SCIP_Real ratio, /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */
269 SCIP_Real balance /**< The value of rightgain/leftgain */
270 );
271
272#ifdef NDEBUG
273
274/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
275 * speed up the algorithms.
276 */
277
278#define SCIPbranchdirOpposite(dir) \
279 ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \
280 : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
281#define SCIPhistoryGetPseudocost(history,solvaldelta) \
282 ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
283 ? (history)->pscostweightedmean[1] : 1.0) \
284 : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \
285 ? (history)->pscostweightedmean[0] : 1.0) )
286#define SCIPhistoryGetPseudocostVariance(history, dir) \
287 ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1) \
288 * ((history)->pscostvariance[dir]) \
289 : 0.0)
290#define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
291#define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0)
292#define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
293#define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \
294 (history)->vsids[1] *= (scalar); }
295#define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
296 (history)->conflengthsum[dir] += length; }
297#define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
298#define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
299 (history)->branchdepthsum[dir] += depth; }
300#define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight)
301#define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight)
302#define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir])
303#define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \
304 ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
305#define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \
306 ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
307#define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \
308 ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
309#define SCIPhistoryIsRatioValid(history) ((history)->ratiovalid)
310#define SCIPhistoryGetLastRatio(history) ((history)->ratio)
311#define SCIPhistorySetRatioHistory(history,newvalid,newratio,newbalance) (history)->ratiovalid = newvalid, \
312 (history)->ratio = newratio, (history)->balance = newbalance
313#define SCIPhistoryGetLastBalance(history) ((history)->balance)
314#define SCIPhistoryGetLastGMIeff(history) ((history)->gmieff)
315#define SCIPhistorySetLastGMIeff(history,newgmieff) (history)->gmieff = newgmieff
316#define SCIPhistoryGetAvgGMIeff(history) ((history)->ngmi > 0 \
317 ? (SCIP_Real)(history)->gmieffsum/(SCIP_Real)(history)->ngmi : 0.0)
318#define SCIPhistoryIncGMIeffSum(history, newgmieff) { (history)->gmieffsum += newgmieff; \
319 (history)->ngmi += 1; }
320
321#endif
322
323#ifdef __cplusplus
324}
325#endif
326
327#endif
common defines and data types used in all packages of SCIP
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:243
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition: history.c:284
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:262
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition: history.c:329
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition: history.c:78
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition: history.c:446
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:665
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:793
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:565
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:639
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:691
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:51
void SCIPhistorySetLastGMIeff(SCIP_HISTORY *history, SCIP_Real gmieff)
Definition: history.c:782
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:727
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:607
SCIP_Real SCIPhistoryGetPseudocostCount(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:484
SCIP_Bool SCIPhistoryIsPseudocostEmpty(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:497
SCIP_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition: history.c:460
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:549
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:524
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:623
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition: history.c:591
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: history.c:174
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:717
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:704
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:738
SCIP_Real SCIPhistoryGetLastGMIeff(SCIP_HISTORY *history)
Definition: history.c:772
SCIP_Real SCIPhistoryGetAvgGMIeff(SCIP_HISTORY *history)
Definition: history.c:749
void SCIPhistoryFree(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:66
void SCIPhistoryUnite(SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
Definition: history.c:113
void SCIPhistoryIncGMIeffSum(SCIP_HISTORY *history, SCIP_Real gmieff)
Definition: history.c:759
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition: history.c:437
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:510
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
datastructures for branching and inference history
Definition: heur_padm.c:135
type definitions for branching and inference history
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for global SCIP settings