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