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_genvbounds.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief generalized variable bounds propagator 28 * @author Stefan Weltge 29 * @author Ambros Gleixner 30 * @author Benjamin Mueller 31 */ 32 33 /**@todo should we only discard events catched from nodes that are not the current node's ancestors? */ 34 /**@todo improve computation of minactivity */ 35 /**@todo for multaggr vars on left-hand side, create a linear constraint, probably in exitpre */ 36 37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 38 39 #include "blockmemshell/memory.h" 40 #include "scip/cons_linear.h" 41 #include "scip/debug.h" 42 #include "scip/prop_genvbounds.h" 43 #include "scip/pub_event.h" 44 #include "scip/pub_message.h" 45 #include "scip/pub_misc.h" 46 #include "scip/pub_prop.h" 47 #include "scip/pub_var.h" 48 #include "scip/scip_conflict.h" 49 #include "scip/scip_cons.h" 50 #include "scip/scip_datastructures.h" 51 #include "scip/scip_event.h" 52 #include "scip/scip_general.h" 53 #include "scip/scip_mem.h" 54 #include "scip/scip_message.h" 55 #include "scip/scip_numerics.h" 56 #include "scip/scip_param.h" 57 #include "scip/scip_prob.h" 58 #include "scip/scip_probing.h" 59 #include "scip/scip_prop.h" 60 #include "scip/scip_sol.h" 61 #include "scip/scip_solve.h" 62 #include "scip/scip_solvingstats.h" 63 #include "scip/scip_tree.h" 64 #include "scip/scip_var.h" 65 #include <string.h> 66 67 #define PROP_NAME "genvbounds" 68 #define PROP_DESC "generalized variable bounds propagator" 69 #define PROP_TIMING SCIP_PROPTIMING_ALWAYS 70 #define PROP_PRIORITY 3000000 /**< propagator priority */ 71 #define PROP_FREQ 1 /**< propagator frequency */ 72 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators 73 * found reductions? */ 74 #define PROP_PRESOL_PRIORITY -2000000 /**< priority of the presolving method (>= 0: before, < 0: after 75 * constraint handlers); combined with presolvers */ 76 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ 77 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates 78 * in (-1: no limit) */ 79 #define DEFAULT_GLOBAL_PROPAGATION TRUE /**< apply global propagation? */ 80 #define DEFAULT_PROPAGATE_IN_ROOT_NODE TRUE /**< apply genvbounds in root node if no new incumbent was found? */ 81 #define DEFAULT_SORT TRUE /**< sort genvbounds and wait for bound change events? (otherwise all 82 * genvbounds are applied in each node) */ 83 #define DEFAULT_PROPASCONSS FALSE /**< should genvbounds be transformed to (linear) constraints? */ 84 85 #define EVENTHDLR_NAME "genvbounds" 86 #define EVENTHDLR_DESC "event handler for generalized variable bounds propagator" 87 88 89 /* 90 * Data structures 91 */ 92 93 /** GenVBound data */ 94 struct GenVBound 95 { 96 SCIP_VAR** vars; /**< pointers to variables x_j occurring in this generalized variable 97 * bound */ 98 SCIP_VAR* var; /**< pointer to variable x_i */ 99 SCIP_Real* coefs; /**< coefficients a_j of the variables listed in vars */ 100 SCIP_Real constant; /**< constant term in generalized variable bound */ 101 SCIP_Real cutoffcoef; /**< cutoff bound's coefficient */ 102 int coefssize; /**< size of coefs array */ 103 int index; /**< index of this genvbound in genvboundstore array */ 104 int ncoefs; /**< number of nonzero coefficients a_j */ 105 SCIP_BOUNDTYPE boundtype; /**< type of bound provided by the genvbound, SCIP_BOUNDTYPE_LOWER/UPPER 106 * if +/- x_i on left-hand side */ 107 SCIP_Bool relaxonly; /**< contains a relaxation-only variable */ 108 }; 109 typedef struct GenVBound GENVBOUND; 110 111 /** starting indices data structure */ 112 struct SCIP_EventData 113 { 114 SCIP_PROP* prop; /**< pointer to genvbounds propagator */ 115 SCIP_VAR* var; /**< variable */ 116 int* startindices; /**< array to store the first indices of genvbounds in components that are 117 * impacted by a change of this bound */ 118 int* startcomponents; /**< array to store the components corresponding to startindices array */ 119 int nstarts; /**< number of indices stored in startindices array */ 120 int startindicessize; /**< size of the startindices and startcomponents arrays */ 121 }; 122 123 /** propagator data */ 124 struct SCIP_PropData 125 { 126 GENVBOUND** genvboundstore; /**< array to store genvbounds; fast access is provided by hashmaps 127 * lbgenvbounds and ubgenvbounds */ 128 SCIP_EVENTDATA** lbevents; /**< array of lower bound event data */ 129 SCIP_EVENTDATA** ubevents; /**< array of upper bound event data */ 130 SCIP_EVENTHDLR* eventhdlr; /**< genvbounds propagator event handler */ 131 SCIP_HASHMAP* lbgenvbounds; /**< hashmap to provide fast access to lower bound genvbounds in 132 * genvboundstore array */ 133 SCIP_HASHMAP* ubgenvbounds; /**< hashmap to provide fast access to upper bound genvbounds in 134 * genvboundstore array */ 135 SCIP_HASHMAP* lbeventsmap; /**< hashmap to provide fast access to lbevents array */ 136 SCIP_HASHMAP* ubeventsmap; /**< hashmap to provide fast access to ubevents array */ 137 SCIP_HASHMAP* startmap; /**< hashmap to provide fast access to startindices array */ 138 SCIP_PROP* prop; /**< pointer to genvbounds propagator */ 139 SCIP_NODE* lastnodecaught; /**< last node where events for starting indices were caught */ 140 SCIP_VAR* cutoffboundvar; /**< artificial variable representing primal cutoff bound */ 141 int* componentsstart; /**< stores the components starting indices in genvboundstore array; the 142 * entry componentsstart[ncomponents] is equal to ngenvbounds, which 143 * makes it easier to iterate over all components */ 144 int componentsstartsize;/**< size of componentsstart array */ 145 int* startindices; /**< storing indices of components where local propagation should start */ 146 int* startcomponents; /**< components corresponding to indices stored in startindices array */ 147 int startindicessize; /**< size of startindices and startcomponents arrays */ 148 int* gstartindices; /**< storing indices of components where global propagation, i.e., 149 * propagation of an improved primal bound, should start */ 150 int* gstartcomponents; /**< components corresponding to indices stored in gstartindices array */ 151 int gstartindicessize; /**< size of gstartindices and gstartcomponents arrays */ 152 SCIP_Real lastcutoff; /**< cutoff bound's value last time genvbounds propagator was called */ 153 int genvboundstoresize; /**< size of genvboundstore array */ 154 int ngenvbounds; /**< number of genvbounds stored in genvboundstore array */ 155 int ncomponents; /**< number of components in genvboundstore array */ 156 int nindices; /**< number of indices stored in startindices array */ 157 int ngindices; /**< number of indices stored in gstartindices array */ 158 int nlbevents; /**< number of data entries in lbevents array */ 159 int nubevents; /**< number of data entries in ubevents array */ 160 SCIP_Bool issorted; /**< stores wether array genvboundstore is topologically sorted */ 161 SCIP_Bool global; /**< apply global propagation? */ 162 SCIP_Bool propinrootnode; /**< apply genvbounds in root node if no new incumbent was found? */ 163 SCIP_Bool sort; /**< sort genvbounds and wait for bound change events? (otherwise all 164 * genvbounds are applied in each node) */ 165 SCIP_Bool propasconss; /**< should genvbounds be transformed to (linear) constraints? */ 166 }; 167 168 169 /* 170 * Local methods 171 */ 172 173 /** returns correct cutoff bound value */ 174 static 175 SCIP_Real getCutoffboundGenVBound( 176 SCIP* scip /**< SCIP data structure */ 177 ) 178 { 179 assert(scip != NULL); 180 181 SCIPdebugMsg(scip, "cutoff = %.9g (%.9g + %.9g * %.9g)\n", 182 (SCIPgetCutoffbound(scip) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip), 183 SCIPgetCutoffbound(scip), SCIPgetTransObjoffset(scip), SCIPgetTransObjscale(scip)); 184 185 /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving, 186 * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective is 187 * subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the 188 * contribution of the cutoff bound in the generalized variable bound to the original problem as described in 189 * function SCIPgenVBoundAdd() 190 */ 191 return (SCIPgetCutoffbound(scip) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip); 192 } 193 194 /** returns corresponding genvbound in genvboundstore if there is one, NULL otherwise */ 195 static 196 GENVBOUND* getGenVBound( 197 SCIP* scip, /**< SCIP data structure */ 198 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */ 199 SCIP_VAR* var, /**< bounds variable */ 200 SCIP_BOUNDTYPE boundtype /**< bounds type */ 201 ) 202 { 203 SCIP_HASHMAP* hashmap; 204 205 assert(scip != NULL); 206 assert(propdata != NULL); 207 assert(var != NULL); 208 209 hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds; 210 211 return (GENVBOUND*) SCIPhashmapGetImage(hashmap, var); 212 } 213 214 #ifdef SCIP_DEBUG 215 /** prints a genvbound as debug message */ 216 static 217 void printGenVBound( 218 SCIP* scip, /**< SCIP data structure */ 219 GENVBOUND* genvbound /**< genvbound to be printed */ 220 ) 221 { 222 SCIP_Bool first; 223 int i; 224 225 assert(genvbound != NULL); 226 227 if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ) 228 { 229 SCIPdebugMsgPrint(scip, "- "); 230 } 231 232 SCIPdebugMsgPrint(scip, "<%s> >= ", SCIPvarGetName(genvbound->var)); 233 234 first = TRUE; 235 for( i = 0; i < genvbound->ncoefs; i++ ) 236 { 237 if( !first ) 238 { 239 SCIPdebugMsgPrint(scip, " + "); 240 } 241 242 SCIPdebugMsgPrint(scip, "%g * <%s>", genvbound->coefs[i], SCIPvarGetName(genvbound->vars[i])); 243 244 first = FALSE; 245 } 246 247 if( !SCIPisZero(scip, genvbound->cutoffcoef) ) 248 { 249 SCIPdebugMsgPrint(scip, " + %g * cutoff_bound", genvbound->cutoffcoef); 250 } 251 252 if( !SCIPisZero(scip, genvbound->constant) ) 253 { 254 SCIPdebugMsgPrint(scip, " + %g", genvbound->constant); 255 } 256 257 SCIPdebugMsgPrint(scip, "\n"); 258 } 259 #endif 260 261 /** calculates the minactivity of a linear combination of variables stored in an array */ 262 static 263 SCIP_Real getGenVBoundsMinActivity( 264 SCIP* scip, /**< SCIP data structure */ 265 SCIP_VAR** vars, /**< array of variables */ 266 SCIP_Real* coefs, /**< array of coefficients */ 267 int nvars, /**< number of variables */ 268 SCIP_Bool global /**< use global variable bounds? */ 269 ) 270 { 271 SCIP_Real minval; 272 int i; 273 274 assert(scip != NULL); 275 assert(vars != NULL); 276 assert(coefs != NULL); 277 assert(nvars >= 0); 278 279 minval = 0.0; 280 281 for( i = 0; i < nvars; i++ ) 282 { 283 SCIP_Real bound; 284 285 /* get global or local bound */ 286 if( global ) 287 bound = coefs[i] > 0.0 ? SCIPvarGetLbGlobal(vars[i]) : SCIPvarGetUbGlobal(vars[i]); 288 else 289 bound = coefs[i] > 0.0 ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetUbLocal(vars[i]); 290 291 /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */ 292 if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) ) 293 return -SCIPinfinity(scip); 294 295 /* add contribution to minactivity */ 296 minval += coefs[i] * bound; 297 } 298 299 return minval; 300 } 301 302 /** calculates the minactivity of a linear combination of variables stored in the current conflict set */ 303 static 304 SCIP_Real getGenVBoundsMinActivityConflict( 305 SCIP* scip, /**< SCIP data structure */ 306 SCIP_VAR** vars, /**< array of variables */ 307 SCIP_Real* coefs, /**< array of coefficients */ 308 int nvars, /**< number of variables */ 309 SCIP_BDCHGIDX* bdchgidx /**< bound change at which minactivity should be computed; if NULL use local bounds */ 310 ) 311 { 312 SCIP_Real minval; 313 int i; 314 315 assert(scip != NULL); 316 assert(vars != NULL); 317 assert(coefs != NULL); 318 assert(nvars >= 0); 319 320 minval = 0.0; 321 322 for( i = 0; i < nvars; i++ ) 323 { 324 SCIP_Real bound; 325 326 if( coefs[i] > 0.0 ) 327 { 328 /* get bound at current bound change */ 329 bound = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE); 330 331 /* if bdchgidx is NULL, assert that we use local bounds */ 332 assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetLbLocal(vars[i]))); 333 334 /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */ 335 if( bdchgidx != NULL && SCIPgetConflictVarLb(scip, vars[i]) > bound ) 336 bound = SCIPgetConflictVarLb(scip, vars[i]); 337 } 338 else 339 { 340 /* get bound at current bound change */ 341 bound = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE); 342 343 /* if bdchgidx is NULL, assert that we use local bounds */ 344 assert(bdchgidx != NULL || SCIPisEQ(scip, bound, SCIPvarGetUbLocal(vars[i]))); 345 346 /* if bdchgidx is not NULL, use the possibly tighter bound already in the current conflict set */ 347 if( bdchgidx != NULL && SCIPgetConflictVarUb(scip, vars[i]) < bound ) 348 bound = SCIPgetConflictVarUb(scip, vars[i]); 349 } 350 351 /* with infinite bounds we cannot compute a valid minactivity and return minus infinity */ 352 if( SCIPisInfinity(scip, bound) || SCIPisInfinity(scip, -bound) ) 353 return -SCIPinfinity(scip); 354 355 /* add contribution to minactivity */ 356 minval += coefs[i] * bound; 357 } 358 359 return minval; 360 } 361 362 /** returns a valid bound given by a generalized variable bound */ 363 static 364 SCIP_Real getGenVBoundsBound( 365 SCIP* scip, /**< SCIP data structure */ 366 GENVBOUND* genvbound, /**< generalized variable bound */ 367 SCIP_Bool global /**< use global variable bounds? */ 368 ) 369 { 370 SCIP_Real boundval; 371 372 assert(scip != NULL); 373 assert(genvbound != NULL); 374 375 boundval = getGenVBoundsMinActivity(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, global); 376 377 if( SCIPisInfinity(scip, -boundval) ) 378 return (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -SCIPinfinity(scip) : SCIPinfinity(scip); 379 380 if( genvbound->cutoffcoef != 0.0 ) 381 boundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip); 382 383 boundval += genvbound->constant; 384 385 if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ) 386 boundval *= -1.0; 387 388 return boundval; 389 } 390 391 #ifdef WITH_DEBUG_SOLUTION 392 /** checks whether a generalized variable bound violates the debug solution */ 393 static 394 SCIP_RETCODE checkDebugSolutionGenVBound( 395 SCIP* scip, /**< SCIP data structure */ 396 GENVBOUND* genvbound /**< generalized variable bound */ 397 ) 398 { 399 SCIP_SOL* debugsol; 400 SCIP_Real activity; 401 SCIP_Real solval; 402 int i; 403 404 assert(scip != NULL); 405 assert(genvbound != NULL); 406 407 if( !SCIPdebugIsMainscip(scip) ) 408 return SCIP_OKAY; 409 410 /* the genvbound must be valid for all cutoff bounds greater equal the objective value of the debug solution */ 411 SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) ); 412 413 /* check whether a debug solution is available */ 414 if( debugsol == NULL ) 415 return SCIP_OKAY; 416 417 activity = 0.0; 418 for( i = 0; i < genvbound->ncoefs; i++ ) 419 { 420 SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->vars[i], &solval) ); 421 if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID ) 422 activity += genvbound->coefs[i] * solval; 423 else 424 printf("***** debug: ignoring variable with %s value in debug solution\n", 425 solval == SCIP_UNKNOWN ? "unknown" : "invalid"); 426 } 427 428 activity += genvbound->cutoffcoef * 429 (SCIPgetSolTransObj(scip, debugsol) + SCIPgetTransObjoffset(scip)) * SCIPgetTransObjscale(scip); 430 activity += genvbound->constant; 431 432 SCIP_CALL( SCIPdebugGetSolVal(scip, genvbound->var, &solval) ); 433 if( solval != SCIP_UNKNOWN || solval != SCIP_INVALID ) 434 { 435 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ) 436 { 437 SCIP_CALL( SCIPdebugCheckLbGlobal(scip, genvbound->var, activity) ); 438 } 439 else if( genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ) 440 { 441 SCIP_CALL( SCIPdebugCheckUbGlobal(scip, genvbound->var, -activity) ); 442 } 443 } 444 445 return SCIP_OKAY; 446 } 447 #endif 448 449 /** allocate local and global startindices, startcomponents and startmap */ 450 static 451 SCIP_RETCODE createStartingData( 452 SCIP* scip, /**< SCIP data structure */ 453 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 454 ) 455 { 456 assert(scip != NULL); 457 assert(propdata != NULL); 458 459 assert(propdata->startcomponents == NULL); 460 assert(propdata->startindices == NULL); 461 assert(propdata->startmap == NULL); 462 assert(propdata->nindices == -1); 463 464 assert(propdata->gstartindices == NULL); 465 assert(propdata->gstartcomponents == NULL); 466 assert(propdata->ngindices == -1); 467 468 assert(propdata->ngenvbounds >= 1); 469 assert(propdata->ncomponents >= 1); 470 471 SCIPdebugMsg(scip, "create starting data\n"); 472 473 /* allocate memory for arrays */ 474 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startindices), propdata->ncomponents) ); 475 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->startcomponents), propdata->ncomponents) ); 476 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->ncomponents) ); 477 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->ncomponents) ); 478 propdata->startindicessize = propdata->ncomponents; 479 propdata->gstartindicessize = propdata->ncomponents; 480 481 /* create hashmap */ 482 SCIP_CALL( SCIPhashmapCreate(&(propdata->startmap), SCIPblkmem(scip), propdata->ncomponents) ); 483 484 propdata->nindices = 0; 485 propdata->ngindices = 0; 486 487 return SCIP_OKAY; 488 } 489 490 /** free local and global startindices, startcomponents and startmap */ 491 static 492 SCIP_RETCODE freeStartingData( 493 SCIP* scip, /**< SCIP data structure */ 494 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 495 ) 496 { 497 assert(scip != NULL); 498 assert(propdata != NULL); 499 500 SCIPdebugMsg(scip, "free starting data\n"); 501 502 if( propdata->startcomponents != NULL ) 503 { 504 assert(propdata->startindices != NULL); 505 assert(propdata->startmap != NULL); 506 assert(propdata->nindices >= 0); 507 508 SCIPfreeBlockMemoryArray(scip, &(propdata->startindices), propdata->startindicessize); 509 SCIPfreeBlockMemoryArray(scip, &(propdata->startcomponents), propdata->startindicessize); 510 propdata->startindicessize = 0; 511 SCIPhashmapFree(&(propdata->startmap)); 512 propdata->nindices = -1; 513 514 assert(propdata->gstartindices != NULL); 515 assert(propdata->gstartcomponents != NULL); 516 assert(propdata->ngindices >= 0); 517 518 SCIPfreeBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize); 519 SCIPfreeBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize); 520 propdata->gstartindicessize = 0; 521 propdata->ngindices = -1; 522 } 523 524 assert(propdata->startcomponents == NULL); 525 assert(propdata->startindices == NULL); 526 assert(propdata->startmap == NULL); 527 assert(propdata->nindices == -1); 528 529 assert(propdata->gstartindices == NULL); 530 assert(propdata->gstartcomponents == NULL); 531 assert(propdata->ngindices == -1); 532 533 return SCIP_OKAY; 534 } 535 536 static 537 SCIP_RETCODE fillGlobalStartingData( 538 SCIP* scip, /**< SCIP data structure */ 539 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 540 ) 541 { 542 int i; 543 544 assert(scip != NULL); 545 assert(propdata != NULL); 546 547 assert(propdata->gstartindices != NULL); 548 assert(propdata->gstartcomponents != NULL); 549 assert(propdata->ngindices == 0); 550 551 SCIPdebugMsg(scip, "fill global starting data\n"); 552 553 for( i = 0; i < propdata->ncomponents; i++ ) 554 { 555 int j; 556 557 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/ 558 { 559 assert(j < propdata->ngenvbounds); 560 561 if( !SCIPisZero(scip, propdata->genvboundstore[j]->cutoffcoef) ) 562 { 563 assert(SCIPisNegative(scip, propdata->genvboundstore[j]->cutoffcoef)); 564 565 propdata->gstartcomponents[propdata->ngindices] = i; 566 propdata->gstartindices[propdata->ngindices] = j; 567 568 /* go to next component */ 569 propdata->ngindices++; 570 break; 571 } 572 } 573 } 574 575 /* resize arrays */ 576 if( propdata->gstartindicessize != propdata->ngindices ) 577 { 578 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartindices), propdata->gstartindicessize, \ 579 propdata->ngindices) ); 580 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->gstartcomponents), propdata->gstartindicessize, \ 581 propdata->ngindices) ); 582 propdata->gstartindicessize = propdata->ngindices; 583 } 584 585 return SCIP_OKAY; 586 } 587 588 589 /** resets local starting data */ 590 static 591 SCIP_RETCODE resetLocalStartingData( 592 SCIP* scip, /**< SCIP data structure */ 593 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 594 ) 595 { 596 assert(scip != NULL); 597 assert(propdata != NULL); 598 assert(propdata->startcomponents != NULL); 599 assert(propdata->startindices != NULL); 600 assert(propdata->startmap != NULL); 601 assert(propdata->nindices >= 0); 602 603 SCIP_CALL( SCIPhashmapRemoveAll(propdata->startmap) ); 604 propdata->nindices = 0; 605 606 return SCIP_OKAY; 607 } 608 609 /** frees sorted components data */ 610 static 611 SCIP_RETCODE freeComponentsData( 612 SCIP* scip, /**< SCIP data structure */ 613 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 614 ) 615 { 616 assert(scip != NULL); 617 assert(propdata != NULL); 618 619 SCIPdebugMsg(scip, "free components data\n"); 620 621 if( propdata->componentsstart != NULL ) 622 { 623 assert(propdata->ncomponents > 0); 624 625 SCIPfreeBlockMemoryArray(scip, &(propdata->componentsstart), propdata->componentsstartsize); 626 propdata->componentsstartsize = 0; 627 propdata->ncomponents = -1; 628 } 629 630 assert(propdata->componentsstart == NULL); 631 assert(propdata->ncomponents == -1); 632 633 return SCIP_OKAY; 634 } 635 636 /** frees memory allocated for a generalized variable bound */ 637 static 638 SCIP_RETCODE freeGenVBound( 639 SCIP* scip, 640 GENVBOUND* genvbound 641 ) 642 { 643 int i; 644 645 assert(scip != NULL); 646 assert(genvbound != NULL); 647 assert(genvbound->coefs != NULL); 648 assert(genvbound->vars != NULL); 649 assert(genvbound->var != NULL); 650 651 /* release variables */ 652 for( i = 0; i < genvbound->ncoefs; ++i ) 653 { 654 assert(genvbound->vars[i] != NULL); 655 SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) ); 656 } 657 SCIP_CALL( SCIPreleaseVar(scip, &genvbound->var) ); 658 659 /* free memory */ 660 SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize); 661 SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize); 662 SCIPfreeBlockMemory(scip, &genvbound); 663 664 return SCIP_OKAY; 665 } 666 667 /** helper function to release all genvbounds */ 668 static 669 SCIP_RETCODE freeGenVBounds( 670 SCIP* scip, 671 SCIP_PROPDATA* propdata 672 ) 673 { 674 int i; 675 676 assert(scip != NULL); 677 assert(propdata != NULL); 678 679 if( propdata->genvboundstore != NULL ) 680 { 681 /* free genvbounds */ 682 for( i = propdata->ngenvbounds - 1; i >= 0; i-- ) 683 { 684 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) ); 685 } 686 687 /* free genvboundstore hashmaps */ 688 SCIPhashmapFree(&(propdata->lbgenvbounds)); 689 SCIPhashmapFree(&(propdata->ubgenvbounds)); 690 691 /* free genvboundstore array */ 692 SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize); 693 694 /* set the number of genvbounds to zero */ 695 propdata->ngenvbounds = 0; 696 697 /* free componentsstart array */ 698 SCIP_CALL( freeComponentsData(scip, propdata) ); 699 700 /* free starting indices data */ 701 SCIP_CALL( freeStartingData(scip, propdata) ); 702 703 /* release the cutoffboundvar and undo the locks */ 704 if( propdata->cutoffboundvar != NULL ) 705 { 706 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, -1, -1) ); 707 SCIP_CALL( SCIPreleaseVar(scip, &(propdata->cutoffboundvar)) ); 708 propdata->cutoffboundvar = NULL; 709 SCIPdebugMsg(scip, "release cutoffboundvar!\n"); 710 } 711 } 712 713 return SCIP_OKAY; 714 } 715 716 /** helper function to release relax-only genvbounds */ 717 static 718 SCIP_RETCODE freeGenVBoundsRelaxOnly( 719 SCIP* scip, 720 SCIP_PROPDATA* propdata 721 ) 722 { 723 SCIP_Bool freedgenvbound; 724 int i; 725 726 assert(scip != NULL); 727 assert(propdata != NULL); 728 729 if( propdata->genvboundstore == NULL ) 730 return SCIP_OKAY; 731 732 /* free genvbounds */ 733 freedgenvbound = FALSE; 734 for( i = 0 ; i < propdata->ngenvbounds; ) 735 { 736 if( propdata->genvboundstore[i]->relaxonly ) 737 { 738 SCIP_CALL( SCIPhashmapRemove(propdata->genvboundstore[i]->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds, 739 propdata->genvboundstore[i]->var) ); 740 741 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) ); 742 if( i != propdata->ngenvbounds-1 ) 743 { 744 propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds-1]; 745 propdata->genvboundstore[i]->index = i; 746 } 747 --propdata->ngenvbounds; 748 749 propdata->issorted = FALSE; 750 freedgenvbound = TRUE; 751 } 752 else 753 ++i; 754 } 755 756 if( freedgenvbound ) 757 { 758 /* free componentsstart array */ 759 SCIP_CALL( freeComponentsData(scip, propdata) ); 760 761 /* free starting indices data */ 762 SCIP_CALL( freeStartingData(scip, propdata) ); 763 } 764 765 return SCIP_OKAY; 766 } 767 768 /** resolves propagation of lower bound on +/- left-hand side variable of a generalized variable bound */ 769 static 770 SCIP_RETCODE resolveGenVBoundPropagation( 771 SCIP* scip, /**< SCIP data structure */ 772 GENVBOUND* genvbound, /**< genvbound data structure */ 773 SCIP_BDCHGIDX* bdchgidx, /**< the index of the bound change, representing the point of time where the change took place */ 774 SCIP_Real* boundval, /**< pointer to lower bound value on +/- left-hand side variable */ 775 SCIP_Bool* success /**< was the explanation succesful? */ 776 ) 777 { 778 SCIP_VAR* lhsvar; 779 SCIP_VAR** vars; 780 SCIP_Real minactivity; 781 SCIP_Real tmpboundval; 782 SCIP_Real slack; 783 int nvars; 784 int i; 785 786 assert(scip != NULL); 787 assert(genvbound != NULL); 788 assert(boundval != NULL); 789 assert(success != NULL); 790 791 *success = FALSE; 792 793 /* get left-hand side variable */ 794 lhsvar = genvbound->var; 795 assert(lhsvar != NULL); 796 797 /* get right-hand side variables */ 798 vars = genvbound->vars; 799 nvars = genvbound->ncoefs; 800 assert(vars != NULL); 801 802 /* if only the primal bound participates in the propagation, it is globally valid and should not be analyzed */ 803 assert(nvars > 0); 804 805 /* when resolving a propagation, bdchgidx is not NULL and boundval should be the bound change performed for the 806 * left-hand side variable 807 */ 808 assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER || SCIPisEQ(scip, 809 SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, SCIPgetVarLbAtIndex(scip, lhsvar, bdchgidx, TRUE))); 810 assert(bdchgidx == NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER || SCIPisEQ(scip, 811 SCIPvarIsIntegral(genvbound->var) ? SCIPfeasCeil(scip, *boundval) : *boundval, -SCIPgetVarUbAtIndex(scip, lhsvar, bdchgidx, TRUE))); 812 813 /* when creating an initial conflict, bdchgidx is NULL and +/-boundval must exceed the upper/lower bound of the 814 * left-hand side variable 815 */ 816 assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_LOWER 817 || SCIPisGT(scip, *boundval, SCIPvarGetUbLocal(lhsvar))); 818 assert(bdchgidx != NULL || genvbound->boundtype != SCIP_BOUNDTYPE_UPPER 819 || SCIPisGT(scip, *boundval, -SCIPvarGetLbLocal(lhsvar))); 820 821 SCIPdebugMsg(scip, "resolving genvbound propagation: lhs=%s<%s> >= boundval=%.15g\n", 822 genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? "+" : "-", SCIPvarGetName(lhsvar), *boundval); 823 824 /* subtract constant terms from bound value */ 825 tmpboundval = *boundval; 826 tmpboundval -= genvbound->cutoffcoef * getCutoffboundGenVBound(scip); 827 tmpboundval -= genvbound->constant; 828 829 SCIPdebugMsg(scip, "subtracting constant terms gives boundval=%.15g\n", tmpboundval); 830 831 /* compute minimal activity; if bdchgidx is NULL, we create the initial conflict and use local bounds */ 832 minactivity = getGenVBoundsMinActivityConflict(scip, genvbound->vars, genvbound->coefs, genvbound->ncoefs, bdchgidx); 833 834 SCIPdebugMsg(scip, "minactivity of right-hand side is minactivity=%.15g\n", minactivity); 835 836 /* a genvbound might have been replaced since the propagation took place, hence we have to check that the current 837 * genvbound can explain the propagation at the given bound change index; note that by now, with smaller cutoff 838 * bound, we might even perform a stronger propagation 839 */ 840 if( SCIPisLT(scip, minactivity, tmpboundval) ) 841 { 842 SCIPdebugMsg(scip, "minactivity is too small to explain propagation; was genvbound replaced?\n"); 843 return SCIP_OKAY; 844 } 845 846 /* if bdchgidx is NULL, i.e., we create the initial conflict, we should be able to explain the bound change */ 847 assert(SCIPisGE(scip, minactivity, tmpboundval)); 848 849 slack = MAX(minactivity - tmpboundval, 0.0); 850 851 SCIPdebugMsg(scip, "slack=%.15g\n", slack); 852 853 /* add variables on the right-hand side as reasons for propagation */ 854 for( i = 0; i < nvars; i++ ) 855 { 856 assert(vars[i] != NULL); 857 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE))); 858 assert(SCIPisEQ(scip, SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE))); 859 860 /* coefficient is positive */ 861 if( genvbound->coefs[i] > 0.0 ) 862 { 863 SCIP_Real lbatindex; 864 SCIP_Real conflictlb; 865 866 /* get bound at current bound change */ 867 lbatindex = SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE); 868 869 /* get bound already enforced by conflict set */ 870 conflictlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]); 871 assert(SCIPisGE(scip, conflictlb, SCIPvarGetLbGlobal(genvbound->vars[i]))); 872 873 SCIPdebugMsg(scip, "lower bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n", 874 SCIPvarGetName(genvbound->vars[i]), i, conflictlb, lbatindex); 875 876 /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the 877 * tighest bound already when computing the initial minactivity, the slack is already correct 878 */ 879 if( SCIPisLE(scip, lbatindex, conflictlb) ) 880 { 881 SCIPdebugMsg(scip, "skipping lower bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n", 882 SCIPvarGetName(genvbound->vars[i]), i); 883 } 884 else 885 { 886 SCIP_Real relaxedlb; 887 888 /* compute relaxed bound that would suffice to explain the bound change */ 889 relaxedlb = lbatindex - (slack / genvbound->coefs[i]); 890 assert(relaxedlb <= lbatindex); 891 892 /* add variable to conflict set */ 893 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->vars[i], bdchgidx, relaxedlb ) ); 894 895 /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictLbRelaxed(), 896 * it should be between conflictlb and lbatindex 897 */ 898 relaxedlb = SCIPgetConflictVarLb(scip, genvbound->vars[i]); 899 assert(SCIPisGE(scip, relaxedlb, conflictlb)); 900 assert(SCIPisLE(scip, relaxedlb, lbatindex)); 901 902 /* update slack and ensure that its nonegative */ 903 slack -= genvbound->coefs[i] * (lbatindex - relaxedlb); 904 slack = MAX(slack, 0.0); 905 906 SCIPdebugMsg(scip, "added lower bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n", 907 SCIPvarGetName(genvbound->vars[i]), i, slack); 908 } 909 } 910 /* coefficient is negative */ 911 else 912 { 913 SCIP_Real ubatindex; 914 SCIP_Real conflictub; 915 916 /* get bound at current bound change */ 917 ubatindex = SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE); 918 919 /* get bound already enforced by conflict set */ 920 conflictub = SCIPgetConflictVarUb(scip, genvbound->vars[i]); 921 assert(SCIPisLE(scip, conflictub, SCIPvarGetUbGlobal(genvbound->vars[i]))); 922 923 SCIPdebugMsg(scip, "upper bound of variable <%s> (genvbound->vars[%d]) in conflict set / at index is %.15g / %.15g\n", 924 SCIPvarGetName(genvbound->vars[i]), i, conflictub, ubatindex); 925 926 /* if bound is already enforced by conflict set we do not need to add the bound change; since we used the 927 * tighest bound already when computing the initial minactivity, the slack is already correct 928 */ 929 if( SCIPisGE(scip, ubatindex, conflictub) ) 930 { 931 SCIPdebugMsg(scip, "skipping upper bound of variable <%s> (genvbound->vars[%d]) already enforced in conflict set\n", 932 SCIPvarGetName(genvbound->vars[i]), i); 933 } 934 else 935 { 936 SCIP_Real relaxedub; 937 938 /* compute relaxed bound that would suffice to explain the bound change */ 939 relaxedub = ubatindex - (slack / genvbound->coefs[i]); 940 assert(relaxedub >= ubatindex); 941 942 /* add variable to conflict set */ 943 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->vars[i], bdchgidx, relaxedub ) ); 944 945 /* get new bound of variable in conflict set; after possible bound widening in SCIPaddConflictUbRelaxed(), 946 * it should be between conflictub and ubatindex 947 */ 948 relaxedub = SCIPgetConflictVarUb(scip, genvbound->vars[i]); 949 assert(SCIPisLE(scip, relaxedub, conflictub)); 950 assert(SCIPisGE(scip, relaxedub, ubatindex)); 951 952 /* update slack and ensure that its nonegative */ 953 slack -= genvbound->coefs[i] * (ubatindex - relaxedub); 954 slack = MAX(slack, 0.0); 955 956 SCIPdebugMsg(scip, "added upper bound of variable <%s> (genvbound->vars[%d]); new slack=%.15g\n", 957 SCIPvarGetName(genvbound->vars[i]), i, slack); 958 } 959 } 960 } 961 962 /* if slack is positive, return increased boundval */ 963 if( SCIPisPositive(scip, slack) ) 964 tmpboundval += slack; 965 966 /* add constant terms again */ 967 tmpboundval += genvbound->cutoffcoef * getCutoffboundGenVBound(scip); 968 tmpboundval += genvbound->constant; 969 970 /* boundval should not have been decreased; if this happened nevertheless, maybe due to numerical errors, we quit 971 * without success 972 */ 973 if( SCIPisLT(scip, tmpboundval, *boundval) ) 974 { 975 SCIPdebugMsg(scip, "boundval was reduced from %.15g to %.15g; propagation not resolved\n", *boundval, tmpboundval); 976 return SCIP_OKAY; 977 } 978 979 /* return widened boundval */ 980 *boundval = tmpboundval; 981 *success = TRUE; 982 983 return SCIP_OKAY; 984 } 985 986 /** create initial conflict */ 987 static 988 SCIP_RETCODE analyzeGenVBoundConflict( 989 SCIP* scip, /**< SCIP data structure */ 990 GENVBOUND* genvbound /**< genvbound data structure */ 991 ) 992 { 993 SCIP_Bool success; 994 995 assert(scip != NULL); 996 assert(genvbound != NULL); 997 998 /* check if conflict analysis is applicable */ 999 if( !SCIPisConflictAnalysisApplicable(scip) ) 1000 return SCIP_OKAY; 1001 1002 /* initialize conflict analysis */ 1003 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, !SCIPisInfinity(scip, REALABS(SCIPgetCutoffbound(scip)))) ); 1004 1005 /* left-hand side variable >= ... */ 1006 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ) 1007 { 1008 SCIP_Real infeasthreshold; 1009 SCIP_Real bound; 1010 1011 /* get minimal right-hand side bound that leads to infeasibility; first try with a factor of 2 for robustness */ 1012 bound = REALABS(SCIPvarGetUbLocal(genvbound->var)); 1013 infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip); 1014 bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold; 1015 1016 /* add right-hand side variables that force the lower bound of the left-hand side variable above its upper bound 1017 * to conflict set 1018 */ 1019 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) ); 1020 assert(!success || SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var))); 1021 1022 /* if infeasibility cannot be proven with the tighter bound, try with actual bound */ 1023 if( !success ) 1024 { 1025 bound = REALABS(SCIPvarGetUbLocal(genvbound->var)); 1026 infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip); 1027 bound = SCIPvarGetUbLocal(genvbound->var) + infeasthreshold; 1028 1029 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) ); 1030 success = success && SCIPisFeasGT(scip, bound, SCIPvarGetUbLocal(genvbound->var)); 1031 } 1032 1033 /* compute upper bound on left-hand side variable that leads to infeasibility */ 1034 bound -= infeasthreshold; 1035 success = success && SCIPisGE(scip, bound, SCIPvarGetUbLocal(genvbound->var)); 1036 1037 /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */ 1038 if( !success ) 1039 { 1040 SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n"); 1041 return SCIP_OKAY; 1042 } 1043 1044 /* if bound is already enforced by conflict set we do not have to add it */ 1045 if( SCIPisGE(scip, bound, SCIPgetConflictVarUb(scip, genvbound->var)) ) 1046 { 1047 SCIPdebugMsg(scip, "skipping upper bound of left-hand side variable <%s> already enforced in conflict set\n", 1048 SCIPvarGetName(genvbound->var)); 1049 } 1050 else 1051 { 1052 SCIPdebugMsg(scip, "adding upper bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var)); 1053 1054 SCIP_CALL( SCIPaddConflictRelaxedUb(scip, genvbound->var, NULL, bound) ); 1055 } 1056 } 1057 /* left-hand side variable <= ..., i.e., - left-hand side variable >= ... */ 1058 else 1059 { 1060 SCIP_Real infeasthreshold; 1061 SCIP_Real bound; 1062 1063 /* get minimal right-hand side bound that leads to infeasibility; try with a factor of 2 first for robustness */ 1064 bound = REALABS(SCIPvarGetLbLocal(genvbound->var)); 1065 infeasthreshold = MAX(bound, 1.0) * 2 * SCIPfeastol(scip); 1066 bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold; 1067 1068 /* add right-hand side variables that force the upper bound of the left-hand side variable below its lower bound 1069 * to conflict set 1070 */ 1071 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) ); 1072 assert(!success || SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var))); 1073 1074 /* if infeasibility cannot be proven with the tighter bound, try with actual bound */ 1075 if( !success ) 1076 { 1077 bound = REALABS(SCIPvarGetLbLocal(genvbound->var)); 1078 infeasthreshold = MAX(bound, 1.0) * SCIPfeastol(scip); 1079 bound = -SCIPvarGetLbLocal(genvbound->var) + infeasthreshold; 1080 1081 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, NULL, &bound, &success) ); 1082 success = success && SCIPisFeasLT(scip, -bound, SCIPvarGetLbLocal(genvbound->var)); 1083 } 1084 1085 /* compute lower bound on left-hand side variable that leads to infeasibility */ 1086 bound = -bound + infeasthreshold; 1087 success = success && SCIPisLE(scip, bound, SCIPvarGetLbLocal(genvbound->var)); 1088 1089 /* initial reason could not be constructed, maybe due to numerics; do not apply conflict analysis */ 1090 if( !success ) 1091 { 1092 SCIPdebugMsg(scip, "strange: could not create initial reason to start conflict analysis\n"); 1093 return SCIP_OKAY; 1094 } 1095 1096 /* if bound is already enforced by conflict set we do not have to add it */ 1097 if( SCIPisLE(scip, bound, SCIPgetConflictVarLb(scip, genvbound->var)) ) 1098 { 1099 SCIPdebugMsg(scip, "skipping lower bound of left-hand side variable <%s> already enforced in conflict set\n", 1100 SCIPvarGetName(genvbound->var)); 1101 } 1102 else 1103 { 1104 SCIPdebugMsg(scip, "adding lower bound of left-hand side variable <%s>\n", SCIPvarGetName(genvbound->var)); 1105 1106 SCIP_CALL( SCIPaddConflictRelaxedLb(scip, genvbound->var, NULL, bound) ); 1107 } 1108 } 1109 1110 /* analyze the conflict */ 1111 SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) ); 1112 1113 return SCIP_OKAY; 1114 } 1115 1116 /** apply propagation for one generalized variable bound; also if the left-hand side variable is locally fixed, we 1117 * compute the right-hand side minactivity to possibly detect infeasibility 1118 */ 1119 static 1120 SCIP_RETCODE applyGenVBound( 1121 SCIP* scip, /**< SCIP data structure */ 1122 SCIP_PROP* prop, /**< genvbounds propagator */ 1123 GENVBOUND* genvbound, /**< genvbound data structure */ 1124 SCIP_Bool global, /**< apply global bound changes? (global: true, local: false)*/ 1125 SCIP_RESULT* result, /**< result pointer */ 1126 int* nchgbds /**< counter to increment if bound was tightened */ 1127 ) 1128 { 1129 SCIP_Real boundval; 1130 SCIP_Bool infeas; 1131 SCIP_Bool tightened; 1132 1133 assert(scip != NULL); 1134 assert(genvbound != NULL); 1135 assert(genvbound->var != NULL); 1136 assert(SCIPvarGetStatus(genvbound->var) != SCIP_VARSTATUS_MULTAGGR); 1137 assert(result != NULL); 1138 assert(*result != SCIP_DIDNOTRUN); 1139 1140 /* get bound value provided by genvbound */ 1141 boundval = getGenVBoundsBound(scip, genvbound, global); 1142 1143 if( SCIPisInfinity(scip, REALABS(boundval)) ) 1144 return SCIP_OKAY; 1145 1146 #ifdef SCIP_DEBUG 1147 { 1148 SCIP_Real lb; 1149 SCIP_Real ub; 1150 SCIP_Real new_lb; 1151 SCIP_Real new_ub; 1152 1153 lb = global ? SCIPvarGetLbGlobal(genvbound->var) : SCIPvarGetLbLocal(genvbound->var); 1154 ub = global ? SCIPvarGetUbGlobal(genvbound->var) : SCIPvarGetUbLocal(genvbound->var); 1155 new_lb = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? boundval : lb; 1156 new_ub = genvbound->boundtype == SCIP_BOUNDTYPE_UPPER ? boundval : ub; 1157 1158 SCIPdebugMsg(scip, " %s genvbound propagation for <%s>\n", global ? 1159 "global" : "local", SCIPvarGetName(genvbound->var)); 1160 SCIPdebugMsg(scip, " genvbound: "); 1161 printGenVBound(scip, genvbound); 1162 SCIPdebugMsg(scip, " [%.15g,%.15g] -> [%.15g,%.15g]\n", lb, ub, new_lb, new_ub); 1163 } 1164 #endif 1165 1166 /* tighten bound globally */ 1167 if( global || genvbound->ncoefs <= 0 ) 1168 { 1169 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ) 1170 { 1171 SCIP_CALL( SCIPtightenVarLbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) ); 1172 } 1173 else 1174 { 1175 SCIP_CALL( SCIPtightenVarUbGlobal(scip, genvbound->var, boundval, FALSE, &infeas, &tightened) ); 1176 } 1177 } 1178 /* tighten bound locally and start conflict analysis in case of infeasibility; as inferinfo we pass the index of the 1179 * genvbound that was used for propagation 1180 */ 1181 else 1182 { 1183 if( genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ) 1184 { 1185 SCIP_CALL( SCIPinferVarLbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) ); 1186 1187 /* initialize conflict analysis if infeasible */ 1188 if( infeas ) 1189 { 1190 SCIPdebugMsg(scip, " -> lower bound tightening on variable <%s> led to infeasibility\n", 1191 SCIPvarGetName(genvbound->var)); 1192 1193 SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) ); 1194 } 1195 } 1196 else 1197 { 1198 SCIP_CALL( SCIPinferVarUbProp(scip, genvbound->var, boundval, prop, genvbound->index, FALSE, &infeas, &tightened) ); 1199 1200 /* initialize conflict analysis if infeasible */ 1201 if( infeas ) 1202 { 1203 SCIPdebugMsg(scip, " -> upper bound tightening on variable <%s> led to infeasibility\n", 1204 SCIPvarGetName(genvbound->var)); 1205 1206 SCIP_CALL( analyzeGenVBoundConflict(scip, genvbound) ); 1207 } 1208 } 1209 } 1210 1211 /* handle result */ 1212 if( infeas ) 1213 { 1214 *result = SCIP_CUTOFF; 1215 SCIPdebugMsg(scip, " cutoff!\n"); 1216 } 1217 else if( tightened ) 1218 { 1219 *result = SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING ? SCIP_SUCCESS : SCIP_REDUCEDDOM; 1220 if( nchgbds != NULL ) 1221 ++(*nchgbds); 1222 SCIPdebugMsg(scip, " tightened!\n"); 1223 } 1224 1225 return SCIP_OKAY; 1226 } 1227 1228 #ifdef SCIP_DEBUG 1229 /** prints event data as debug message */ 1230 static 1231 void printEventData( 1232 SCIP_EVENTDATA* eventdata, 1233 SCIP_BOUNDTYPE boundtype 1234 ) 1235 { 1236 int i; 1237 1238 SCIPdebugMessage("event data: %s bound of <%s> tightened ==> start propagating at ", 1239 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(eventdata->var)); 1240 1241 /* if there is eventdata it should contain at least one starting index */ 1242 assert(eventdata->nstarts > 0); 1243 1244 for( i = 0; i < eventdata->nstarts; i++ ) 1245 { 1246 SCIPdebugPrintf("(component %d, index %d) ", eventdata->startcomponents[i], eventdata->startindices[i]); 1247 } 1248 SCIPdebugPrintf("\n"); 1249 } 1250 #endif 1251 1252 /** frees event data */ 1253 static 1254 SCIP_RETCODE freeEventData( 1255 SCIP* scip, /**< SCIP data structure */ 1256 SCIP_EVENTDATA** eventdata /**< event data to be freed */ 1257 ) 1258 { 1259 assert(scip != NULL); 1260 assert(eventdata != NULL); 1261 assert(*eventdata != NULL); 1262 1263 SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startcomponents), (*eventdata)->startindicessize); 1264 SCIPfreeBlockMemoryArray(scip, &((*eventdata)->startindices), (*eventdata)->startindicessize); 1265 1266 (*eventdata)->startindicessize = 0; 1267 (*eventdata)->nstarts = -1; 1268 (*eventdata)->var = NULL; 1269 (*eventdata)->prop = NULL; 1270 1271 SCIPfreeBlockMemory(scip, eventdata); 1272 1273 return SCIP_OKAY; 1274 } 1275 1276 /** frees all eventdata stored */ 1277 static 1278 SCIP_RETCODE freeAllEventData( 1279 SCIP* scip, /**< SCIP data structure */ 1280 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 1281 ) 1282 { 1283 int i; 1284 1285 assert(scip != NULL); 1286 assert(propdata != NULL); 1287 1288 if( propdata->lbevents != NULL ) 1289 { 1290 assert(propdata->ubevents != NULL); 1291 assert(propdata->lbeventsmap != NULL); 1292 assert(propdata->ubeventsmap != NULL); 1293 1294 SCIPhashmapFree(&(propdata->lbeventsmap)); 1295 SCIPhashmapFree(&(propdata->ubeventsmap)); 1296 1297 for( i = propdata->nlbevents - 1; i >= 0; i-- ) 1298 { 1299 SCIP_CALL( freeEventData(scip, &(propdata->lbevents[i])) ); 1300 } 1301 1302 for( i = propdata->nubevents - 1; i >= 0; i-- ) 1303 { 1304 SCIP_CALL( freeEventData(scip, &(propdata->ubevents[i])) ); 1305 } 1306 1307 SCIPfreeBlockMemoryArray(scip, &(propdata->ubevents), propdata->nubevents); 1308 SCIPfreeBlockMemoryArray(scip, &(propdata->lbevents), propdata->nlbevents); 1309 propdata->nlbevents = -1; 1310 propdata->nubevents = -1; 1311 } 1312 1313 assert(propdata->lbevents == NULL); 1314 assert(propdata->ubevents == NULL); 1315 assert(propdata->lbeventsmap == NULL); 1316 assert(propdata->ubeventsmap == NULL); 1317 assert(propdata->nlbevents == -1); 1318 assert(propdata->nubevents == -1); 1319 1320 return SCIP_OKAY; 1321 } 1322 1323 /** drops all events caught by genvbounds propagator and frees their data */ 1324 static 1325 SCIP_RETCODE dropAndFreeEvents( 1326 SCIP* scip, /**< SCIP data structure */ 1327 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 1328 ) 1329 { 1330 int i; 1331 1332 SCIPdebugMsg(scip, "drop and free events\n"); 1333 1334 assert(scip != NULL); 1335 assert(propdata != NULL); 1336 assert(propdata->eventhdlr != NULL); 1337 1338 if( propdata->lbevents != NULL ) 1339 { 1340 assert(propdata->ubevents != NULL); 1341 assert(propdata->nlbevents >= 0); 1342 assert(propdata->nubevents >= 0); 1343 1344 for( i = propdata->nlbevents - 1; i >= 0; i-- ) 1345 { 1346 /* drop event */ 1347 SCIP_CALL( SCIPdropVarEvent(scip, propdata->lbevents[i]->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr, 1348 propdata->lbevents[i], -1) ); 1349 } 1350 1351 for( i = propdata->nubevents - 1; i >= 0; i-- ) 1352 { 1353 /* drop event */ 1354 SCIP_CALL( SCIPdropVarEvent(scip, propdata->ubevents[i]->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr, 1355 propdata->ubevents[i], -1) ); 1356 } 1357 1358 /* free event data */ 1359 SCIP_CALL( freeAllEventData(scip, propdata) ); 1360 } 1361 1362 assert(propdata->lbevents == NULL); 1363 assert(propdata->ubevents == NULL); 1364 assert(propdata->nlbevents == -1); 1365 assert(propdata->nubevents == -1); 1366 1367 return SCIP_OKAY; 1368 } 1369 1370 /** returns the corresponding event data entry in the corresponding array, if there is one; if not: allocates a new 1371 * event data entry, stores it in the array and returns its adress 1372 */ 1373 static 1374 SCIP_RETCODE getEventData( 1375 SCIP* scip, /**< SCIP data structure */ 1376 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */ 1377 SCIP_VAR* var, /**< variable */ 1378 SCIP_BOUNDTYPE boundtype, /**< type of bound */ 1379 SCIP_EVENTDATA** eventdata /**< event data to return */ 1380 ) 1381 { 1382 SCIP_HASHMAP* hashmap; 1383 1384 assert(scip != NULL); 1385 assert(propdata != NULL); 1386 assert(var != NULL); 1387 1388 hashmap = boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbeventsmap : propdata->ubeventsmap; 1389 1390 if( SCIPhashmapExists(hashmap, var) ) 1391 *eventdata = (SCIP_EVENTDATA*) SCIPhashmapGetImage(hashmap, var); 1392 else 1393 { 1394 /* set up new eventdata entry */ 1395 SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) ); 1396 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startcomponents), propdata->ncomponents) ); 1397 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*eventdata)->startindices), propdata->ncomponents) ); 1398 (*eventdata)->startindicessize = propdata->ncomponents; 1399 (*eventdata)->nstarts = 0; 1400 (*eventdata)->var = var; 1401 (*eventdata)->prop = propdata->prop; 1402 1403 /* store event data in eventarray */ 1404 if( boundtype == SCIP_BOUNDTYPE_LOWER ) 1405 { 1406 propdata->lbevents[propdata->nlbevents] = *eventdata; 1407 propdata->nlbevents++; 1408 } 1409 else 1410 { 1411 propdata->ubevents[propdata->nubevents] = *eventdata; 1412 propdata->nubevents++; 1413 } 1414 1415 /* store hashmap entry */ 1416 SCIP_CALL( SCIPhashmapInsert(hashmap, var, (*eventdata)) ); 1417 } 1418 1419 return SCIP_OKAY; 1420 } 1421 1422 /** adds an event to the event array lbevents (if boundtype == SCIP_BOUNDTYPE_LOWER) or ubevents (if boundtype == 1423 * SCIP_BOUNDTYPE_UPPER) 1424 */ 1425 static 1426 SCIP_RETCODE addEventData( 1427 SCIP* scip, /**< SCIP data structure */ 1428 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */ 1429 SCIP_VAR* var, /**< variable thats event to be added */ 1430 int startindex, /**< starting index */ 1431 int startcomponent, /**< starting components index */ 1432 SCIP_BOUNDTYPE boundtype /**< type of bound */ 1433 ) 1434 { 1435 SCIP_EVENTDATA* eventdata; 1436 1437 assert(scip != NULL); 1438 assert(propdata != NULL); 1439 assert(var != NULL); 1440 assert(startindex >= 0); 1441 assert(startcomponent >= 0); 1442 1443 /* get eventdata entry */ 1444 SCIP_CALL( getEventData(scip, propdata, var, boundtype, &eventdata) ); 1445 assert(eventdata != NULL); 1446 1447 if( eventdata->nstarts > 0 && eventdata->startcomponents[eventdata->nstarts - 1] == startcomponent ) 1448 { 1449 /* if there is already a starting index for startcomponent stored at the last entry of eventdata->startindices, 1450 * it should be smaller; this relies on the implementation of setUpEvents(), calling addEventData() in 1451 * topological order 1452 */ 1453 assert(eventdata->startindices[eventdata->nstarts - 1] < startindex); 1454 } 1455 else 1456 { 1457 /* append starting information */ 1458 eventdata->startcomponents[eventdata->nstarts] = startcomponent; 1459 eventdata->startindices[eventdata->nstarts] = startindex; 1460 1461 /* increase counter */ 1462 eventdata->nstarts++; 1463 } 1464 1465 return SCIP_OKAY; 1466 } 1467 1468 static 1469 SCIP_RETCODE setUpEvents( 1470 SCIP* scip, /**< SCIP data structure */ 1471 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 1472 ) 1473 { 1474 int nprobvars; 1475 int i; 1476 1477 assert(scip != NULL); 1478 assert(propdata != NULL); 1479 assert(propdata->eventhdlr != NULL); 1480 assert(propdata->lbevents == NULL); 1481 assert(propdata->ubevents == NULL); 1482 assert(propdata->issorted); 1483 assert(propdata->nlbevents == -1); 1484 assert(propdata->nubevents == -1); 1485 1486 SCIPdebugMsg(scip, "set up events\n"); 1487 1488 /* allocate lbevents, ubevents, and their hashmaps */ 1489 nprobvars = SCIPgetNVars(scip) + SCIPgetNFixedVars(scip); 1490 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars) ); 1491 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars) ); 1492 SCIP_CALL( SCIPhashmapCreate(&(propdata->lbeventsmap), SCIPblkmem(scip), nprobvars) ); 1493 SCIP_CALL( SCIPhashmapCreate(&(propdata->ubeventsmap), SCIPblkmem(scip), nprobvars) ); 1494 propdata->nlbevents = 0; 1495 propdata->nubevents = 0; 1496 1497 /* loop over all components of genvboundstore */ 1498 for( i = 0; i < propdata->ncomponents; i++ ) 1499 { 1500 int j; 1501 1502 /* loop over all genvbounds in this component */ 1503 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) /*lint !e679*/ 1504 { 1505 GENVBOUND* genvbound; 1506 int k; 1507 1508 assert(j < propdata->ngenvbounds); 1509 1510 genvbound = propdata->genvboundstore[j]; 1511 assert(genvbound != NULL); 1512 1513 /* loop over all coefficients in this genvbound */ 1514 for( k = 0; k < genvbound->ncoefs; k++ ) 1515 { 1516 if( SCIPisPositive(scip, genvbound->coefs[k]) ) 1517 { 1518 SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_LOWER) ); 1519 } 1520 else 1521 { 1522 SCIP_CALL( addEventData(scip, propdata, genvbound->vars[k], j, i, SCIP_BOUNDTYPE_UPPER) ); 1523 } 1524 } 1525 } 1526 } 1527 1528 /* resize lbevents and ubevents array */ 1529 assert(propdata->nlbevents <= nprobvars); 1530 assert(propdata->nubevents <= nprobvars); 1531 if( propdata->nlbevents < nprobvars ) 1532 { 1533 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->lbevents), nprobvars, propdata->nlbevents) ); 1534 } 1535 if( propdata->nubevents < nprobvars ) 1536 { 1537 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->ubevents), nprobvars, propdata->nubevents) ); 1538 } 1539 1540 /* resize and register lower bound events */ 1541 for( i = 0; i < propdata->nlbevents; i++ ) 1542 { 1543 SCIP_EVENTDATA* eventdata = propdata->lbevents[i]; 1544 1545 assert(eventdata != NULL); 1546 assert(eventdata->nstarts > 0); 1547 assert(eventdata->startcomponents != NULL); 1548 assert(eventdata->startindices != NULL); 1549 1550 /* resize arrays stored in eventdata */ 1551 if( eventdata->startindicessize != eventdata->nstarts ) 1552 { 1553 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \ 1554 eventdata->nstarts) ); 1555 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \ 1556 eventdata->nstarts) ); 1557 eventdata->startindicessize = eventdata->nstarts; 1558 } 1559 1560 /* register event */ 1561 SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_LBTIGHTENED, propdata->eventhdlr, eventdata, \ 1562 NULL) ); 1563 } 1564 1565 /* resize and register upper bound events */ 1566 for( i = 0; i < propdata->nubevents; i++ ) 1567 { 1568 SCIP_EVENTDATA* eventdata = propdata->ubevents[i]; 1569 1570 assert(eventdata != NULL); 1571 assert(eventdata->nstarts > 0); 1572 assert(eventdata->startcomponents != NULL); 1573 assert(eventdata->startindices != NULL); 1574 1575 /* resize arrays stored in eventdata */ 1576 if( eventdata->startindicessize != eventdata->nstarts ) 1577 { 1578 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startcomponents), eventdata->startindicessize, \ 1579 eventdata->nstarts) ); 1580 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(eventdata->startindices), eventdata->startindicessize, \ 1581 eventdata->nstarts) ); 1582 eventdata->startindicessize = eventdata->nstarts; 1583 } 1584 /* register event */ 1585 SCIP_CALL( SCIPcatchVarEvent(scip, eventdata->var, SCIP_EVENTTYPE_UBTIGHTENED, propdata->eventhdlr, eventdata, 1586 NULL) ); 1587 } 1588 1589 return SCIP_OKAY; 1590 } 1591 1592 /** performs a topological sort on genvboundstore array 1593 * 1594 * The genvbounds graph is defined as follows: Given two genvbounds 1595 * 1596 * (genvbound1) c1 * x_i1 >= RHS1 1597 * 1598 * and 1599 * 1600 * (genvbound2) c2 * x_i2 >= RHS2, 1601 * 1602 * there is an arc from genvbound1 to genvbound2 iff c1 = +1 and x_i1 appears with positive coefficient in RHS2 or 1603 * c1 = -1 and x_i1 appears with negative coefficient in RHS2; in this case, a bound change of x_i1 deduced from 1604 * genvbound1 improves genvbound2's minactivity in RHS2. 1605 * 1606 * The method computes the strongly connected components and sorts them topologically. The order of the nodes in an 1607 * strongly connected component is arbitrary. 1608 */ 1609 static 1610 SCIP_RETCODE sortGenVBounds( 1611 SCIP* scip, /**< SCIP data structure */ 1612 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 1613 ) 1614 { 1615 GENVBOUND** genvboundssorted; /* array to store the sorted genvbounds */ 1616 SCIP_DIGRAPH* graph; 1617 int* strongcomponents; 1618 int* strongcompstartidx; 1619 int sortedindex; 1620 int i; 1621 1622 assert(scip != NULL); 1623 assert(propdata != NULL); 1624 assert(propdata->componentsstart == NULL); 1625 1626 SCIPdebugMsg(scip, "(re-)sort genvbounds topologically\n"); 1627 1628 /* create digraph */ 1629 SCIP_CALL( SCIPcreateDigraph(scip, &graph, propdata->ngenvbounds) ); 1630 1631 /* add outgoing arcs for each genvbound */ 1632 for( i = 0; i < propdata->ngenvbounds; i++ ) 1633 { 1634 GENVBOUND* genvbound; 1635 int j; 1636 1637 assert(i < propdata->ngenvbounds); 1638 1639 genvbound = propdata->genvboundstore[i]; 1640 1641 for( j = 0; j < genvbound->ncoefs; j++ ) 1642 { 1643 if( SCIPisPositive(scip, genvbound->coefs[j]) && 1644 SCIPhashmapExists(propdata->lbgenvbounds, genvbound->vars[j]) ) 1645 { 1646 int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->lbgenvbounds, genvbound->vars[j]))->index; 1647 SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) ); 1648 } 1649 else if( SCIPisNegative(scip, genvbound->coefs[j]) && 1650 SCIPhashmapExists(propdata->ubgenvbounds, genvbound->vars[j]) ) 1651 { 1652 int from = ((GENVBOUND*) SCIPhashmapGetImage(propdata->ubgenvbounds, genvbound->vars[j]))->index; 1653 SCIP_CALL( SCIPdigraphAddArc(graph, from, i, NULL) ); 1654 } 1655 } 1656 } 1657 1658 /* perform the topological sort */ 1659 SCIP_CALL( SCIPdigraphComputeUndirectedComponents(graph, 1, NULL, &(propdata->ncomponents)) ); 1660 SCIP_CALL( SCIPdigraphTopoSortComponents(graph) ); 1661 assert(SCIPdigraphGetNComponents(graph) == propdata->ncomponents); 1662 1663 /* allocate memory for genvboundssorted and componentsstart array */ 1664 SCIP_CALL( SCIPallocBufferArray(scip, &genvboundssorted, propdata->ngenvbounds) ); 1665 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->componentsstart), propdata->ncomponents + 1) ); 1666 propdata->componentsstartsize = propdata->ncomponents + 1; 1667 1668 /* allocate memory for strong component arrays */ 1669 SCIP_CALL( SCIPallocBufferArray(scip, &strongcomponents, SCIPdigraphGetNNodes(graph)) ); /*lint !e666*/ 1670 SCIP_CALL( SCIPallocBufferArray(scip, &strongcompstartidx, SCIPdigraphGetNNodes(graph) + 1) ); /*lint !e666*/ 1671 1672 /* compute sorted genvbounds array, fill componentsstart array */ 1673 sortedindex = 0; 1674 propdata->componentsstart[propdata->ncomponents] = propdata->ngenvbounds; 1675 for( i = 0; i < propdata->ncomponents; i++ ) 1676 { 1677 int j; 1678 int *nodes; 1679 int nnodes; 1680 int nstrongcomponents; 1681 1682 SCIPdigraphGetComponent(graph, i, &nodes, &nnodes); 1683 propdata->componentsstart[i] = sortedindex; 1684 1685 /* compute the strong components of the i-th undirected component */ 1686 if( nnodes > 2 ) 1687 { 1688 SCIP_CALL( SCIPdigraphComputeDirectedComponents(graph, i, strongcomponents, strongcompstartidx, 1689 &nstrongcomponents) ); 1690 1691 for( j = 0; j < nnodes; ++j ) 1692 { 1693 int node; 1694 1695 /* take the nodes at the end of the strong components array first to respect the topological 1696 * order of the different strong components 1697 */ 1698 node = strongcomponents[nnodes - j - 1]; 1699 1700 assert(node < propdata->ngenvbounds); 1701 genvboundssorted[sortedindex] = propdata->genvboundstore[node]; 1702 sortedindex++; 1703 } 1704 } 1705 else 1706 { 1707 for( j = 0; j < nnodes; j++ ) 1708 { 1709 assert(nodes[j] < propdata->ngenvbounds); 1710 genvboundssorted[sortedindex] = propdata->genvboundstore[nodes[j]]; 1711 sortedindex++; 1712 } 1713 } 1714 } 1715 assert(sortedindex == propdata->ngenvbounds); 1716 1717 /* copy sorted genvbounds into genvboundstore */ 1718 for( i = 0; i < propdata->ngenvbounds; i++ ) 1719 { 1720 assert(genvboundssorted[i] != NULL); 1721 1722 propdata->genvboundstore[i] = genvboundssorted[i]; 1723 propdata->genvboundstore[i]->index = i; 1724 } 1725 1726 /* free strong component arrays */ 1727 SCIPfreeBufferArray(scip, &strongcompstartidx); 1728 SCIPfreeBufferArray(scip, &strongcomponents); 1729 1730 SCIPfreeBufferArray(scip, &(genvboundssorted)); 1731 1732 /* free digraph */ 1733 SCIPdigraphFree(&graph); 1734 1735 /* remember genvboundstore as sorted */ 1736 propdata->issorted = TRUE; 1737 1738 #ifdef SCIP_DEBUG 1739 SCIPdebugMsg(scip, "genvbounds got: %d\n", propdata->ngenvbounds); 1740 for( i = 0; i < propdata->ncomponents; i++ ) 1741 { 1742 int j; 1743 1744 SCIPdebugMsg(scip, "{\n"); 1745 1746 for( j = propdata->componentsstart[i]; j < propdata->componentsstart[i+1]; j++ ) 1747 { 1748 SCIPdebugMsg(scip, " [%d] ", j); 1749 printGenVBound(scip, propdata->genvboundstore[j]); 1750 } 1751 1752 SCIPdebugMsg(scip, "}\n"); 1753 } 1754 #endif 1755 1756 return SCIP_OKAY; 1757 } 1758 1759 /** apply propagation of generalized variable bounds */ 1760 static 1761 SCIP_RETCODE applyGenVBounds( 1762 SCIP* scip, /**< SCIP data structure */ 1763 SCIP_PROP* prop, /**< genvbounds propagator */ 1764 SCIP_Bool global, /**< use global variable bounds for propagation? */ 1765 SCIP_RESULT* result, /**< result pointer */ 1766 int* nchgbds /**< counter to increase by the number of changed bounds */ 1767 ) 1768 { 1769 SCIP_PROPDATA* propdata; 1770 int* startingcomponents; 1771 int* startingindices; 1772 int nindices; 1773 int i; 1774 1775 SCIPdebugMsg(scip, "applying %s genvbound propagation in depth %d\n", global ? 1776 "global" : "local", SCIPgetDepth(scip)); 1777 1778 assert(scip != NULL); 1779 assert(prop != NULL); 1780 assert(result != NULL); 1781 1782 propdata = SCIPpropGetData(prop); 1783 assert(propdata != NULL); 1784 assert(propdata->genvboundstore != NULL); 1785 1786 if( *result == SCIP_DIDNOTRUN ) 1787 *result = SCIP_DIDNOTFIND; 1788 1789 /* if the genvbounds are not sorted, i.e. if root node processing has not been finished, yet, we just propagate in 1790 * the order in which they have been added to genvboundstore 1791 */ 1792 if( !propdata->issorted ) 1793 { 1794 int j; 1795 1796 assert(!propdata->sort || SCIPinProbing(scip) || SCIPgetDepth(scip) == 0); 1797 1798 for( j = 0; j < propdata->ngenvbounds && *result != SCIP_CUTOFF; j++ ) 1799 { 1800 if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) ) 1801 { 1802 /**@todo resolve multiaggregation in exitpre */ 1803 } 1804 else 1805 { 1806 SCIPdebugMsg(scip, "applying genvbound with index %d (unsorted mode)\n", j); 1807 SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) ); 1808 } 1809 } 1810 1811 return SCIP_OKAY; 1812 } 1813 1814 /* otherwise, we propagate only components affected by the latest bound changes */ 1815 startingcomponents = global ? propdata->gstartcomponents : propdata->startcomponents; 1816 startingindices = global ? propdata->gstartindices : propdata->startindices; 1817 nindices = global ? propdata->ngindices : propdata->nindices; 1818 1819 for( i = 0; i < nindices && *result != SCIP_CUTOFF; i++ ) 1820 { 1821 int j; 1822 1823 SCIPdebugMsg(scip, "starting in component %d at index %d\n", startingcomponents[i], startingindices[i]); 1824 for( j = startingindices[i]; j < propdata->componentsstart[startingcomponents[i] + 1] && 1825 *result != SCIP_CUTOFF; j++ ) /*lint !e679*/ 1826 { 1827 assert(j < propdata->ngenvbounds); 1828 1829 if( ! SCIPvarIsActive(propdata->genvboundstore[j]->var) ) 1830 { 1831 /**@todo resolve multiaggregation in exitpre */ 1832 } 1833 else 1834 { 1835 SCIPdebugMsg(scip, "applying genvbound with index %d, component %d\n", j, startingcomponents[i]); 1836 SCIP_CALL( applyGenVBound(scip, prop, propdata->genvboundstore[j], global, result, nchgbds) ); 1837 } 1838 } 1839 } 1840 1841 /* we dont want to run again caused by this starting data */ 1842 if( !global ) 1843 { 1844 SCIP_CALL( resetLocalStartingData(scip, propdata) ); 1845 } 1846 1847 return SCIP_OKAY; 1848 } 1849 1850 /** initialize propagator data */ 1851 static 1852 SCIP_RETCODE initPropdata( 1853 SCIP* scip, /**< SCIP data structure */ 1854 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 1855 ) 1856 { 1857 int nprobvars; 1858 1859 assert(scip != NULL); 1860 assert(propdata != NULL); 1861 assert(propdata->eventhdlr != NULL); 1862 1863 SCIPdebugMsg(scip, "init propdata\n"); 1864 1865 nprobvars = SCIPgetNVars(scip); 1866 1867 /* init genvboundstore */ 1868 propdata->genvboundstoresize = 2 * nprobvars; 1869 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize) ); 1870 BMSclearMemoryArray(propdata->genvboundstore, propdata->genvboundstoresize); 1871 propdata->ngenvbounds = 0; 1872 1873 /* init genvboundstore hashmaps */ 1874 SCIP_CALL( SCIPhashmapCreate(&(propdata->lbgenvbounds), SCIPblkmem(scip), nprobvars) ); 1875 SCIP_CALL( SCIPhashmapCreate(&(propdata->ubgenvbounds), SCIPblkmem(scip), nprobvars) ); 1876 1877 return SCIP_OKAY; 1878 } 1879 1880 /** adds a new genvbound to genvboundstore array and sets a hashmap entry */ 1881 static 1882 SCIP_RETCODE addNewGenVBound( 1883 SCIP* scip, /**< SCIP data structure */ 1884 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */ 1885 GENVBOUND* genvbound /**< genvbound to be added */ 1886 ) 1887 { 1888 SCIP_HASHMAP* hashmap; 1889 1890 assert(scip != NULL); 1891 assert(propdata != NULL); 1892 assert(genvbound != NULL); 1893 assert(getGenVBound(scip, propdata, genvbound->var, genvbound->boundtype) == NULL); 1894 1895 hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds; 1896 1897 /* e.g., during presolving after a restart, new variables might have been created; in this case, we need to extend 1898 * the genvboundstore; the new size may even exceed 2*SCIPgetNVars() if we have genvbounds with nonactive left-hand 1899 * side variables 1900 */ 1901 assert(propdata->ngenvbounds <= propdata->genvboundstoresize); 1902 if( propdata->ngenvbounds == propdata->genvboundstoresize ) 1903 { 1904 int oldsize = propdata->genvboundstoresize; 1905 propdata->genvboundstoresize = 2*propdata->genvboundstoresize + 1; 1906 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(propdata->genvboundstore), oldsize, propdata->genvboundstoresize) ); 1907 } 1908 1909 /* new index is propdata->ngenvbounds */ 1910 SCIP_CALL( SCIPhashmapInsert(hashmap, genvbound->var, genvbound) ); 1911 propdata->genvboundstore[propdata->ngenvbounds] = genvbound; 1912 genvbound->index = propdata->ngenvbounds; 1913 propdata->ngenvbounds++; 1914 1915 assert(propdata->ngenvbounds <= propdata->genvboundstoresize); 1916 1917 return SCIP_OKAY; 1918 } 1919 1920 /** runs propagation routine */ 1921 static 1922 SCIP_RETCODE execGenVBounds( 1923 SCIP* scip, /**< SCIP data structure */ 1924 SCIP_PROPDATA* propdata, /**< data of the genvbounds propagator */ 1925 SCIP_RESULT* result, /**< result pointer */ 1926 SCIP_Bool local, /**< should local propagation be applied? */ 1927 int* nchgbds /**< counter to increase by the number of changed bounds */ 1928 ) 1929 { 1930 assert(scip != NULL); 1931 assert(propdata != NULL); 1932 assert(propdata->prop != NULL); 1933 assert(result != NULL); 1934 1935 /* we only sort after the root node is finished; this avoids having to sort again after adding more genvbounds; if 1936 * the genvbounds are not sorted, we will simply propagate all of them in the order given 1937 */ 1938 if( propdata->sort && !SCIPinProbing(scip) && SCIPgetDepth(scip) > 0 ) 1939 { 1940 if( !propdata->issorted ) 1941 { 1942 *result = SCIP_DIDNOTFIND; 1943 1944 SCIPdebugMsg(scip, "genvbounds are not sorted\n"); 1945 1946 /* drop and free old events */ 1947 SCIP_CALL( dropAndFreeEvents(scip, propdata) ); 1948 1949 /* free old starting data */ 1950 SCIP_CALL( freeStartingData(scip, propdata) ); 1951 1952 /* free sorted components data */ 1953 SCIP_CALL( freeComponentsData(scip, propdata) ); 1954 1955 /* sort genvbounds */ 1956 SCIP_CALL( sortGenVBounds(scip, propdata) ); 1957 1958 /* create starting data */ 1959 SCIP_CALL( createStartingData(scip, propdata) ); 1960 1961 /* fill global starting data */ 1962 SCIP_CALL( fillGlobalStartingData(scip, propdata) ); 1963 } 1964 1965 /* set up new events to catch (if not done so far) */ 1966 if( propdata->lbevents == NULL ) 1967 { 1968 SCIP_CALL( setUpEvents(scip, propdata) ); 1969 } 1970 } 1971 1972 /* apply global propagation if primal bound has improved */ 1973 if( propdata->global && SCIPgetDepth(scip) > 0 && SCIPisFeasLT(scip, SCIPgetCutoffbound(scip), propdata->lastcutoff) ) 1974 { 1975 if( propdata->ngindices > 0 ) 1976 { 1977 SCIP_CALL( applyGenVBounds(scip, propdata->prop, TRUE, result, nchgbds) ); 1978 assert(*result != SCIP_DIDNOTRUN); 1979 } 1980 1981 /* within the tree, the objective function should not change anymore, hence the cutoff bound should be a stable 1982 * point of reference 1983 */ 1984 propdata->lastcutoff = SCIPgetCutoffbound(scip); 1985 } 1986 1987 /* apply local propagation if allowed */ 1988 if( local && *result != SCIP_CUTOFF ) 1989 { 1990 /* check if local propagation in root node is allowed */ 1991 if( SCIPgetDepth(scip) > 0 || propdata->propinrootnode ) 1992 { 1993 /* if genvbounds are already sorted, check if bound change events were caught; otherwise apply all genvbounds */ 1994 if( !propdata->issorted || ( SCIPgetCurrentNode(scip) == propdata->lastnodecaught && propdata->nindices > 0 ) ) 1995 { 1996 SCIP_CALL( applyGenVBounds(scip, propdata->prop, FALSE, result, nchgbds) ); 1997 assert(*result != SCIP_DIDNOTRUN); 1998 } 1999 } 2000 } 2001 2002 return SCIP_OKAY; 2003 } 2004 2005 /* adds all genvbounds in the genvboundstore as constraints to the problem; afterwards clears the genvboundstore */ 2006 static 2007 SCIP_RETCODE createConstraints( 2008 SCIP* scip, /**< SCIP data structure */ 2009 SCIP_PROPDATA* propdata /**< data of the genvbounds propagator */ 2010 ) 2011 { 2012 int i; 2013 2014 assert(scip != NULL); 2015 assert(propdata != NULL); 2016 assert(propdata->propasconss); 2017 2018 /* ensure that the cutoffboundvar is available */ 2019 if( propdata->cutoffboundvar == NULL ) 2020 { 2021 SCIP_Real ub; 2022 char name[16]; 2023 2024 /* set the upper bound to the best primal value in the original problem */ 2025 ub = getCutoffboundGenVBound(scip); 2026 2027 SCIPdebugMsg(scip, "initialize cutoffboundvar with UB = %e\n", ub); 2028 2029 (void) SCIPsnprintf(name, 16, "cutoffboundvar"); 2030 SCIP_CALL( SCIPcreateVarBasic(scip, &propdata->cutoffboundvar, name, -SCIPinfinity(scip), ub, 0.0, SCIP_VARTYPE_CONTINUOUS) ); 2031 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, propdata->cutoffboundvar) ); 2032 2033 SCIP_CALL( SCIPaddVar(scip, propdata->cutoffboundvar) ); 2034 2035 /* lock the variable because it should not be subject to dual presolving reductions; because we create the 2036 * linear constraints as non-check constraints, the cutoffboundvar will not be locked by the linear constraint 2037 * handler 2038 */ 2039 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) ); 2040 } 2041 2042 assert(propdata->cutoffboundvar != NULL); 2043 2044 /* now iterate over all genvbounds in the store and construct a linear constraint for each of them */ 2045 for( i = 0; i < propdata->ngenvbounds; ++i ) 2046 { 2047 GENVBOUND* genvbound; 2048 SCIP_CONS* cons; 2049 SCIP_VAR** vars; 2050 SCIP_Real* vals; 2051 char name[SCIP_MAXSTRLEN]; 2052 int nvars; 2053 int j; 2054 2055 genvbound = propdata->genvboundstore[i]; 2056 assert(genvbound != NULL); 2057 2058 nvars = genvbound->ncoefs + 2; 2059 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 2060 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 2061 2062 SCIPdebugMsgPrint(scip, "add cons: "); 2063 2064 /* copy the coefs/vars array */ 2065 for( j = 0; j < genvbound->ncoefs; j++ ) 2066 { 2067 vars[j] = genvbound->vars[j]; 2068 vals[j] = genvbound->coefs[j]; 2069 SCIPdebugMsgPrint(scip, "%e%s + ", vals[j], SCIPvarGetName(vars[j])); 2070 } 2071 2072 /* add the variable and the coefficient of the genvbound */ 2073 vars[genvbound->ncoefs] = genvbound->var; 2074 vals[genvbound->ncoefs] = (genvbound->boundtype == SCIP_BOUNDTYPE_LOWER) ? -1.0 : 1.0; 2075 2076 SCIPdebugMsgPrint(scip, "%e%s + ", vals[genvbound->ncoefs], SCIPvarGetName(vars[genvbound->ncoefs])); 2077 2078 /* add cutoffcoef * cutoffboundvar */ 2079 vars[genvbound->ncoefs + 1] = propdata->cutoffboundvar; 2080 vals[genvbound->ncoefs + 1] = genvbound->cutoffcoef; 2081 2082 SCIPdebugMsgPrint(scip, "%e%s <= %e\n", vals[genvbound->ncoefs + 1], SCIPvarGetName(vars[genvbound->ncoefs + 1]), -1.0*genvbound->constant); 2083 2084 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "genvbound_cons%d", genvbound->index); 2085 2086 /* create linear constraint with only propagate flag as TRUE */ 2087 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, nvars, vars, vals, -SCIPinfinity(scip), -genvbound->constant, 2088 FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 2089 2090 SCIP_CALL( SCIPaddCons(scip, cons) ); 2091 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 2092 2093 /* free memory */ 2094 SCIPfreeBufferArray(scip, &vars); 2095 SCIPfreeBufferArray(scip, &vals); 2096 } 2097 2098 /* now delete all genvbounds in the genvboundstore */ 2099 if( propdata->ngenvbounds > 0 ) 2100 { 2101 assert(propdata->genvboundstore != NULL); 2102 2103 for( i = propdata->ngenvbounds - 1; i >= 0; i-- ) 2104 { 2105 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) ); 2106 } 2107 2108 /* free genvboundstore hashmaps */ 2109 SCIPhashmapFree(&(propdata->lbgenvbounds)); 2110 SCIPhashmapFree(&(propdata->ubgenvbounds)); 2111 2112 /* drop and free all events */ 2113 SCIP_CALL( dropAndFreeEvents(scip, propdata) ); 2114 2115 /* free componentsstart array */ 2116 SCIP_CALL( freeComponentsData(scip, propdata) ); 2117 2118 /* free starting indices data */ 2119 SCIP_CALL( freeStartingData(scip, propdata) ); 2120 2121 SCIPfreeBlockMemoryArray(scip, &(propdata->genvboundstore), propdata->genvboundstoresize); 2122 propdata->genvboundstore = NULL; 2123 propdata->genvboundstoresize = 0; 2124 propdata->ngenvbounds = 0; 2125 } 2126 2127 return SCIP_OKAY; 2128 } 2129 2130 2131 2132 /* 2133 * Public methods 2134 */ 2135 2136 /** adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound 2137 * "boundtype" of variable "var", it will be replaced 2138 */ 2139 SCIP_RETCODE SCIPgenVBoundAdd( 2140 SCIP* scip, /**< SCIP data structure */ 2141 SCIP_PROP* genvboundprop, /**< genvbound propagator */ 2142 SCIP_VAR** vars, /**< array of RHSs variables */ 2143 SCIP_VAR* var, /**< LHSs variable */ 2144 SCIP_Real* coefs, /**< array of coefficients for the RHSs variables */ 2145 int ncoefs, /**< size of coefs array */ 2146 SCIP_Real coefcutoffbound, /**< nonpositive value of the cutoff bounds multiplier */ 2147 SCIP_Real constant, /**< constant term */ 2148 SCIP_BOUNDTYPE boundtype /**< type of bound provided by the genvbound */ 2149 ) 2150 { 2151 /**@todo in debug mode: check if genvbound is nontrivial */ 2152 2153 SCIP_PROPDATA* propdata; 2154 GENVBOUND* genvbound; 2155 SCIP_Bool newgenvbound; 2156 int i; 2157 2158 assert(scip != NULL); 2159 assert(genvboundprop != NULL); 2160 assert(strcmp(SCIPpropGetName(genvboundprop), PROP_NAME) == 0); 2161 assert(vars != NULL); 2162 assert(var != NULL); 2163 assert(coefs != NULL); 2164 assert(ncoefs >= 0); 2165 assert(coefcutoffbound <= 0.0); 2166 assert(!SCIPisInfinity(scip, -constant)); 2167 2168 if( ncoefs < 0 || coefcutoffbound > 0.0 || SCIPisInfinity(scip, -constant) ) 2169 { 2170 SCIPerrorMessage("cannot create generalized variable bound from invalid data\n"); 2171 return SCIP_INVALIDDATA; 2172 } 2173 2174 propdata = SCIPpropGetData(genvboundprop); 2175 assert(propdata != NULL); 2176 2177 /* initialize propdata if not done yet */ 2178 if( propdata->genvboundstore == NULL ) 2179 { 2180 SCIP_CALL( initPropdata(scip, propdata) ); 2181 } 2182 2183 genvbound = getGenVBound(scip, propdata, var, boundtype); 2184 newgenvbound = (genvbound == NULL); 2185 2186 /* release previous variables */ 2187 if( !newgenvbound ) 2188 { 2189 for( i = 0; i < genvbound->ncoefs; ++i ) 2190 { 2191 assert(genvbound->vars[i] != NULL); 2192 SCIP_CALL( SCIPreleaseVar(scip, &(genvbound->vars[i])) ); 2193 } 2194 } 2195 2196 /* check if there already is a genvbound corresponding to this bound, freeing its data and overwriting it */ 2197 if( !newgenvbound && genvbound->ncoefs < ncoefs ) 2198 { 2199 /* do not realloc since we do not want to keep and possibly copy the old entries */ 2200 SCIPfreeBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize); 2201 SCIPfreeBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize); 2202 2203 /* allocate and copy arrays in genvbound */ 2204 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) ); 2205 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) ); 2206 genvbound->coefssize = ncoefs; 2207 } 2208 else if( !newgenvbound && genvbound->ncoefs == ncoefs ) 2209 { 2210 /* just update entries */ 2211 for( i = 0; i < ncoefs; i++ ) 2212 { 2213 genvbound->coefs[i] = coefs[i]; 2214 genvbound->vars[i] = vars[i]; 2215 } 2216 } 2217 else if( !newgenvbound && genvbound->ncoefs > ncoefs ) 2218 { 2219 /* reallocate memory for arrays in genvbound to free unused memory */ 2220 if( genvbound->coefssize < ncoefs ) 2221 { 2222 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, ncoefs) ); 2223 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, ncoefs) ); 2224 genvbound->coefssize = ncoefs; 2225 } 2226 2227 /* update entries */ 2228 for( i = 0; i < ncoefs; i++ ) 2229 { 2230 genvbound->coefs[i] = coefs[i]; 2231 genvbound->vars[i] = vars[i]; 2232 } 2233 } 2234 else if( newgenvbound ) 2235 { 2236 /* allocate memory for genvbound data */ 2237 SCIP_CALL( SCIPallocBlockMemory(scip, &genvbound) ); 2238 2239 /* allocate and copy arrays in genvbound */ 2240 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->coefs), coefs, ncoefs) ); 2241 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(genvbound->vars), vars, ncoefs) ); 2242 genvbound->coefssize = ncoefs; 2243 } 2244 2245 /* set up data for genvbound */ 2246 genvbound->boundtype = boundtype; 2247 genvbound->var = var; 2248 genvbound->ncoefs = ncoefs; 2249 genvbound->constant = constant; 2250 genvbound->relaxonly = SCIPvarIsRelaxationOnly(genvbound->var); 2251 2252 /* capture variables and check for relax-only vars */ 2253 for( i = 0; i < genvbound->ncoefs; ++i ) 2254 { 2255 assert(genvbound->vars[i] != NULL); 2256 SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[i]) ); 2257 if( SCIPvarIsRelaxationOnly(genvbound->vars[i]) ) 2258 genvbound->relaxonly = TRUE; 2259 } 2260 if( newgenvbound ) 2261 { 2262 assert(genvbound->var != NULL); 2263 SCIP_CALL( SCIPcaptureVar(scip, genvbound->var) ); 2264 } 2265 2266 /* the cutoff bound is valid w.r.t. the current objective function in the transformed problem; during presolving, 2267 * however, the objective function can change (e.g., when a variable is fixed, its contribution in the objective 2268 * is subtracted from the cutoff bound and added to the objective offset); we solve this by transforming the 2269 * contribution of the cutoff bound in the generalized variable bound to the original problem as follows: 2270 * 2271 * +/- var >= ... + z * SCIPgetCutoffbound() + constant 2272 * 2273 * becomes 2274 * 2275 * +/- var >= ... + (z / SCIPgetTransObjscale()) * origcutoffbound + (constant - z * SCIPgetTransObjoffset()) 2276 * 2277 * with SCIPgetCutoffbound() = origcutoffbound / SCIPgetTransObjscale() - SCIPgetTransObjoffset(); in the 2278 * propagation later, we will use (SCIPgetCutoffbound() + SCIPgetTransObjoffset()) * SCIPgetTransObjscale(), see 2279 * function getCutoffboundGenVBound() 2280 */ 2281 if( SCIPisNegative(scip, coefcutoffbound) ) 2282 { 2283 assert(SCIPisPositive(scip, SCIPgetTransObjscale(scip))); 2284 genvbound->cutoffcoef = coefcutoffbound / SCIPgetTransObjscale(scip); 2285 genvbound->constant -= (coefcutoffbound * SCIPgetTransObjoffset(scip)); 2286 } 2287 else 2288 genvbound->cutoffcoef = 0.0; 2289 2290 /* if genvbound is not overwritten, create a new entry in genvboundstore */ 2291 if( newgenvbound ) 2292 { 2293 SCIP_CALL( addNewGenVBound(scip, propdata, genvbound) ); 2294 } 2295 2296 /* mark genvbounds array to be resorted */ 2297 propdata->issorted = FALSE; 2298 2299 /* debug message */ 2300 SCIPdebugMsg(scip, "added genvbound "); 2301 SCIPdebug( printGenVBound(scip, genvbound) ); 2302 #ifdef WITH_DEBUG_SOLUTION 2303 SCIP_CALL( checkDebugSolutionGenVBound(scip, genvbound) ); 2304 #endif 2305 2306 return SCIP_OKAY; 2307 } 2308 2309 2310 /* 2311 * Callback methods of propagator 2312 */ 2313 2314 /** copy method for propagator plugins (called when SCIP copies plugins) 2315 * 2316 * @note The UG framework assumes that all default plug-ins of SCIP implement a copy callback. 2317 */ 2318 static 2319 SCIP_DECL_PROPCOPY(propCopyGenvbounds) 2320 { /*lint --e{715}*/ 2321 assert(scip != NULL); 2322 assert(prop != NULL); 2323 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2324 2325 /* call inclusion method of constraint handler */ 2326 SCIP_CALL( SCIPincludePropGenvbounds(scip) ); 2327 2328 return SCIP_OKAY; 2329 } 2330 2331 /** initialization method of propagator (called after problem was transformed) */ 2332 static 2333 SCIP_DECL_PROPINIT(propInitGenvbounds) 2334 { /*lint --e{715}*/ 2335 SCIP_PROPDATA* propdata; 2336 2337 assert(scip != NULL); 2338 assert(prop != NULL); 2339 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2340 2341 /* get propagator data */ 2342 propdata = SCIPpropGetData(prop); 2343 assert(propdata != NULL); 2344 2345 propdata->genvboundstore = NULL; 2346 propdata->genvboundstoresize = 0; 2347 propdata->lbevents = NULL; 2348 propdata->ubevents = NULL; 2349 propdata->lbgenvbounds = NULL; 2350 propdata->ubgenvbounds = NULL; 2351 propdata->lbeventsmap = NULL; 2352 propdata->ubeventsmap = NULL; 2353 propdata->startmap = NULL; 2354 propdata->componentsstart = NULL; 2355 propdata->startindices = NULL; 2356 propdata->startcomponents = NULL; 2357 propdata->gstartindices = NULL; 2358 propdata->gstartcomponents = NULL; 2359 propdata->lastcutoff = SCIPinfinity(scip); 2360 propdata->lastnodecaught = NULL; 2361 propdata->cutoffboundvar = NULL; 2362 propdata->ngenvbounds = -1; 2363 propdata->ncomponents = -1; 2364 propdata->nindices = -1; 2365 propdata->ngindices = -1; 2366 propdata->nlbevents = -1; 2367 propdata->nubevents = -1; 2368 propdata->issorted = FALSE; 2369 2370 propdata->prop = prop; 2371 2372 return SCIP_OKAY; 2373 } 2374 2375 2376 /** presolving method of propagator */ 2377 static 2378 SCIP_DECL_PROPPRESOL(propPresolGenvbounds) 2379 { /*lint --e{715}*/ 2380 SCIP_PROPDATA* propdata; 2381 2382 assert(scip != NULL); 2383 assert(prop != NULL); 2384 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2385 2386 *result = SCIP_DIDNOTRUN; 2387 2388 if( !SCIPallowStrongDualReds(scip) ) 2389 return SCIP_OKAY; 2390 2391 /* get propagator data */ 2392 propdata = SCIPpropGetData(prop); 2393 assert(propdata != NULL); 2394 2395 SCIPdebugMsg(scip, "proppresol in problem <%s>\n", SCIPgetProbName(scip)); 2396 2397 /* do not run if no genvbounds were added yet */ 2398 if( propdata->ngenvbounds < 1 ) 2399 { 2400 SCIPdebugMsg(scip, "no bounds were added yet\n"); 2401 return SCIP_OKAY; 2402 } 2403 2404 /* propagate */ 2405 SCIP_CALL( execGenVBounds(scip, propdata, result, TRUE, nchgbds) ); 2406 2407 return SCIP_OKAY; 2408 } 2409 2410 2411 /** presolving initialization method of propagator (called when presolving is about to begin) */ 2412 static 2413 SCIP_DECL_PROPINITPRE(propInitpreGenvbounds) 2414 { /*lint --e{715}*/ 2415 SCIP_PROPDATA* propdata; 2416 2417 assert(scip != NULL); 2418 assert(prop != NULL); 2419 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2420 2421 /* get propagator data */ 2422 propdata = SCIPpropGetData(prop); 2423 assert(propdata != NULL); 2424 2425 /* lock the variable because it should not be deleted after a restart */ 2426 if( propdata->cutoffboundvar != NULL ) 2427 { 2428 SCIPdebugMsg(scip, "propinitpre in problem <%s>: locking cutoffboundvar (current downlocks=%d, uplocks=%d)\n", 2429 SCIPgetProbName(scip), SCIPvarGetNLocksDownType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL), 2430 SCIPvarGetNLocksUpType(propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL)); 2431 2432 SCIP_CALL( SCIPaddVarLocksType(scip, propdata->cutoffboundvar, SCIP_LOCKTYPE_MODEL, 1, 1) ); 2433 } 2434 2435 return SCIP_OKAY; 2436 } 2437 2438 2439 /** presolving deinitialization method of propagator (called after presolving has been finished) */ 2440 static 2441 SCIP_DECL_PROPEXITPRE(propExitpreGenvbounds) 2442 { /*lint --e{715}*/ 2443 SCIP_VAR** vars; 2444 SCIP_PROPDATA* propdata; 2445 int i; 2446 2447 assert(scip != NULL); 2448 assert(prop != NULL); 2449 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2450 2451 SCIPdebugMsg(scip, "propexitpre in problem <%s>: removing fixed, aggregated, negated, and multi-aggregated variables from right-hand side\n", 2452 SCIPgetProbName(scip)); 2453 2454 /* get propagator data */ 2455 propdata = SCIPpropGetData(prop); 2456 assert(propdata != NULL); 2457 2458 /* there should be no events on the right-hand side variables */ 2459 assert(propdata->lbevents == NULL); 2460 assert(propdata->ubevents == NULL); 2461 2462 /* allocate memory to store new variables */ 2463 SCIP_CALL( SCIPallocBufferArray(scip, &vars, SCIPgetNTotalVars(scip)) ); 2464 2465 for( i = 0; i < propdata->ngenvbounds; ) 2466 { 2467 GENVBOUND* genvbound; 2468 int requiredsize; 2469 int nvars; 2470 int j; 2471 2472 genvbound = propdata->genvboundstore[i]; 2473 assert(genvbound != NULL); 2474 2475 /* store variables of the genvbound to release them properly */ 2476 assert(genvbound->ncoefs <= SCIPgetNTotalVars(scip)); 2477 BMScopyMemoryArray(vars, genvbound->vars, genvbound->ncoefs); 2478 nvars = genvbound->ncoefs; 2479 2480 /* replace non-active by active variables and update constant; note that this may result in coefficients where 2481 * SCIPisZero() is true; this should not create any problems 2482 */ 2483 SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, genvbound->ncoefs, &genvbound->constant, &requiredsize, TRUE) ); 2484 2485 /* if space was not enough we need to resize the buffers */ 2486 if( requiredsize > genvbound->ncoefs ) 2487 { 2488 /* reallocate memory for arrays in genvbound to free unused memory */ 2489 if( genvbound->coefssize < requiredsize ) 2490 { 2491 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->coefs), genvbound->coefssize, requiredsize) ); 2492 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(genvbound->vars), genvbound->coefssize, requiredsize) ); 2493 genvbound->coefssize = requiredsize; 2494 } 2495 2496 SCIP_CALL( SCIPgetProbvarLinearSum(scip, genvbound->vars, genvbound->coefs, &genvbound->ncoefs, requiredsize, &genvbound->constant, &requiredsize, TRUE) ); 2497 assert(requiredsize <= genvbound->ncoefs); 2498 } 2499 2500 /* capture new and release old variables */ 2501 for( j = 0; j < genvbound->ncoefs; ++j ) 2502 { 2503 assert(genvbound->vars[j] != NULL); 2504 SCIP_CALL( SCIPcaptureVar(scip, genvbound->vars[j]) ); 2505 } 2506 for( j = 0; j < nvars; ++j ) 2507 { 2508 assert(vars[j] != NULL); 2509 SCIP_CALL( SCIPreleaseVar(scip, &vars[j]) ); 2510 } 2511 2512 /* if the resulting genvbound is trivial, remove it */ 2513 /* we remove all genvbounds with an aggregated or multi-aggregated genvbound->var; tightening aggregated variables 2514 * might lead to some asserts in tree.c if the active variable has been already tightened (see !398); 2515 * 2516 * @todo replace aggregated variable by their active part 2517 */ 2518 if( (genvbound->ncoefs == 0 && SCIPisZero(scip, genvbound->cutoffcoef)) 2519 || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_MULTAGGR 2520 || SCIPvarGetStatus(genvbound->var) == SCIP_VARSTATUS_AGGREGATED ) 2521 { 2522 SCIP_HASHMAP* hashmap; 2523 2524 hashmap = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER ? propdata->lbgenvbounds : propdata->ubgenvbounds; 2525 2526 /* remove genvbound from hashmap */ 2527 assert(SCIPhashmapExists(hashmap, genvbound->var)); 2528 SCIP_CALL( SCIPhashmapRemove(hashmap, genvbound->var) ); 2529 2530 /* free genvbound and fill gap */ 2531 SCIP_CALL( freeGenVBound(scip, propdata->genvboundstore[i]) ); 2532 --(propdata->ngenvbounds); 2533 2534 /* move the last genvbound to the i-th position */ 2535 if( i < propdata->ngenvbounds ) 2536 { 2537 propdata->genvboundstore[i] = propdata->genvboundstore[propdata->ngenvbounds]; 2538 propdata->genvboundstore[i]->index = i; 2539 2540 /* mark genvbounds array to be resorted */ 2541 propdata->issorted = FALSE; 2542 } 2543 } 2544 else 2545 ++i; 2546 } 2547 2548 SCIPfreeBufferArray(scip, &vars); 2549 2550 return SCIP_OKAY; 2551 } 2552 2553 /** deinitialization method of propagator (called before transformed problem is freed) */ 2554 static 2555 SCIP_DECL_PROPEXIT(propExitGenvbounds) 2556 { 2557 SCIP_PROPDATA* propdata; 2558 2559 assert(scip != NULL); 2560 assert(prop != NULL); 2561 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2562 2563 /* get propagator data */ 2564 propdata = SCIPpropGetData(prop); 2565 assert(propdata != NULL); 2566 2567 /* free remaining genvbounds */ 2568 SCIP_CALL( freeGenVBounds(scip, propdata) ); 2569 2570 return SCIP_OKAY; 2571 } 2572 2573 /** execution method of propagator */ 2574 static 2575 SCIP_DECL_PROPEXEC(propExecGenvbounds) 2576 { /*lint --e{715}*/ 2577 SCIP_PROPDATA* propdata; 2578 2579 assert(scip != NULL); 2580 assert(prop != NULL); 2581 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2582 2583 *result = SCIP_DIDNOTRUN; 2584 2585 /* do not run if propagation w.r.t. current objective is not allowed */ 2586 if( !SCIPallowWeakDualReds(scip) ) 2587 return SCIP_OKAY; 2588 2589 /* get propagator data */ 2590 propdata = SCIPpropGetData(prop); 2591 assert(propdata != NULL); 2592 2593 /* update upper bound of the cutoffboundvar */ 2594 if( propdata->cutoffboundvar != NULL ) 2595 { 2596 SCIP_Real newub; 2597 SCIP_Real oldub; 2598 SCIP_Bool infeasible; 2599 SCIP_Bool tightened; 2600 2601 assert(propdata->propasconss); 2602 2603 /* compute the primal bound in the original problem */ 2604 newub = getCutoffboundGenVBound(scip); 2605 oldub = SCIPvarGetUbLocal(propdata->cutoffboundvar); 2606 2607 if( SCIPisInfinity(scip, newub) == FALSE && SCIPisFeasLT(scip, newub, oldub) ) 2608 { 2609 SCIP_CALL( SCIPtightenVarUbGlobal(scip, propdata->cutoffboundvar, newub, FALSE, &infeasible, &tightened) ); 2610 2611 if( tightened ) 2612 { 2613 SCIPdebugMsg(scip, "tightened UB of cutoffboundvar to %e (old: %e, infeas: %u, tightened: %u)\n", 2614 newub, oldub, infeasible, tightened); 2615 } 2616 2617 assert(infeasible == FALSE); 2618 } 2619 } 2620 2621 SCIPdebugMsg(scip, "propexec in problem <%s> at depth %d%s\n", SCIPgetProbName(scip), SCIPgetDepth(scip), 2622 SCIPinProbing(scip) ? " in probing" : ""); 2623 2624 /* do not run if no genvbounds were added yet */ 2625 if( propdata->ngenvbounds < 1 ) 2626 { 2627 /**@todo is it really no performance issue to be called each time when there are no genvbounds, e.g., for MIPs? */ 2628 SCIPdebugMsg(scip, "no bounds were added yet\n"); 2629 return SCIP_OKAY; 2630 } 2631 2632 /* add the genvbounds in the genvboundstore as constraints to the problem; afterwards clear the genvboundstore */ 2633 if( propdata->propasconss ) 2634 { 2635 SCIP_CALL( createConstraints(scip, propdata) ); 2636 return SCIP_OKAY; 2637 } 2638 2639 /* propagate locally and globally */ 2640 SCIP_CALL( execGenVBounds(scip, propdata, result, !SCIPinProbing(scip), NULL) ); 2641 2642 /* when called in presolving stage the result is set to SCIP_SUCCESS instead of SCIP_REDUCEDDOM, this is corrected 2643 * here 2644 */ 2645 if( *result == SCIP_SUCCESS ) 2646 *result = SCIP_REDUCEDDOM; 2647 2648 SCIPdebugMsg(scip, "end of exec\n"); 2649 2650 return SCIP_OKAY; 2651 } 2652 2653 /** propagation conflict resolving method of propagator */ 2654 static 2655 SCIP_DECL_PROPRESPROP(propRespropGenvbounds) 2656 { /*lint --e{715}*/ 2657 SCIP_PROPDATA* propdata; 2658 GENVBOUND* genvbound; 2659 SCIP_Real boundval; 2660 SCIP_Bool success; 2661 2662 SCIPdebugMsg(scip, "explain %s bound change of variable <%s>\n", 2663 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", SCIPvarGetName(infervar)); 2664 2665 /* get propagator data */ 2666 propdata = SCIPpropGetData(prop); 2667 assert(propdata != NULL); 2668 assert(propdata->genvboundstore != NULL); 2669 2670 /* as inferinfo we passed the index of the genvbound that was used for propagation; the genvbound might have been 2671 * replaced, but also the new genvbound at this position has the same variable on the left-hand side 2672 */ 2673 assert(inferinfo >= 0); 2674 assert(inferinfo < propdata->ngenvbounds); 2675 2676 *result = SCIP_DIDNOTFIND; 2677 2678 /* check also in optimized mode that inferinfo is correct */ 2679 if( inferinfo >= propdata->ngenvbounds) 2680 { 2681 SCIPerrorMessage("generalized variable bounds propagator received inferinfo out of range; propagation not resolved, safe to continue\n"); 2682 return SCIP_OKAY; 2683 } 2684 2685 /* get genvbound responsible for the bound change */ 2686 genvbound = propdata->genvboundstore[inferinfo]; 2687 assert(genvbound != NULL); 2688 assert(genvbound->var == infervar); 2689 2690 /* check also in optimized mode that inferinfo is correct */ 2691 if( genvbound->var != infervar ) 2692 { 2693 SCIPerrorMessage("generalized variable bounds propagator received incorrect inferinfo; propagation not resolved, but it's safe to continue\n"); 2694 return SCIP_OKAY; 2695 } 2696 2697 /* get value of bound change on left-hand side */ 2698 boundval = genvbound->boundtype == SCIP_BOUNDTYPE_LOWER 2699 ? SCIPgetVarLbAtIndex(scip, genvbound->var, bdchgidx, TRUE) 2700 : -SCIPgetVarUbAtIndex(scip, genvbound->var, bdchgidx, TRUE); 2701 2702 /* if left-hand side variable is integral, it suffices to explain a bound change greater than boundval - 1 */ 2703 if( SCIPvarIsIntegral(genvbound->var) ) 2704 { 2705 SCIP_Real roundedboundval; 2706 2707 assert(SCIPisIntegral(scip, boundval)); 2708 2709 roundedboundval = SCIPfeasCeil(scip, boundval - 1.0) + 2 * SCIPfeastol(scip); 2710 boundval = MIN(boundval, roundedboundval); 2711 } 2712 2713 /* resolve propagation */ 2714 SCIP_CALL( resolveGenVBoundPropagation(scip, genvbound, bdchgidx, &boundval, &success) ); 2715 2716 if( success ) 2717 *result = SCIP_SUCCESS; 2718 2719 return SCIP_OKAY; 2720 } 2721 2722 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */ 2723 static 2724 SCIP_DECL_PROPEXITSOL(propExitsolGenvbounds) 2725 { /*lint --e{715}*/ 2726 SCIP_PROPDATA* propdata; 2727 2728 assert(scip != NULL); 2729 assert(prop != NULL); 2730 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2731 2732 SCIPdebugMsg(scip, "propexitsol in problem <%s>\n", SCIPgetProbName(scip)); 2733 2734 /* get propagator data */ 2735 propdata = SCIPpropGetData(prop); 2736 assert(propdata != NULL); 2737 2738 if( !SCIPisInRestart(scip) ) 2739 { 2740 /* free all genvbounds if we are not in a restart */ 2741 SCIP_CALL( freeGenVBounds(scip, propdata) ); 2742 } 2743 else 2744 { 2745 /* free all genvbounds that use relax-only variables if we are in a restart */ 2746 SCIP_CALL( freeGenVBoundsRelaxOnly(scip, propdata) ); 2747 } 2748 2749 /* drop and free all events */ 2750 SCIP_CALL( dropAndFreeEvents(scip, propdata) ); 2751 2752 return SCIP_OKAY; 2753 } 2754 2755 /** destructor of propagator to free user data (called when SCIP is exiting) */ 2756 static 2757 SCIP_DECL_PROPFREE(propFreeGenvbounds) 2758 { /*lint --e{715}*/ 2759 SCIP_PROPDATA* propdata; 2760 2761 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 2762 2763 /* free propagator data */ 2764 propdata = SCIPpropGetData(prop); 2765 assert(propdata != NULL); 2766 2767 SCIPfreeBlockMemory(scip, &propdata); 2768 2769 SCIPpropSetData(prop, NULL); 2770 2771 return SCIP_OKAY; 2772 } 2773 2774 2775 /* 2776 * Callback methods of event handler 2777 */ 2778 2779 static 2780 SCIP_DECL_EVENTEXEC(eventExecGenvbounds) 2781 { /*lint --e{715}*/ 2782 SCIP_PROPDATA* propdata; 2783 int i; 2784 2785 assert(scip != NULL); 2786 assert(eventdata != NULL); 2787 2788 assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED || SCIPeventGetType(event) == 2789 SCIP_EVENTTYPE_UBTIGHTENED); 2790 2791 assert(eventdata->startcomponents != NULL); 2792 assert(eventdata->startindices != NULL); 2793 assert(eventdata->nstarts > 0); 2794 assert(eventdata->prop != NULL); 2795 2796 propdata = SCIPpropGetData(eventdata->prop); 2797 assert(propdata != NULL); 2798 2799 assert(propdata->startcomponents != NULL); 2800 assert(propdata->startmap != NULL); 2801 assert(propdata->startindices != NULL); 2802 2803 SCIPdebugMsg(scip, "catching eventdata:\n"); 2804 SCIPdebug( printEventData(eventdata, SCIPeventGetType(event) == SCIP_EVENTTYPE_LBTIGHTENED ? 2805 SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) ); 2806 2807 /* check if we need to reset old local starting indices data */ 2808 if( SCIPgetCurrentNode(scip) != propdata->lastnodecaught ) 2809 { 2810 SCIP_CALL( resetLocalStartingData(scip, propdata) ); 2811 propdata->lastnodecaught = SCIPgetCurrentNode(scip); 2812 } 2813 2814 for( i = 0; i < eventdata->nstarts; i++ ) 2815 { 2816 int component; 2817 int startidx; 2818 2819 component = eventdata->startcomponents[i]; 2820 assert(component >= 0); 2821 startidx = eventdata->startindices[i]; 2822 2823 /* there is already an entry for this component */ 2824 if( SCIPhashmapExists(propdata->startmap, (void*)(size_t) (component + 1)) ) 2825 { 2826 int componentidx; 2827 2828 /* get its index */ 2829 componentidx = (SCIPhashmapGetImageInt(propdata->startmap, (void*)(size_t) (component + 1))) - 1; /*lint !e571 !e776*/ 2830 assert(componentidx >= 0); 2831 assert(propdata->startcomponents[componentidx] == component); 2832 2833 if( propdata->startindices[componentidx] > startidx ) 2834 propdata->startindices[componentidx] = startidx; 2835 } 2836 else 2837 { 2838 /* get a new entry */ 2839 int componentidx; 2840 componentidx = propdata->nindices; 2841 2842 /* store index */ 2843 propdata->startcomponents[componentidx] = component; 2844 propdata->startindices[componentidx] = startidx; 2845 2846 /* store component in hashmap */ 2847 SCIP_CALL( SCIPhashmapInsertInt(propdata->startmap, (void*)(size_t) (component + 1), componentidx + 1) ); /*lint !e571 !e776*/ 2848 2849 /* increase number of starting indices */ 2850 propdata->nindices++; 2851 } 2852 } 2853 2854 return SCIP_OKAY; 2855 } 2856 2857 /* 2858 * propagator specific interface methods 2859 */ 2860 2861 /** creates the genvbounds propagator and includes it in SCIP */ 2862 SCIP_RETCODE SCIPincludePropGenvbounds( 2863 SCIP* scip /**< SCIP data structure */ 2864 ) 2865 { 2866 SCIP_PROPDATA* propdata; 2867 SCIP_PROP* prop; 2868 2869 /* create genvbounds propagator data */ 2870 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) ); 2871 2872 /* include propagator */ 2873 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 2874 propExecGenvbounds, propdata) ); 2875 2876 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyGenvbounds) ); 2877 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeGenvbounds) ); 2878 SCIP_CALL( SCIPsetPropInit(scip, prop, propInitGenvbounds) ); 2879 SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreGenvbounds) ); 2880 SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreGenvbounds) ); 2881 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitGenvbounds) ); 2882 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolGenvbounds) ); 2883 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolGenvbounds, PROP_PRESOL_PRIORITY, 2884 PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) ); 2885 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropGenvbounds) ); 2886 2887 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/global", 2888 "apply global propagation?", 2889 &propdata->global, TRUE, DEFAULT_GLOBAL_PROPAGATION, NULL, NULL) ); 2890 2891 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propinrootnode", 2892 "apply genvbounds in root node if no new incumbent was found?", 2893 &propdata->propinrootnode, TRUE, DEFAULT_PROPAGATE_IN_ROOT_NODE, NULL, NULL) ); 2894 2895 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/sort", 2896 "sort genvbounds and wait for bound change events?", 2897 &propdata->sort, TRUE, DEFAULT_SORT, NULL, NULL) ); 2898 2899 SCIP_CALL( SCIPaddBoolParam(scip, "propagating/" PROP_NAME "/propasconss", 2900 "should genvbounds be transformed to (linear) constraints?", 2901 &propdata->propasconss, TRUE, DEFAULT_PROPASCONSS, NULL, NULL) ); 2902 2903 /* include event handler */ 2904 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecGenvbounds, NULL) ); 2905 2906 return SCIP_OKAY; 2907 } 2908