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