1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 */
SCIPhistoryCreate(SCIP_HISTORY ** history,BMS_BLKMEM * blkmem)42 SCIP_RETCODE SCIPhistoryCreate(
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 */
SCIPhistoryFree(SCIP_HISTORY ** history,BMS_BLKMEM * blkmem)57 void SCIPhistoryFree(
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 */
SCIPhistoryReset(SCIP_HISTORY * history)69 void SCIPhistoryReset(
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 */
SCIPhistoryUnite(SCIP_HISTORY * history,SCIP_HISTORY * addhistory,SCIP_Bool switcheddirs)101 void SCIPhistoryUnite(
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 */
SCIPhistoryUpdatePseudocost(SCIP_HISTORY * history,SCIP_SET * set,SCIP_Real solvaldelta,SCIP_Real objdelta,SCIP_Real weight)162 void SCIPhistoryUpdatePseudocost(
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 */
SCIPvaluehistoryCreate(SCIP_VALUEHISTORY ** valuehistory,BMS_BLKMEM * blkmem)231 SCIP_RETCODE SCIPvaluehistoryCreate(
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 */
SCIPvaluehistoryFree(SCIP_VALUEHISTORY ** valuehistory,BMS_BLKMEM * blkmem)250 void SCIPvaluehistoryFree(
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 */
SCIPvaluehistoryFind(SCIP_VALUEHISTORY * valuehistory,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_Real value,SCIP_HISTORY ** history)272 SCIP_RETCODE SCIPvaluehistoryFind(
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 */
SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY * valuehistory,SCIP_Real scalar)317 void SCIPvaluehistoryScaleVSIDS(
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 */
SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY * valuehistory)351 int SCIPvaluehistoryGetNValues(
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 */
SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY * valuehistory)361 SCIP_HISTORY** SCIPvaluehistoryGetHistories(
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 */
SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY * valuehistory)371 SCIP_Real* SCIPvaluehistoryGetValues(
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 */
SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)421 SCIP_BRANCHDIR SCIPbranchdirOpposite(
422 SCIP_BRANCHDIR dir /**< branching direction */
423 )
424 {
425 return (dir == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS
426 : (dir == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO));
427 }
428
429 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
SCIPhistoryGetPseudocost(SCIP_HISTORY * history,SCIP_Real solvaldelta)430 SCIP_Real SCIPhistoryGetPseudocost(
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. */
SCIPhistoryGetPseudocostVariance(SCIP_HISTORY * history,SCIP_BRANCHDIR direction)444 SCIP_Real SCIPhistoryGetPseudocostVariance(
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 */
SCIPhistoryGetPseudocostCount(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)468 SCIP_Real SCIPhistoryGetPseudocostCount(
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) */
SCIPhistoryIsPseudocostEmpty(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)481 SCIP_Bool SCIPhistoryIsPseudocostEmpty(
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 */
SCIPhistoryIncVSIDS(SCIP_HISTORY * history,SCIP_BRANCHDIR dir,SCIP_Real weight)494 void SCIPhistoryIncVSIDS(
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 */
SCIPhistoryScaleVSIDS(SCIP_HISTORY * history,SCIP_Real scalar)508 void SCIPhistoryScaleVSIDS(
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 */
SCIPhistoryGetVSIDS(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)520 SCIP_Real SCIPhistoryGetVSIDS(
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 */
SCIPhistoryIncNActiveConflicts(SCIP_HISTORY * history,SCIP_BRANCHDIR dir,SCIP_Real length)533 void SCIPhistoryIncNActiveConflicts(
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 */
SCIPhistoryGetNActiveConflicts(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)549 SCIP_Longint SCIPhistoryGetNActiveConflicts(
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 */
SCIPhistoryGetAvgConflictlength(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)562 SCIP_Real SCIPhistoryGetAvgConflictlength(
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 */
SCIPhistoryIncNBranchings(SCIP_HISTORY * history,SCIP_BRANCHDIR dir,int depth)575 void SCIPhistoryIncNBranchings(
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 */
SCIPhistoryIncInferenceSum(SCIP_HISTORY * history,SCIP_BRANCHDIR dir,SCIP_Real weight)591 void SCIPhistoryIncInferenceSum(
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 */
SCIPhistoryIncCutoffSum(SCIP_HISTORY * history,SCIP_BRANCHDIR dir,SCIP_Real weight)607 void SCIPhistoryIncCutoffSum(
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 */
SCIPhistoryGetNBranchings(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)623 SCIP_Longint SCIPhistoryGetNBranchings(
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 */
SCIPhistoryGetInferenceSum(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)636 SCIP_Real SCIPhistoryGetInferenceSum(
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 */
SCIPhistoryGetAvgInferences(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)649 SCIP_Real SCIPhistoryGetAvgInferences(
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 */
SCIPhistoryGetCutoffSum(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)662 SCIP_Real SCIPhistoryGetCutoffSum(
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 */
SCIPhistoryGetAvgCutoffs(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)675 SCIP_Real SCIPhistoryGetAvgCutoffs(
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 */
SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY * history,SCIP_BRANCHDIR dir)688 SCIP_Real SCIPhistoryGetAvgBranchdepth(
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 */
SCIPhistoryIsRatioValid(SCIP_HISTORY * history)701 SCIP_Bool SCIPhistoryIsRatioValid(
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 */
SCIPhistoryGetLastRatio(SCIP_HISTORY * history)711 SCIP_Real SCIPhistoryGetLastRatio(
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 */
SCIPhistoryGetLastBalance(SCIP_HISTORY * history)722 SCIP_Real SCIPhistoryGetLastBalance(
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 */
SCIPhistorySetRatioHistory(SCIP_HISTORY * history,SCIP_Bool valid,SCIP_Real ratio,SCIP_Real balance)733 void SCIPhistorySetRatioHistory(
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
748