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