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 type_prop.h 17 * @ingroup TYPEDEFINITIONS 18 * @brief type definitions for propagators 19 * @author Tobias Achterberg 20 */ 21 22 /** @defgroup DEFPLUGINS_PROP Default Propagators 23 * @ingroup DEFPLUGINS 24 * @brief implementation files (.c files) of the default propagators of SCIP 25 */ 26 27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 28 29 #ifndef __SCIP_TYPE_PROP_H__ 30 #define __SCIP_TYPE_PROP_H__ 31 32 #include "scip/def.h" 33 #include "scip/type_retcode.h" 34 #include "scip/type_result.h" 35 #include "scip/type_scip.h" 36 #include "scip/type_timing.h" 37 38 #ifdef __cplusplus 39 extern "C" { 40 #endif 41 42 typedef struct SCIP_Prop SCIP_PROP; /**< propagator */ 43 typedef struct SCIP_PropData SCIP_PROPDATA; /**< locally defined propagator data */ 44 45 46 /** copy method for propagator plugins (called when SCIP copies plugins) 47 * 48 * input: 49 * - scip : SCIP main data structure 50 * - prop : the propagator itself 51 */ 52 #define SCIP_DECL_PROPCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 53 54 /** destructor of propagator to free user data (called when SCIP is exiting) 55 * 56 * input: 57 * - scip : SCIP main data structure 58 * - prop : the propagator itself 59 */ 60 #define SCIP_DECL_PROPFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 61 62 /** initialization method of propagator (called after problem was transformed) 63 * 64 * input: 65 * - scip : SCIP main data structure 66 * - prop : the propagator itself 67 */ 68 #define SCIP_DECL_PROPINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 69 70 /** deinitialization method of propagator (called before transformed problem is freed) 71 * 72 * input: 73 * - scip : SCIP main data structure 74 * - prop : the propagator itself 75 */ 76 #define SCIP_DECL_PROPEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 77 78 /** presolving initialization method of propagator (called when presolving is about to begin) 79 * 80 * This method is called when the presolving process is about to begin, even if presolving is turned off. The 81 * propagator may use this call to initialize its presolving data, before the presolving process begins. 82 * 83 * Necessary modifications that have to be performed even if presolving is turned off should be done here or in the 84 * presolving deinitialization call (SCIP_DECL_PROPEXITPRE()). 85 * 86 * input: 87 * - scip : SCIP main data structure 88 * - prop : the propagator itself 89 */ 90 #define SCIP_DECL_PROPINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 91 92 /** presolving deinitialization method of propagator (called after presolving has been finished) 93 * 94 * This method is called after the presolving has been finished, even if presolving is turned off. 95 * The propagator may use this call e.g. to clean up its presolving data. 96 * 97 * Besides necessary modifications and clean up, no time consuming operations should be performed, especially if the 98 * problem has already been solved. Use the method SCIPgetStatus(), which in this case returns SCIP_STATUS_OPTIMAL, 99 * SCIP_STATUS_INFEASIBLE, SCIP_STATUS_UNBOUNDED, or SCIP_STATUS_INFORUNBD. 100 * 101 * input: 102 * - scip : SCIP main data structure 103 * - prop : the propagator itself 104 */ 105 #define SCIP_DECL_PROPEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 106 107 /** solving process initialization method of propagator (called when branch and bound process is about to begin) 108 * 109 * This method is called when the presolving was finished and the branch and bound process is about to begin. 110 * The propagator may use this call to initialize its branch and bound specific data. 111 * 112 * Besides necessary modifications and clean up, no time consuming operations should be performed, especially if the 113 * problem has already been solved. Use the method SCIPgetStatus(), which in this case returns SCIP_STATUS_OPTIMAL, 114 * SCIP_STATUS_INFEASIBLE, SCIP_STATUS_UNBOUNDED, or SCIP_STATUS_INFORUNBD. 115 * 116 * input: 117 * - scip : SCIP main data structure 118 * - prop : the propagator itself 119 */ 120 #define SCIP_DECL_PROPINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop) 121 122 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) 123 * 124 * This method is called before the branch and bound process is freed. 125 * The propagator should use this call to clean up its branch and bound data. 126 * 127 * input: 128 * - scip : SCIP main data structure 129 * - prop : the propagator itself 130 * - restart : was this exit solve call triggered by a restart? 131 */ 132 #define SCIP_DECL_PROPEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_Bool restart) 133 134 /** presolving method of propagator 135 * 136 * The presolver should go through the variables and constraints and tighten the domains or 137 * constraints. Each tightening should increase the given total numbers of changes. 138 * 139 * input: 140 * - scip : SCIP main data structure 141 * - prop : the propagator itself 142 * - nrounds : number of presolving rounds already done 143 * - presoltiming : current presolving timing 144 * - nnewfixedvars : number of variables fixed since the last call to the presolving method 145 * - nnewaggrvars : number of variables aggregated since the last call to the presolving method 146 * - nnewchgvartypes : number of variable type changes since the last call to the presolving method 147 * - nnewchgbds : number of variable bounds tightened since the last call to the presolving method 148 * - nnewholes : number of domain holes added since the last call to the presolving method 149 * - nnewdelconss : number of deleted constraints since the last call to the presolving method 150 * - nnewaddconss : number of added constraints since the last call to the presolving method 151 * - nnewupgdconss : number of upgraded constraints since the last call to the presolving method 152 * - nnewchgcoefs : number of changed coefficients since the last call to the presolving method 153 * - nnewchgsides : number of changed left or right hand sides since the last call to the presolving method 154 * 155 * @note the counters state the changes since the last call including the changes of this presolving method during its 156 * last call 157 * 158 * @note if the propagator uses dual information for presolving it is nesassary to check via calling SCIPallowWeakDualReds 159 * or SCIPallowStrongDualReds if dual reductions are allowed. 160 * 161 * input/output: 162 * - nfixedvars : pointer to total number of variables fixed of all presolvers 163 * - naggrvars : pointer to total number of variables aggregated of all presolvers 164 * - nchgvartypes : pointer to total number of variable type changes of all presolvers 165 * - nchgbds : pointer to total number of variable bounds tightened of all presolvers 166 * - naddholes : pointer to total number of domain holes added of all presolvers 167 * - ndelconss : pointer to total number of deleted constraints of all presolvers 168 * - naddconss : pointer to total number of added constraints of all presolvers 169 * - nupgdconss : pointer to total number of upgraded constraints of all presolvers 170 * - nchgcoefs : pointer to total number of changed coefficients of all presolvers 171 * - nchgsides : pointer to total number of changed left/right hand sides of all presolvers 172 * 173 * output: 174 * - result : pointer to store the result of the presolving call 175 * 176 * possible return values for *result: 177 * - SCIP_UNBOUNDED : at least one variable is not bounded by any constraint in obj. direction -> problem is unbounded 178 * - SCIP_CUTOFF : at least one constraint is infeasible in the variable's bounds -> problem is infeasible 179 * - SCIP_SUCCESS : the presolving method found a reduction 180 * - SCIP_DIDNOTFIND : the presolving method searched, but did not find a presolving change 181 * - SCIP_DIDNOTRUN : the presolving method was skipped 182 * - SCIP_DELAYED : the presolving method was skipped, but should be called again 183 */ 184 #define SCIP_DECL_PROPPRESOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, int nrounds, SCIP_PRESOLTIMING presoltiming, \ 185 int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, \ 186 int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, \ 187 int* nfixedvars, int* naggrvars, int* nchgvartypes, int* nchgbds, int* naddholes, \ 188 int* ndelconss, int* naddconss, int* nupgdconss, int* nchgcoefs, int* nchgsides, SCIP_RESULT* result) 189 190 /** execution method of propagator 191 * 192 * Searches for domain propagations. The method is called in the node processing loop. 193 * 194 * input: 195 * - scip : SCIP main data structure 196 * - prop : the propagator itself 197 * - proptiming : current point in the node solving loop 198 * - result : pointer to store the result of the propagation call 199 * 200 * possible return values for *result: 201 * - SCIP_CUTOFF : the current node is infeasible for the current domains 202 * - SCIP_REDUCEDDOM : at least one domain reduction was found 203 * - SCIP_DIDNOTFIND : the propagator searched, but did not find a domain reduction 204 * - SCIP_DIDNOTRUN : the propagator was skipped 205 * - SCIP_DELAYED : the propagator was skipped, but should be called again 206 * - SCIP_DELAYNODE : the current node should be postponed (return value only valid for BEFORELP propagation) 207 */ 208 #define SCIP_DECL_PROPEXEC(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_PROPTIMING proptiming, SCIP_RESULT* result) 209 210 211 /** propagation conflict resolving method of propagator 212 * 213 * This method is called during conflict analysis. If the propagator wants to support conflict analysis, 214 * it should call SCIPinferVarLbProp() or SCIPinferVarUbProp() in domain propagation instead of SCIPchgVarLb() or 215 * SCIPchgVarUb() in order to deduce bound changes on variables. 216 * In the SCIPinferVarLbProp() and SCIPinferVarUbProp() calls, the propagator provides a pointer to itself 217 * and an integer value "inferinfo" that can be arbitrarily chosen. 218 * The propagation conflict resolving method can then be implemented, to provide a "reasons" for the bound 219 * changes, i.e. the bounds of variables at the time of the propagation, that forced the propagator to set the 220 * conflict variable's bound to its current value. It can use the "inferinfo" tag to identify its own propagation 221 * rule and thus identify the "reason" bounds. The bounds that form the reason of the assignment must then be provided 222 * by calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), 223 * SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), and/or SCIPaddConflictBinvar() in the propagation conflict 224 * resolving method. 225 * 226 * See the description of the propagation conflict resolving method of constraint handlers for further details. 227 * 228 * @note if the propagtor uses dual information it is nesassary to check via calling SCIPallowWeakDualReds and 229 * SCIPallowStrongDualReds if dual reductions and propgation with the current cutoff bound, resp., are allowed. 230 * 231 * input: 232 * - scip : SCIP main data structure 233 * - prop : the propagator itself 234 * - infervar : the conflict variable whose bound change has to be resolved 235 * - inferinfo : the user information passed to the corresponding SCIPinferVarLbProp() or SCIPinferVarUbProp() call 236 * - boundtype : the type of the changed bound (lower or upper bound) 237 * - bdchgidx : the index of the bound change, representing the point of time where the change took place 238 * - relaxedbd : the relaxed bound which is sufficient to be explained 239 * 240 * output: 241 * - result : pointer to store the result of the propagation conflict resolving call 242 * 243 * possible return values for *result: 244 * - SCIP_SUCCESS : the conflicting bound change has been successfully resolved by adding all reason bounds 245 * - SCIP_DIDNOTFIND : the conflicting bound change could not be resolved and has to be put into the conflict set 246 * 247 * @note it is sufficient to explain/resolve the relaxed bound 248 */ 249 #define SCIP_DECL_PROPRESPROP(x) SCIP_RETCODE x (SCIP* scip, SCIP_PROP* prop, SCIP_VAR* infervar, int inferinfo, \ 250 SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX* bdchgidx, SCIP_Real relaxedbd, SCIP_RESULT* result) 251 252 #ifdef __cplusplus 253 } 254 #endif 255 256 #endif 257