SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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"
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 */
204SCIP_Longint SCIPhistoryGetNBranchings(
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
common defines and data types used in all packages of SCIP
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition history.c:240
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition history.c:281
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition history.c:259
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition history.c:326
int depth
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition history.c:78
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition history.c:439
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition history.c:658
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition history.c:742
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition history.c:558
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition history.c:632
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition history.c:684
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition history.c:51
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition history.c:720
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition history.c:600
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_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition history.c:453
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition history.c:542
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition history.c:517
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition history.c:616
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition history.c:584
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition history.c:171
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition history.c:710
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition history.c:697
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition history.c:731
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:110
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition history.c:430
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition history.c:503
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:439
datastructures for branching and inference history
type definitions for branching and inference history
enum SCIP_BranchDir SCIP_BRANCHDIR
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
type definitions for global SCIP settings