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_pseudoobj.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief Pseudo objective propagator 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 * 31 * This propagator propagates the objective function using the cutoff bound and the pseudo objective value. The pseudo 32 * objective value can be seen as minimum activity of the linear objective function. Using this, this propagator checks 33 * if variables with non-zero objective coefficients can exceed the cutoff bound. If this is the case the corresponding 34 * bound can be tightened. 35 * 36 * @todo use the complete implication to initialize the objective implication data structure 37 */ 38 39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 40 41 #include "blockmemshell/memory.h" 42 #include "scip/prop_pseudoobj.h" 43 #include "scip/pub_event.h" 44 #include "scip/pub_implics.h" 45 #include "scip/pub_message.h" 46 #include "scip/pub_misc.h" 47 #include "scip/pub_misc_sort.h" 48 #include "scip/pub_prop.h" 49 #include "scip/pub_var.h" 50 #include "scip/scip_conflict.h" 51 #include "scip/scip_event.h" 52 #include "scip/scip_general.h" 53 #include "scip/scip_lp.h" 54 #include "scip/scip_mem.h" 55 #include "scip/scip_message.h" 56 #include "scip/scip_numerics.h" 57 #include "scip/scip_param.h" 58 #include "scip/scip_pricer.h" 59 #include "scip/scip_prob.h" 60 #include "scip/scip_probing.h" 61 #include "scip/scip_prop.h" 62 #include "scip/scip_solvingstats.h" 63 #include "scip/scip_tree.h" 64 #include "scip/scip_var.h" 65 #include "scip/dbldblarith.h" 66 #include <string.h> 67 68 #define PROP_NAME "pseudoobj" 69 #define PROP_DESC "pseudo objective function propagator" 70 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP 71 #define PROP_PRIORITY 3000000 /**< propagator priority */ 72 #define PROP_FREQ 1 /**< propagator frequency */ 73 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 74 #define PROP_PRESOL_PRIORITY +6000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */ 75 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no 76 * limit) */ 77 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ 78 79 #define EVENTHDLR_NAME "pseudoobj" 80 #define EVENTHDLR_DESC "bound change event handler for pseudo objective function propagator" 81 82 #define DEFAULT_MINUSELESS 100 /**< minimal number of successive non-binary variable propagator whithout a 83 * bound reduction before aborted */ 84 #define DEFAULT_MAXVARSFRAC 0.1 /**< maximal fraction of non-binary variables with non-zero objective 85 * without a bound reduction before aborted */ 86 #define DEFAULT_PROPFULLINROOT TRUE /**< do we want to propagate all non-binary variables if we are propagating the root node? */ 87 #define DEFAULT_PROPCUTOFFBOUND TRUE /**< propagate new cutoff bound directly globally */ 88 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that 89 * can be done if it is known that the pseudo objective activity is given by 90 * the zero bound for all variables which are currently not present in the 91 * problem */ 92 #define DEFAULT_MAXNEWVARS 1000 /**< number of variable added after the propagator is reinitialized? */ 93 #define DEFAULT_PROPUSEIMPLICS TRUE /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */ 94 #define DEFAULT_RESPROPUSEIMPLICS TRUE /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */ 95 #define DEFAULT_MAXIMPLVARS 50000 /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */ 96 97 98 /* 99 * Data structures 100 */ 101 102 /** implication data structure for objective contributions of a binary variable */ 103 struct SCIP_ObjImplics 104 { 105 SCIP_VAR** objvars; /**< variables y in implications y == 0 or y == 1, first we store the 106 * implications by x == 0 and second the implications x == 1 */ 107 SCIP_Real maxobjchg; /**< maximum objective contribution if variables x is fixed to zero or one */ 108 int nlbimpls; /**< number of all implications result through for x == 0 */ 109 int nubimpls; /**< number of all implications result through for x == 1 */ 110 int size; /**< size of the objvars array */ 111 }; 112 typedef struct SCIP_ObjImplics SCIP_OBJIMPLICS; /**< implications in the form x == 0 or x == 1 ==> y == 0 or y == 1 for (x and y binary) */ 113 114 115 /** propagator data */ 116 struct SCIP_PropData 117 { 118 SCIP_EVENTHDLR* eventhdlr; /**< event handler for global bound change events */ 119 SCIP_VAR** minactvars; /**< binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */ 120 SCIP_OBJIMPLICS** minactimpls; /**< implication data structure for the binary variables w.r.t. minimum activity */ 121 SCIP_VAR** maxactvars; /**< binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */ 122 SCIP_Real* maxactchgs; /**< the maximal potential change of the objective if the binary variable 123 * is fixed to its best bound w.r.t. maximum activity of the objective function */ 124 125 SCIP_VAR** objintvars; /**< non-binary variable with non-zero objective coefficient */ 126 SCIP_HASHTABLE* addedvars; /**< hash table used during resolving of a bound change (conflict analysis) */ 127 SCIP_Real lastlowerbound; /**< last lower bound which was propagated */ 128 SCIP_Real cutoffbound; /**< last cutoff bound used for propagation */ 129 SCIP_Real glbpseudoobjval; /**< last global pseudo objective used in presolving */ 130 SCIP_Real maxvarsfrac; /**< maximal fraction of non-binary variables with non-zero objective 131 * without a bound reduction before aborted 132 */ 133 SCIP_Real maxpseudoobjact; /**< maximal global pseudo objective activity */ 134 int maxpseudoobjactinf; /**< number of coefficients contributing with infinite value to maxpseudoobjact */ 135 int nminactvars; /**< number of binary variables with non-zero objective contribution w.r.t. minimum activity of the objective function */ 136 int nmaxactvars; /**< number of binary variables with non-zero objective contribution w.r.t. maximum activity of the objective function */ 137 int nobjintvars; /**< number of non-binary variables with non-zero objective */ 138 int minuseless; /**< minimal number of successive non-binary variable propagator whithout 139 * a bound reduction before aborted 140 */ 141 int lastvarnum; /**< last non-binary variable number that was looked at */ 142 int glbfirstnonfixed; /**< index of first globally non-fixed binary variable in minactvars array */ 143 int maxactfirstnonfixed;/**< index of first globally non-fixed binary variable in maxctvars array */ 144 int firstnonfixed; /**< index of first locally non-fixed binary variable in minactvars array */ 145 int nnewvars; /**< counter for counting number of new variables added */ 146 int maxnewvars; /**< number of variable added after the propagator is reinitialized? */ 147 int maximplvars; /**< maximum number of binary variables the implications are used if turned on (-1: unlimited)? */ 148 int minactsize; /**< size of minactvars and minactimpls array */ 149 int maxactsize; /**< size of maxactvars and maxactchgs array */ 150 int objintvarssize; /**< size of objintvars array*/ 151 SCIP_Bool glbpropagated; /**< are global domains propagated */ 152 SCIP_Bool propfullinroot; /**< do we want to propagate all non-binary variables if we are propagating the root node */ 153 SCIP_Bool propcutoffbound; /**< propagate new cutoff bound directly globally */ 154 SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */ 155 SCIP_Bool catchvaradded; /**< do we catch the variable added event? */ 156 SCIP_Bool propuseimplics; /**< use implications to strengthen the propagation of binary variable (increasing the objective change)? */ 157 SCIP_Bool respropuseimplics; /**< use implications to strengthen the resolve propagation of binary variable (increasing the objective change)? */ 158 SCIP_Bool initialized; /**< is propagator data structure initialized */ 159 }; 160 161 /* 162 * Debug methods 163 */ 164 165 #ifndef NDEBUG 166 /** check that the implications are applied for a globally fixed variable */ 167 static 168 void checkImplicsApplied( 169 SCIP* scip, /**< SCIP data structure */ 170 SCIP_VAR* var /**< variable to check the implications */ 171 ) 172 { 173 SCIP_VAR** vars; 174 SCIP_Real* bounds; 175 SCIP_BOUNDTYPE* boundtypes; 176 SCIP_Bool varfixing; 177 int nvars; 178 int v; 179 180 /* check that the given variable is locally or globally fixed */ 181 assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5); 182 183 /* get fixed value */ 184 varfixing = SCIPvarGetLbGlobal(var) > 0.5; 185 186 vars = SCIPvarGetImplVars(var, varfixing); 187 nvars = SCIPvarGetNImpls(var, varfixing); 188 bounds = SCIPvarGetImplBounds(var, varfixing); 189 boundtypes = SCIPvarGetImplTypes(var, varfixing); 190 191 /* check that each implication was applied */ 192 for( v = 0; v < nvars; ++v ) 193 { 194 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER ) 195 { 196 SCIP_Real lb; 197 198 lb = SCIPvarGetLbGlobal(vars[v]); 199 assert(SCIPisLE(scip, lb, bounds[v])); 200 } 201 else 202 { 203 SCIP_Real ub; 204 205 assert(boundtypes[v] == SCIP_BOUNDTYPE_UPPER); 206 207 ub = SCIPvarGetLbGlobal(vars[v]); 208 assert(SCIPisGE(scip, ub, bounds[v])); 209 } 210 } 211 } 212 213 /** check if the global fixed indices are correct */ 214 static 215 void checkGlbfirstnonfixed( 216 SCIP_PROPDATA* propdata /**< propagator data */ 217 ) 218 { 219 SCIP_VAR* var; 220 int v; 221 222 for( v = 0; v < propdata->glbfirstnonfixed; ++v ) 223 { 224 var = propdata->minactvars[v]; 225 assert(var != NULL); 226 227 assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5); 228 } 229 230 for( v = 0; v < propdata->maxactfirstnonfixed; ++v ) 231 { 232 var = propdata->maxactvars[v]; 233 assert(var != NULL); 234 235 assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5); 236 } 237 } 238 #endif /* end of debug methods */ 239 240 /* 241 * Comparer 242 */ 243 244 /** compares objective implications w.r.t. their maximum contribution */ 245 static 246 SCIP_DECL_SORTPTRCOMP(objimplicsComp) 247 { 248 SCIP_OBJIMPLICS* objimplics1; 249 SCIP_OBJIMPLICS* objimplics2; 250 251 objimplics1 = (SCIP_OBJIMPLICS*)elem1; 252 objimplics2 = (SCIP_OBJIMPLICS*)elem2; 253 254 if( objimplics1->maxobjchg > objimplics2->maxobjchg ) 255 return +1; 256 257 if( objimplics1->maxobjchg < objimplics2->maxobjchg ) 258 return -1; 259 260 return 0; 261 } 262 263 /** compare variables w.r.t. 264 * (i) the absolute value the objective coefficient; 265 * (ii) the locks which indicate most effect -- for the variables with a positive (negative) objective coefficient the 266 * down (up) lock is used since this lock indicates that tightened of the upper (lower) bound will triegger 267 * further domain propagations; 268 * (iii) the other locks; 269 * (iv) variable problem index; 270 */ 271 static 272 SCIP_DECL_SORTPTRCOMP(varCompObj) 273 { 274 SCIP_VAR* var1; 275 SCIP_VAR* var2; 276 int locks1; 277 int locks2; 278 279 var1 = (SCIP_VAR*)elem1; 280 var2 = (SCIP_VAR*)elem2; 281 282 assert(SCIPvarGetObj(var1) != 0.0); 283 assert(SCIPvarGetObj(var2) != 0.0); 284 285 /* first criteria is the absolute value of objective coefficient */ 286 if( REALABS(SCIPvarGetObj(var1)) < REALABS(SCIPvarGetObj(var2)) ) 287 return -1; 288 else if( REALABS(SCIPvarGetObj(var1)) > REALABS(SCIPvarGetObj(var2)) ) 289 return +1; 290 291 /* second criteria the locks which indicate most effect */ 292 if( SCIPvarGetObj(var1) > 0.0 ) 293 locks1 = SCIPvarGetNLocksDownType(var1, SCIP_LOCKTYPE_MODEL); 294 else 295 locks1 = SCIPvarGetNLocksUpType(var1, SCIP_LOCKTYPE_MODEL); 296 297 if( SCIPvarGetObj(var2) > 0.0 ) 298 locks2 = SCIPvarGetNLocksDownType(var2, SCIP_LOCKTYPE_MODEL); 299 else 300 locks2 = SCIPvarGetNLocksUpType(var2, SCIP_LOCKTYPE_MODEL); 301 302 if( locks1 < locks2 ) 303 return -1; 304 if( locks1 > locks2 ) 305 return 1; 306 307 /* third criteria the other locks */ 308 if( SCIPvarGetObj(var1) > 0.0 ) 309 locks1 = SCIPvarGetNLocksUpType(var1, SCIP_LOCKTYPE_MODEL); 310 else 311 locks1 = SCIPvarGetNLocksDownType(var1, SCIP_LOCKTYPE_MODEL); 312 313 if( SCIPvarGetObj(var2) > 0.0 ) 314 locks2 = SCIPvarGetNLocksUpType(var2, SCIP_LOCKTYPE_MODEL); 315 else 316 locks2 = SCIPvarGetNLocksDownType(var2, SCIP_LOCKTYPE_MODEL); 317 318 if( locks1 < locks2 ) 319 return -1; 320 if( locks1 > locks2 ) 321 return 1; 322 323 /* forth criteria use the problem index */ 324 return SCIPvarCompare(var1, var2); 325 } 326 327 /** hash key retrieval function for cliques*/ 328 static 329 SCIP_DECL_HASHGETKEY(cliqueGetHashkey) 330 { /*lint --e{715}*/ 331 return elem; 332 } 333 334 /** returns TRUE iff the cliques are equal */ 335 static 336 SCIP_DECL_HASHKEYEQ(cliqueIsHashkeyEq) 337 { /*lint --e{715}*/ 338 if( key1 == key2 ) 339 return TRUE; 340 return FALSE; 341 } 342 343 /** returns the hash value of the key */ 344 static 345 SCIP_DECL_HASHKEYVAL(cliqueGetHashkeyVal) 346 { /*lint --e{715}*/ 347 return SCIPcliqueGetId((SCIP_CLIQUE*) key); 348 } 349 350 /* 351 * methods for SCIP_OBJIMPLICS data structure 352 */ 353 354 /** creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper 355 * bound fixing, and clears the collected arrays for lower and upper bound 356 */ 357 static 358 SCIP_RETCODE objimplicsCreate( 359 SCIP* scip, /**< SCIP data structure */ 360 SCIP_OBJIMPLICS** objimplics, /**< pointer to objective implication data structure */ 361 SCIP_VAR** objvars, /**< objective contributor variables, or NULL */ 362 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays, or NULL */ 363 SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing, or NULL */ 364 SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing, or NULL */ 365 SCIP_Real maxlbobjchg, /**< maximum objective contributor if variables id fixed to zero */ 366 SCIP_Real maxubobjchg, /**< maximum objective contributor if variables id fixed to one */ 367 int nlbimpls, /**< number of variables contributing to to lower bound fix */ 368 int nubimpls /**< number of variables contributing to to upper bound fix */ 369 ) 370 371 { 372 assert(scip != NULL); 373 assert(objimplics != NULL); 374 assert(!SCIPisNegative(scip, maxlbobjchg)); 375 assert(!SCIPisNegative(scip, maxubobjchg)); 376 377 /* allocate block memory for the implication data structure */ 378 SCIP_CALL( SCIPallocBlockMemory(scip, objimplics) ); 379 380 if( nlbimpls + nubimpls == 0 ) 381 { 382 assert(nlbimpls == 0); 383 assert(nubimpls == 0); 384 (*objimplics)->objvars = NULL; 385 (*objimplics)->maxobjchg = 0.0; 386 (*objimplics)->nlbimpls = 0; 387 (*objimplics)->nubimpls = 0; 388 (*objimplics)->size = 0; 389 } 390 else 391 { 392 SCIP_VAR* var; 393 int nvars; 394 int pos; 395 int v; 396 397 assert(objvars != NULL); 398 assert(binobjvarmap != NULL); 399 assert(collectedlbvars != NULL); 400 assert(collectedubvars != NULL); 401 402 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*objimplics)->objvars, nlbimpls + nubimpls) ); 403 (*objimplics)->size = nlbimpls + nubimpls; 404 405 nvars = 0; 406 407 for( v = 0; v < nlbimpls; ++v ) 408 { 409 var = objvars[v]; 410 assert(var != NULL); 411 assert(!SCIPisZero(scip, SCIPvarGetObj(var))); 412 413 assert(SCIPhashmapExists(binobjvarmap, var)); 414 pos = SCIPhashmapGetImageInt(binobjvarmap, (void*)var); 415 assert(pos > 0); 416 assert(collectedlbvars[pos]); 417 418 if( collectedubvars[pos] ) 419 { 420 SCIP_Bool infeasible; 421 SCIP_Bool tightened; 422 423 if( SCIPvarGetBestBoundType(var) == SCIP_BOUNDTYPE_LOWER ) 424 { 425 SCIPdebugMsg(scip, "fix variables <%s> to 1.0 due to implications\n", SCIPvarGetName(var)); 426 427 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, &infeasible, &tightened) ); 428 maxlbobjchg -= SCIPvarGetObj(var); 429 } 430 else 431 { 432 SCIPdebugMsg(scip, "fix variables <%s> to 0.0 due to implications\n", SCIPvarGetName(var)); 433 434 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, 0.0, FALSE, &infeasible, &tightened) ); 435 maxlbobjchg += SCIPvarGetObj(var); 436 } 437 assert(!infeasible); 438 assert(tightened); 439 } 440 else 441 { 442 (*objimplics)->objvars[nvars] = var; 443 nvars++; 444 } 445 collectedlbvars[pos] = FALSE; 446 } 447 (*objimplics)->nlbimpls = nvars; 448 449 for( v = 0; v < nubimpls; ++v ) 450 { 451 var = objvars[nlbimpls + v]; 452 assert(var != NULL); 453 assert(!SCIPisZero(scip, SCIPvarGetObj(var))); 454 455 assert(SCIPhashmapExists(binobjvarmap, var)); 456 pos = SCIPhashmapGetImageInt(binobjvarmap, (void*)var); 457 assert(pos > 0); 458 assert(collectedubvars[pos]); 459 460 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 ) 461 { 462 if( SCIPvarGetBestBoundType(var) == SCIP_BOUNDTYPE_LOWER ) 463 maxubobjchg -= SCIPvarGetObj(var); 464 else 465 maxubobjchg += SCIPvarGetObj(var); 466 } 467 else 468 { 469 (*objimplics)->objvars[nvars] = var; 470 nvars++; 471 } 472 collectedubvars[pos] = FALSE; 473 } 474 (*objimplics)->nubimpls = nvars - (*objimplics)->nlbimpls; 475 476 /* capture the variables */ 477 for( v = 0; v < nvars; ++v ) 478 { 479 assert(SCIPvarIsBinary((*objimplics)->objvars[v])); 480 assert(!SCIPisZero(scip, SCIPvarGetObj((*objimplics)->objvars[v]))); 481 SCIP_CALL( SCIPcaptureVar(scip, (*objimplics)->objvars[v]) ); 482 } 483 } 484 485 (*objimplics)->maxobjchg = MAX(maxlbobjchg, maxubobjchg); 486 487 return SCIP_OKAY; 488 } 489 490 /** frees an objective implication data structure */ 491 static 492 SCIP_RETCODE objimplicsFree( 493 SCIP* scip, /**< SCIP data structure */ 494 SCIP_OBJIMPLICS** objimplics /**< pointer to objective implication data structure */ 495 ) 496 { 497 int v; 498 499 assert(scip != NULL); 500 assert(objimplics != NULL); 501 assert(*objimplics != NULL); 502 503 /* release all variables */ 504 for( v = 0; v < (*objimplics)->nlbimpls + (*objimplics)->nubimpls; ++v ) 505 { 506 SCIP_CALL( SCIPreleaseVar(scip, &(*objimplics)->objvars[v]) ); 507 } 508 509 /* free objective variable array */ 510 SCIPfreeBlockMemoryArrayNull(scip, &(*objimplics)->objvars, (*objimplics)->size); 511 512 /* frees block memory for the implication data structure */ 513 SCIPfreeBlockMemory(scip, objimplics); 514 515 return SCIP_OKAY; 516 } 517 518 /** remove the given variable at the given pos from the objective implication data structure */ 519 static 520 SCIP_RETCODE objimplicsDelPos( 521 SCIP* scip, /**< SCIP data structure */ 522 SCIP_OBJIMPLICS* objimplics, /**< objective implication data structure */ 523 int pos /**< position */ 524 ) 525 { 526 assert(0 <= pos); 527 assert(pos < objimplics->nlbimpls + objimplics->nubimpls); 528 529 SCIPdebugMsg(scip, "variable <%s> ", SCIPvarGetName(objimplics->objvars[pos])); 530 531 /* release variable */ 532 SCIP_CALL( SCIPreleaseVar(scip, &objimplics->objvars[pos]) ); 533 534 /* copy last lower bound variable to that position */ 535 if( pos < objimplics->nlbimpls ) 536 { 537 objimplics->nlbimpls--; 538 assert(objimplics->nlbimpls >= 0); 539 540 /* copy last lower bound variable to that position */ 541 objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls]; 542 543 /* copy last upper bound variable to open slot */ 544 objimplics->objvars[objimplics->nlbimpls] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls]; 545 546 SCIPdebugMsgPrint(scip, "remove lower bound implication\n"); 547 } 548 else 549 { 550 objimplics->nubimpls--; 551 assert(objimplics->nubimpls >= 0); 552 553 /* copy last upper bound variable to that position */ 554 objimplics->objvars[pos] = objimplics->objvars[objimplics->nlbimpls + objimplics->nubimpls]; 555 556 SCIPdebugMsgPrint(scip, "remove upper bound implication\n"); 557 } 558 559 return SCIP_OKAY; 560 } 561 562 /* 563 * Local methods 564 */ 565 566 567 /** catch bound change events if the variable has a non-zero objective coefficient to check if the maximum activity of 568 * the objective function changed 569 */ 570 static 571 SCIP_RETCODE catchObjEvent( 572 SCIP* scip, /**< SCIP data structure */ 573 SCIP_PROPDATA* propdata, /**< propagator data */ 574 SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */ 575 SCIP_VAR* var /**< variable for which the event should be dropped */ 576 ) 577 { 578 SCIP_Real objval; 579 580 assert(propdata != NULL); 581 assert(eventhdlr != NULL); 582 583 objval = SCIPvarGetObj(var); 584 585 if( !SCIPisZero(scip, objval) ) 586 { 587 if( objval > 0.0 ) 588 { 589 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) ); 590 } 591 else 592 { 593 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) ); 594 } 595 } 596 597 return SCIP_OKAY; 598 } 599 600 /** drop variable event w.r.t. objective coefficient */ 601 static 602 SCIP_RETCODE dropObjEvent( 603 SCIP* scip, /**< SCIP data structure */ 604 SCIP_PROPDATA* propdata, /**< propagator data */ 605 SCIP_EVENTHDLR* eventhdlr, /**< event handler for global bound change events */ 606 SCIP_VAR* var /**< variable for which the event should be dropped */ 607 ) 608 { 609 SCIP_Real objval; 610 611 assert(propdata != NULL); 612 assert(eventhdlr != NULL); 613 614 objval = SCIPvarGetObj(var); 615 616 /* drop bound change event */ 617 if( !SCIPisZero(scip, objval) ) 618 { 619 if( objval > 0.0 ) 620 { 621 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GUBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) ); 622 } 623 else 624 { 625 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_GLBCHANGED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) ); 626 } 627 } 628 return SCIP_OKAY; 629 } 630 631 /** drop all variable events */ 632 static 633 SCIP_RETCODE dropVarEvents( 634 SCIP* scip, /**< SCIP data structure */ 635 SCIP_PROPDATA* propdata /**< propagator data */ 636 ) 637 { 638 SCIP_EVENTHDLR* eventhdlr; 639 SCIP_VAR* var; 640 int k; 641 642 assert(scip != NULL); 643 assert(propdata != NULL); 644 645 eventhdlr = propdata->eventhdlr; 646 assert(eventhdlr != NULL); 647 648 /* drop all events and release variables */ 649 for( k = 0; k < propdata->nminactvars; ++k ) 650 { 651 var = propdata->minactvars[k]; 652 assert(var != NULL); 653 assert(SCIPvarIsBinary(var)); 654 655 /* drop bound relax event which is caught for all binary variables which are used for propagation the objective 656 * function via the minimum activity of the objective function 657 */ 658 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, -1) ); 659 660 /* release variable */ 661 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 662 } 663 664 /* release variables */ 665 for( k = 0; k < propdata->nmaxactvars; ++k ) 666 { 667 var = propdata->maxactvars[k]; 668 assert(var != NULL); 669 assert(SCIPvarIsBinary(var)); 670 671 /* drop events which are needed for evaluating the maximum activity of the objective function */ 672 SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) ); 673 674 /* release variable */ 675 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 676 } 677 678 /* drop all events and release variables */ 679 for( k = 0; k < propdata->nobjintvars; ++k ) 680 { 681 var = propdata->objintvars[k]; 682 assert(var != NULL); 683 684 /* drop events which are needed for evaluating the maximum activity of the objective function */ 685 SCIP_CALL( dropObjEvent(scip, propdata, eventhdlr, var) ); 686 687 /* release variable */ 688 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 689 } 690 691 return SCIP_OKAY; 692 } 693 694 /** reset propagatore data structure */ 695 static 696 void propdataReset( 697 SCIP_PROPDATA* propdata /**< propagator data */ 698 ) 699 { 700 propdata->minactvars = NULL; 701 propdata->minactimpls = NULL; 702 propdata->maxactvars = NULL; 703 propdata->maxactchgs = NULL; 704 propdata->objintvars = NULL; 705 propdata->nminactvars = 0; 706 propdata->nmaxactvars = 0; 707 propdata->nobjintvars = 0; 708 propdata->maxpseudoobjact = SCIP_INVALID; 709 propdata->maxpseudoobjactinf = 0; 710 propdata->lastvarnum = -1; 711 propdata->glbpropagated = FALSE; 712 propdata->cutoffbound = SCIP_INVALID; 713 propdata->lastlowerbound = -SCIP_INVALID; 714 propdata->glbpseudoobjval = -SCIP_INVALID; 715 propdata->glbfirstnonfixed = 0; 716 propdata->maxactfirstnonfixed = 0; 717 propdata->firstnonfixed = 0; 718 propdata->nnewvars = 0; 719 propdata->minactsize = 0; 720 propdata->maxactsize = 0; 721 propdata->objintvarssize = 0; 722 propdata->catchvaradded = FALSE; 723 propdata->initialized = FALSE; 724 } 725 726 /** free propagator data */ 727 static 728 SCIP_RETCODE propdataExit( 729 SCIP* scip, /**< SCIP data structure */ 730 SCIP_PROPDATA* propdata /**< propagator data */ 731 ) 732 { 733 int v; 734 735 if( !propdata->initialized ) 736 return SCIP_OKAY; 737 738 if( propdata->addedvars != NULL ) 739 SCIPhashtableFree(&propdata->addedvars); 740 741 /* drop events for the variables */ 742 SCIP_CALL( dropVarEvents(scip, propdata) ); 743 744 for( v = 0; v < propdata->nminactvars; ++v ) 745 { 746 SCIP_CALL( objimplicsFree(scip, &(propdata->minactimpls[v])) ); 747 } 748 749 /* free memory for non-zero objective variables */ 750 SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactvars, propdata->minactsize); 751 SCIPfreeBlockMemoryArrayNull(scip, &propdata->minactimpls, propdata->minactsize); 752 SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactvars, propdata->maxactsize); 753 SCIPfreeBlockMemoryArrayNull(scip, &propdata->maxactchgs, propdata->maxactsize); 754 SCIPfreeBlockMemoryArrayNull(scip, &propdata->objintvars, propdata->objintvarssize); 755 756 /* reset propagator data structure */ 757 propdataReset(propdata); 758 759 return SCIP_OKAY; 760 } 761 762 /** returns the objective change for the given binary variable */ 763 static 764 SCIP_Real getVarObjchg( 765 SCIP_VAR* var, /**< variable to get objective change for */ 766 SCIP_BOUNDTYPE boundtype, /**< bound type to consider */ 767 SCIP_BOUNDTYPE bound /**< fixing bound */ 768 ) 769 { 770 assert(SCIPvarIsBinary(var)); 771 assert((int)SCIP_BOUNDTYPE_LOWER == 0); /*lint !e506*/ 772 assert((int)SCIP_BOUNDTYPE_UPPER == 1); /*lint !e506*/ 773 774 /* collect contribution of variable itself */ 775 return (SCIP_Real)((int)bound - (int)(boundtype == SCIP_BOUNDTYPE_UPPER)) * SCIPvarGetObj(var); 776 } 777 778 /** returns the objective change provided by the implication variable by fixing it to the given bound 779 * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective 780 * change; 781 */ 782 static 783 SCIP_Real collectMinactImplicVar( 784 SCIP* scip, /**< SCIP data structure */ 785 SCIP_VAR* var, /**< variable to computes the objective contribution */ 786 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */ 787 SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */ 788 int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */ 789 SCIP_VAR** contributors, /**< array to store the contributors */ 790 int* ncontributors /**< pointer to store number of contributor to the objective contribution */ 791 ) 792 { 793 SCIP_Real objval; 794 int pos; 795 796 assert(scip != NULL); 797 assert(var != NULL); 798 assert(binobjvarmap != NULL); 799 assert(collectedvars != NULL); 800 assert(contributors != NULL); 801 assert(ncontributors != NULL); 802 803 /* ignore global fixed variables */ 804 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 ) 805 return 0.0; 806 807 objval = SCIPvarGetObj(var); 808 809 /* ignore variables with zero objective coefficient */ 810 if( SCIPisZero(scip, objval) ) 811 return 0.0; 812 813 assert(SCIPhashmapExists(binobjvarmap, var)); 814 pos = SCIPhashmapGetImageInt(binobjvarmap, var); 815 assert(pos > 0); 816 817 /* check if the variables was already collected through other cliques */ 818 if( collectedvars[pos] ) 819 return 0.0; 820 821 /* collect variable */ 822 assert(*ncontributors < nbinobjvars); 823 contributors[*ncontributors] = var; 824 (*ncontributors)++; 825 826 /* mark variable to be collected */ 827 collectedvars[pos] = TRUE; 828 829 /* return the absolute value of the objective coefficient as constriction */ 830 return REALABS(objval); 831 } 832 833 #define MAX_CLIQUELENGTH 50 834 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound 835 * w.r.t. minimum activity of the objective function; additionally it collects all contributors for that objective 836 * change; 837 * 838 * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to 839 * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the 840 * implications are: 841 * 842 * \f[ 843 * \displaystyle 844 * sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x) 845 * = 846 * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) 847 * \f] 848 */ 849 static 850 SCIP_RETCODE collectMinactImplicVars( 851 SCIP* scip, /**< SCIP data structure */ 852 SCIP_VAR* var, /**< variable to computes the objective contribution */ 853 SCIP_BOUNDTYPE bound, /**< bound to check for */ 854 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */ 855 SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */ 856 int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */ 857 SCIP_VAR** contributors, /**< array to store the contributors */ 858 SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */ 859 int* ncontributors, /**< pointer to store number of contributor to the objective contribution */ 860 SCIP_Real* objchg /**< pointer to store the objective change */ 861 ) 862 { 863 SCIP_CLIQUE** cliques; 864 SCIP_CLIQUE* clique; 865 SCIP_VAR** vars; 866 SCIP_VAR* implvar; 867 SCIP_Bool* values; 868 SCIP_Bool varfixing; 869 int nbinvars; 870 int ncliques; 871 int c; 872 int v; 873 874 assert(SCIPvarIsBinary(var)); 875 assert(SCIPvarGetLbGlobal(var) < 0.5); 876 assert(SCIPvarGetUbGlobal(var) > 0.5); 877 assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER); 878 assert(objchg != NULL); 879 assert(contributors != NULL); 880 assert(ncontributors != NULL); 881 assert(*ncontributors == 0); 882 883 assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/ 884 assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e506*/ 885 varfixing = (SCIP_Bool)bound; 886 887 cliques = SCIPvarGetCliques(var, varfixing); 888 ncliques = SCIPvarGetNCliques(var, varfixing); 889 890 if( uselesscliques == NULL ) 891 return SCIP_INVALIDDATA; 892 893 #ifndef NDEBUG 894 /* check that the marker array is reset */ 895 for( c = 0; c < nbinobjvars; ++c ) 896 assert(collectedvars[c] == FALSE); 897 #endif 898 899 /* collect all implication which are given via cliques */ 900 for( c = 0; c < ncliques; ++c ) 901 { 902 SCIP_Bool useless; 903 904 clique = cliques[c]; 905 assert(clique != NULL); 906 907 /* check if the clique was previously detected to be useless with respect to minimum activity */ 908 if( SCIPhashtableExists(uselesscliques, (void*)clique) ) 909 continue; 910 911 nbinvars = SCIPcliqueGetNVars(clique); 912 913 if( nbinvars > MAX_CLIQUELENGTH ) 914 { 915 SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) ); 916 continue; 917 } 918 919 vars = SCIPcliqueGetVars(clique); 920 values = SCIPcliqueGetValues(clique); 921 useless = TRUE; 922 923 for( v = 0; v < nbinvars; ++v ) 924 { 925 implvar = vars[v]; 926 assert(implvar != NULL); 927 928 if( implvar == var ) 929 { 930 /* check if the clique is useful at all */ 931 if( useless ) 932 { 933 SCIP_Real objval; 934 935 objval = SCIPvarGetObj(var); 936 937 if( varfixing == (SCIP_Bool)SCIPvarGetBestBoundType(var) && !SCIPisZero(scip, objval) ) 938 useless = FALSE; 939 } 940 } 941 else if( values[v] == (SCIP_Bool)SCIPvarGetBestBoundType(implvar) ) 942 { 943 useless = FALSE; 944 (*objchg) += collectMinactImplicVar(scip, implvar, binobjvarmap, collectedvars, nbinobjvars, contributors, ncontributors); 945 } 946 } 947 948 /* if the clique is useless store it in the hash table to skip it later */ 949 if( useless ) 950 { 951 assert(!SCIPhashtableExists(uselesscliques, (void*)clique)); 952 SCIP_CALL( SCIPhashtableInsert(uselesscliques, (void*)clique) ); 953 } 954 } 955 956 return SCIP_OKAY; 957 } 958 959 /** returns the objective change provided by the implications of the given variable by fixing it to the given bound 960 * w.r.t. minimum activity of the objective function 961 * 962 * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to 963 * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by the 964 * implications are: 965 * 966 * \f[ 967 * \displaystyle 968 * sum_{x\in I(1)} (1 - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{bestbound}(x) \cdot \mbox{objval}(x) 969 * = 970 * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{bestbound}(x)) \cdot \mbox{objval}(x) 971 * \f] 972 * 973 * This can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local variable bounds (local == TRUE && 974 * bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL) 975 */ 976 static 977 SCIP_RETCODE getMinactImplicObjchg( 978 SCIP* scip, /**< SCIP data structure */ 979 SCIP_VAR* var, /**< variable to computes the objective contribution */ 980 SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */ 981 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */ 982 SCIP_BOUNDTYPE bound, /**< bound to check for */ 983 SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */ 984 SCIP_Real* objchg /**< pointer to store the objective change */ 985 ) 986 { 987 SCIP_VAR* implvar; 988 SCIP_Bool lb; 989 SCIP_Bool ub; 990 int nbinvars; 991 int v; 992 993 assert(SCIPvarIsBinary(var)); 994 assert(!local || SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE) < 0.5); 995 assert(!local || SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE) > 0.5); 996 assert(SCIPvarGetLbGlobal(var) < 0.5); 997 assert(SCIPvarGetUbGlobal(var) > 0.5); 998 assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER); 999 1000 if( bound == SCIP_BOUNDTYPE_LOWER ) 1001 { 1002 v = 0; 1003 nbinvars = objimplics->nlbimpls; 1004 } 1005 else 1006 { 1007 assert(bound == SCIP_BOUNDTYPE_UPPER); 1008 v = objimplics->nlbimpls; 1009 nbinvars = objimplics->nlbimpls + objimplics->nubimpls; 1010 } 1011 1012 /* loop over all implications */ 1013 while( v < nbinvars ) 1014 { 1015 implvar = objimplics->objvars[v]; 1016 assert(implvar != NULL); 1017 assert(!SCIPisZero(scip, SCIPvarGetObj(implvar))); 1018 1019 if( local ) 1020 { 1021 lb = SCIPgetVarLbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5; 1022 ub = SCIPgetVarUbAtIndex(scip, implvar, bdchgidx, FALSE) > 0.5; 1023 1024 /* check if variable is fixed */ 1025 if( lb == TRUE || ub == FALSE ) 1026 { 1027 v++; 1028 continue; 1029 } 1030 } 1031 else 1032 { 1033 lb = SCIPvarGetLbGlobal(implvar) > 0.5; 1034 ub = SCIPvarGetUbGlobal(implvar) > 0.5; 1035 1036 /* check if variable is global fixed; if so remove it from the objective implication data structure and 1037 * continue with the next candidate 1038 */ 1039 if( lb == TRUE || ub == FALSE ) 1040 { 1041 SCIP_CALL( objimplicsDelPos(scip, objimplics, v) ); 1042 nbinvars--; 1043 continue; 1044 } 1045 } 1046 1047 assert(SCIPvarGetObj(implvar) > 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, TRUE, TRUE)); 1048 assert(SCIPvarGetObj(implvar) < 0.0 || SCIPvarsHaveCommonClique(var, (SCIP_Bool) bound, implvar, FALSE, TRUE)); 1049 1050 /* add objective change */ 1051 (*objchg) += REALABS(SCIPvarGetObj(implvar)); 1052 v++; 1053 } 1054 1055 return SCIP_OKAY; 1056 } 1057 1058 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum 1059 * activity of the objective function; additionally it collects all contributors for that objective change; 1060 */ 1061 static 1062 SCIP_RETCODE collectMinactObjchg( 1063 SCIP* scip, /**< SCIP data structure */ 1064 SCIP_VAR* var, /**< variable to computes the objective contribution */ 1065 SCIP_BOUNDTYPE bound, /**< bound to check for */ 1066 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */ 1067 SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables */ 1068 int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */ 1069 SCIP_VAR** contributors, /**< array to store the contriboters */ 1070 SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */ 1071 int* ncontributors, /**< pointer to store number of contributor to the objective contribution */ 1072 SCIP_Real* objchg /**< pointer to store the objective change */ 1073 ) 1074 { 1075 assert(SCIPvarIsBinary(var)); 1076 assert(contributors != NULL); 1077 assert(ncontributors != NULL); 1078 1079 /* collects the contribution of the variable itself w.r.t. the best bound */ 1080 (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound); 1081 1082 (*ncontributors) = 0; 1083 1084 /* add the objective contribution from the implication variable */ 1085 SCIP_CALL( collectMinactImplicVars(scip, var, bound, binobjvarmap, collectedvars, nbinobjvars, contributors, uselesscliques, ncontributors, objchg) ); 1086 1087 return SCIP_OKAY; 1088 } 1089 1090 /** computes for the given binary variable the objective contribution by fixing it to given bound w.r.t. minimum 1091 * activity of the objective function; this can be done w.r.t. global variable bounds (local == FALSE), w.r.t. local 1092 * variable bounds (local == TRUE && bdchgidx == NULL), and w.r.t. given time stamp (local == TRUE && bdchgidx != NULL) 1093 */ 1094 static 1095 SCIP_RETCODE getMinactObjchg( 1096 SCIP* scip, /**< SCIP data structure */ 1097 SCIP_VAR* var, /**< variable to computes the objective contribution */ 1098 SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */ 1099 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, or NULL */ 1100 SCIP_BOUNDTYPE bound, /**< bound to check for */ 1101 SCIP_Bool local, /**< propagate local bounds, otherwise global bounds */ 1102 SCIP_Real* objchg /**< pointer to store the objective change */ 1103 ) 1104 { 1105 assert(SCIPvarIsBinary(var)); 1106 1107 /* collects the contribution of the variable itself w.r.t. the best bound */ 1108 (*objchg) = getVarObjchg(var, SCIPvarGetBestBoundType(var), bound); 1109 1110 /* add the objective contribution from the implication variable */ 1111 SCIP_CALL( getMinactImplicObjchg(scip, var, objimplics, bdchgidx, bound, local, objchg) ); 1112 1113 return SCIP_OKAY; 1114 } 1115 1116 /** returns the global (that means w.r.t. global bounds of the variables) objective change provided by all cliques of 1117 * the given variable by fixing it to the given bound w.r.t. maximum activity of the objective function 1118 * 1119 * Let I(0) and I(1) be all implications of the given variable which follow by fixing it to given bound and evaluate to 1120 * fixing the implication variable to zero (I(0)) or one (I(1)), respectively. The objective change provided by these 1121 * implications are: 1122 * 1123 * \f[ 1124 * \displaystyle 1125 * sum_{x\in I(1)} (1 - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) - sum_{x\in I(1)} \mbox{worst}(x) \cdot \mbox{objval}(x) 1126 * = 1127 * sum_{x\in I(0) \cup I(1)} (\mbox{impliedbound}(x) - \mbox{worstbound}(x)) \cdot \mbox{objval}(x) 1128 * \f] 1129 */ 1130 static 1131 SCIP_RETCODE getMaxactImplicObjchg( 1132 SCIP* scip, /**< SCIP data structure */ 1133 SCIP_VAR* var, /**< variable to computes the objective contribution */ 1134 SCIP_BOUNDTYPE bound, /**< bound to check for */ 1135 SCIP_Real* objchg /**< pointer to store the objective change */ 1136 ) 1137 { 1138 SCIP_Bool varfixing; 1139 int ncliques; 1140 int nvars; 1141 1142 assert(scip != NULL); 1143 assert(SCIPvarIsBinary(var)); 1144 assert(SCIPvarGetLbGlobal(var) < 0.5); 1145 assert(SCIPvarGetUbGlobal(var) > 0.5); 1146 assert(bound == SCIP_BOUNDTYPE_LOWER || bound == SCIP_BOUNDTYPE_UPPER); 1147 assert(objchg != NULL); 1148 1149 varfixing = (SCIP_Bool)bound; 1150 assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/ 1151 assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e506*/ 1152 1153 *objchg = 0.0; 1154 ncliques = SCIPvarGetNCliques(var, varfixing); 1155 1156 if( ncliques > 0 ) 1157 { 1158 SCIP_CLIQUE** cliques; 1159 SCIP_CLIQUE* clique; 1160 SCIP_VAR** clqvars; 1161 SCIP_VAR** probvars; 1162 SCIP_VAR* clqvar; 1163 SCIP_Bool* clqvalues; 1164 int* entries; 1165 int* ids; 1166 SCIP_Real obj; 1167 int nclqvars; 1168 int nentries; 1169 int objmult; 1170 int nids; 1171 int id; 1172 int c; 1173 int v; 1174 1175 assert(SCIPisTransformed(scip)); 1176 1177 nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip) + 1; 1178 1179 SCIP_CALL( SCIPallocBufferArray(scip, &ids, 2*nentries) ); 1180 nids = 0; 1181 /* @todo move this memory allocation to SCIP_SET and add a memory list there, to decrease the number of 1182 * allocations and clear ups 1183 */ 1184 SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) ); 1185 BMSclearMemoryArray(entries, nentries); 1186 1187 cliques = SCIPvarGetCliques(var, varfixing); 1188 assert(cliques != NULL); 1189 1190 /* iterate over all cliques and determine all importantimplications */ 1191 for( c = ncliques - 1; c >= 0; --c ) 1192 { 1193 clique = cliques[c]; 1194 clqvars = SCIPcliqueGetVars(clique); 1195 clqvalues = SCIPcliqueGetValues(clique); 1196 nclqvars = SCIPcliqueGetNVars(clique); 1197 assert(nclqvars > 0); 1198 assert(clqvars != NULL); 1199 assert(clqvalues != NULL); 1200 1201 if( nclqvars > MAX_CLIQUELENGTH ) 1202 continue; 1203 1204 /* iterate over all clique variables */ 1205 for( v = nclqvars - 1; v >= 0; --v ) 1206 { 1207 clqvar = clqvars[v]; 1208 assert(clqvar != NULL); 1209 1210 objmult = (int)!clqvalues[v] - (int)SCIPvarGetWorstBoundType(clqvar); 1211 assert(-1 <= objmult && objmult <= 1); 1212 1213 /* ignore binary variable which are either fixed and were the objective contribution will not be zero */ 1214 if( clqvar != var && objmult != 0 && SCIPvarIsActive(clqvar) && 1215 (SCIPvarGetLbGlobal(clqvar) < 0.5 && SCIPvarGetUbGlobal(clqvar) > 0.5) && !SCIPisZero(scip, SCIPvarGetObj(clqvar)) ) 1216 { 1217 int probindex = SCIPvarGetProbindex(clqvar) + 1; 1218 assert(0 < probindex && probindex < nentries); 1219 1220 /* check that the variable was not yet visited */ 1221 assert(entries[probindex] == 0 || entries[probindex] == objmult); 1222 if( entries[probindex] == 0 ) 1223 { 1224 /* memorize probindex */ 1225 ids[nids] = probindex; 1226 ++nids; 1227 1228 assert(ABS(objmult) == 1); 1229 1230 /* mark variable as visited */ 1231 entries[probindex] = objmult; 1232 } 1233 } 1234 } 1235 } 1236 1237 probvars = SCIPgetVars(scip); 1238 assert(probvars != NULL); 1239 1240 /* add all implied objective values */ 1241 for( v = nids - 1; v >= 0; --v ) 1242 { 1243 id = ids[v]; 1244 assert(0 < id && id < nentries); 1245 assert(entries[id] != 0); 1246 1247 clqvar = probvars[id - 1]; 1248 assert(clqvar != NULL); 1249 assert(SCIPvarIsBinary(clqvar)); 1250 assert(SCIPvarIsActive(clqvar)); 1251 assert(SCIPvarGetLbGlobal(clqvar) < 0.5); 1252 assert(SCIPvarGetUbGlobal(clqvar) > 0.5); 1253 1254 obj = SCIPvarGetObj(clqvar); 1255 assert(!SCIPisZero(scip, obj)); 1256 1257 *objchg += entries[id] * obj; 1258 } 1259 1260 /* free temporary memory */ 1261 SCIPfreeBufferArray(scip, &entries); 1262 SCIPfreeBufferArray(scip, &ids); 1263 } 1264 1265 #ifdef SCIP_MORE_DEBUG 1266 SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques is %g\n", SCIPvarGetName(var), 1267 varfixing, *objchg); 1268 #endif 1269 1270 /* collect non-binary implication information */ 1271 nvars = SCIPvarGetNImpls(var, varfixing); 1272 1273 if( nvars > 0 ) 1274 { 1275 SCIP_VAR** vars; 1276 SCIP_VAR* implvar; 1277 SCIP_Real* bounds; 1278 SCIP_BOUNDTYPE* boundtypes; 1279 SCIP_Real obj; 1280 SCIP_Real lb; 1281 SCIP_Real ub; 1282 int v; 1283 1284 vars = SCIPvarGetImplVars(var, varfixing); 1285 boundtypes = SCIPvarGetImplTypes(var, varfixing); 1286 bounds = SCIPvarGetImplBounds(var, varfixing); 1287 1288 for( v = nvars - 1; v >= 0; --v ) 1289 { 1290 implvar = vars[v]; 1291 assert(implvar != NULL); 1292 1293 lb = SCIPvarGetLbLocal(implvar); 1294 ub = SCIPvarGetUbLocal(implvar); 1295 obj = SCIPvarGetObj(implvar); 1296 1297 /* ignore binary variable which are fixed or not of column status */ 1298 if( SCIPisZero(scip, obj) ) 1299 continue; 1300 1301 /* add up objective change if applicable */ 1302 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGT(scip, bounds[v], lb) ) 1303 *objchg += (bounds[v] - lb)*obj; 1304 else if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPvarGetWorstBoundType(implvar) == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLT(scip, bounds[v], ub) ) 1305 *objchg += (bounds[v] - ub)*obj; 1306 } 1307 } 1308 1309 #ifdef SCIP_MORE_DEBUG 1310 SCIPdebugMsg(scip, "objective contribution when variable <%s> fixed to %u using cliques and implications is %g\n", SCIPvarGetName(var), 1311 varfixing, *objchg); 1312 #endif 1313 1314 return SCIP_OKAY; 1315 } 1316 1317 /** computes for the given binary variable the gloabl (that means w.r.t. global bounds of the variables) objective 1318 * contribution by fixing it to given bound w.r.t. maximum activity of the objective function 1319 */ 1320 static 1321 SCIP_RETCODE getMaxactObjchg( 1322 SCIP* scip, /**< SCIP data structure */ 1323 SCIP_VAR* var, /**< variable to computes the objective contribution */ 1324 SCIP_BOUNDTYPE bound, /**< bound to check for */ 1325 SCIP_Bool useimplics, /**< should implications be used */ 1326 SCIP_Real* objchg /**< pointer to store the objective change */ 1327 ) 1328 { 1329 assert(scip != NULL); 1330 assert(SCIPvarIsBinary(var)); 1331 assert(objchg != NULL); 1332 1333 *objchg = 0; 1334 1335 /* check if the implications should be used to increase the objective contribution for given variable */ 1336 if( useimplics ) 1337 { 1338 /* using cliques and @todo other implications */ 1339 SCIP_CALL( getMaxactImplicObjchg(scip, var, bound, objchg) ); 1340 } 1341 1342 /* collects the contribution of the variable itself w.r.t. the worst bound */ 1343 *objchg += getVarObjchg(var, SCIPvarGetWorstBoundType(var), bound); 1344 1345 return SCIP_OKAY; 1346 } 1347 1348 /** reset variables array which marks variables which are collected */ 1349 static 1350 void resetContributors( 1351 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */ 1352 SCIP_Bool* collectedvars, /**< temporary buffer to mark collected variables which should be reset */ 1353 SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */ 1354 int ncontributors /**< number of contributors */ 1355 ) 1356 { 1357 SCIP_VAR* var; 1358 int pos; 1359 int c; 1360 1361 for( c = 0; c < ncontributors; ++c ) 1362 { 1363 var = contributors[c]; 1364 assert(var != NULL); 1365 1366 assert(SCIPhashmapExists(binobjvarmap, var)); 1367 pos = SCIPhashmapGetImageInt(binobjvarmap, var); 1368 assert(pos > 0); 1369 collectedvars[pos] = FALSE; 1370 } 1371 } 1372 1373 /** check if the given variable should be collected for the minimum activity propagation */ 1374 static 1375 SCIP_RETCODE collectMinactVar( 1376 SCIP* scip, /**< SCIP data structure */ 1377 SCIP_VAR* var, /**< variable to check */ 1378 SCIP_OBJIMPLICS** objimplics, /**< pointer to store the objective implication data structure w.r.t. minimum activity */ 1379 SCIP_Bool useimplics, /**< should implications be used */ 1380 SCIP_HASHMAP* binobjvarmap, /**< hash map mapping binary variables with none-zero objective to position in collected variables arrays */ 1381 SCIP_Bool* collectedlbvars, /**< temporary buffer to mark collected variables for lower bound fixing */ 1382 SCIP_Bool* collectedubvars, /**< temporary buffer to mark collected variables for upper bound fixing */ 1383 int nbinobjvars, /**< number of binary variables with non-zero objective coefficient */ 1384 SCIP_VAR** contributors, /**< temporary buffer to use for collecting contributors */ 1385 SCIP_HASHTABLE* uselesscliques, /**< hash table to store useless cliques, or NULL */ 1386 SCIP_Bool* collect /**< pointer to store if the variable should be stored */ 1387 ) 1388 { 1389 SCIP_Real lbobjchg; 1390 SCIP_Real ubobjchg; 1391 SCIP_Real objval; 1392 int nlbcliques; 1393 int nubcliques; 1394 1395 assert(objimplics != NULL); 1396 1397 objval = SCIPvarGetObj(var); 1398 (*objimplics) = NULL; 1399 1400 if( SCIPisZero(scip, objval) ) 1401 (*collect) = FALSE; 1402 else 1403 (*collect) = TRUE; 1404 1405 nlbcliques = SCIPvarGetNCliques(var, FALSE); 1406 nubcliques = SCIPvarGetNCliques(var, TRUE); 1407 1408 /* check if implications should be used and if implications are existing */ 1409 if( useimplics && nlbcliques + nubcliques > 0 ) 1410 { 1411 int nlbcontributors; 1412 int nubcontributors; 1413 1414 assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/ 1415 assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e506*/ 1416 1417 /* get contribution of variable by fixing it to its lower bound w.r.t. minimum activity of the objective function */ 1418 SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, binobjvarmap, collectedlbvars, nbinobjvars, 1419 contributors, uselesscliques, &nlbcontributors, &lbobjchg) ); 1420 assert(!SCIPisNegative(scip, lbobjchg)); 1421 1422 SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var), 1423 SCIP_BOUNDTYPE_LOWER, 0, nlbcontributors); 1424 1425 /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since 1426 * this is covered by that implied variable 1427 */ 1428 if( !(*collect) && nlbcontributors == 1 ) 1429 { 1430 /* reset lower bound contributors */ 1431 resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors); 1432 1433 assert(SCIPisZero(scip, objval)); 1434 nlbcontributors = 0; 1435 } 1436 1437 /* get contribution of variable by fixing it to its upper bound w.r.t. minimum activity of the objective function */ 1438 SCIP_CALL( collectMinactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, binobjvarmap, collectedubvars, nbinobjvars, 1439 &contributors[nlbcontributors], uselesscliques, &nubcontributors, &ubobjchg) ); 1440 assert(!SCIPisNegative(scip, ubobjchg)); 1441 1442 SCIPdebugMsg(scip, "variable <%s> fixed to bound=%d implies %d(%d)\n", SCIPvarGetName(var), 1443 SCIP_BOUNDTYPE_UPPER, 0, nubcontributors); 1444 1445 /* ignore implications if the variable has a zero objective coefficient and implications only one variable, since 1446 * this is covered by that implied variable 1447 */ 1448 if( !(*collect) && nubcontributors == 1 ) 1449 { 1450 /* reset upper bound contributors */ 1451 resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors); 1452 1453 assert(SCIPisZero(scip, objval)); 1454 nubcontributors = 0; 1455 } 1456 1457 if( (*collect) || nlbcontributors > 1 || nubcontributors > 1 ) 1458 { 1459 /* creates an objective implication data structure, fixes (globally) variables which are implied by lower and upper 1460 * bound fixing, and clears the collected arrays for lower and upper bound 1461 */ 1462 SCIP_CALL( objimplicsCreate(scip, objimplics, contributors, binobjvarmap, collectedlbvars, collectedubvars, lbobjchg, ubobjchg, nlbcontributors, nubcontributors) ); 1463 (*collect) = TRUE; 1464 } 1465 else 1466 { 1467 /* reset lower bound contributors */ 1468 resetContributors(binobjvarmap, collectedlbvars, contributors, nlbcontributors); 1469 1470 /* reset upper bound contributors */ 1471 resetContributors(binobjvarmap, collectedubvars, &contributors[nlbcontributors], nubcontributors); 1472 } 1473 } 1474 else if( (*collect) ) 1475 { 1476 lbobjchg = getVarObjchg(var, SCIPvarGetBestBoundType(var), SCIP_BOUNDTYPE_LOWER); 1477 ubobjchg = getVarObjchg(var, SCIPvarGetBestBoundType(var), SCIP_BOUNDTYPE_UPPER); 1478 assert(!SCIPisZero(scip, lbobjchg) || !SCIPisZero(scip, ubobjchg)); 1479 assert(!SCIPisNegative(scip, lbobjchg)); 1480 assert(!SCIPisNegative(scip, ubobjchg)); 1481 1482 /* creates an "empty" objective implication data structure */ 1483 SCIP_CALL( objimplicsCreate(scip, objimplics, NULL, NULL, NULL, NULL, lbobjchg, ubobjchg, 0, 0) ); 1484 } 1485 1486 return SCIP_OKAY; 1487 } 1488 1489 /** check if the given variable should be collected for the maximum activity propagation */ 1490 static 1491 SCIP_RETCODE collectMaxactVar( 1492 SCIP* scip, /**< SCIP data structure */ 1493 SCIP_VAR* var, /**< variable to check */ 1494 SCIP_Bool useimplics, /**< should implications be used */ 1495 SCIP_Real* objchg, /**< pointer to store the objective change w.r.t. maximum activity */ 1496 SCIP_Bool* isnotzero /**< pointer to store if the objective change is unequal to zero or not */ 1497 ) 1498 { 1499 SCIP_Real lbobjchg; 1500 SCIP_Real ubobjchg; 1501 1502 assert(scip != NULL); 1503 assert(SCIPvarIsBinary(var)); 1504 assert(objchg != NULL); 1505 assert(isnotzero != NULL); 1506 1507 /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */ 1508 SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) ); 1509 assert(!SCIPisPositive(scip, lbobjchg)); 1510 1511 /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */ 1512 SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) ); 1513 assert(!SCIPisPositive(scip, ubobjchg)); 1514 1515 (*objchg) = MIN(lbobjchg, ubobjchg); 1516 1517 /* only consider variables with non-zero objective contribution */ 1518 if( SCIPisZero(scip, (*objchg)) ) 1519 *isnotzero = FALSE; 1520 else 1521 *isnotzero = TRUE; 1522 1523 return SCIP_OKAY; 1524 } 1525 1526 /** initializate the propagator */ 1527 static 1528 SCIP_RETCODE propdataInit( 1529 SCIP* scip, /**< SCIP data structure */ 1530 SCIP_PROPDATA* propdata /**< propagator data */ 1531 ) 1532 { 1533 SCIP_VAR** vars; 1534 SCIP_VAR* var; 1535 SCIP_HASHMAP* binobjvarmap; 1536 int nvars; 1537 int nbinvars; 1538 int nintvars; 1539 int nminactvars; 1540 int nmaxactvars; 1541 int nobjintvars; 1542 int nobjcontvars; 1543 int nobjvars; 1544 int nbinobjvars; 1545 int v; 1546 1547 assert(scip != NULL); 1548 assert(propdata != NULL); 1549 1550 /* get problem variables */ 1551 vars = SCIPgetVars(scip); 1552 nvars = SCIPgetNVars(scip); 1553 nintvars = nvars - SCIPgetNContVars(scip); 1554 1555 nbinvars = 0; 1556 nobjvars = 0; 1557 nbinobjvars = 0; 1558 1559 SCIP_CALL( SCIPhashmapCreate(&binobjvarmap, SCIPblkmem(scip), SCIPgetNObjVars(scip)) ); 1560 1561 /* count and collect variable problem indices of variables with non-zero objective coefficient */ 1562 for( v = 0; v < nvars; ++v ) 1563 { 1564 var = vars[v]; 1565 assert(var != NULL); 1566 1567 if( !SCIPisZero(scip, SCIPvarGetObj(var)) ) 1568 { 1569 nobjvars++; 1570 1571 if( SCIPvarIsBinary(var) ) 1572 { 1573 SCIP_CALL( SCIPhashmapInsertInt(binobjvarmap, (void*)var, nbinobjvars + 1) ); 1574 nbinobjvars++; 1575 } 1576 } 1577 1578 if( SCIPvarIsBinary(var) ) 1579 nbinvars++; 1580 } 1581 1582 nminactvars = 0; 1583 nmaxactvars = 0; 1584 nobjintvars = 0; 1585 nobjcontvars = 0; 1586 1587 if( nobjvars > 0 ) 1588 { 1589 SCIP_EVENTHDLR* eventhdlr; 1590 SCIP_OBJIMPLICS* objimplics; 1591 SCIP_HASHTABLE* uselesscliques; 1592 SCIP_VAR** contributors; 1593 SCIP_Bool* collectedlbvars; 1594 SCIP_Bool* collectedubvars; 1595 SCIP_Bool collect; 1596 SCIP_Bool useimplics; 1597 SCIP_Real objval; 1598 SCIP_Real objchg; 1599 1600 eventhdlr = propdata->eventhdlr; 1601 assert(eventhdlr != NULL); 1602 1603 useimplics = (propdata->propuseimplics && nbinobjvars < propdata->maximplvars); 1604 1605 /* allocate memory for all arrays */ 1606 propdata->minactsize = nbinvars; 1607 propdata->maxactsize = nbinvars; 1608 propdata->objintvarssize = nobjvars - nbinobjvars; 1609 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize) ); 1610 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize) ); 1611 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize) ); 1612 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize) ); 1613 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize) ); 1614 1615 if( useimplics ) 1616 { 1617 int ncliques; 1618 1619 /* create temporary buffer */ 1620 /* we store both lb and ub contributors in array contributors, and both could be nbinobjvars, we need twice that size */ 1621 SCIP_CALL( SCIPallocBufferArray(scip, &contributors, 2 * nbinobjvars) ); 1622 /* @todo: use SCIPallocCleanBufferArray instead? */ 1623 SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedlbvars, nbinobjvars+1) ); 1624 /* @todo: use SCIPallocCleanBufferArray instead? */ 1625 SCIP_CALL( SCIPallocClearBufferArray(scip, &collectedubvars, nbinobjvars+1) ); 1626 1627 ncliques = SCIPgetNCliques(scip); 1628 1629 if( ncliques > 0 ) 1630 { 1631 SCIP_CALL( SCIPhashtableCreate(&uselesscliques, SCIPblkmem(scip), ncliques, 1632 cliqueGetHashkey, cliqueIsHashkeyEq, cliqueGetHashkeyVal, NULL) ); 1633 } 1634 else 1635 uselesscliques = NULL; 1636 } 1637 else 1638 { 1639 contributors = NULL; 1640 collectedlbvars = NULL; 1641 collectedubvars = NULL; 1642 uselesscliques = NULL; 1643 } 1644 1645 /* collect the variables with non-zero objective contribution and catch global bound tighten events that decrease the 1646 * maximal pseudo objective activity 1647 */ 1648 for( v = 0; v < nvars && (nobjintvars == 0 || nobjintvars < propdata->objintvarssize); ++v ) 1649 { 1650 var = vars[v]; 1651 assert(var != NULL); 1652 1653 objval = SCIPvarGetObj(var); 1654 1655 if( SCIPvarIsBinary(var) ) 1656 { 1657 /* ignore variables which are globally fixed */ 1658 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 ) 1659 { 1660 #ifndef NDEBUG 1661 /* check that the binary implications are applied for binary variables which are globally fixed */ 1662 checkImplicsApplied(scip, var); 1663 #endif 1664 continue; 1665 } 1666 1667 /* check if the variable should be collected for the minimum activity propagation */ 1668 SCIP_CALL( collectMinactVar(scip, var, &objimplics, useimplics, binobjvarmap, collectedlbvars, collectedubvars, 1669 nbinobjvars, contributors, uselesscliques, &collect) ); 1670 1671 if( collect ) 1672 { 1673 assert(nminactvars < nbinvars); 1674 assert(objimplics != NULL); 1675 assert(objimplics->nlbimpls + objimplics->nubimpls <= nbinobjvars); 1676 1677 /* collect the binary variable with non-zero objective contribution */ 1678 propdata->minactvars[nminactvars] = var; 1679 propdata->minactimpls[nminactvars] = objimplics; 1680 nminactvars++; 1681 1682 /* catch bound relax event for the binary variable to handel the firstnonfixed index correctly */ 1683 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDRELAXED, eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) ); 1684 1685 SCIPdebugMsg(scip, "variable <%s>[obj: <%g>] implicit objective change %g\n", 1686 SCIPvarGetName(var), objval, objimplics->maxobjchg); 1687 1688 /* captures the variable */ 1689 SCIP_CALL( SCIPcaptureVar(scip, var) ) ; 1690 } 1691 /* check if the variable should be collected for the maximum activity propagation */ 1692 SCIP_CALL( collectMaxactVar(scip, var, useimplics, &objchg, &collect) ); 1693 1694 if( collect ) 1695 { 1696 assert(nmaxactvars < nbinvars); 1697 1698 /* collect the binary variable with non-zero objective contribution */ 1699 propdata->maxactvars[nmaxactvars] = var; 1700 propdata->maxactchgs[nmaxactvars] = -objchg; 1701 nmaxactvars++; 1702 1703 /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum 1704 * activity of the objective function changed 1705 */ 1706 SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) ); 1707 1708 /* captures the variable */ 1709 SCIP_CALL( SCIPcaptureVar(scip, var) ) ; 1710 } 1711 } 1712 else 1713 { 1714 /* only consider non-binary variables with a non-zero objective */ 1715 if( SCIPisZero(scip, objval) ) 1716 continue; 1717 1718 assert(nobjintvars < propdata->objintvarssize); 1719 1720 propdata->objintvars[nobjintvars] = var; 1721 nobjintvars++; 1722 1723 if( v >= nintvars ) 1724 nobjcontvars++; 1725 1726 /* catch bound change events if the variable has a non-zero objective coefficient to check if the maximum 1727 * activity of the objective function changed 1728 */ 1729 SCIP_CALL( catchObjEvent(scip, propdata, eventhdlr, var) ); 1730 1731 /* captures the variable */ 1732 SCIP_CALL( SCIPcaptureVar(scip, var) ); 1733 } 1734 } 1735 1736 if( useimplics ) 1737 { 1738 if( uselesscliques != NULL ) 1739 SCIPhashtableFree(&uselesscliques); 1740 1741 SCIPfreeBufferArray(scip, &collectedubvars); 1742 SCIPfreeBufferArray(scip, &collectedlbvars); 1743 SCIPfreeBufferArray(scip, &contributors); 1744 } 1745 1746 if( nminactvars == 0 ) 1747 { 1748 SCIPfreeBlockMemoryArray(scip, &propdata->minactvars, propdata->minactsize); 1749 SCIPfreeBlockMemoryArray(scip, &propdata->minactimpls, propdata->minactsize); 1750 propdata->minactsize = 0; 1751 propdata->minactvars = NULL; 1752 propdata->minactimpls = NULL; 1753 } 1754 else 1755 { 1756 /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for 1757 * the minimum activity of the objective function 1758 */ 1759 SCIPsortDownPtrPtr((void**)propdata->minactimpls, (void**)propdata->minactvars, objimplicsComp, nminactvars); 1760 1761 SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the minimum activity of the objective function\n", nminactvars); 1762 } 1763 1764 if( nmaxactvars == 0 ) 1765 { 1766 SCIPfreeBlockMemoryArray(scip, &propdata->maxactvars, propdata->maxactsize); 1767 SCIPfreeBlockMemoryArray(scip, &propdata->maxactchgs, propdata->maxactsize); 1768 propdata->maxactsize = 0; 1769 propdata->maxactvars = NULL; 1770 propdata->maxactchgs = NULL; 1771 } 1772 else 1773 { 1774 /* sort binary variables with respect to the absolute value of their maximal potential objective contribution for 1775 * the maximum activity of the objective function 1776 */ 1777 SCIPsortDownRealPtr(propdata->maxactchgs, (void**)propdata->maxactvars, nmaxactvars); 1778 1779 SCIPdebugMsg(scip, "%d binary variables with non-zero objective contribution w.r.t. the maximum activity of the objective function\n", nmaxactvars); 1780 } 1781 1782 if( nobjintvars == 0 ) 1783 { 1784 SCIPfreeBlockMemoryArray(scip, &propdata->objintvars, propdata->objintvarssize); 1785 propdata->objintvarssize = 0; 1786 propdata->objintvars = NULL; 1787 } 1788 else 1789 { 1790 /* sort integer variables with respect to the absolute value of their objective coefficient */ 1791 SCIPsortDownPtr((void**)propdata->objintvars, varCompObj, nobjintvars - nobjcontvars); 1792 1793 /* sort continuous variables with respect to the absolute value of their objective coefficient */ 1794 SCIPsortDownPtr((void**)(&propdata->objintvars[nobjintvars - nobjcontvars]), varCompObj, nobjcontvars); 1795 1796 SCIPdebugMsg(scip, "%d integer variables and %d continuous variables with non-zero objective contribution\n", 1797 nobjintvars - nobjcontvars, nobjcontvars); 1798 } 1799 } 1800 1801 SCIPhashmapFree(&binobjvarmap); 1802 1803 propdata->nminactvars = nminactvars; 1804 propdata->nmaxactvars = nmaxactvars; 1805 propdata->nobjintvars = nobjintvars; 1806 propdata->maxpseudoobjact = SCIP_INVALID; 1807 propdata->maxpseudoobjactinf = 0; 1808 propdata->lastvarnum = -1; 1809 propdata->glbfirstnonfixed = 0; 1810 propdata->maxactfirstnonfixed = 0; 1811 propdata->firstnonfixed = 0; 1812 propdata->nnewvars = 0; 1813 propdata->cutoffbound = SCIPinfinity(scip); 1814 propdata->lastlowerbound = -SCIPinfinity(scip); 1815 propdata->glbpseudoobjval = -SCIPinfinity(scip); 1816 1817 propdata->initialized = TRUE; 1818 1819 /* due to scaling after presolving we need to update the global pseudoactivity and the cutoffbound */ 1820 propdata->glbpropagated = FALSE; 1821 propdata->glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip); 1822 propdata->cutoffbound = SCIPgetCutoffbound(scip); 1823 assert(SCIPgetDepth(scip) > 0 || SCIPisFeasEQ(scip, propdata->glbpseudoobjval, SCIPgetPseudoObjval(scip))); 1824 1825 /* create hash table which is used for resolving bound changes */ 1826 if( nminactvars > 0 ) 1827 { 1828 SCIP_CALL( SCIPhashtableCreate(&propdata->addedvars, SCIPblkmem(scip), nvars, 1829 SCIPvarGetHashkey, SCIPvarIsHashkeyEq, SCIPvarGetHashkeyVal, NULL) ); 1830 } 1831 else 1832 propdata->addedvars = NULL; 1833 1834 return SCIP_OKAY; 1835 } 1836 1837 /** adds for the given non-binary variable a conflict bound depending on its objective contribution */ 1838 static 1839 SCIP_RETCODE addConflictBounds( 1840 SCIP* scip, /**< SCIP data structure */ 1841 SCIP_VAR* var, /**< variable to check for objective contribution */ 1842 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 1843 SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */ 1844 ) 1845 { 1846 SCIP_Real objval; 1847 1848 objval = SCIPvarGetObj(var); 1849 assert(!SCIPisZero(scip, objval)); 1850 1851 if( objval > 0.0 ) 1852 { 1853 SCIP_Real loclb; 1854 SCIP_Real glblb; 1855 1856 glblb = SCIPvarGetLbGlobal(var); 1857 loclb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE); 1858 assert(SCIPisFeasGE(scip, loclb, glblb)); 1859 1860 /* check if the local lower bound (at time stamp bdchgidx) is larger than the global lower bound */ 1861 if( SCIPisGT(scip, loclb, glblb) ) 1862 { 1863 SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g>\n", SCIPvarGetName(var), objval, loclb); 1864 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) ); 1865 1866 /* hard comparison is enough to make requiredpseudoobjval nonincreasing */ 1867 assert((loclb - glblb) * objval > 0.0); 1868 1869 (*reqpseudoobjval) -= (loclb - glblb) * objval; 1870 } 1871 } 1872 else 1873 { 1874 SCIP_Real locub; 1875 SCIP_Real glbub; 1876 1877 glbub = SCIPvarGetUbGlobal(var); 1878 locub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE); 1879 assert(SCIPisFeasLE(scip, locub, glbub)); 1880 1881 /* check if the local upper bound (at time stamp bdchgidx) is smaller than the global upper bound */ 1882 if( SCIPisLT(scip, locub, glbub) ) 1883 { 1884 SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g>\n", SCIPvarGetName(var), objval, locub); 1885 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) ); 1886 1887 /* hard comparison is enough to make requiredpseudoobjval nonincreasing */ 1888 assert((locub - glbub) * objval > 0.0); 1889 1890 (*reqpseudoobjval) -= (locub - glbub) * objval; 1891 } 1892 } 1893 1894 return SCIP_OKAY; 1895 } 1896 1897 /** check for the given implication variables if they also contribute to the required minimum activity */ 1898 static 1899 SCIP_RETCODE getConflictImplics( 1900 SCIP* scip, /**< SCIP data structure */ 1901 SCIP_VAR** vars, /**< variable to check for objective contribution */ 1902 int start, /**< start index */ 1903 int end, /**< end index */ 1904 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 1905 SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already added directly or implicitly due to implications */ 1906 SCIP_Real* reqpseudoobjval, /**< pointer to store the remaining minimum activity which has to be proven */ 1907 SCIP_Bool* foundimplics /**< pointer to store if an implication is found */ 1908 ) 1909 { 1910 SCIP_VAR* var; 1911 SCIP_Real lb; 1912 SCIP_Real ub; 1913 int v; 1914 1915 assert(foundimplics != NULL); 1916 assert(*foundimplics == FALSE); 1917 1918 for( v = start; v < end; ++v ) 1919 { 1920 var = vars[v]; 1921 assert(var != NULL); 1922 assert(SCIPvarIsBinary(var)); 1923 1924 /* we need to take the bounds after the bdchgidx here, since the variable of the bound change may be the implied one; 1925 * we already counted its contribution before, so we want to see it as fixed here, which it is after the bound change. 1926 */ 1927 lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE); 1928 ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE); 1929 1930 if( lb < 0.5 && ub > 0.5 && !SCIPhashtableExists(addedvars, (void*)var) ) 1931 { 1932 (*reqpseudoobjval) -= REALABS(SCIPvarGetObj(var)); 1933 SCIPdebugMsg(scip, " implicated variables <%s>[%g] bdchgidx [%g,%g] -> remaining <%g>\n", SCIPvarGetName(var), SCIPvarGetObj(var), lb, ub, *reqpseudoobjval); 1934 1935 SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) ); 1936 assert(SCIPhashtableExists(addedvars, (void*)var)); 1937 (*foundimplics) = TRUE; 1938 } 1939 } 1940 1941 return SCIP_OKAY; 1942 } 1943 1944 /** adds for the given binary variable a conflict bound depending on its objective contribution */ 1945 static 1946 SCIP_RETCODE addConflictBinvar( 1947 SCIP* scip, /**< SCIP data structure */ 1948 SCIP_VAR* var, /**< variable to check for objective contribution */ 1949 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 1950 SCIP_OBJIMPLICS* objimplics, /**< objective implication data for the given variable */ 1951 SCIP_HASHTABLE* addedvars, /**< hash table containing variables which are already add directly or implicitly due to implications */ 1952 SCIP_Bool respropuseimplics, /**< should implications be used */ 1953 SCIP_Real* reqpseudoobjval /**< pointer to store the remaining minimum activity which has to be proven */ 1954 ) 1955 { 1956 SCIP_Real objval; 1957 SCIP_Real lb; 1958 SCIP_Real ub; 1959 SCIP_Bool foundimplics; 1960 1961 assert(SCIPvarIsBinary(var)); 1962 1963 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5 ) 1964 return SCIP_OKAY; 1965 1966 lb = SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE); 1967 ub = SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE); 1968 1969 objval = SCIPvarGetObj(var); 1970 foundimplics = FALSE; 1971 1972 /* only consider variables which are fixed */ 1973 if( lb > 0.5 ) 1974 { 1975 if( respropuseimplics ) 1976 { 1977 assert(objimplics != NULL); 1978 SCIP_CALL( getConflictImplics(scip, objimplics->objvars, objimplics->nlbimpls, objimplics->nlbimpls + objimplics->nubimpls, 1979 bdchgidx, addedvars, reqpseudoobjval, &foundimplics) ); 1980 } 1981 1982 /* check if the binary variable has a positive contribution (positive objective coefficient since it is fixed to 1983 * one) or is needed due a positive contribution of an implied variable 1984 */ 1985 if( foundimplics || SCIPisPositive(scip, objval) ) 1986 { 1987 SCIPdebugMsg(scip, " add bound change <%s>[%g] >= <%g> bdchgidx [%g,%g]\n", SCIPvarGetName(var), objval, lb, lb, ub); 1988 SCIP_CALL( SCIPaddConflictLb(scip, var, NULL) ); 1989 1990 (*reqpseudoobjval) -= MAX(0.0, objval); 1991 1992 if( addedvars != NULL ) 1993 { 1994 assert(!SCIPhashtableExists(addedvars, (void*)var)); 1995 SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) ); 1996 } 1997 } 1998 } 1999 else if( ub < 0.5 ) 2000 { 2001 if( respropuseimplics ) 2002 { 2003 assert(objimplics != NULL); 2004 SCIP_CALL( getConflictImplics(scip, objimplics->objvars, 0, objimplics->nlbimpls, 2005 bdchgidx, addedvars, reqpseudoobjval, &foundimplics) ); 2006 } 2007 2008 /* check if the binary variable has a positive contribution (negative objective coefficient since it is fixed to 2009 * zero) or is needed due a positive contribution of an implied variable 2010 */ 2011 if( foundimplics || SCIPisNegative(scip, objval) ) 2012 { 2013 SCIPdebugMsg(scip, " add bound change <%s>[%g] <= <%g> bdchgidx=[%g,%g]\n", SCIPvarGetName(var), objval, ub, lb, ub); 2014 SCIP_CALL( SCIPaddConflictUb(scip, var, NULL) ); 2015 2016 (*reqpseudoobjval) += MIN(0.0, objval); 2017 2018 if( addedvars != NULL ) 2019 { 2020 assert(!SCIPhashtableExists(addedvars, (void*)var)); 2021 SCIP_CALL( SCIPhashtableInsert(addedvars, (void*)var) ); 2022 } 2023 } 2024 } 2025 2026 return SCIP_OKAY; 2027 } 2028 2029 2030 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the 2031 * cutoff bound 2032 */ 2033 static 2034 SCIP_RETCODE adjustCutoffbound( 2035 SCIP* scip, /**< SCIP data structure */ 2036 SCIP_PROPDATA* propdata, /**< propagator data */ 2037 SCIP_VAR* var, /**< variable that was deduced */ 2038 int inferinfo, /**< inference information */ 2039 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */ 2040 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */ 2041 SCIP_HASHTABLE* addedvars, /**< hash table which contains variables which are already added or implicitly given as reason for the resolve, or NULL */ 2042 SCIP_Real* cutoffbound /**< pointer to store the adjusted cutoff bound */ 2043 ) 2044 { 2045 if( inferinfo != -1 ) 2046 { 2047 SCIP_OBJIMPLICS* objimplics; 2048 int start; 2049 int end; 2050 2051 assert(var != NULL); 2052 assert(SCIPvarIsBinary(var)); 2053 assert(bdchgidx != NULL); 2054 assert(SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE))); 2055 assert(inferinfo >= 0); 2056 assert(inferinfo < propdata->nminactvars); 2057 assert((SCIP_Bool)SCIP_BOUNDTYPE_LOWER == FALSE); /*lint !e506*/ 2058 assert((SCIP_Bool)SCIP_BOUNDTYPE_UPPER == TRUE); /*lint !e506*/ 2059 2060 objimplics = propdata->minactimpls[inferinfo]; 2061 assert(objimplics != NULL); 2062 2063 /* get the objective contribution if we would fix the binary inference variable to its other bound */ 2064 (*cutoffbound) -= getVarObjchg(var, SCIPvarGetBestBoundType(var), boundtype); 2065 2066 if( boundtype == SCIP_BOUNDTYPE_LOWER ) 2067 { 2068 start = 0; 2069 end = objimplics->nlbimpls; 2070 } 2071 else 2072 { 2073 start = objimplics->nlbimpls; 2074 end = objimplics->nlbimpls + objimplics->nubimpls; 2075 } 2076 2077 if( addedvars != NULL ) 2078 { 2079 SCIP_Bool foundimplics = FALSE; 2080 SCIP_CALL( getConflictImplics(scip, objimplics->objvars, start, end, bdchgidx, addedvars, cutoffbound, &foundimplics) ); 2081 } /*lint !e438*/ 2082 } 2083 else 2084 { 2085 SCIP_Real glbbound; 2086 SCIP_Real newbound; 2087 SCIP_Real objval; 2088 2089 objval = SCIPvarGetObj(var); 2090 2091 assert(!SCIPisZero(scip, objval)); 2092 2093 if( objval > 0.0 ) 2094 { 2095 newbound = SCIPgetVarUbAtIndex(scip, var, bdchgidx, TRUE); 2096 glbbound = SCIPvarGetLbGlobal(var); 2097 } 2098 else 2099 { 2100 newbound = SCIPgetVarLbAtIndex(scip, var, bdchgidx, TRUE); 2101 glbbound = SCIPvarGetUbGlobal(var); 2102 } 2103 2104 /* in case the variable is integral we just need to prove the newbound plus/minus (1 - epsilon) since the this bound 2105 * would be rounded to newbound due to integrability which is global information 2106 */ 2107 if( SCIPvarIsIntegral(var) ) 2108 { 2109 if( objval > 0.0 ) 2110 newbound += 1 - 10 * SCIPfeastol(scip); 2111 else 2112 newbound -= 1 - 10 * SCIPfeastol(scip); 2113 } 2114 2115 /* adjust the cutoff bound by the portion the inference variable contributes to the presudo objective activity 2116 * (minactivity) 2117 */ 2118 assert(!SCIPisNegative(scip, objval * (newbound - glbbound))); 2119 (*cutoffbound) -= objval * (newbound - glbbound); 2120 } 2121 2122 return SCIP_OKAY; 2123 } 2124 2125 2126 /** resolves a propagation by supplying the variables whose bound changes increased the pseudo objective value above the 2127 * cutoff bound 2128 */ 2129 static 2130 SCIP_RETCODE resolvePropagation( 2131 SCIP* scip, /**< SCIP data structure */ 2132 SCIP_PROPDATA* propdata, /**< propagator data */ 2133 SCIP_Real cutoffbound, /**< the global cutoff */ 2134 SCIP_VAR* infervar, /**< variable that was deduced, or NULL for conflict analysis initialization */ 2135 int inferinfo, /**< inference information */ 2136 SCIP_BOUNDTYPE boundtype, /**< the type of the changed bound (lower or upper bound) */ 2137 SCIP_BDCHGIDX* bdchgidx /**< bound change index (time stamp of bound change), or NULL for current time */ 2138 ) 2139 { 2140 SCIP_HASHTABLE* addedvars; 2141 SCIP_VAR** vars; 2142 SCIP_VAR* var; 2143 SCIP_Real glbpseudoobjval; 2144 SCIP_Real reqpseudoobjval; 2145 SCIP_Bool infinity; 2146 int nvars; 2147 int v; 2148 2149 infinity = FALSE; 2150 addedvars = NULL; 2151 nvars = propdata->nminactvars; 2152 2153 /* the global pseudo value gives us a global valid minimal activity 2154 * 2155 * @note The global pseudo objective activity can be minus infinity. In that case all variable are part of the 2156 * reason/explanation 2157 * 2158 * @note If the global pseudo objective activity is greater than the required minactivity, the local bound change 2159 * which has to explained is actually (now) a global one. That means, the reason/explanation is empty 2160 */ 2161 glbpseudoobjval = SCIPgetGlobalPseudoObjval(scip); 2162 2163 if( SCIPisInfinity(scip, -glbpseudoobjval) ) 2164 { 2165 infinity = TRUE; 2166 reqpseudoobjval = cutoffbound; 2167 } 2168 else 2169 { 2170 /* clear hash table for storing variables which are not needed to add the reason due to global implications or 2171 * already added 2172 */ 2173 if( nvars > 0 ) 2174 { 2175 addedvars = propdata->addedvars; 2176 SCIPhashtableRemoveAll(addedvars); 2177 } 2178 2179 if( infervar != NULL ) 2180 { 2181 SCIP_CALL( adjustCutoffbound(scip, propdata, infervar, inferinfo, boundtype, bdchgidx, addedvars, &cutoffbound) ); 2182 } 2183 2184 reqpseudoobjval = cutoffbound - glbpseudoobjval; 2185 } 2186 2187 SCIPdebugMsg(scip, "resolve propagation global pseudo objective <%g>, cutoff bounda <%g>, required minactivity <%g>\n", 2188 glbpseudoobjval, cutoffbound, reqpseudoobjval); 2189 2190 /* the variables responsible for the propagation are the ones with 2191 * - obj > 0 and local lb > global lb 2192 * - obj < 0 and local ub < global ub 2193 * 2194 * collect all variables which contribute positively to the pseudo objective value (minimum activity) until we 2195 * reached the (adjusted) required minimum activity for the inference bound change 2196 */ 2197 2198 /* first, consider the binary variables */ 2199 if( nvars > 0 ) 2200 { 2201 SCIP_OBJIMPLICS** minactimpls; 2202 2203 vars = propdata->minactvars; 2204 assert(vars != NULL); 2205 2206 minactimpls = propdata->minactimpls; 2207 assert(minactimpls != NULL); 2208 2209 #ifndef NDEBUG 2210 checkGlbfirstnonfixed(propdata); 2211 #endif 2212 2213 if( infinity ) 2214 { 2215 /* if the required minimum activity is minus infinity, we have to add all variables which contribute the local 2216 * pseudo objective activity 2217 */ 2218 2219 for( v = propdata->glbfirstnonfixed; v < nvars; ++v ) 2220 { 2221 var = vars[v]; 2222 assert(var != NULL); 2223 2224 /* @note binary variables can have a zero objective value */ 2225 2226 if( var == infervar ) 2227 continue; 2228 2229 SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, NULL, NULL, FALSE, &reqpseudoobjval) ); 2230 } 2231 } 2232 else 2233 { 2234 assert(addedvars != NULL); 2235 2236 for( v = propdata->glbfirstnonfixed; v < nvars && SCIPisPositive(scip, reqpseudoobjval); ++v ) 2237 { 2238 var = vars[v]; 2239 assert(var != NULL); 2240 2241 /* @note binary variables can have a zero objective value */ 2242 2243 if( var == infervar ) 2244 continue; 2245 2246 if( SCIPhashtableExists(addedvars, (void*)var) ) 2247 continue; 2248 2249 SCIP_CALL( addConflictBinvar(scip, var, bdchgidx, minactimpls[v], addedvars, propdata->respropuseimplics, &reqpseudoobjval) ); 2250 } 2251 } 2252 } 2253 2254 vars = propdata->objintvars; 2255 nvars = propdata->nobjintvars; 2256 assert(nvars == 0 || vars != NULL); 2257 2258 /* second, consider the non-binary variables */ 2259 for( v = 0; v < nvars && (infinity || SCIPisPositive(scip, reqpseudoobjval)); ++v ) 2260 { 2261 var = vars[v]; 2262 assert(var != NULL); 2263 assert(!SCIPisZero(scip, SCIPvarGetObj(var))); 2264 2265 if( var == infervar ) 2266 continue; 2267 2268 SCIP_CALL( addConflictBounds(scip, var, bdchgidx, &reqpseudoobjval) ); 2269 } 2270 2271 return SCIP_OKAY; 2272 } 2273 2274 /** propagates the given variable against the cutoff bound */ 2275 static 2276 SCIP_RETCODE propagateCutoffboundVar( 2277 SCIP* scip, /**< SCIP data structure */ 2278 SCIP_PROP* prop, /**< propagator, or NULL */ 2279 SCIP_VAR* var, /**< variable to propagate */ 2280 int inferinfo, /**< inference information to store with the bound change */ 2281 SCIP_Real objchg, /**< objective change */ 2282 SCIP_Real cutoffbound, /**< cutoff bound to use */ 2283 SCIP_Real pseudoobjval, /**< pseudo objective value to use */ 2284 SCIP_Bool local, /**< local or global propagation */ 2285 SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */ 2286 ) 2287 { 2288 SCIP_Real lb; 2289 SCIP_Real ub; 2290 SCIP_Real newbd; 2291 SCIP_Bool infeasible; 2292 2293 assert(!SCIPisZero(scip, objchg)); 2294 assert(!SCIPisInfinity(scip, -pseudoobjval)); 2295 assert(!SCIPisInfinity(scip, cutoffbound)); 2296 assert(SCIPisLT(scip, pseudoobjval, cutoffbound) ); 2297 assert(tightened != NULL); 2298 2299 *tightened = FALSE; 2300 2301 /* collect bounds of the variable */ 2302 if( local ) 2303 { 2304 assert(prop != NULL); 2305 lb = SCIPvarGetLbLocal(var); 2306 ub = SCIPvarGetUbLocal(var); 2307 } 2308 else 2309 { 2310 lb = SCIPvarGetLbGlobal(var); 2311 ub = SCIPvarGetUbGlobal(var); 2312 } 2313 2314 if( SCIPisFeasEQ(scip, lb, ub) ) 2315 return SCIP_OKAY; 2316 2317 /* depending on the objective contribution we can try to tighten the lower or upper bound of the variable */ 2318 if( objchg > 0.0 ) 2319 { 2320 SCIP_Real QUAD(newbdq); 2321 2322 /* the new variable bound is lb + (cutoffbound - pseudoobjval) / objchg */ 2323 SCIPquadprecSumDD(newbdq, cutoffbound, -pseudoobjval); 2324 SCIPquadprecDivQD(newbdq, newbdq, objchg); 2325 SCIPquadprecSumQD(newbdq, newbdq, lb); 2326 newbd = QUAD_TO_DBL(newbdq); 2327 2328 if( local ) 2329 { 2330 SCIP_CALL( SCIPinferVarUbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) ); 2331 assert(!infeasible); 2332 2333 if( *tightened ) /* might not be tightened due to numerical reasons */ 2334 { 2335 SCIPdebugMsg(scip, " -> new (local) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n", 2336 SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound); 2337 } 2338 } 2339 else 2340 { 2341 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) ); 2342 assert(!infeasible); 2343 2344 if( *tightened ) 2345 { 2346 SCIPdebugMsg(scip, " -> new (global) upper bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n", 2347 SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound); 2348 } 2349 } 2350 } 2351 else 2352 { 2353 SCIP_Real QUAD(newbdq); 2354 2355 /* the new variable bound is ub + (cutoffbound - pseudoobjval) / objchg */ 2356 SCIPquadprecSumDD(newbdq, cutoffbound, -pseudoobjval); 2357 SCIPquadprecDivQD(newbdq, newbdq, objchg); 2358 SCIPquadprecSumQD(newbdq, newbdq, ub); 2359 newbd = QUAD_TO_DBL(newbdq); 2360 2361 if( local ) 2362 { 2363 SCIP_CALL( SCIPinferVarLbProp(scip, var, newbd, prop, inferinfo, FALSE, &infeasible, tightened) ); 2364 assert(!infeasible); 2365 2366 if( *tightened ) /* might not be tightened due to numerical reasons */ 2367 { 2368 SCIPdebugMsg(scip, " -> new (local) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n", 2369 SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound); 2370 } 2371 } 2372 else 2373 { 2374 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, &infeasible, tightened) ); 2375 assert(!infeasible); 2376 2377 if( *tightened ) 2378 { 2379 SCIPdebugMsg(scip, " -> new (global) lower bound of variable <%s>[%g,%g]: %g, objective change <%g>, pseudo objective <%g>, cutoff bound <%g>\n", 2380 SCIPvarGetName(var), lb, ub, newbd, objchg, pseudoobjval, cutoffbound); 2381 } 2382 } 2383 } 2384 2385 return SCIP_OKAY; 2386 } 2387 2388 /** propagates the given binary variable against the cutoff bound */ 2389 static 2390 SCIP_RETCODE propagateCutoffboundBinvar( 2391 SCIP* scip, /**< SCIP data structure */ 2392 SCIP_PROP* prop, /**< propagator, or NULL */ 2393 SCIP_VAR* var, /**< variable to propagate */ 2394 int pos, /**< position of the variable in the corresponding propdata variable array */ 2395 SCIP_Real cutoffbound, /**< cutoff bound to use */ 2396 SCIP_Real pseudoobjval, /**< pseudo objective value to use */ 2397 SCIP_Bool* tightened, /**< pointer to store if the variable domain was tightened */ 2398 SCIP_Bool* cutoff, /**< pointer to store if a cutoff was detected */ 2399 SCIP_Bool local /**< propagate local bounds, otherwise global bounds */ 2400 ) 2401 { 2402 SCIP_PROPDATA* propdata; 2403 SCIP_OBJIMPLICS* objimplics; 2404 SCIP_Real lbobjchg; 2405 SCIP_Real ubobjchg; 2406 SCIP_Real objchg; 2407 2408 assert(SCIPvarIsBinary(var)); 2409 2410 propdata = SCIPpropGetData(prop); 2411 assert(propdata != NULL); 2412 2413 objimplics = propdata->minactimpls[pos]; 2414 assert(objimplics != NULL); 2415 2416 /* get objective change in case of fixing the variable to its lower bound (that is zero) */ 2417 SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_LOWER, local, &lbobjchg) ); 2418 assert(!SCIPisNegative(scip, lbobjchg)); 2419 2420 /* get objective change in case of fixing the variable to its upper bound (that is one) */ 2421 SCIP_CALL( getMinactObjchg(scip, var, objimplics, NULL, SCIP_BOUNDTYPE_UPPER, local, &ubobjchg) ); 2422 assert(!SCIPisNegative(scip, ubobjchg)); 2423 2424 (*tightened) = FALSE; 2425 2426 /* nothing can be done if the objective contribution is zero independently of the bound */ 2427 if( SCIPisZero(scip, lbobjchg) && SCIPisZero(scip, ubobjchg) ) 2428 return SCIP_OKAY; 2429 2430 /* if the lbobjchg and ubobjchg are both able to fix the variable to its upper (1.0) or lower (0.0) bound, 2431 * respectively, we detected an cutoff 2432 * 2433 * @note There is no need to use SCIPisFeasLT() in case the objective is integral since the cutoff bound in that case 2434 * is the upper bound minus 1 plus the SCIPcutoffbounddelta() (which is MIN(100.0 * feastol, 0.0001)). However, 2435 * if the objective is not integral we have to check w.r.t. an epsilon to avoid numerical problems. 2436 */ 2437 if( SCIPisFeasLT(scip, cutoffbound, pseudoobjval + ubobjchg) && SCIPisFeasLT(scip, cutoffbound, pseudoobjval + lbobjchg) ) 2438 { 2439 /* check if conflict analysis is applicable */ 2440 if( local && SCIPisConflictAnalysisApplicable(scip) ) 2441 { 2442 assert(SCIPgetDepth(scip) > 0); 2443 2444 /* initialize conflict analysis */ 2445 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, TRUE) ); 2446 2447 /* add all variable whose best bound changes increased the pseudo objective value above to cutoff bound */ 2448 SCIP_CALL( resolvePropagation(scip, propdata, pseudoobjval, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) ); 2449 2450 /* analyze the conflict */ 2451 SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) ); 2452 } 2453 2454 (*cutoff) = TRUE; 2455 } 2456 else 2457 { 2458 /* try to tighten the variable bound use the larger objective contribution */ 2459 if( lbobjchg > ubobjchg ) 2460 objchg = -lbobjchg; 2461 else 2462 objchg = ubobjchg; 2463 2464 SCIP_CALL( propagateCutoffboundVar(scip, prop, var, pos, objchg, cutoffbound, pseudoobjval, local, tightened) ); 2465 } 2466 2467 return SCIP_OKAY; 2468 } 2469 2470 /** globally propagates if a new cutoff bound or global pseudo objective value (minimum activity of the objective 2471 * function) is available 2472 */ 2473 static 2474 SCIP_RETCODE propagateCutoffboundGlobally( 2475 SCIP* scip, /**< SCIP data structure */ 2476 SCIP_PROP* prop, /**< propagator */ 2477 int* nchgbds, /**< pointer to store the number of bound changes */ 2478 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 2479 ) 2480 { 2481 SCIP_PROPDATA* propdata; 2482 SCIP_VAR** minactvars; 2483 SCIP_VAR** objintvars; 2484 SCIP_VAR* var; 2485 SCIP_Bool tightened; 2486 SCIP_Real pseudoobjval; 2487 SCIP_Real cutoffbound; 2488 int nminactvars; 2489 int nobjintvars; 2490 int v; 2491 2492 /* this method should not be called in the root node of the search tree since the standard propagation already does 2493 * the job 2494 */ 2495 assert(SCIPgetDepth(scip) > 0); 2496 2497 propdata = SCIPpropGetData(prop); 2498 assert(propdata != NULL); 2499 2500 pseudoobjval = SCIPgetGlobalPseudoObjval(scip); 2501 cutoffbound = propdata->cutoffbound; 2502 2503 /* nothing can be done if the global pseudo objective is minus infinity */ 2504 if( SCIPisInfinity(scip, -pseudoobjval) ) 2505 return SCIP_OKAY; 2506 2507 /* check if the global pseudo objective value (minimum activity of the objective function) is greater or equal to 2508 * the cutoff bound 2509 */ 2510 if( SCIPisGE(scip, pseudoobjval, cutoffbound) ) 2511 { 2512 *cutoff = TRUE; 2513 return SCIP_OKAY; 2514 } 2515 2516 minactvars = propdata->minactvars; 2517 objintvars = propdata->objintvars; 2518 nminactvars = propdata->nminactvars; 2519 nobjintvars = propdata->nobjintvars; 2520 2521 #ifndef NDEBUG 2522 checkGlbfirstnonfixed(propdata); 2523 #endif 2524 2525 *cutoff = FALSE; 2526 2527 /* always propagate the binary variables completely */ 2528 for( v = propdata->glbfirstnonfixed; v < nminactvars; ++v ) 2529 { 2530 var = minactvars[v]; 2531 assert(var != NULL); 2532 2533 /* check if the variables is already globally fixed; if so continue with the potential candidate */ 2534 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 2535 continue; 2536 2537 /* propagates the cutoff bound for the given binary variable */ 2538 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) ); 2539 2540 /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective 2541 * contribution w.r.t. minimum activity (pseudo objective value) of the objective function; these values are the 2542 * increase in the pseudo objective activity we would get if we fix the variable to its worse bound; hence, we can 2543 * stop if for a variable this potential increase is not enough too exceed the cutoff bound; 2544 */ 2545 if( !tightened ) 2546 { 2547 SCIPdebugMsg(scip, "interrupt global pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n", 2548 cutoffbound, v, nminactvars); 2549 break; 2550 } 2551 2552 if( *cutoff ) 2553 return SCIP_OKAY; 2554 2555 /* @note The variable might not be globally fixed right away since this would destroy the local internal 2556 * data structure of a search node; the bound change is in that case pending; hence we cannot assert 2557 * that the variable is globally fixed 2558 */ 2559 (*nchgbds)++; 2560 } 2561 propdata->glbfirstnonfixed = v; 2562 propdata->firstnonfixed = MAX(propdata->firstnonfixed, v); 2563 2564 /* check all binary variables which could potentially be fixed */ 2565 for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v ) 2566 { 2567 var = minactvars[v]; 2568 assert(var != NULL); 2569 2570 /* check if the variables is already globally fixed; if so continue with the potential candidate */ 2571 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 2572 continue; 2573 2574 /* propagates the cutoff bound for the given binary variable */ 2575 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) ); 2576 2577 /* check if the domain of the variable was reduced */ 2578 if( tightened ) 2579 (*nchgbds)++; 2580 2581 if( *cutoff ) 2582 return SCIP_OKAY; 2583 } 2584 2585 #if 0 /* might fail, but is not a real error, still need to investigate */ 2586 #ifndef NDEBUG 2587 /* check that the abort criteria for the binary variables works */ 2588 for( ; v < nminactvars; ++v ) 2589 { 2590 assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg); 2591 2592 var = minactvars[v]; 2593 assert(var != NULL); 2594 2595 /* check if the variable is already locally fixed; in that case we just continue with the next potential 2596 * candidate 2597 */ 2598 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 2599 continue; 2600 2601 /* propagates the cutoff bound for the given binary variable */ 2602 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, FALSE) ); 2603 assert(!tightened); 2604 assert(!(*cutoff)); 2605 } 2606 #endif 2607 #endif 2608 2609 /* propagate the non-binary variables completely */ 2610 for( v = 0; v < nobjintvars; ++v ) 2611 { 2612 var = objintvars[v]; 2613 assert(var != NULL); 2614 assert(!SCIPisZero(scip, SCIPvarGetObj(var))); 2615 2616 /* try to tighten the bound of the variable */ 2617 SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, SCIPvarGetObj(var), cutoffbound, pseudoobjval, FALSE, &tightened) ); 2618 2619 /* check if the domain of the variable was reduced */ 2620 if( tightened ) 2621 (*nchgbds)++; 2622 } 2623 2624 propdata->glbpropagated = TRUE; 2625 2626 return SCIP_OKAY; 2627 } 2628 2629 /** propagates the cutoff bound for binary variables (c*x <= cutoff) */ 2630 static 2631 SCIP_RETCODE propagateCutoffboundBinvars( 2632 SCIP* scip, /**< SCIP data structure */ 2633 SCIP_PROP* prop, /**< propagator */ 2634 SCIP_Real cutoffbound, /**< cutoff bound to use */ 2635 SCIP_Real pseudoobjval, /**< pseudo objective value to use */ 2636 int* nfixedvars, /**< pointer to store the number of fixed variables */ 2637 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 2638 ) 2639 { 2640 SCIP_PROPDATA* propdata; 2641 SCIP_VAR** minactvars; 2642 SCIP_VAR* var; 2643 SCIP_Bool tightened; 2644 int nminactvars; 2645 int v; 2646 2647 propdata = SCIPpropGetData(prop); 2648 assert(propdata != NULL); 2649 2650 minactvars = propdata->minactvars; 2651 nminactvars = propdata->nminactvars; 2652 assert(nminactvars == 0 || minactvars != NULL); 2653 2654 /* always propagate the binary variables completely; note that the variables before the firstnonfixed indexed are 2655 * already locally fixed and those before glbfirstnonfixed are already globally fixed 2656 */ 2657 2658 #ifndef NDEBUG 2659 /* check that the variables before glbfirstnonfixed are globally fixed */ 2660 checkGlbfirstnonfixed(propdata); 2661 2662 /* check that the variables before firstnonfixed are locally fixed */ 2663 for( v = propdata->glbfirstnonfixed; v < propdata->firstnonfixed; ++v ) 2664 { 2665 var = minactvars[v]; 2666 assert(var != NULL); 2667 2668 assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5); 2669 } 2670 #endif 2671 2672 (*cutoff) = FALSE; 2673 2674 for( v = propdata->firstnonfixed; v < nminactvars; ++v ) 2675 { 2676 var = minactvars[v]; 2677 assert(var != NULL); 2678 2679 /* check if the variable is already locally fixed; in that case we just continue with the next potential 2680 * candidate 2681 */ 2682 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5) 2683 continue; 2684 2685 /* propagates the cutoff bound for the given binary variable */ 2686 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) ); 2687 2688 /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective 2689 * contribution w.r.t. minimum activity of the objective function; These values are the increase in the pseudo 2690 * objective activity (minimum activity of the objective function) we would get if we fix the variable to its 2691 * worse bound; hence, we can stop if for a variable this potential increase is not enough too exceed the cutoff 2692 * bound; 2693 */ 2694 if( !tightened ) 2695 { 2696 SCIPdebugMsg(scip, "interrupt local pseudo objective propagation w.r.t. cutoff bound <%.15g> for binary variables after %d from %d binary variables\n", 2697 cutoffbound, v, nminactvars); 2698 break; 2699 } 2700 2701 if( *cutoff ) 2702 return SCIP_OKAY; 2703 2704 /* check that the binary variable is locally fixed */ 2705 assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5); 2706 (*nfixedvars)++; 2707 } 2708 propdata->firstnonfixed = v; 2709 2710 /* check all binary variables which could potentially be fixed */ 2711 for( ; v < nminactvars && cutoffbound - pseudoobjval < propdata->minactimpls[v]->maxobjchg; ++v ) 2712 { 2713 var = minactvars[v]; 2714 assert(var != NULL); 2715 2716 /* check if the variable is already locally fixed; in that case we just continue with the next potential 2717 * candidate 2718 */ 2719 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5) 2720 continue; 2721 2722 /* propagates the cutoff bound for the given binary variable */ 2723 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) ); 2724 2725 if( tightened ) 2726 { 2727 assert(SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5); 2728 (*nfixedvars)++; 2729 } 2730 2731 if( *cutoff ) 2732 return SCIP_OKAY; 2733 } 2734 2735 #if 0 /* might fail, but is not a real error, still need to investigate */ 2736 #ifndef NDEBUG 2737 /* check that the abort criteria for the binary variables works */ 2738 for( ; v < nminactvars; ++v ) 2739 { 2740 var = minactvars[v]; 2741 assert(var != NULL); 2742 2743 assert(cutoffbound - pseudoobjval >= propdata->minactimpls[v]->maxobjchg); 2744 2745 /* check if the variable is already locally fixed; in that case we just continue with the next potential 2746 * candidate 2747 */ 2748 if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5) 2749 continue; 2750 2751 /* propagates the cutoff bound for the given binary variable */ 2752 SCIP_CALL( propagateCutoffboundBinvar(scip, prop, var, v, cutoffbound, pseudoobjval, &tightened, cutoff, TRUE) ); 2753 assert(!tightened); 2754 assert(!(*cutoff)); 2755 } 2756 #endif 2757 #endif 2758 2759 return SCIP_OKAY; 2760 } 2761 2762 /** propagates the cutoff bound c*x <= cutoff */ 2763 static 2764 SCIP_RETCODE propagateCutoffbound( 2765 SCIP* scip, /**< SCIP data structure */ 2766 SCIP_PROP* prop, /**< propagator */ 2767 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 2768 ) 2769 { 2770 SCIP_PROPDATA* propdata; 2771 SCIP_Real pseudoobjval; 2772 SCIP_Real cutoffbound; 2773 SCIP_Bool cutoff; 2774 SCIP_Bool tightened; 2775 int nchgbds; 2776 2777 assert(result != NULL); 2778 2779 (*result) = SCIP_DIDNOTRUN; 2780 2781 propdata = SCIPpropGetData(prop); 2782 assert(propdata != NULL); 2783 2784 /* get current pseudo objective value (minimum activity of the objective function) and cutoff bound */ 2785 pseudoobjval = SCIPgetPseudoObjval(scip); 2786 if( SCIPisInfinity(scip, -pseudoobjval) ) 2787 return SCIP_OKAY; 2788 cutoffbound = SCIPgetCutoffbound(scip); 2789 if( SCIPisInfinity(scip, cutoffbound) ) 2790 return SCIP_OKAY; 2791 2792 /* @note A new global pseudo objective value could be used to retrieve global fixings. There is, however, no need to 2793 * check if a new global pseudo objective value is available. This is the case since a new (better) global 2794 * pseudo activity implies that a global bound change was performed. That causes that the root node of the 2795 * search tree gets marked for repropagation. That will result in a propagation call of the pseudo objective 2796 * propagator. 2797 */ 2798 2799 /* check current cutoff bound */ 2800 if( cutoffbound < propdata->cutoffbound ) 2801 { 2802 propdata->glbpropagated = FALSE; 2803 propdata->cutoffbound = cutoffbound; 2804 } 2805 2806 nchgbds = 0; 2807 cutoff = FALSE; 2808 (*result) = SCIP_DIDNOTFIND; 2809 2810 /* check if we have a new cutoff bound; in that case we globally propagate this new bound 2811 * 2812 * @note there is no need to propagate the cutoff bound if we are in the root node since this will be done by the 2813 * standard local propagation 2814 */ 2815 if( propdata->propcutoffbound && !propdata->glbpropagated && SCIPgetDepth(scip) > 0 ) 2816 { 2817 /* first globally propagate new cutoff bound or pseudo objective activity */ 2818 SCIP_CALL( propagateCutoffboundGlobally(scip, prop, &nchgbds, &cutoff) ); 2819 2820 if( cutoff ) 2821 { 2822 /* we are done with solving since a global pseudo activity is greater or equal to the cutoff bound */ 2823 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) ); 2824 2825 (*result) = SCIP_CUTOFF; 2826 return SCIP_OKAY; 2827 } 2828 2829 /* check if the global propagation cut off the active/current node */ 2830 if( SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip) ) 2831 { 2832 (*result) = SCIP_CUTOFF; 2833 return SCIP_OKAY; 2834 } 2835 } 2836 2837 /* check if the pseudo objective value (minimum activity of the objective function) is greater or equal to the cutoff 2838 * bound 2839 */ 2840 if( SCIPisGE(scip, pseudoobjval, cutoffbound) ) 2841 { 2842 SCIPdebugMsg(scip, "pseudo objective value <%g> exceeds cutoff bound <%g>\n", pseudoobjval, cutoffbound); 2843 2844 /* check if conflict analysis is applicable */ 2845 if( SCIPisConflictAnalysisApplicable(scip) ) 2846 { 2847 assert(SCIPgetDepth(scip) > 0); 2848 2849 /* initialize conflict analysis */ 2850 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, TRUE) ); 2851 2852 /* add all variable whose best bound changes increased the pseudo objective value above the cutoff bound */ 2853 SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, NULL, -1, SCIP_BOUNDTYPE_UPPER, NULL) ); 2854 2855 /* analyze the conflict */ 2856 SCIP_CALL( SCIPanalyzeConflict(scip, 0, NULL) ); 2857 } 2858 (*result) = SCIP_CUTOFF; 2859 2860 return SCIP_OKAY; 2861 } 2862 2863 SCIPdebugMsg(scip, "propagating pseudo objective function (pseudoobj: %g, cutoffbound: %g)\n", pseudoobjval, cutoffbound); 2864 2865 /* propagate binary variables */ 2866 SCIP_CALL( propagateCutoffboundBinvars(scip, prop, cutoffbound, pseudoobjval, &nchgbds, &cutoff) ); 2867 2868 if( cutoff ) 2869 { 2870 (*result) = SCIP_CUTOFF; 2871 return SCIP_OKAY; 2872 } 2873 2874 /* tighten domains of non-binary variables, if they would increase the pseudo objective value above the cutoff 2875 * bound 2876 */ 2877 if( propdata->propfullinroot && SCIPgetDepth(scip) == 0 ) 2878 { 2879 SCIP_VAR** objintvars; 2880 SCIP_VAR* var; 2881 SCIP_Real objval; 2882 int nobjintvars; 2883 int v; 2884 2885 objintvars = propdata->objintvars; 2886 nobjintvars = propdata->nobjintvars; 2887 assert(nobjintvars == 0 || objintvars != NULL); 2888 2889 /* propagate all non-binary variables */ 2890 for( v = 0; v < nobjintvars; ++v ) 2891 { 2892 var = objintvars[v]; 2893 assert(var != NULL); 2894 2895 objval = SCIPvarGetObj(var); 2896 assert(!SCIPisZero(scip, objval)); 2897 2898 /* try to tighten the bound of the variable */ 2899 SCIP_CALL( propagateCutoffboundVar(scip, NULL, var, -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) ); 2900 2901 /* check if the domain of the variable was reduced */ 2902 if( tightened ) 2903 nchgbds++; 2904 } 2905 } 2906 else 2907 { 2908 SCIP_VAR** objintvars; 2909 SCIP_VAR* var; 2910 SCIP_Real objval; 2911 int nobjintvars; 2912 int nmaxuseless; 2913 int nuseless; 2914 int c; 2915 int v; 2916 2917 objintvars = propdata->objintvars; 2918 nobjintvars = propdata->nobjintvars; 2919 assert(nobjintvars == 0 || objintvars != NULL); 2920 2921 /* compute maximum number of useless propagations before aborting */ 2922 nmaxuseless = MAX(propdata->minuseless, (int)propdata->maxvarsfrac*(nobjintvars)); 2923 2924 nuseless = 0; 2925 v = propdata->lastvarnum; 2926 2927 for( c = 0; c < nobjintvars && nuseless < nmaxuseless; ++c ) 2928 { 2929 v++; 2930 if( v >= nobjintvars ) 2931 v = 0; 2932 2933 var = objintvars[v]; 2934 assert(var != NULL); 2935 2936 objval = SCIPvarGetObj(var); 2937 assert(!SCIPisZero(scip, objval)); 2938 2939 /* try to tighten the bound of the variable */ 2940 SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, &tightened) ); 2941 2942 /* check if the domain of the variable was reduced */ 2943 if( tightened ) 2944 nchgbds++; 2945 else 2946 nuseless++; 2947 } 2948 propdata->lastvarnum = v; 2949 } 2950 2951 /* check if we chanced bounds */ 2952 if( nchgbds > 0 ) 2953 (*result) = SCIP_REDUCEDDOM; 2954 2955 return SCIP_OKAY; 2956 } 2957 2958 /** recalculates the maximum objective pseudoactivity */ 2959 static 2960 void calcMaxObjPseudoactivity( 2961 SCIP* scip, /**< SCIP data structure */ 2962 SCIP_PROPDATA* propdata /**< propagator data */ 2963 ) 2964 { 2965 SCIP_VAR** vars; 2966 SCIP_Real objval; 2967 SCIP_Real contrib; 2968 int nvars; 2969 int v; 2970 2971 assert(propdata != NULL); 2972 2973 /* get problem variables */ 2974 vars = SCIPgetVars(scip); 2975 nvars = SCIPgetNVars(scip); 2976 2977 /* calculate current max pseudo activity and largest contribution */ 2978 propdata->maxpseudoobjact = 0.0; 2979 propdata->maxpseudoobjactinf = 0; 2980 2981 for( v = 0; v < nvars; ++v ) 2982 { 2983 objval = SCIPvarGetObj(vars[v]); 2984 if( SCIPisPositive(scip, objval) ) 2985 { 2986 contrib = SCIPvarGetUbGlobal(vars[v]); 2987 if( !SCIPisInfinity(scip, contrib) ) 2988 contrib *= objval; 2989 } 2990 else if( SCIPisNegative(scip, objval) ) 2991 { 2992 contrib = SCIPvarGetLbGlobal(vars[v]); 2993 if( !SCIPisInfinity(scip, -contrib) ) 2994 contrib *= objval; 2995 else 2996 contrib *= -1.0; 2997 } 2998 else 2999 continue; 3000 3001 if( SCIPisInfinity(scip, contrib) ) 3002 propdata->maxpseudoobjactinf++; 3003 else 3004 propdata->maxpseudoobjact += contrib; 3005 } 3006 } 3007 3008 /** updates the pseudo objective activity if necessary */ 3009 static 3010 void updateMaxObjPseudoactivity( 3011 SCIP* scip, /**< SCIP data structure */ 3012 SCIP_PROPDATA* propdata /**< propagator data */ 3013 ) 3014 { 3015 assert(propdata != NULL); 3016 3017 /* if necessary, calculate the maximum pseudo objective activity */ 3018 if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/ 3019 calcMaxObjPseudoactivity(scip, propdata); 3020 assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/ 3021 } 3022 3023 /** returns the residual pseudo objective activity without the given value */ 3024 static 3025 SCIP_Real getMaxObjPseudoactivityResidualValue( 3026 SCIP* scip, /**< SCIP data structure */ 3027 SCIP_PROPDATA* propdata, /**< propagator data */ 3028 SCIP_Real contrib /**< value to eliminate from pseudo objective activity */ 3029 ) 3030 { 3031 SCIP_Real residual; 3032 3033 assert(propdata != NULL); 3034 3035 /* if necessary, calculate the maximum pseudo objective activity */ 3036 if( propdata->maxpseudoobjact == SCIP_INVALID ) /*lint !e777*/ 3037 calcMaxObjPseudoactivity(scip, propdata); 3038 assert(propdata->maxpseudoobjact != SCIP_INVALID); /*lint !e777*/ 3039 3040 if( SCIPisInfinity(scip, contrib) ) 3041 { 3042 assert(propdata->maxpseudoobjactinf >= 1); 3043 /* check if this variable yields the only infinite contribution */ 3044 if( propdata->maxpseudoobjactinf == 1 ) 3045 residual = propdata->maxpseudoobjact; 3046 else 3047 residual = SCIPinfinity(scip); 3048 } 3049 else 3050 { 3051 /* check if there is an infinite contribution */ 3052 if( propdata->maxpseudoobjactinf >= 1 ) 3053 residual = SCIPinfinity(scip); 3054 else 3055 residual = propdata->maxpseudoobjact - contrib; 3056 } 3057 3058 return residual; 3059 } 3060 3061 /** returns the residual pseudo objective activity */ 3062 static 3063 SCIP_Real getMaxObjPseudoactivityResidual( 3064 SCIP* scip, /**< SCIP data structure */ 3065 SCIP_PROPDATA* propdata, /**< propagator data */ 3066 SCIP_VAR* var /**< variable to get residual activity for */ 3067 ) 3068 { 3069 SCIP_Real objval; 3070 SCIP_Real contrib; 3071 3072 assert(propdata != NULL); 3073 3074 objval = SCIPvarGetObj(var); 3075 if( SCIPvarGetWorstBoundType(var) == SCIP_BOUNDTYPE_UPPER ) 3076 { 3077 contrib = SCIPvarGetUbGlobal(var); 3078 if( !SCIPisInfinity(scip, contrib) ) 3079 contrib *= objval; 3080 } 3081 else 3082 { 3083 assert(SCIPvarGetWorstBoundType(var) == SCIP_BOUNDTYPE_LOWER); 3084 contrib = SCIPvarGetLbGlobal(var); 3085 if( !SCIPisInfinity(scip, -contrib) ) 3086 contrib *= objval; 3087 else 3088 contrib *= -1.0; 3089 } 3090 3091 return getMaxObjPseudoactivityResidualValue(scip, propdata, contrib); 3092 } 3093 3094 /** returns the maximum pseudo objective activity of the objective function */ 3095 static 3096 SCIP_Real getMaxObjPseudoactivity( 3097 SCIP* scip, /**< SCIP data structure */ 3098 SCIP_PROPDATA* propdata /**< propagator data */ 3099 ) 3100 { 3101 return getMaxObjPseudoactivityResidualValue(scip, propdata, 0.0); 3102 } 3103 3104 /** propagates the global domain of the given binary variable against the lower bound (c*x >= lowerbound) */ 3105 static 3106 SCIP_RETCODE propagateLowerboundBinvar( 3107 SCIP* scip, /**< SCIP data structure */ 3108 SCIP_VAR* var, /**< variable to propagate */ 3109 SCIP_Real lowerbound, /**< lower bound to use */ 3110 SCIP_Real maxpseudoobjact, /**< maximum pseudo objective activity */ 3111 SCIP_Bool useimplics, /**< should implications be used */ 3112 SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */ 3113 SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */ 3114 ) 3115 { 3116 SCIP_Real lbobjchg; 3117 SCIP_Real ubobjchg; 3118 3119 assert(SCIPvarIsBinary(var)); 3120 assert(SCIPisDualfeasLE(scip, lowerbound, maxpseudoobjact)); 3121 assert(!SCIPisInfinity(scip, maxpseudoobjact)); 3122 3123 /*@todo Instead of running always over all implications use SCIP_OBJIMPLICS in the same way as for the propagation of 3124 * the minimum activity against the cutoff bound. If so we could use the cliques as well. 3125 */ 3126 3127 /* get contribution of variable by fixing it to its lower bound w.r.t. maximum activity of the objective function */ 3128 SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_LOWER, useimplics, &lbobjchg) ); 3129 assert(!SCIPisPositive(scip, lbobjchg)); 3130 3131 /* get contribution of variable by fixing it to its upper bound w.r.t. maximum activity of the objective function */ 3132 SCIP_CALL( getMaxactObjchg(scip, var, SCIP_BOUNDTYPE_UPPER, useimplics, &ubobjchg) ); 3133 assert(!SCIPisPositive(scip, ubobjchg)); 3134 3135 (*infeasible) = FALSE; 3136 (*tightened) = FALSE; 3137 3138 /* if the maximum activity of the objective function without the contribution of the given variable shrinks below the 3139 * global lower bound, the contribution of the variable is need; hence, we can fix it to corresponding bound globally 3140 */ 3141 if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) && SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) ) 3142 { 3143 /* fixing the variable to zero or one leads to decreases of the maximum activity below the lower bound, hence, we 3144 * detected an cutoff 3145 */ 3146 (*infeasible) = TRUE; 3147 } 3148 else if( SCIPisFeasLT(scip, maxpseudoobjact + lbobjchg, lowerbound) ) 3149 { 3150 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 1.0, FALSE, infeasible, tightened) ); 3151 } 3152 else if( SCIPisFeasLT(scip, maxpseudoobjact + ubobjchg, lowerbound) ) 3153 { 3154 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, 0.0, FALSE, infeasible, tightened) ); 3155 } 3156 3157 return SCIP_OKAY; 3158 } 3159 3160 /** propagates the global domains of the given variable with non-zero objective coefficient against the lower bound 3161 * (c*x >= lowerbound) 3162 */ 3163 static 3164 SCIP_RETCODE propagateLowerboundVar( 3165 SCIP* scip, /**< SCIP data structure */ 3166 SCIP_PROPDATA* propdata, /**< propagator data */ 3167 SCIP_VAR* var, /**< variable to propagate */ 3168 SCIP_Real lowerbound, /**< lower bound to use */ 3169 SCIP_Bool* infeasible, /**< pointer to store if the variable domain got empty, infeasible */ 3170 SCIP_Bool* tightened /**< pointer to store if the variable domain was tightened */ 3171 ) 3172 { 3173 SCIP_Real residual; 3174 SCIP_Real newbd; 3175 SCIP_Real objval; 3176 3177 objval = SCIPvarGetObj(var); 3178 assert(!SCIPisZero(scip, objval)); 3179 3180 (*tightened) = FALSE; 3181 3182 /* get residual pseudo objective activity, that is the pseudo objective activity without the given variable */ 3183 residual = getMaxObjPseudoactivityResidual(scip, propdata, var); 3184 3185 if( SCIPisInfinity(scip, residual) ) 3186 return SCIP_OKAY; 3187 3188 /* compute potential mew bound */ 3189 newbd = (lowerbound - residual) / objval; 3190 3191 /**@note In case the variable is integral we force the update of the new bound */ 3192 3193 if( objval > 0.0 ) 3194 { 3195 SCIP_Real lb; 3196 3197 lb = SCIPvarGetLbGlobal(var); 3198 3199 if( !SCIPvarIsIntegral(var) ) 3200 { 3201 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) ); 3202 } 3203 else if( SCIPisFeasGT(scip, newbd, lb) ) 3204 { 3205 SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, TRUE, infeasible, tightened) ); 3206 } 3207 } 3208 else 3209 { 3210 SCIP_Real ub; 3211 3212 ub = SCIPvarGetUbGlobal(var); 3213 3214 if( !SCIPvarIsIntegral(var) ) 3215 { 3216 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) ); 3217 } 3218 else if( SCIPisFeasLT(scip, newbd, ub) ) 3219 { 3220 SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, TRUE, infeasible, tightened) ); 3221 } 3222 } 3223 3224 return SCIP_OKAY; 3225 } 3226 3227 /** propagates the global lower (dual) bound c*x >= lowerbound */ 3228 static 3229 SCIP_RETCODE propagateLowerbound( 3230 SCIP* scip, /**< SCIP data structure */ 3231 SCIP_PROP* prop, /**< propagator */ 3232 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 3233 ) 3234 { /*lint --e{715}*/ 3235 SCIP_PROPDATA* propdata; 3236 SCIP_Real lowerbound; 3237 SCIP_Real maxpseudoobjact; 3238 SCIP_Bool cutoff; 3239 int nchgbds; 3240 3241 assert(result != NULL); 3242 3243 (*result) = SCIP_DIDNOTRUN; 3244 cutoff = FALSE; 3245 nchgbds = 0; 3246 3247 propdata = SCIPpropGetData(prop); 3248 assert(propdata != NULL); 3249 assert(propdata->nminactvars > 0 || propdata->nobjintvars > 0); 3250 3251 /* check if there is a chance to find a reduction */ 3252 lowerbound = SCIPgetLowerbound(scip); 3253 3254 if( SCIPisInfinity(scip, -lowerbound) ) 3255 return SCIP_OKAY; 3256 3257 /* if the lower bound did not change since the last propagation as well as the global bounds of the variables with a 3258 * non-zero objective coefficient we do nothing since there is no new information available 3259 */ 3260 if( SCIPisLE(scip, lowerbound, propdata->lastlowerbound) && propdata->maxpseudoobjact < SCIP_INVALID ) 3261 return SCIP_OKAY; 3262 3263 /* updates the pseudo objective activity if necessary */ 3264 updateMaxObjPseudoactivity(scip, propdata); 3265 3266 /* if more than one variable contributes an infinity to the maximal pseudo activity we can do nothing */ 3267 assert(propdata->maxpseudoobjact < SCIP_INVALID); 3268 if( propdata->maxpseudoobjactinf > 1 ) 3269 return SCIP_OKAY; 3270 3271 maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata); 3272 assert(!SCIPisInfinity(scip, maxpseudoobjact) || !SCIPisInfinity(scip, lowerbound)); 3273 3274 #ifndef NDEBUG 3275 /* check that the global indices are correct */ 3276 checkGlbfirstnonfixed(propdata); 3277 #endif 3278 3279 /* if the maximum pseudo objective activity is smaller than the lower bound the problem is infeasible */ 3280 if( SCIPisDualfeasLT(scip, maxpseudoobjact, lowerbound) ) 3281 cutoff = TRUE; 3282 else 3283 { 3284 SCIP_VAR** objintvars; 3285 SCIP_VAR* var; 3286 SCIP_Bool tightened; 3287 int nobjintvars; 3288 int v; 3289 3290 if( propdata->maxpseudoobjactinf == 0 && !SCIPisInfinity(scip, maxpseudoobjact) ) 3291 { 3292 SCIP_VAR** maxactvars; 3293 int nmaxactvars; 3294 3295 maxactvars = propdata->maxactvars; 3296 nmaxactvars = propdata->nmaxactvars; 3297 assert(nmaxactvars == 0 || maxactvars != NULL); 3298 3299 for( v = propdata->maxactfirstnonfixed; v < nmaxactvars; ++v ) 3300 { 3301 var = maxactvars[v]; 3302 assert(var != NULL); 3303 assert(SCIPvarIsBinary(var)); 3304 3305 /* check if the variables is already globally fixed; if so continue with the next potential candidate */ 3306 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 3307 continue; 3308 3309 /* try to propagate variable domain globally */ 3310 SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) ); 3311 3312 /* the binary variables are sorted in non-increasing manner w.r.t. the absolute value of their objective 3313 * contribution w.r.t. maximum activity of the objective function; These values are the decrease we would 3314 * get with the maximum pseudo objective activity if we fix the variable to its best bound; hence, we can 3315 * stop if for a variable this potential decrease is not enough anymore to fall below the lower bound. 3316 * 3317 * @note In case a fixing was performed. The variable might not be globally fixed right away since this would 3318 * destroy the local internal data structure of a search node; the bound change is in that case pending; 3319 * hence we cannot assert that the variable is globally fixed 3320 */ 3321 if( !tightened ) 3322 { 3323 assert(!SCIPisInfinity(scip, propdata->maxpseudoobjact)); 3324 SCIPdebugMsg(scip, "interrupt pseudo objective propagation w.r.t. lower bound <%.15g> for binary variables after %d from %d binary variables\n", 3325 lowerbound, v, nmaxactvars); 3326 break; 3327 } 3328 3329 if( cutoff ) 3330 break; 3331 3332 /* update maximum pseudo activity since the previous global bound change might invalidated the maximum 3333 * pseudo activity 3334 */ 3335 maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata); 3336 nchgbds++; 3337 } 3338 3339 /* update globally fixed index if abort criteria was applied */ 3340 propdata->maxactfirstnonfixed = v; 3341 3342 /* check all binary variables which could potentially be fixed */ 3343 for( ; v < nmaxactvars && maxpseudoobjact - lowerbound < propdata->maxactchgs[v] && !cutoff; ++v ) 3344 { 3345 var = maxactvars[v]; 3346 assert(var != NULL); 3347 assert(SCIPvarIsBinary(var)); 3348 3349 /* check if the variables is already globally fixed; if so continue with the potential candidate */ 3350 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 3351 continue; 3352 3353 /* propagates the cutoff bound for the given binary variable */ 3354 SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) ); 3355 3356 if( tightened ) 3357 { 3358 /* update maximum pseudo activity since the previous global bound change might invalidated the maximum 3359 * pseudo activity 3360 */ 3361 maxpseudoobjact = getMaxObjPseudoactivity(scip, propdata); 3362 nchgbds++; 3363 } 3364 } 3365 3366 #if 0 /* might fail, but is not a real error, still need to investigate */ 3367 #ifndef NDEBUG 3368 /* check that the abort criteria for the binary variables works */ 3369 for( ; v < nmaxactvars && !cutoff; ++v ) 3370 { 3371 var = maxactvars[v]; 3372 assert(var != NULL); 3373 assert(SCIPvarIsBinary(var)); 3374 3375 /* check if the variables is already globally fixed; if so continue with the next potential candidate */ 3376 if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5) 3377 continue; 3378 3379 /* try to propagate variable domain globally */ 3380 SCIP_CALL( propagateLowerboundBinvar(scip, var, lowerbound, maxpseudoobjact, propdata->propuseimplics, &cutoff, &tightened) ); 3381 assert(!tightened); 3382 assert(!cutoff); 3383 } 3384 #endif 3385 #endif 3386 } 3387 3388 objintvars = propdata->objintvars; 3389 nobjintvars = propdata->nobjintvars; 3390 assert(nobjintvars == 0 || objintvars != NULL); 3391 3392 /* propagate c*x >= lowerbound for non-binary variables */ 3393 for( v = 0; v < nobjintvars && !cutoff; ++v ) 3394 { 3395 var = objintvars[v]; 3396 assert(var != NULL); 3397 assert(!SCIPisZero(scip, SCIPvarGetObj(var))); 3398 3399 /* try to propagate variable domain globally */ 3400 SCIP_CALL( propagateLowerboundVar(scip, propdata, var, lowerbound, &cutoff, &tightened) ); 3401 3402 if( tightened ) 3403 nchgbds++; 3404 } 3405 } 3406 3407 /* evaluate propagation results */ 3408 if( cutoff ) 3409 { 3410 /* we are done with solving since a global bound change is infeasible: cutoff root node */ 3411 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) ); 3412 (*result) = SCIP_CUTOFF; 3413 } 3414 else if( nchgbds > 0 ) 3415 (*result) = SCIP_REDUCEDDOM; 3416 3417 /* remember the lower bound which we already propagated */ 3418 propdata->lastlowerbound = lowerbound; 3419 3420 return SCIP_OKAY; 3421 } 3422 3423 3424 /* 3425 * Callback methods of propagator 3426 */ 3427 3428 /** copy method for propagator plugins (called when SCIP copies plugins) */ 3429 static 3430 SCIP_DECL_PROPCOPY(propCopyPseudoobj) 3431 { /*lint --e{715}*/ 3432 assert(scip != NULL); 3433 assert(prop != NULL); 3434 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 3435 3436 /* call inclusion method of propagator */ 3437 SCIP_CALL( SCIPincludePropPseudoobj(scip) ); 3438 3439 return SCIP_OKAY; 3440 } 3441 3442 /** destructor of propagator to free user data (called when SCIP is exiting) */ 3443 static 3444 SCIP_DECL_PROPFREE(propFreePseudoobj) 3445 { /*lint --e{715}*/ 3446 SCIP_PROPDATA* propdata; 3447 3448 /* free propagator data */ 3449 propdata = SCIPpropGetData(prop); 3450 SCIPfreeBlockMemory(scip, &propdata); 3451 SCIPpropSetData(prop, NULL); 3452 3453 return SCIP_OKAY; 3454 } 3455 3456 3457 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */ 3458 static 3459 SCIP_DECL_PROPINITSOL(propInitsolPseudoobj) 3460 { 3461 SCIP_PROPDATA* propdata; 3462 3463 propdata = SCIPpropGetData(prop); 3464 assert(propdata != NULL); 3465 3466 /* do nothing if active pricer are present and force flag is not TRUE */ 3467 if( !propdata->force && SCIPgetNActivePricers(scip) > 0 ) 3468 return SCIP_OKAY; 3469 3470 /* if active pricer are present we want to catch the variable added event */ 3471 if( SCIPgetNActivePricers(scip) > 0 ) 3472 { 3473 assert(!propdata->catchvaradded); 3474 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, NULL) ); 3475 propdata->catchvaradded = TRUE; 3476 } 3477 3478 return SCIP_OKAY; 3479 } 3480 3481 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */ 3482 static 3483 SCIP_DECL_PROPEXITSOL(propExitsolPseudoobj) 3484 { /*lint --e{715}*/ 3485 SCIP_PROPDATA* propdata; 3486 3487 propdata = SCIPpropGetData(prop); 3488 assert(propdata != NULL); 3489 3490 if( propdata->catchvaradded ) 3491 { 3492 /* drop the variable added event */ 3493 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_VARADDED, propdata->eventhdlr, (SCIP_EVENTDATA*)propdata, -1) ); 3494 propdata->catchvaradded = FALSE; 3495 } 3496 3497 /* free propagator data */ 3498 SCIP_CALL( propdataExit(scip, propdata) ); 3499 3500 return SCIP_OKAY; 3501 } 3502 3503 3504 /** presolving method of propagator */ 3505 static 3506 SCIP_DECL_PROPPRESOL(propPresolPseudoobj) 3507 { /*lint --e{715}*/ 3508 SCIP_PROPDATA* propdata; 3509 SCIP_VAR** vars; 3510 SCIP_Real cutoffbound; 3511 SCIP_Real pseudoobjval; 3512 int oldnchgbds; 3513 int nvars; 3514 int v; 3515 3516 assert(result != NULL); 3517 3518 propdata = SCIPpropGetData(prop); 3519 assert(propdata != NULL); 3520 3521 (*result) = SCIP_DIDNOTRUN; 3522 3523 /* do nothing if active pricer are present and force flag is not TRUE */ 3524 if( !propdata->force && SCIPgetNActivePricers(scip) > 0 ) 3525 return SCIP_OKAY; 3526 3527 /* do nothing if objective propagation is not allowed */ 3528 if( !SCIPallowWeakDualReds(scip) ) 3529 return SCIP_OKAY; 3530 3531 pseudoobjval = SCIPgetGlobalPseudoObjval(scip); 3532 if( SCIPisInfinity(scip, -pseudoobjval) ) 3533 return SCIP_OKAY; 3534 3535 cutoffbound = SCIPgetCutoffbound(scip); 3536 if( SCIPisInfinity(scip, cutoffbound) ) 3537 return SCIP_OKAY; 3538 3539 if( SCIPisGE(scip, pseudoobjval, cutoffbound) ) 3540 { 3541 (*result) = SCIP_CUTOFF; 3542 return SCIP_OKAY; 3543 } 3544 3545 /* only propagate if a new cutoff bound or global pseudo objective value is available */ 3546 if( cutoffbound < propdata->cutoffbound || pseudoobjval > propdata->glbpseudoobjval ) 3547 { 3548 SCIP_Real objval; 3549 SCIP_Bool tightened; 3550 3551 (*result) = SCIP_DIDNOTFIND; 3552 oldnchgbds = *nchgbds; 3553 3554 /* get the problem variables */ 3555 vars = SCIPgetVars(scip); 3556 nvars = SCIPgetNVars(scip); 3557 3558 /* scan the variables for pseudoobj bound reductions 3559 * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array) 3560 */ 3561 for( v = nvars - 1; v >= 0; --v ) 3562 { 3563 objval = SCIPvarGetObj(vars[v]); 3564 3565 if( SCIPisZero(scip, objval) ) 3566 continue; 3567 3568 SCIP_CALL( propagateCutoffboundVar(scip, NULL, vars[v], -1, objval, cutoffbound, pseudoobjval, FALSE, &tightened) ); 3569 3570 if( tightened ) 3571 (*nchgbds)++; 3572 } 3573 3574 /* evaluate if bound change was detected */ 3575 if( *nchgbds > oldnchgbds ) 3576 (*result) = SCIP_SUCCESS; 3577 3578 /* store the old values */ 3579 propdata->cutoffbound = cutoffbound; 3580 propdata->glbpseudoobjval = pseudoobjval; 3581 propdata->glbpropagated = TRUE; 3582 } 3583 3584 return SCIP_OKAY; 3585 } 3586 3587 /** execution method of propagator */ 3588 static 3589 SCIP_DECL_PROPEXEC(propExecPseudoobj) 3590 { /*lint --e{715}*/ 3591 SCIP_PROPDATA* propdata; 3592 3593 propdata = SCIPpropGetData(prop); 3594 assert(propdata != NULL); 3595 3596 (*result) = SCIP_DIDNOTRUN; 3597 3598 if( SCIPinProbing(scip) ) 3599 return SCIP_OKAY; 3600 3601 if( proptiming == SCIP_PROPTIMING_DURINGLPLOOP && SCIPgetDepth(scip) != 0 ) 3602 return SCIP_OKAY; 3603 3604 /* do nothing if active pricer are present and force flag is not TRUE */ 3605 if( !propdata->force && SCIPgetNActivePricers(scip) > 0 ) 3606 return SCIP_OKAY; 3607 3608 /* do not run if propagation w.r.t. objective is not allowed */ 3609 if( !SCIPallowWeakDualReds(scip) ) 3610 return SCIP_OKAY; 3611 3612 /* check if enough new variable are added (due to column generation to reinitialized the propagator data) */ 3613 if( !propdata->initialized || propdata->nnewvars > propdata->maxnewvars ) 3614 { 3615 /* free current propdata data */ 3616 SCIP_CALL( propdataExit(scip, propdata) ); 3617 3618 /* initialize propdata data from scratch */ 3619 SCIP_CALL( propdataInit(scip, propdata) ); 3620 } 3621 3622 /* nothing to do for zero objective */ 3623 if( propdata->nminactvars == 0 && propdata->nmaxactvars == 0 && propdata->nobjintvars == 0 ) 3624 return SCIP_OKAY; 3625 3626 /* propagate c*x <= cutoff */ 3627 SCIP_CALL( propagateCutoffbound(scip, prop, result) ); 3628 3629 if( (*result) != SCIP_CUTOFF && (propdata->nmaxactvars > 0 || propdata->nobjintvars > 0) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING ) 3630 { 3631 SCIP_RESULT dualresult; 3632 3633 /* propagates the global lower (dual) bound c*x >= lowerbound */ 3634 SCIP_CALL( propagateLowerbound(scip, prop, &dualresult) ); 3635 3636 if( dualresult == SCIP_REDUCEDDOM || dualresult == SCIP_CUTOFF ) 3637 (*result) = dualresult; 3638 } 3639 3640 return SCIP_OKAY; 3641 } 3642 3643 /** propagation conflict resolving method of propagator */ 3644 static 3645 SCIP_DECL_PROPRESPROP(propRespropPseudoobj) 3646 { /*lint --e{715}*/ 3647 SCIP_PROPDATA* propdata; 3648 SCIP_Real cutoffbound; 3649 3650 assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(infervar), SCIPvarGetUbGlobal(infervar))); 3651 3652 propdata = SCIPpropGetData(prop); 3653 assert(propdata != NULL); 3654 3655 cutoffbound = SCIPgetCutoffbound(scip); 3656 assert(!SCIPisInfinity(scip, cutoffbound)); 3657 assert(infervar != NULL); 3658 3659 SCIPdebugMsg(scip, "resolve bound change <%s> %s <%g>(%g), cutoff bound <%g>\n", SCIPvarGetName(infervar), 3660 boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), 3661 SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE), cutoffbound); 3662 3663 /* resolve the propagation of the inference variable w.r.t. required minactivity */ 3664 SCIP_CALL( resolvePropagation(scip, propdata, cutoffbound, infervar, inferinfo, boundtype, bdchgidx) ); 3665 3666 (*result) = SCIP_SUCCESS; 3667 3668 return SCIP_OKAY; 3669 } 3670 3671 3672 /* 3673 * Event handler 3674 */ 3675 3676 /** execution method of bound change event handler */ 3677 static 3678 SCIP_DECL_EVENTEXEC(eventExecPseudoobj) 3679 { /*lint --e{715}*/ 3680 SCIP_PROPDATA* propdata; 3681 SCIP_EVENTTYPE eventtype; 3682 3683 propdata = (SCIP_PROPDATA*)eventdata; 3684 assert(propdata != NULL); 3685 3686 assert(eventhdlr != NULL); 3687 assert(eventdata != NULL); 3688 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 3689 assert(event != NULL); 3690 3691 eventtype = SCIPeventGetType(event); 3692 3693 switch( eventtype ) 3694 { 3695 case SCIP_EVENTTYPE_LBRELAXED: 3696 case SCIP_EVENTTYPE_UBRELAXED: 3697 /* if bound got relaxed we need to start up front for trial of bound tightening */ 3698 propdata->firstnonfixed = 0; 3699 break; 3700 case SCIP_EVENTTYPE_VARADDED: 3701 propdata->nnewvars++; 3702 break; 3703 default: 3704 assert(eventtype == SCIP_EVENTTYPE_GLBCHANGED || eventtype == SCIP_EVENTTYPE_GUBCHANGED); 3705 3706 /* invalidate the maximum pseudo objective activity */ 3707 propdata->maxpseudoobjact = SCIP_INVALID; 3708 propdata->maxpseudoobjactinf = 0; 3709 } 3710 3711 return SCIP_OKAY; 3712 } 3713 3714 3715 /* 3716 * propagator specific interface methods 3717 */ 3718 3719 /** creates the pseudo objective function propagator and includes it in SCIP */ 3720 SCIP_RETCODE SCIPincludePropPseudoobj( 3721 SCIP* scip /**< SCIP data structure */ 3722 ) 3723 { 3724 SCIP_PROPDATA* propdata; 3725 SCIP_PROP* prop; 3726 3727 /* create pseudoobj propagator data */ 3728 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) ); 3729 3730 /* reset propagator data structure */ 3731 propdataReset(propdata); 3732 3733 propdata->eventhdlr = NULL; 3734 /* include event handler for gloabl bound change events and variable added event (in case of pricing) */ 3735 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &propdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 3736 eventExecPseudoobj, NULL) ); 3737 3738 if( propdata->eventhdlr == NULL ) 3739 { 3740 SCIPerrorMessage("event handler for pseudo objective propagator not found\n"); 3741 return SCIP_PLUGINNOTFOUND; 3742 } 3743 3744 /* include propagator */ 3745 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 3746 propExecPseudoobj, 3747 propdata) ); 3748 assert(prop != NULL); 3749 3750 /* set optional callbacks via setter functions */ 3751 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyPseudoobj) ); 3752 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreePseudoobj) ); 3753 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolPseudoobj) ); 3754 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolPseudoobj) ); 3755 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolPseudoobj, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) ); 3756 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropPseudoobj) ); 3757 3758 /* add pseudoobj propagator parameters */ 3759 SCIP_CALL( SCIPaddIntParam(scip, 3760 "propagating/" PROP_NAME "/minuseless", 3761 "minimal number of successive non-binary variable propagations without a bound reduction before aborted", 3762 &propdata->minuseless, TRUE, DEFAULT_MINUSELESS, 0, INT_MAX, NULL, NULL) ); 3763 3764 SCIP_CALL( SCIPaddRealParam(scip, 3765 "propagating/" PROP_NAME "/maxvarsfrac", 3766 "maximal fraction of non-binary variables with non-zero objective without a bound reduction before aborted", 3767 &propdata->maxvarsfrac, TRUE, DEFAULT_MAXVARSFRAC, 0.0, 1.0, NULL, NULL) ); 3768 3769 SCIP_CALL( SCIPaddBoolParam(scip, 3770 "propagating/" PROP_NAME "/propfullinroot", 3771 "whether to propagate all non-binary variables when we are propagating the root node", 3772 &propdata->propfullinroot, TRUE, DEFAULT_PROPFULLINROOT, NULL, NULL) ); 3773 3774 SCIP_CALL( SCIPaddBoolParam(scip, 3775 "propagating/" PROP_NAME "/propcutoffbound", 3776 "propagate new cutoff bound directly globally", 3777 &propdata->propcutoffbound, TRUE, DEFAULT_PROPCUTOFFBOUND, NULL, NULL) ); 3778 3779 SCIP_CALL( SCIPaddBoolParam(scip, 3780 "propagating/" PROP_NAME "/force", 3781 "should the propagator be forced even if active pricer are present?", 3782 &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) ); 3783 3784 SCIP_CALL( SCIPaddIntParam(scip, 3785 "propagating/" PROP_NAME "/maxnewvars", 3786 "number of variables added after the propagator is reinitialized?", 3787 &propdata->maxnewvars, TRUE, DEFAULT_MAXNEWVARS, 0, INT_MAX, NULL, NULL) ); 3788 3789 SCIP_CALL( SCIPaddBoolParam(scip, 3790 "propagating/" PROP_NAME "/propuseimplics", 3791 "use implications to strengthen the propagation of binary variable (increasing the objective change)?", 3792 &propdata->propuseimplics, TRUE, DEFAULT_PROPUSEIMPLICS, NULL, NULL) ); 3793 3794 SCIP_CALL( SCIPaddBoolParam(scip, 3795 "propagating/" PROP_NAME "/respropuseimplics", 3796 "use implications to strengthen the resolve propagation of binary variable (increasing the objective change)?", 3797 &propdata->respropuseimplics, TRUE, DEFAULT_RESPROPUSEIMPLICS, NULL, NULL) ); 3798 3799 SCIP_CALL( SCIPaddIntParam(scip, 3800 "propagating/" PROP_NAME "/maximplvars", 3801 "maximum number of binary variables the implications are used if turned on (-1: unlimited)?", 3802 &propdata->maximplvars, TRUE, DEFAULT_MAXIMPLVARS, -1, INT_MAX, NULL, NULL) ); 3803 3804 return SCIP_OKAY; 3805 } 3806 3807 /** propagates the cutoff bound for the given variables */ 3808 SCIP_RETCODE SCIPpropagateCutoffboundVar( 3809 SCIP* scip, /**< SCIP data structure */ 3810 SCIP_PROP* prop, /**< propagator, or NULL */ 3811 SCIP_VAR* var, /**< variables to propagate */ 3812 SCIP_Real cutoffbound, /**< cutoff bound to use */ 3813 SCIP_Real pseudoobjval, /**< pseudo objective value to use */ 3814 SCIP_Bool* tightened /**< pointer to if the domain was tightened */ 3815 ) 3816 { 3817 SCIP_Real objval; 3818 3819 objval = SCIPvarGetObj(var); 3820 3821 SCIP_CALL( propagateCutoffboundVar(scip, prop, var, -1, objval, cutoffbound, pseudoobjval, TRUE, tightened) ); 3822 3823 return SCIP_OKAY; 3824 } 3825