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.h 17 * @ingroup INTERNALAPI 18 * @brief internal methods for branching and inference history 19 * @author Tobias Achterberg 20 * @author Timo Berthold 21 */ 22 23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 24 25 #ifndef __SCIP_HISTORY_H__ 26 #define __SCIP_HISTORY_H__ 27 28 29 #include "scip/def.h" 30 #include "blockmemshell/memory.h" 31 #include "scip/type_retcode.h" 32 #include "scip/type_set.h" 33 #include "scip/type_history.h" 34 35 #ifdef NDEBUG 36 #include "scip/struct_history.h" 37 #endif 38 39 #ifdef __cplusplus 40 extern "C" { 41 #endif 42 43 /** creates an empty history entry */ 44 SCIP_RETCODE SCIPhistoryCreate( 45 SCIP_HISTORY** history, /**< pointer to store branching and inference history */ 46 BMS_BLKMEM* blkmem /**< block memory */ 47 ); 48 49 /** frees a history entry */ 50 void SCIPhistoryFree( 51 SCIP_HISTORY** history, /**< pointer to branching and inference history */ 52 BMS_BLKMEM* blkmem /**< block memory */ 53 ); 54 55 /** resets history entry to zero */ 56 void SCIPhistoryReset( 57 SCIP_HISTORY* history /**< branching and inference history */ 58 ); 59 60 /** unites two history entries by adding the values of the second one to the first one */ 61 void SCIPhistoryUnite( 62 SCIP_HISTORY* history, /**< branching and inference history */ 63 SCIP_HISTORY* addhistory, /**< history values to add to history */ 64 SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */ 65 ); 66 67 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta" 68 * in the LP's objective value 69 */ 70 void SCIPhistoryUpdatePseudocost( 71 SCIP_HISTORY* history, /**< branching and inference history */ 72 SCIP_SET* set, /**< global SCIP settings */ 73 SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */ 74 SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */ 75 SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */ 76 ); 77 78 79 /**@defgroup ValueHistory Value Based History 80 * @ingroup INTERNALAPI 81 * @brief Value based history methods 82 * 83 * @{ 84 */ 85 86 /** creates an empty value history */ 87 SCIP_RETCODE SCIPvaluehistoryCreate( 88 SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */ 89 BMS_BLKMEM* blkmem /**< block memory */ 90 ); 91 92 /** frees a value history */ 93 void SCIPvaluehistoryFree( 94 SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */ 95 BMS_BLKMEM* blkmem /**< block memory */ 96 ); 97 98 /** finds for the given domain value the history if it does not exist yet it will be created */ 99 SCIP_RETCODE SCIPvaluehistoryFind( 100 SCIP_VALUEHISTORY* valuehistory, /**< value based history */ 101 BMS_BLKMEM* blkmem, /**< block memory */ 102 SCIP_SET* set, /**< global SCIP settings */ 103 SCIP_Real value, /**< domain value of interest */ 104 SCIP_HISTORY** history /**< pointer to store the history for the given domain value */ 105 ); 106 107 /** scales the conflict score values with the given scalar for each value history entry */ 108 void SCIPvaluehistoryScaleVSIDS( 109 SCIP_VALUEHISTORY* valuehistory, /**< value based history */ 110 SCIP_Real scalar /**< scalar to multiply the conflict scores with */ 111 ); 112 113 /**@} */ 114 115 /** returns the opposite direction of the given branching direction */ 116 SCIP_BRANCHDIR SCIPbranchdirOpposite( 117 SCIP_BRANCHDIR dir /**< branching direction */ 118 ); 119 120 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */ 121 SCIP_Real SCIPhistoryGetPseudocost( 122 SCIP_HISTORY* history, /**< branching and inference history */ 123 SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */ 124 ); 125 126 /** returns the variance of pseudo costs about the mean. */ 127 SCIP_Real SCIPhistoryGetPseudocostVariance( 128 SCIP_HISTORY* history, /**< branching and inference history */ 129 SCIP_BRANCHDIR direction /**< direction of variable: 1 for upwards history, 0 for downwards history */ 130 ); 131 132 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in 133 * the given branching direction 134 */ 135 SCIP_Real SCIPhistoryGetPseudocostCount( 136 SCIP_HISTORY* history, /**< branching and inference history */ 137 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 138 ); 139 140 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */ 141 SCIP_Bool SCIPhistoryIsPseudocostEmpty( 142 SCIP_HISTORY* history, /**< branching and inference history */ 143 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 144 ); 145 146 /** increases the conflict score of the history entry by the given weight */ 147 void SCIPhistoryIncVSIDS( 148 SCIP_HISTORY* history, /**< branching and inference history */ 149 SCIP_BRANCHDIR dir, /**< branching direction */ 150 SCIP_Real weight /**< weight of this update in conflict score */ 151 ); 152 153 /** scales the conflict score values with the given scalar */ 154 void SCIPhistoryScaleVSIDS( 155 SCIP_HISTORY* history, /**< branching and inference history */ 156 SCIP_Real scalar /**< scalar to multiply the conflict scores with */ 157 ); 158 159 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */ 160 void SCIPhistoryIncNActiveConflicts( 161 SCIP_HISTORY* history, /**< branching and inference history */ 162 SCIP_BRANCHDIR dir, /**< branching direction */ 163 SCIP_Real length /**< length of the conflict */ 164 ); 165 166 /** gets the number of active conflicts of the history entry */ 167 SCIP_Longint SCIPhistoryGetNActiveConflicts( 168 SCIP_HISTORY* history, /**< branching and inference history */ 169 SCIP_BRANCHDIR dir /**< branching direction */ 170 ); 171 172 /** gets the average conflict length of the history entry */ 173 SCIP_Real SCIPhistoryGetAvgConflictlength( 174 SCIP_HISTORY* history, /**< branching and inference history */ 175 SCIP_BRANCHDIR dir /**< branching direction */ 176 ); 177 178 /** increases the number of branchings counter */ 179 void SCIPhistoryIncNBranchings( 180 SCIP_HISTORY* history, /**< branching and inference history */ 181 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 182 int depth /**< depth at which the bound change took place */ 183 ); 184 185 /** increases the number of inferences counter */ 186 void SCIPhistoryIncInferenceSum( 187 SCIP_HISTORY* history, /**< branching and inference history */ 188 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 189 SCIP_Real weight /**< weight of this update in cutoff score */ 190 ); 191 192 193 /** increases the number of cutoffs counter */ 194 void SCIPhistoryIncCutoffSum( 195 SCIP_HISTORY* history, /**< branching and inference history */ 196 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 197 SCIP_Real weight /**< weight of this update in cutoff score */ 198 ); 199 200 /** get number of branchings counter */ 201 SCIP_Longint SCIPhistoryGetNBranchings( 202 SCIP_HISTORY* history, /**< branching and inference history */ 203 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 204 ); 205 206 /** get number of inferences counter */ 207 SCIP_Real SCIPhistoryGetInferenceSum( 208 SCIP_HISTORY* history, /**< branching and inference history */ 209 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 210 ); 211 212 /** returns the average number of inferences per branching */ 213 SCIP_Real SCIPhistoryGetAvgInferences( 214 SCIP_HISTORY* history, /**< branching and inference history */ 215 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 216 ); 217 218 /** returns the average number of cutoffs per branching */ 219 SCIP_Real SCIPhistoryGetAvgCutoffs( 220 SCIP_HISTORY* history, /**< branching and inference history */ 221 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 222 ); 223 224 /** returns the average depth of bound changes due to branching */ 225 SCIP_Real SCIPhistoryGetAvgBranchdepth( 226 SCIP_HISTORY* history, /**< branching and inference history */ 227 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 228 ); 229 230 /** returns true if the given history contains a valid ratio */ 231 SCIP_Bool SCIPhistoryIsRatioValid( 232 SCIP_HISTORY* history /**< branching and inference history */ 233 ); 234 235 /** returns the most recent ratio computed given the variable history */ 236 SCIP_Real SCIPhistoryGetLastRatio( 237 SCIP_HISTORY* history /**< branching and inference history */ 238 ); 239 240 /** returns the most recent value of r/l used to compute this variable's ratio */ 241 SCIP_Real SCIPhistoryGetLastBalance( 242 SCIP_HISTORY* history /**< branching and inference history */ 243 ); 244 245 /** sets the ratio history for a particular variable */ 246 void SCIPhistorySetRatioHistory( 247 SCIP_HISTORY* history, /**< branching and inference history */ 248 SCIP_Bool valid, /**< True iff the ratio computed is valid */ 249 SCIP_Real ratio, /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */ 250 SCIP_Real balance /**< The value of rightgain/leftgain */ 251 ); 252 253 #ifdef NDEBUG 254 255 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and 256 * speed up the algorithms. 257 */ 258 259 #define SCIPbranchdirOpposite(dir) \ 260 ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS \ 261 : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO)) 262 #define SCIPhistoryGetPseudocost(history,solvaldelta) \ 263 ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \ 264 ? (history)->pscostweightedmean[1] : 1.0) \ 265 : -(solvaldelta) * ((history)->pscostcount[0] > 0.0 \ 266 ? (history)->pscostweightedmean[0] : 1.0) ) 267 #define SCIPhistoryGetPseudocostVariance(history, dir) \ 268 ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1) \ 269 * ((history)->pscostvariance[dir]) \ 270 : 0.0) 271 #define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir]) 272 #define SCIPhistoryIsPseudocostEmpty(history,dir) ((history)->pscostcount[dir] == 0.0) 273 #define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight) 274 #define SCIPhistoryScaleVSIDS(history,scalar) { (history)->vsids[0] *= (scalar); \ 275 (history)->vsids[1] *= (scalar); } 276 #define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \ 277 (history)->conflengthsum[dir] += length; } 278 #define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir]) 279 #define SCIPhistoryGetAvgConflictlength(history,dir) ((history)->conflengthsum[dir] > 0.0 \ 280 ? (SCIP_Real)(history)->nactiveconflicts[dir]/(SCIP_Real)(history)->conflengthsum[dir] : 0.0) 281 #define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \ 282 (history)->branchdepthsum[dir] += depth; } 283 #define SCIPhistoryIncInferenceSum(history,dir,weight) (history)->inferencesum[dir] += (weight) 284 #define SCIPhistoryIncCutoffSum(history,dir,weight) (history)->cutoffsum[dir] += (weight) 285 #define SCIPhistoryGetNBranchings(history,dir) ((history)->nbranchings[dir]) 286 #define SCIPhistoryGetInferenceSum(history,dir) ((history)->inferencesum[dir]) 287 #define SCIPhistoryGetAvgInferences(history,dir) ((history)->nbranchings[dir] > 0 \ 288 ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0) 289 #define SCIPhistoryGetAvgCutoffs(history,dir) ((history)->nbranchings[dir] > 0 \ 290 ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0) 291 #define SCIPhistoryGetAvgBranchdepth(history,dir) ((history)->nbranchings[dir] > 0 \ 292 ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0) 293 #define SCIPhistoryIsRatioValid(history) ((history)->ratiovalid) 294 #define SCIPhistoryGetLastRatio(history) ((history)->ratio) 295 #define SCIPhistorySetRatioHistory(history,newvalid,newratio,newbalance) (history)->ratiovalid = newvalid, \ 296 (history)->ratio = newratio, (history)->balance = newbalance 297 #define SCIPhistoryGetLastBalance(history) ((history)->balance) 298 299 #endif 300 301 #ifdef __cplusplus 302 } 303 #endif 304 305 #endif 306