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;
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 */
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
common defines and data types used in all packages of SCIP
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPsortedvecFindReal(SCIP_Real *realarray, SCIP_Real val, int len, int *pos)
void SCIPsortedvecInsertRealPtr(SCIP_Real *realarray, void **ptrarray, SCIP_Real keyval, void *field1val, int *len, int *pos)
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:363
SCIP_RETCODE SCIPvaluehistoryCreate(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:243
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:373
SCIP_RETCODE SCIPvaluehistoryFind(SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
Definition: history.c:284
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:383
void SCIPvaluehistoryFree(SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
Definition: history.c:262
void SCIPvaluehistoryScaleVSIDS(SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
Definition: history.c:329
void SCIPhistoryReset(SCIP_HISTORY *history)
Definition: history.c:78
SCIP_Real SCIPhistoryGetPseudocost(SCIP_HISTORY *history, SCIP_Real solvaldelta)
Definition: history.c:446
SCIP_Real SCIPhistoryGetAvgInferences(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:665
void SCIPhistorySetRatioHistory(SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
Definition: history.c:793
SCIP_Longint SCIPhistoryGetNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:565
SCIP_Longint SCIPhistoryGetNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:639
SCIP_Real SCIPhistoryGetAvgConflictlength(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:578
SCIP_Real SCIPhistoryGetAvgCutoffs(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:691
SCIP_RETCODE SCIPhistoryCreate(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:51
void SCIPhistorySetLastGMIeff(SCIP_HISTORY *history, SCIP_Real gmieff)
Definition: history.c:782
SCIP_Real SCIPhistoryGetLastRatio(SCIP_HISTORY *history)
Definition: history.c:727
void SCIPhistoryIncInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:607
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:678
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
SCIP_Real SCIPhistoryGetPseudocostVariance(SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
Definition: history.c:460
void SCIPhistoryIncNActiveConflicts(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
Definition: history.c:549
void SCIPhistoryScaleVSIDS(SCIP_HISTORY *history, SCIP_Real scalar)
Definition: history.c:524
void SCIPhistoryIncCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:623
void SCIPhistoryIncNBranchings(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
Definition: history.c:591
void SCIPhistoryUpdatePseudocost(SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: history.c:174
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:536
SCIP_Bool SCIPhistoryIsRatioValid(SCIP_HISTORY *history)
Definition: history.c:717
SCIP_Real SCIPhistoryGetAvgBranchdepth(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:704
SCIP_Real SCIPhistoryGetLastBalance(SCIP_HISTORY *history)
Definition: history.c:738
SCIP_Real SCIPhistoryGetLastGMIeff(SCIP_HISTORY *history)
Definition: history.c:772
SCIP_Real SCIPhistoryGetAvgGMIeff(SCIP_HISTORY *history)
Definition: history.c:749
SCIP_Real SCIPhistoryGetInferenceSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:652
void SCIPhistoryFree(SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
Definition: history.c:66
void SCIPhistoryUnite(SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
Definition: history.c:113
void SCIPhistoryIncGMIeffSum(SCIP_HISTORY *history, SCIP_Real gmieff)
Definition: history.c:759
SCIP_BRANCHDIR SCIPbranchdirOpposite(SCIP_BRANCHDIR dir)
Definition: history.c:437
void SCIPhistoryIncVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
Definition: history.c:510
internal methods for branching and inference history
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:454
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:467
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
real eps
public methods for branching and inference history structure
public methods for message output
public data structures and miscellaneous methods
SCIP_Real SCIPsetPseudocosteps(SCIP_SET *set)
Definition: set.c:6144
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6322
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Real SCIPsetPseudocostdelta(SCIP_SET *set)
Definition: set.c:6154
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5764
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6333
internal methods for global SCIP settings
#define SCIPsetDebugMsg
Definition: set.h:1784
SCIP_Longint nbranchings[2]
SCIP_Real pscostweightedmean[2]
SCIP_Longint nactiveconflicts[2]
SCIP_Bool ratiovalid
SCIP_Real pscostvariance[2]
SCIP_Real vsids[2]
SCIP_Real pscostcount[2]
SCIP_Real ratio
SCIP_Real cutoffsum[2]
SCIP_Real ngmi
SCIP_Real inferencesum[2]
SCIP_Real balance
SCIP_Real gmieff
SCIP_Real conflengthsum[2]
SCIP_Real gmieffsum
SCIP_Longint branchdepthsum[2]
SCIP_Real * values
SCIP_HISTORY ** histories
datastructures for branching and inference history
Definition: heur_padm.c:135
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_AUTO
Definition: type_history.h:46
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63