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