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 */
53   	SCIP_RETCODE SCIPhistoryCreate(
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   	 */
79   	void SCIPhistoryUpdatePseudocost(
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 */
96   	SCIP_RETCODE SCIPvaluehistoryCreate(
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 */
102  	void SCIPvaluehistoryFree(
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 */
108  	SCIP_RETCODE SCIPvaluehistoryFind(
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 */
117  	void SCIPvaluehistoryScaleVSIDS(
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  	SCIP_BRANCHDIR SCIPbranchdirOpposite(
126  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
127  	   );
128  	
129  	/** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
130  	SCIP_Real SCIPhistoryGetPseudocost(
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. */
136  	SCIP_Real SCIPhistoryGetPseudocostVariance(
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  	 */
144  	SCIP_Real SCIPhistoryGetPseudocostCount(
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) */
150  	SCIP_Bool SCIPhistoryIsPseudocostEmpty(
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 */
156  	void SCIPhistoryIncVSIDS(
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 */
163  	void SCIPhistoryScaleVSIDS(
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 */
169  	void SCIPhistoryIncNActiveConflicts(
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 */
176  	SCIP_Longint SCIPhistoryGetNActiveConflicts(
177  	   SCIP_HISTORY*         history,            /**< branching and inference history */
178  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
179  	   );
180  	
181  	/** increases the number of branchings counter */
182  	void SCIPhistoryIncNBranchings(
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 */
189  	void SCIPhistoryIncInferenceSum(
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 */
197  	void SCIPhistoryIncCutoffSum(
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 */
204  	SCIP_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 */
210  	SCIP_Real SCIPhistoryGetAvgInferences(
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 */
216  	SCIP_Real SCIPhistoryGetAvgCutoffs(
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 */
222  	SCIP_Real SCIPhistoryGetAvgBranchdepth(
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 */
228  	SCIP_Bool SCIPhistoryIsRatioValid(
229  	   SCIP_HISTORY*         history             /**< branching and inference history */
230  	   );
231  	
232  	/** returns the most recent ratio computed given the variable history */
233  	SCIP_Real SCIPhistoryGetLastRatio(
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 */
238  	SCIP_Real SCIPhistoryGetLastBalance(
239  	   SCIP_HISTORY*         history             /**< branching and inference history */
240  	   );
241  	
242  	/** returns the average efficacy value for the GMI cut produced by this variable */
243  	SCIP_Real SCIPhistoryGetAvgGMIeff(
244  	   SCIP_HISTORY*         history             /**< branching and inference history */
245  	   );
246  	
247  	/** increases the average efficacy value for the GMI cut produced by this variable */
248  	void SCIPhistoryIncGMIeffSum(
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 */
254  	SCIP_Real SCIPhistoryGetLastGMIeff(
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 */
259  	void SCIPhistorySetLastGMIeff(
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 */
265  	void SCIPhistorySetRatioHistory(
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
328