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 prop_sync.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief propagator for applying global bound changes that were communicated by other 28 * concurrent solvers 29 * @author Leona Gottwald 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/concurrent.h" 36 #include "scip/prop_sync.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_prop.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_mem.h" 41 #include "scip/scip_message.h" 42 #include "scip/scip_probing.h" 43 #include "scip/scip_prop.h" 44 #include "scip/scip_var.h" 45 #include "scip/scip_message.h" 46 #include <string.h> 47 #include "tpi/tpi.h" 48 49 /* fundamental propagator properties */ 50 #define PROP_NAME "sync" 51 #define PROP_DESC "propagator for synchronization of bound changes" 52 #define PROP_PRIORITY (INT_MAX/4) /**< propagator priority */ 53 #define PROP_FREQ -1 /**< propagator frequency */ 54 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 55 #define PROP_TIMING SCIP_PROPTIMING_ALWAYS /**< propagation timing mask */ 56 57 #define PROP_PRESOL_PRIORITY (INT_MAX/4) /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */ 58 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS /* timing of the presolving method (fast, medium, or exhaustive) */ 59 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no 60 * limit) */ 61 62 /* 63 * Data structures 64 */ 65 66 /** propagator data */ 67 struct SCIP_PropData 68 { 69 SCIP_VAR** bndvar; /**< array of variables with a bound change */ 70 SCIP_Real* bndval; /**< array of new bound values */ 71 SCIP_BOUNDTYPE* bndtype; /**< array of bound types */ 72 int nbnds; /**< number of boundchanges */ 73 int bndsize; /**< current size of bound change array */ 74 SCIP_Longint ntightened; /**< number of tightened bounds */ 75 SCIP_Longint ntightenedint; /**< number of tightened bounds of integer variables */ 76 }; 77 78 79 /* 80 * Local methods 81 */ 82 83 /* put your local methods here, and declare them static */ 84 85 static 86 SCIP_RETCODE applyBoundChanges( 87 SCIP* scip, 88 SCIP_PROPDATA* data, 89 SCIP_RESULT* result, 90 int* ntightened, 91 int* ntightenedint 92 ) 93 { 94 int i; 95 96 assert(data != NULL); 97 assert(ntightened != NULL); 98 assert(ntightenedint != NULL); 99 100 *ntightened = 0; 101 *ntightenedint = 0; 102 103 SCIPdisableConcurrentBoundStorage(scip); 104 *result = SCIP_DIDNOTFIND; 105 106 for( i = 0; i < data->nbnds; ++i ) 107 { 108 SCIP_Bool infeas, tightened; 109 SCIP_CALL( SCIPvarGetProbvarBound(&data->bndvar[i], &data->bndval[i], &data->bndtype[i]) ); 110 111 /* cannot change bounds of multi-aggregated variables so skip this bound-change */ 112 if( SCIPvarGetStatus(data->bndvar[i]) == SCIP_VARSTATUS_MULTAGGR ) 113 continue; 114 115 if( data->bndtype[i] == SCIP_BOUNDTYPE_LOWER ) 116 { 117 SCIP_CALL( SCIPtightenVarLbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) ); 118 } 119 else 120 { 121 assert(data->bndtype[i] == SCIP_BOUNDTYPE_UPPER); 122 SCIP_CALL( SCIPtightenVarUbGlobal(scip, data->bndvar[i], data->bndval[i], FALSE, &infeas, &tightened) ); 123 } 124 if( tightened ) 125 { 126 ++(*ntightened); 127 if( SCIPvarGetType(data->bndvar[i]) <= SCIP_VARTYPE_INTEGER ) 128 ++(*ntightenedint); 129 } 130 if( infeas ) 131 { 132 #ifndef NDEBUG 133 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "sync propagator found cutoff in thread %i\n", SCIPtpiGetThreadNum()); 134 #endif 135 *result = SCIP_CUTOFF; 136 break; 137 } 138 } 139 140 data->nbnds = 0; 141 SCIPenableConcurrentBoundStorage(scip); 142 143 return SCIP_OKAY; 144 } 145 146 147 /* 148 * Callback methods of propagator 149 */ 150 151 /** destructor of propagator to free user data (called when SCIP is exiting) */ 152 static 153 SCIP_DECL_PROPFREE(propFreeSync) 154 { /*lint --e{715}*/ 155 SCIP_PROPDATA* propdata; 156 157 assert(scip != NULL); 158 assert(prop != NULL); 159 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 160 161 propdata = SCIPpropGetData(prop); 162 assert(propdata != NULL); 163 164 SCIPfreeMemory(scip, &propdata); 165 SCIPpropSetData(prop, NULL); 166 167 return SCIP_OKAY; 168 } 169 170 /** initialization method of propagator (called after problem was transformed) */ 171 static 172 SCIP_DECL_PROPINIT(propInitSync) 173 { /*lint --e{715}*/ 174 SCIP_PROPDATA* data; 175 176 assert(prop != NULL); 177 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 178 179 data = SCIPpropGetData(prop); 180 assert(data != NULL); 181 182 data->bndsize = 0; 183 data->nbnds = 0; 184 data->bndvar = NULL; 185 data->bndval = NULL; 186 data->bndtype = NULL; 187 data->ntightened = 0; 188 data->ntightenedint = 0; 189 190 return SCIP_OKAY; 191 } 192 193 /** deinitialization method of propagator (called before transformed problem is freed) */ 194 static 195 SCIP_DECL_PROPEXIT(propExitSync) 196 { /*lint --e{715}*/ 197 SCIP_PROPDATA* data; 198 199 assert(prop != NULL); 200 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 201 202 data = SCIPpropGetData(prop); 203 assert(data != NULL); 204 205 SCIPfreeBlockMemoryArrayNull(scip, &data->bndvar, data->bndsize); 206 SCIPfreeBlockMemoryArrayNull(scip, &data->bndval, data->bndsize); 207 SCIPfreeBlockMemoryArrayNull(scip, &data->bndtype, data->bndsize); 208 209 return SCIP_OKAY; 210 } 211 212 static 213 SCIP_DECL_PROPPRESOL(propPresolSync) 214 { /*lint --e{715}*/ 215 SCIP_PROPDATA* data; 216 int ntightened; 217 int ntightenedint; 218 219 assert(prop != NULL); 220 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 221 222 data = SCIPpropGetData(prop); 223 assert(data != NULL); 224 225 *result = SCIP_DIDNOTRUN; 226 227 if( data->nbnds == 0 || SCIPinProbing(scip) ) 228 return SCIP_OKAY; 229 230 /* remember number of tightened bounds before applying new bound tightenings */ 231 232 SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) ); 233 234 /* add number of tightened bounds to the total number of presolving boundchanges */ 235 if( ntightened > 0 ) 236 { 237 *nchgbds += ntightened; 238 data->ntightened += ntightened; 239 data->ntightenedint += ntightened; 240 if( *result != SCIP_CUTOFF ) 241 *result = SCIP_SUCCESS; 242 } 243 244 SCIPpropSetFreq(prop, -1); 245 246 return SCIP_OKAY; 247 } 248 249 /** execution method of propagator */ 250 static 251 SCIP_DECL_PROPEXEC(propExecSync) 252 { /*lint --e{715}*/ 253 SCIP_PROPDATA* data; 254 int ntightened; 255 int ntightenedint; 256 257 assert(prop != NULL); 258 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 259 260 *result = SCIP_DIDNOTRUN; 261 262 if( SCIPinProbing(scip) ) 263 return SCIP_OKAY; 264 265 data = SCIPpropGetData(prop); 266 assert(data != NULL); 267 268 SCIP_CALL( applyBoundChanges(scip, data, result, &ntightened, &ntightenedint) ); 269 270 if( ntightened > 0 ) 271 { 272 data->ntightened += ntightened; 273 data->ntightenedint += ntightenedint; 274 if( *result != SCIP_CUTOFF ) 275 *result = SCIP_REDUCEDDOM; 276 } 277 278 SCIPpropSetFreq(prop, -1); 279 280 return SCIP_OKAY; 281 } 282 283 /* 284 * propagator specific interface methods 285 */ 286 287 /** creates the sync propagator and includes it in SCIP */ 288 SCIP_RETCODE SCIPincludePropSync( 289 SCIP* scip /**< SCIP data structure */ 290 ) 291 { 292 SCIP_PROPDATA* propdata; 293 SCIP_PROP* prop; 294 295 /* create xyz propagator data */ 296 propdata = NULL; 297 /* create propagator specific data */ 298 SCIP_CALL( SCIPallocMemory(scip, &propdata) ); 299 300 prop = NULL; 301 302 /* include propagator */ 303 304 /* use SCIPincludePropBasic() plus setter functions if you want to set callbacks one-by-one and your code should 305 * compile independent of new callbacks being added in future SCIP versions 306 */ 307 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 308 propExecSync, propdata) ); 309 310 assert(prop != NULL); 311 312 /* set optional callbacks via setter functions */ 313 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSync) ); 314 SCIP_CALL( SCIPsetPropInit(scip, prop, propInitSync) ); 315 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitSync) ); 316 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSync, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) ); 317 318 return SCIP_OKAY; 319 } 320 321 322 /** adds a boundchange to the sync propagator */ 323 SCIP_RETCODE SCIPpropSyncAddBndchg( 324 SCIP* scip, /**< SCIP data structure */ 325 SCIP_PROP* prop, /**< sync propagator */ 326 SCIP_VAR* var, /**< variable for bound */ 327 SCIP_Real val, /**< value of bound */ 328 SCIP_BOUNDTYPE bndtype /**< type of bound */ 329 ) 330 { 331 SCIP_PROPDATA* data; 332 333 assert(prop != NULL); 334 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 335 336 data = SCIPpropGetData(prop); 337 assert(data != NULL); 338 339 if( data->nbnds + 1 > data->bndsize ) 340 { 341 int newsize; 342 newsize = SCIPcalcMemGrowSize(scip, data->nbnds+1); 343 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndvar, data->bndsize, newsize) ); 344 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndval, data->bndsize, newsize) ); 345 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->bndtype, data->bndsize, newsize) ); 346 data->bndsize = newsize; 347 } 348 349 data->bndvar[data->nbnds] = var; 350 data->bndval[data->nbnds] = val; 351 data->bndtype[data->nbnds] = bndtype; 352 353 if( data->nbnds == 0 ) 354 { 355 SCIPpropSetFreq(prop, 1); 356 } 357 ++data->nbnds; 358 359 return SCIP_OKAY; 360 } 361 362 /** gives the total number of tightened bounds found by the sync propagator */ 363 SCIP_Longint SCIPpropSyncGetNTightenedBnds( 364 SCIP_PROP* prop /**< sync propagator */ 365 ) 366 { 367 SCIP_PROPDATA* data; 368 369 assert(prop != NULL); 370 371 data = SCIPpropGetData(prop); 372 assert(data != NULL); 373 374 return data->ntightened; 375 } 376 377 /** gives the total number of tightened bounds for integer variables found by the sync propagator */ 378 SCIP_Longint SCIPpropSyncGetNTightenedIntBnds( 379 SCIP_PROP* prop /**< sync propagator */ 380 ) 381 { 382 SCIP_PROPDATA* data; 383 384 assert(prop != NULL); 385 386 data = SCIPpropGetData(prop); 387 assert(data != NULL); 388 389 return data->ntightenedint; 390 } 391