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