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