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