Scippy

SCIP

Solving Constraint Integer Programs

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