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.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for branching and inference history
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include <assert.h>
34   	
35   	#include "scip/def.h"
36   	#include "scip/set.h"
37   	#include "scip/history.h"
38   	#include "scip/pub_misc.h"
39   	#include "scip/pub_history.h"
40   	#include "scip/pub_message.h"
41   	
42   	#ifndef NDEBUG
43   	#include "scip/struct_history.h"
44   	#endif
45   	
46   	/*
47   	 * methods for branching and inference history
48   	 */
49   	
50   	/** creates an empty history entry */
51   	SCIP_RETCODE SCIPhistoryCreate(
52   	   SCIP_HISTORY**        history,            /**< pointer to store branching and inference history */
53   	   BMS_BLKMEM*           blkmem              /**< block memory */
54   	   )
55   	{
56   	   assert(history != NULL);
57   	
58   	   SCIP_ALLOC( BMSallocBlockMemory(blkmem, history) );
59   	
60   	   SCIPhistoryReset(*history);
61   	
62   	   return SCIP_OKAY;
63   	}
64   	
65   	/** frees a history entry */
66   	void SCIPhistoryFree(
67   	   SCIP_HISTORY**        history,            /**< pointer to branching and inference history */
68   	   BMS_BLKMEM*           blkmem              /**< block memory */
69   	   )
70   	{
71   	   assert(history != NULL);
72   	   assert(*history != NULL);
73   	
74   	   BMSfreeBlockMemory(blkmem, history);
75   	}
76   	
77   	/** resets history entry to zero */
78   	void SCIPhistoryReset(
79   	   SCIP_HISTORY*         history             /**< branching and inference history */
80   	   )
81   	{
82   	   assert(history != NULL);
83   	
84   	   history->pscostcount[0] = 0.0;
85   	   history->pscostcount[1] = 0.0;
86   	   history->pscostweightedmean[0] = 0.0;
87   	   history->pscostweightedmean[1] = 0.0;
88   	   history->pscostvariance[0] = 0.0;
89   	   history->pscostvariance[1] = 0.0;
90   	   history->vsids[0] = 0.0;
91   	   history->vsids[1] = 0.0;
92   	   history->conflengthsum[0] = 0.0;
93   	   history->conflengthsum[1] = 0.0;
94   	   history->inferencesum[0] = 0.0;
95   	   history->inferencesum[1] = 0.0;
96   	   history->cutoffsum[0] = 0.0;
97   	   history->cutoffsum[1] = 0.0;
98   	   history->ratio = 0.0;
99   	   history->ratiovalid = FALSE;
100  	   history->balance = 0.0;
101  	   history->ngmi = 0;
102  	   history->gmieff = 0.0;
103  	   history->gmieffsum = 0.0;
104  	   history->nactiveconflicts[0] = 0;
105  	   history->nactiveconflicts[1] = 0;
106  	   history->nbranchings[0] = 0;
107  	   history->nbranchings[1] = 0;
108  	   history->branchdepthsum[0] = 0;
109  	   history->branchdepthsum[1] = 0;
110  	}
111  	
112  	/** unites two history entries by adding the values of the second one to the first one */
113  	void SCIPhistoryUnite(
114  	   SCIP_HISTORY*         history,            /**< branching and inference history */
115  	   SCIP_HISTORY*         addhistory,         /**< history values to add to history */
116  	   SCIP_Bool             switcheddirs        /**< should the history entries be united with switched directories */
117  	   )
118  	{
119  	   int i;
120  	
121  	   assert(history != NULL);
122  	   assert(addhistory != NULL);
123  	
124  	   /* loop over both directions and combine the statistics */
125  	   for( i = 0; i <= 1; ++i )
126  	   {
127  	      int d;
128  	      d = (switcheddirs ? 1 - i : i);
129  	
130  	      history->pscostcount[i] += addhistory->pscostcount[d];
131  	
132  	      /* if both histories a count of zero, there is nothing to do */
133  	      if( history->pscostcount[i] > 0.0 )
134  	      {
135  	         SCIP_Real oldmean;
136  	
137  	         oldmean = history->pscostweightedmean[i];
138  	
139  	         /* we update the mean as if the history was one observation with a large weight */
140  	         history->pscostweightedmean[i] += addhistory->pscostcount[d] * (addhistory->pscostweightedmean[d] - history->pscostweightedmean[i]) / history->pscostcount[i];
141  	
142  	         /* we update the variance of two sets A and B as S_A+B = S_A + (mu_A)^2 * count_A ...*/
143  	         /* @todo is there a numerically more stable variant for this merge? */
144  	         history->pscostvariance[i] = history->pscostvariance[i] + oldmean * oldmean * (history->pscostcount[i] - addhistory->pscostcount[d]) + \
145  	               /* S_B + (mu_B)^2 * count_B */
146  	               addhistory->pscostvariance[d] + addhistory->pscostcount[d] * addhistory->pscostweightedmean[d] * addhistory->pscostweightedmean[d] -  \
147  	               /* - count_A+B * mu_A+B^ 2 */
148  	               history->pscostcount[i] * history->pscostweightedmean[i] * history->pscostweightedmean[i];
149  	
150  	         /* slight violations of nonnegativity are numerically possible */
151  	         history->pscostvariance[i] = MAX(history->pscostvariance[i], 0.0);
152  	      }
153  	#ifndef NDEBUG
154  	      else
155  	      {
156  	         assert(history->pscostweightedmean[i] == 0.0);
157  	         assert(history->pscostvariance[i] == 0.0);
158  	      }
159  	#endif
160  	
161  	      history->vsids[i] += addhistory->vsids[d];
162  	      history->conflengthsum[i] += addhistory->conflengthsum[d];
163  	      history->inferencesum[i] += addhistory->inferencesum[d];
164  	      history->cutoffsum[i] += addhistory->cutoffsum[d];
165  	      history->nactiveconflicts[i] += addhistory->nactiveconflicts[d];
166  	      history->nbranchings[i] += addhistory->nbranchings[d];
167  	      history->branchdepthsum[i] += addhistory->branchdepthsum[d];
168  	   }
169  	}
170  	
171  	/** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
172  	 *  in the LP's objective value
173  	 */
174  	void SCIPhistoryUpdatePseudocost(
175  	   SCIP_HISTORY*         history,            /**< branching and inference history */
176  	   SCIP_SET*             set,                /**< global SCIP settings */
177  	   SCIP_Real             solvaldelta,        /**< difference of variable's new LP value - old LP value */
178  	   SCIP_Real             objdelta,           /**< difference of new LP's objective value - old LP's objective value */
179  	   SCIP_Real             weight              /**< weight of this update in pseudo cost sum (added to pscostcount) */
180  	   )
181  	{
182  	   SCIP_Real distance;
183  	   SCIP_Real eps;
184  	   SCIP_Real sumcontribution;
185  	   SCIP_Real olddelta;
186  	   int dir;
187  	
188  	   assert(history != NULL);
189  	   assert(set != NULL);
190  	   assert(!SCIPsetIsInfinity(set, REALABS(solvaldelta)));
191  	   assert(!SCIPsetIsInfinity(set, objdelta));
192  	   assert(!SCIPsetIsNegative(set, objdelta));
193  	   assert(0.0 < weight && weight <= 1.0);
194  	
195  	   if( SCIPsetIsPositive(set, solvaldelta) )
196  	   {
197  	      /* variable's solution value moved upwards */
198  	      dir = 1;
199  	      distance = solvaldelta;
200  	   }
201  	   else if( SCIPsetIsNegative(set, solvaldelta) )
202  	   {
203  	      /* variable's solution value moved downwards */
204  	      dir = 0;
205  	      distance = -solvaldelta;
206  	   }
207  	   else
208  	   {
209  	      /* the variable's solution value didn't change, and the pseudo costs cannot be updated */
210  	      return;
211  	   }
212  	   assert(dir == 0 || dir == 1);
213  	   assert(SCIPsetIsPositive(set, distance));
214  	
215  	   /* apply a lower limit on the distance to avoid numerical instabilities due to very large summands */
216  	   eps = SCIPsetPseudocosteps(set);
217  	   distance = MAX(distance, eps);
218  	
219  	   /* slightly increase objective delta, s.t. pseudo cost values are not zero, and fractionalities are
220  	    * always used at least a bit
221  	    */
222  	   objdelta += SCIPsetPseudocostdelta(set);
223  	
224  	   sumcontribution = objdelta/distance;
225  	   /* update the pseudo cost values */
226  	   olddelta = sumcontribution - history->pscostweightedmean[dir];
227  	   history->pscostcount[dir] += weight;
228  	   history->pscostweightedmean[dir] += weight * olddelta / history->pscostcount[dir];
229  	   history->pscostvariance[dir] = history->pscostvariance[dir] + weight * olddelta * (sumcontribution - history->pscostweightedmean[dir]);
230  	
231  	   SCIPsetDebugMsg(set, "updated pseudo costs of history %p: dir=%d, distance=%g, objdelta=%g, weight=%g  ->  %g/%g\n",
232  	      (void*)history, dir, distance, objdelta, weight, history->pscostcount[dir], history->pscostweightedmean[dir]);
233  	}
234  	
235  	/**@name Value based history
236  	 *
237  	 * Value based history methods
238  	 *
239  	 * @{
240  	 */
241  	
242  	/** creates an empty value history */
243  	SCIP_RETCODE SCIPvaluehistoryCreate(
244  	   SCIP_VALUEHISTORY**   valuehistory,       /**< pointer to store the value based branching and inference histories */
245  	   BMS_BLKMEM*           blkmem              /**< block memory */
246  	   )
247  	{
248  	   assert(valuehistory != NULL);
249  	
250  	   SCIP_ALLOC( BMSallocBlockMemory(blkmem, valuehistory) );
251  	
252  	   (*valuehistory)->nvalues = 0;
253  	   (*valuehistory)->sizevalues = 5;
254  	
255  	   SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*valuehistory)->histories, (*valuehistory)->sizevalues) );
256  	   SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*valuehistory)->values, (*valuehistory)->sizevalues) );
257  	
258  	   return SCIP_OKAY;
259  	}
260  	
261  	/** frees a value history */
262  	void SCIPvaluehistoryFree(
263  	   SCIP_VALUEHISTORY**   valuehistory,       /**< pointer to value based history */
264  	   BMS_BLKMEM*           blkmem              /**< block memory */
265  	   )
266  	{
267  	   assert(valuehistory != NULL);
268  	
269  	   if( *valuehistory != NULL )
270  	   {
271  	      int i;
272  	
273  	      for( i = (*valuehistory)->nvalues-1; i >= 0; --i )
274  	         SCIPhistoryFree(&(*valuehistory)->histories[i], blkmem);
275  	
276  	      BMSfreeBlockMemoryArray(blkmem, &(*valuehistory)->histories, (*valuehistory)->sizevalues);
277  	      BMSfreeBlockMemoryArray(blkmem, &(*valuehistory)->values, (*valuehistory)->sizevalues);
278  	
279  	      BMSfreeBlockMemory(blkmem, valuehistory);
280  	   }
281  	}
282  	
283  	/** finds for the given domain value the history if it does not exist yet it will be created */
284  	SCIP_RETCODE SCIPvaluehistoryFind(
285  	   SCIP_VALUEHISTORY*    valuehistory,       /**< value based history */
286  	   BMS_BLKMEM*           blkmem,             /**< block memory */
287  	   SCIP_SET*             set,                /**< global SCIP settings */
288  	   SCIP_Real             value,              /**< domain value of interest */
289  	   SCIP_HISTORY**        history             /**< pointer to store the history for the given domain value */
290  	   )
291  	{
292  	   int pos;
293  	
294  	   assert(valuehistory != NULL);
295  	   assert(blkmem != NULL);
296  	   assert(set != NULL);
297  	   assert(history != NULL);
298  	
299  	   *history = NULL;
300  	
301  	   if( valuehistory->nvalues == 0 || !SCIPsortedvecFindReal(valuehistory->values, value, valuehistory->nvalues, &pos) )
302  	   {
303  	      /* check if we need to resize the history array */
304  	      if( valuehistory->nvalues == valuehistory->sizevalues )
305  	      {
306  	         int newsize;
307  	
308  	         newsize = SCIPsetCalcMemGrowSize(set, valuehistory->sizevalues + 1);
309  	         SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &valuehistory->histories, valuehistory->nvalues, newsize) );
310  	         SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &valuehistory->values, valuehistory->nvalues, newsize) );
311  	         valuehistory->sizevalues = newsize;
312  	      }
313  	
314  	      /* create new empty history entry */
315  	      SCIP_CALL( SCIPhistoryCreate(history, blkmem) );
316  	
317  	      /* insert new history into the value based history array */
318  	      SCIPsortedvecInsertRealPtr(valuehistory->values, (void**)valuehistory->histories, value, (void*)(*history), &valuehistory->nvalues, NULL);
319  	   }
320  	   else
321  	      (*history) = valuehistory->histories[pos]; /*lint !e530*/
322  	
323  	   assert(*history != NULL);
324  	
325  	   return SCIP_OKAY;
326  	}
327  	
328  	/** scales the conflict score values with the given scalar for each value history entry */
329  	void SCIPvaluehistoryScaleVSIDS(
330  	   SCIP_VALUEHISTORY*    valuehistory,       /**< value based history */
331  	   SCIP_Real             scalar              /**< scalar to multiply the conflict scores with */
332  	   )
333  	{
334  	   if( valuehistory != NULL )
335  	   {
336  	      int i;
337  	
338  	      for( i = valuehistory->nvalues-1; i >= 0; --i )
339  	      {
340  	         SCIPhistoryScaleVSIDS(valuehistory->histories[i], scalar);
341  	      }
342  	   }
343  	}
344  	
345  	
346  	/*
347  	 * simple functions implemented as defines
348  	 */
349  	
350  	#ifndef NDEBUG
351  	
352  	/* In debug mode, the following methods are implemented as function calls to ensure
353  	 * type validity.
354  	 * In optimized mode, the methods are implemented as defines to improve performance.
355  	 * However, we want to have them in the library anyways, so we have to undef the defines.
356  	 */
357  	
358  	#undef SCIPvaluehistoryGetNValues
359  	#undef SCIPvaluehistoryGetHistories
360  	#undef SCIPvaluehistoryGetValues
361  	
362  	/** return the number of (domain) values for which a history exists */
363  	int SCIPvaluehistoryGetNValues(
364  	   SCIP_VALUEHISTORY*    valuehistory        /**< value based history */
365  	   )
366  	{
367  	   assert(valuehistory != NULL);
368  	
369  	   return valuehistory->nvalues;
370  	}
371  	
372  	/** return the array containing the histories for the individual (domain) values */
373  	SCIP_HISTORY** SCIPvaluehistoryGetHistories(
374  	   SCIP_VALUEHISTORY*    valuehistory        /**< value based history */
375  	   )
376  	{
377  	   assert(valuehistory != NULL);
378  	
379  	   return valuehistory->histories;
380  	}
381  	
382  	/** return the array containing the (domain) values for which a history exists */
383  	SCIP_Real* SCIPvaluehistoryGetValues(
384  	   SCIP_VALUEHISTORY*    valuehistory        /**< value based history */
385  	   )
386  	{
387  	   assert(valuehistory != NULL);
388  	
389  	   return valuehistory->values;
390  	}
391  	
392  	#endif
393  	
394  	/**@} */
395  	
396  	/*
397  	 * simple functions implemented as defines
398  	 */
399  	
400  	#ifndef NDEBUG
401  	
402  	/* In debug mode, the following methods are implemented as function calls to ensure
403  	 * type validity.
404  	 * In optimized mode, the methods are implemented as defines to improve performance.
405  	 * However, we want to have them in the library anyways, so we have to undef the defines.
406  	 */
407  	
408  	#undef SCIPbranchdirOpposite
409  	#undef SCIPhistoryGetPseudocost
410  	#undef SCIPhistoryGetPseudocostCount
411  	#undef SCIPhistoryIsPseudocostEmpty
412  	#undef SCIPhistoryIncVSIDS
413  	#undef SCIPhistoryScaleVSIDS
414  	#undef SCIPhistoryGetVSIDS
415  	#undef SCIPhistoryIncNActiveConflicts
416  	#undef SCIPhistoryGetNActiveConflicts
417  	#undef SCIPhistoryGetAvgConflictlength
418  	#undef SCIPhistoryIncNBranchings
419  	#undef SCIPhistoryIncInferenceSum
420  	#undef SCIPhistoryIncCutoffSum
421  	#undef SCIPhistoryGetNBranchings
422  	#undef SCIPhistoryGetInferenceSum
423  	#undef SCIPhistoryGetAvgInferences
424  	#undef SCIPhistoryGetCutoffSum
425  	#undef SCIPhistoryGetAvgCutoffs
426  	#undef SCIPhistoryGetAvgBranchdepth
427  	#undef SCIPhistoryIsRatioValid
428  	#undef SCIPhistoryGetLastRatio
429  	#undef SCIPhistorySetRatioHistory
430  	#undef SCIPhistoryGetLastBalance
431  	#undef SCIPhistorySetLastGMIeff
432  	#undef SCIPhistoryGetLastGMIeff
433  	#undef SCIPhistoryIncGMIeffSum
434  	#undef SCIPhistoryGetAvgGMIeff
435  	
436  	/** returns the opposite direction of the given branching direction */
437  	SCIP_BRANCHDIR SCIPbranchdirOpposite(
438  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
439  	   )
440  	{
441  	   return (dir == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS
442  	      : (dir == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO));
443  	}
444  	
445  	/** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
446  	SCIP_Real SCIPhistoryGetPseudocost(
447  	   SCIP_HISTORY*         history,            /**< branching and inference history */
448  	   SCIP_Real             solvaldelta         /**< difference of variable's new LP value - old LP value */
449  	   )
450  	{
451  	   assert(history != NULL);
452  	
453  	   if( solvaldelta >= 0.0 )
454  	      return solvaldelta * (history->pscostcount[1] > 0.0 ? history->pscostweightedmean[1] : 1.0);
455  	   else
456  	      return -solvaldelta * (history->pscostcount[0] > 0.0 ? history->pscostweightedmean[0] : 1.0);
457  	}
458  	
459  	/** returns the variance of pseudo costs about the mean. */
460  	SCIP_Real SCIPhistoryGetPseudocostVariance(
461  	   SCIP_HISTORY*         history,            /**< branching and inference history */
462  	   SCIP_BRANCHDIR        direction           /**< direction of variable: 1 for upwards history, 0 for downwards history */
463  	   )
464  	{
465  	   int dir;
466  	   SCIP_Real correctionfactor;
467  	
468  	   assert(history != NULL);
469  	   assert(direction == SCIP_BRANCHDIR_UPWARDS || direction == SCIP_BRANCHDIR_DOWNWARDS);
470  	
471  	   dir = (direction == SCIP_BRANCHDIR_UPWARDS ? 1 : 0);
472  	   correctionfactor = history->pscostcount[dir] - 1.0;
473  	
474  	   /** @todo for an unbiased estimate of the weighted sample variance, we need a correction factor that uses the sum of squared weights */
475  	   if( correctionfactor > 0.9 )
476  	      return history->pscostvariance[dir] / correctionfactor;
477  	   else
478  	      return 0.0;
479  	}
480  	
481  	/** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in 
482  	 *  the given branching direction
483  	 */
484  	SCIP_Real SCIPhistoryGetPseudocostCount(
485  	   SCIP_HISTORY*         history,            /**< branching and inference history */
486  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
487  	   )
488  	{
489  	   assert(history != NULL);
490  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
491  	   assert((int)dir == 0 || (int)dir == 1);
492  	
493  	   return history->pscostcount[dir];
494  	}
495  	
496  	/** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
497  	SCIP_Bool SCIPhistoryIsPseudocostEmpty(
498  	   SCIP_HISTORY*         history,            /**< branching and inference history */
499  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
500  	   )
501  	{
502  	   assert(history != NULL);
503  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
504  	   assert((int)dir == 0 || (int)dir == 1);
505  	
506  	   return (history->pscostcount[dir] == 0.0);
507  	}
508  	
509  	/** increases the conflict score of the history entry by the given weight */
510  	void SCIPhistoryIncVSIDS(
511  	   SCIP_HISTORY*         history,            /**< branching and inference history */
512  	   SCIP_BRANCHDIR        dir,                /**< branching direction */
513  	   SCIP_Real             weight              /**< weight of this update in conflict score */
514  	   )
515  	{
516  	   assert(history != NULL);
517  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
518  	   assert((int)dir == 0 || (int)dir == 1);
519  	
520  	   history->vsids[dir] += weight;
521  	}
522  	
523  	/** scales the conflict score values with the given scalar */
524  	void SCIPhistoryScaleVSIDS(
525  	   SCIP_HISTORY*         history,            /**< branching and inference history */
526  	   SCIP_Real             scalar              /**< scalar to multiply the conflict scores with */
527  	   )
528  	{
529  	   assert(history != NULL);
530  	
531  	   history->vsids[0] *= scalar;
532  	   history->vsids[1] *= scalar;
533  	}
534  	
535  	/** gets the conflict score of the history entry */
536  	SCIP_Real SCIPhistoryGetVSIDS(
537  	   SCIP_HISTORY*         history,            /**< branching and inference history */
538  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
539  	   )
540  	{
541  	   assert(history != NULL);
542  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
543  	   assert((int)dir == 0 || (int)dir == 1);
544  	
545  	   return history->vsids[dir];
546  	}
547  	
548  	/** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
549  	void SCIPhistoryIncNActiveConflicts(
550  	   SCIP_HISTORY*         history,            /**< branching and inference history */
551  	   SCIP_BRANCHDIR        dir,                /**< branching direction */
552  	   SCIP_Real             length              /**< length of the conflict */
553  	   )
554  	{
555  	   assert(history != NULL);
556  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
557  	   assert((int)dir == 0 || (int)dir == 1); 
558  	   assert(length >= 0.0);
559  	
560  	   history->nactiveconflicts[dir]++;
561  	   history->conflengthsum[dir] += length;
562  	}
563  	
564  	/** gets the number of active conflicts of the history entry */
565  	SCIP_Longint SCIPhistoryGetNActiveConflicts(
566  	   SCIP_HISTORY*         history,            /**< branching and inference history */
567  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
568  	   )
569  	{
570  	   assert(history != NULL);
571  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
572  	   assert((int)dir == 0 || (int)dir == 1);
573  	
574  	   return history->nactiveconflicts[dir];
575  	}
576  	
577  	/** gets the average conflict length of the history entry */
578  	SCIP_Real SCIPhistoryGetAvgConflictlength(
579  	   SCIP_HISTORY*         history,            /**< branching and inference history */
580  	   SCIP_BRANCHDIR        dir                 /**< branching direction */
581  	   )
582  	{
583  	   assert(history != NULL);
584  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
585  	   assert((int)dir == 0 || (int)dir == 1);
586  	
587  	   return history->conflengthsum[dir] > 0.0 ? (SCIP_Real)history->nactiveconflicts[dir]/(SCIP_Real)history->conflengthsum[dir] : 0.0;
588  	}
589  	
590  	/** increases the number of branchings counter */
591  	void SCIPhistoryIncNBranchings(
592  	   SCIP_HISTORY*         history,            /**< branching and inference history */
593  	   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
594  	   int                   depth               /**< depth at which the bound change took place */
595  	   )
596  	{
597  	   assert(history != NULL);
598  	   assert(depth >= 1);
599  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
600  	   assert((int)dir == 0 || (int)dir == 1);
601  	
602  	   history->nbranchings[dir]++;
603  	   history->branchdepthsum[dir] += depth;
604  	}
605  	
606  	/** increases the number of inferences counter by a certain value */
607  	void SCIPhistoryIncInferenceSum(
608  	   SCIP_HISTORY*         history,            /**< branching and inference history */
609  	   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
610  	   SCIP_Real             weight              /**< weight of this update in inference score */
611  	   ) 
612  	{
613  	   assert(history != NULL);
614  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
615  	   assert((int)dir == 0 || (int)dir == 1);
616  	   assert(history->nbranchings[dir] >= 1);
617  	   assert(weight >= 0.0);
618  	
619  	   history->inferencesum[dir] += weight;
620  	} 
621  	
622  	/** increases the number of cutoffs counter */
623  	void SCIPhistoryIncCutoffSum(
624  	   SCIP_HISTORY*         history,            /**< branching and inference history */
625  	   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
626  	   SCIP_Real             weight              /**< weight of this update in cutoff score */
627  	   )
628  	{
629  	   assert(history != NULL);
630  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
631  	   assert((int)dir == 0 || (int)dir == 1);
632  	   assert(history->nbranchings[dir] >= 1);
633  	   assert(weight >= 0.0);
634  	
635  	   history->cutoffsum[dir] += weight;
636  	}
637  	
638  	/** get number of branchings counter */
639  	SCIP_Longint SCIPhistoryGetNBranchings(
640  	   SCIP_HISTORY*         history,            /**< branching and inference history */
641  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
642  	   )
643  	{
644  	   assert(history != NULL);
645  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
646  	   assert((int)dir == 0 || (int)dir == 1);
647  	
648  	   return history->nbranchings[dir];
649  	}
650  	
651  	/** get number of inferences counter */
652  	SCIP_Real SCIPhistoryGetInferenceSum(
653  	   SCIP_HISTORY*         history,            /**< branching and inference history */
654  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
655  	   )
656  	{
657  	   assert(history != NULL);
658  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
659  	   assert((int)dir == 0 || (int)dir == 1);
660  	
661  	   return history->inferencesum[dir];
662  	}
663  	
664  	/** returns the average number of inferences per branching */
665  	SCIP_Real SCIPhistoryGetAvgInferences(
666  	   SCIP_HISTORY*         history,            /**< branching and inference history */
667  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
668  	   )
669  	{
670  	   assert(history != NULL);
671  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
672  	   assert((int)dir == 0 || (int)dir == 1);
673  	
674  	   return history->nbranchings[dir] > 0 ? (SCIP_Real)history->inferencesum[dir]/(SCIP_Real)history->nbranchings[dir] : 0.0;
675  	}
676  	
677  	/** get number of cutoffs counter */
678  	SCIP_Real SCIPhistoryGetCutoffSum(
679  	   SCIP_HISTORY*         history,            /**< branching and inference history */
680  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
681  	   )
682  	{
683  	   assert(history != NULL);
684  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
685  	   assert((int)dir == 0 || (int)dir == 1);
686  	
687  	   return history->cutoffsum[dir];
688  	}
689  	
690  	/** returns the average number of cutoffs per branching */
691  	SCIP_Real SCIPhistoryGetAvgCutoffs(
692  	   SCIP_HISTORY*         history,            /**< branching and inference history */
693  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
694  	   )
695  	{
696  	   assert(history != NULL);
697  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
698  	   assert((int)dir == 0 || (int)dir == 1);
699  	
700  	   return history->nbranchings[dir] > 0 ? (SCIP_Real)history->cutoffsum[dir]/(SCIP_Real)history->nbranchings[dir] : 0.0;
701  	}
702  	
703  	/** returns the average depth of bound changes due to branching */
704  	SCIP_Real SCIPhistoryGetAvgBranchdepth(
705  	   SCIP_HISTORY*         history,            /**< branching and inference history */
706  	   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
707  	   )
708  	{
709  	   assert(history != NULL);
710  	   assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS);
711  	   assert((int)dir == 0 || (int)dir == 1);
712  	
713  	   return history->nbranchings[dir] > 0 ? (SCIP_Real)history->branchdepthsum[dir]/(SCIP_Real)history->nbranchings[dir] : 1.0;
714  	}
715  	
716  	/** returns true if the given history contains a valid ratio */
717  	SCIP_Bool SCIPhistoryIsRatioValid(
718  	   SCIP_HISTORY*         history             /**< branching and inference history */
719  	   )
720  	{
721  	   assert(history != NULL);
722  	
723  	   return history->ratiovalid;
724  	}
725  	
726  	/** returns the most recent ratio computed given the variable history */
727  	SCIP_Real SCIPhistoryGetLastRatio(
728  	   SCIP_HISTORY*         history             /**< branching and inference history */
729  	   )
730  	{
731  	   assert(history != NULL);
732  	   assert(history->ratiovalid);
733  	
734  	   return history->ratio;
735  	}
736  	
737  	/** returns the most recent value of r/l used to compute this variable's ratio */
738  	SCIP_Real SCIPhistoryGetLastBalance(
739  	   SCIP_HISTORY*         history             /**< branching and inference history */
740  	   )
741  	{
742  	   assert(history != NULL);
743  	   assert(history->ratiovalid);
744  	
745  	   return history->balance;
746  	}
747  	
748  	/** returns the average efficacy value for the GMI cut produced by this variable */
749  	SCIP_Real SCIPhistoryGetAvgGMIeff(
750  	   SCIP_HISTORY*         history             /**< branching and inference history */
751  	)
752  	{
753  	   assert(history != NULL);
754  	
755  	   return history->ngmi > 0 ? history->gmieffsum / history->ngmi : 0.0;
756  	}
757  	
758  	/** increases the average efficacy value for the GMI cut produced by this variable */
759  	void SCIPhistoryIncGMIeffSum(
760  	   SCIP_HISTORY*         history,            /**< branching and inference history */
761  	   SCIP_Real             gmieff              /**< normalized efficacy value of a cut which will increase gmieff */
762  	)
763  	{
764  	   assert(history != NULL);
765  	   assert(gmieff >= 0.0);
766  	
767  	   history->gmieffsum += gmieff;
768  	   history->ngmi += 1;
769  	}
770  	
771  	/** returns the most recent efficacy value for the GMI cut produced by this variable */
772  	SCIP_Real SCIPhistoryGetLastGMIeff(
773  	   SCIP_HISTORY*         history             /**< branching and inference history */
774  	)
775  	{
776  	   assert(history != NULL);
777  	
778  	   return history->gmieff;
779  	}
780  	
781  	/** sets the new most recent efficacy value for the GMI cut produced by this variable */
782  	void SCIPhistorySetLastGMIeff(
783  	   SCIP_HISTORY*         history,            /**< branching and inference history */
784  	   SCIP_Real             gmieff              /**< Efficacy of GMI cut produced from simplex tableau row of this var */
785  	)
786  	{
787  	   assert(history != NULL);
788  	
789  	   history->gmieff = gmieff;
790  	}
791  	
792  	/** sets the ratio history for a particular variable */
793  	void SCIPhistorySetRatioHistory(
794  	   SCIP_HISTORY*         history,            /**< branching and inference history */
795  	   SCIP_Bool             valid,              /**< True iff the ratio computed is valid */
796  	   SCIP_Real             ratio,              /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */
797  	   SCIP_Real             balance             /**< The value of rightgain/leftgain */
798  	   )
799  	{
800  	   assert(history != NULL);
801  	
802  	   history->ratiovalid = valid;
803  	   history->ratio = ratio;
804  	   history->balance = balance;
805  	}
806  	
807  	#endif
808