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_probing.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief probing propagator 28 * @author Tobias Achterberg 29 * @author Matthias Miltenberger 30 * @author Michael Winkler 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include "blockmemshell/memory.h" 36 #include "scip/prop_probing.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_misc_sort.h" 40 #include "scip/pub_prop.h" 41 #include "scip/pub_tree.h" 42 #include "scip/pub_var.h" 43 #include "scip/scip_branch.h" 44 #include "scip/scip_general.h" 45 #include "scip/scip_lp.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_numerics.h" 49 #include "scip/scip_param.h" 50 #include "scip/scip_prob.h" 51 #include "scip/scip_probing.h" 52 #include "scip/scip_prop.h" 53 #include "scip/scip_randnumgen.h" 54 #include "scip/scip_solvingstats.h" 55 #include "scip/scip_timing.h" 56 #include "scip/scip_tree.h" 57 #include "scip/scip_var.h" 58 #include <string.h> 59 60 #define PROP_NAME "probing" 61 #define PROP_DESC "probing propagator on binary variables" 62 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP 63 #define PROP_PRIORITY -100000 /**< propagation priority */ 64 #define PROP_FREQ -1 /**< propagation frequency */ 65 #define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators found 66 * reductions? */ 67 #define PROP_PRESOL_PRIORITY -100000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */ 68 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */ 69 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no 70 * limit) */ 71 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */ 72 73 74 /* @todo check for restricting the maximal number of implications that can be added by probing */ 75 76 /* sorting of probing variables, two different variants are implemeneted */ 77 /* #define VARIANT_B */ 78 79 80 /* 81 * Default parameter settings 82 */ 83 84 #define DEFAULT_MAXRUNS 1 /**< maximal number of runs, probing participates in (-1: no limit) */ 85 #define DEFAULT_PROPROUNDS -1 /**< maximal number of propagation rounds in probing subproblems */ 86 #define DEFAULT_MAXFIXINGS 25 /**< maximal number of fixings found, until probing is interrupted 87 * (0: don't interrupt) */ 88 #define DEFAULT_MAXUSELESS 1000 /**< maximal number of successive probings without fixings, 89 * until probing is aborted (0: don't abort) */ 90 #define DEFAULT_MAXTOTALUSELESS 50 /**< maximal number of successive probings without fixings, bound changes, 91 * and implications, until probing is aborted (0: don't abort) */ 92 #define DEFAULT_MAXSUMUSELESS 0 /**< maximal number of probings without fixings, until probing is aborted 93 * (0: don't abort) */ 94 #define DEFAULT_MAXDEPTH -1 /**< maximal depth until propagation is executed(-1: no limit) */ 95 #define DEFAULT_RANDSEED 59 /**< random initial seed */ 96 97 /* 98 * Data structures 99 */ 100 101 /** propagator data */ 102 struct SCIP_PropData 103 { 104 SCIP_VAR** sortedvars; /**< problem variables sorted by number of rounding locks, used in presolving */ 105 int* nprobed; /**< array of numbers how often we already probed on each variables */ 106 int noldtotalvars; /**< number of total variables in problem */ 107 int nsortedvars; /**< number of problem variables, used in presolving */ 108 int nsortedbinvars; /**< number of binary problem variables, used in presolving */ 109 int maxruns; /**< maximal number of runs, probing participates in (-1: no limit) */ 110 int proprounds; /**< maximal number of propagation rounds in probing subproblems */ 111 int maxfixings; /**< maximal number of fixings found, until probing is interrupted 112 * (0: don't interrupt) */ 113 int maxuseless; /**< maximal number of successive probings without fixings, 114 * until probing is aborted (0: don't abort) */ 115 int maxtotaluseless; /**< maximal number of successive probings without fixings, bound changes, 116 * and implications, until probing is aborted (0: don't abort) */ 117 int maxsumuseless; /**< maximal number of probings without fixings, until probing is aborted 118 * (0: don't abort) */ 119 int startidx; /**< starting variable index of next call, used in presolving */ 120 int lastsortstartidx; /**< last starting variable index where the variables have been sorted, used in presolving */ 121 int nfixings; /**< total number of fixings found in probing */ 122 int naggregations; /**< total number of aggregations found in probing */ 123 int nimplications; /**< total number of implications found in probing */ 124 int nbdchgs; /**< total number of bound changes found in probing */ 125 int nuseless; /**< current number of successive useless probings */ 126 int ntotaluseless; /**< current number of successive totally useless probings */ 127 int nsumuseless; /**< current number of useless probings */ 128 int maxdepth; /**< maximal depth until propagation is executed */ 129 SCIP_Longint lastnode; /**< last node where probing was applied, or -1 for presolving, and -2 for not applied yet */ 130 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */ 131 }; 132 133 134 /* 135 * Local methods 136 */ 137 /** initializes the propagator data */ 138 static 139 SCIP_RETCODE initPropdata( 140 SCIP_PROPDATA* propdata /**< propagator data */ 141 ) 142 { 143 assert(propdata != NULL); 144 145 propdata->sortedvars = NULL; 146 propdata->nprobed = NULL; 147 propdata->noldtotalvars = 0; 148 propdata->nsortedvars = 0; 149 propdata->nsortedbinvars = 0; 150 propdata->startidx = 0; 151 propdata->lastsortstartidx = -1; 152 propdata->nfixings = 0; 153 propdata->naggregations = 0; 154 propdata->nimplications = 0; 155 propdata->nbdchgs = 0; 156 propdata->nuseless = 0; 157 propdata->ntotaluseless = 0; 158 propdata->nsumuseless = 0; 159 propdata->lastnode = -2; 160 propdata->randnumgen = NULL; 161 162 return SCIP_OKAY; 163 } 164 165 /** frees the sorted vars array */ 166 static 167 SCIP_RETCODE freeSortedvars( 168 SCIP* scip, /**< SCIP data structure */ 169 SCIP_PROPDATA* propdata /**< propagator data */ 170 ) 171 { 172 assert(propdata != NULL); 173 174 if( propdata->sortedvars != NULL ) 175 { 176 int i; 177 178 /* release variables */ 179 for( i = 0; i < propdata->nsortedvars; ++i ) 180 { 181 SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[i]) ); 182 } 183 SCIPfreeMemoryArray(scip, &propdata->sortedvars); 184 propdata->nsortedvars = 0; 185 propdata->nsortedbinvars = 0; 186 } 187 188 SCIPfreeMemoryArrayNull(scip, &propdata->nprobed); 189 propdata->noldtotalvars = 0; 190 191 return SCIP_OKAY; 192 } 193 194 /** sorts the binary variables starting with the given index by rounding locks and implications */ 195 static 196 SCIP_RETCODE sortVariables( 197 SCIP* scip, /**< SCIP data structure */ 198 SCIP_PROPDATA* propdata, /**< propagator data */ 199 SCIP_VAR** vars, /**< problem variables to be sorted */ 200 int nvars, /**< number of problem variables to be sorted */ 201 int firstidx /**< first index that should be subject to sorting */ 202 ) 203 { 204 SCIP_VAR** sortedvars; 205 int nsortedvars; 206 SCIP_Real* scores; 207 int i; 208 int minnprobings; 209 SCIP_Real maxscore; 210 int nlocksdown; 211 int nlocksup; 212 int nimplzero; 213 int nimplone; 214 int nclqzero; 215 int nclqone; 216 217 assert(propdata != NULL); 218 assert(propdata->nprobed != NULL); 219 220 assert(vars != NULL || nvars == 0); 221 222 nsortedvars = nvars - firstidx; 223 if( nsortedvars <= 0 ) 224 return SCIP_OKAY; 225 226 assert(vars != NULL); 227 228 sortedvars = &(vars[firstidx]); 229 230 SCIPdebugMsg(scip, "resorting probing variables %d to %d\n", firstidx, nvars-1); 231 232 /* sort the variables by number of rounding locks and implications */ 233 SCIP_CALL( SCIPallocBufferArray(scip, &scores, nsortedvars) ); 234 235 maxscore = -1.0; 236 minnprobings = INT_MAX; 237 238 /* determine maximal possible score and minimal number of probings over all variables */ 239 for( i = 0; i < nvars; ++i ) 240 { 241 SCIP_VAR* var; 242 SCIP_Real tmp; 243 244 var = vars[i]; 245 246 assert(SCIPvarIsBinary(var)); 247 assert(propdata->noldtotalvars > SCIPvarGetIndex(var)); 248 assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0); 249 250 if( SCIPvarIsActive(var) ) 251 { 252 nlocksdown = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL); 253 nlocksup = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 254 nimplzero = SCIPvarGetNImpls(var, FALSE); 255 nimplone = SCIPvarGetNImpls(var, TRUE); 256 nclqzero = SCIPvarGetNCliques(var, FALSE); 257 nclqone = SCIPvarGetNCliques(var, TRUE); 258 259 #ifndef VARIANT_B 260 tmp = -MAX(nlocksdown, nlocksup) 261 + 10.0 * MIN(nimplzero, nimplone) 262 + 100.0 * MIN(nclqzero, nclqone); 263 #else 264 tmp = - ABS(nlocksdown - nlocksup) 265 + MIN(nlocksdown, nlocksup) 266 + 500.0 * nimplzero + 50.0 * nimplone 267 + 50000.0 * nclqzero + 5000.0 * nclqone; 268 #endif 269 270 if( tmp > maxscore ) 271 maxscore = tmp; 272 if( propdata->nprobed[SCIPvarGetIndex(var)] < minnprobings ) 273 minnprobings = propdata->nprobed[SCIPvarGetIndex(var)]; 274 } 275 } 276 277 /* correct number of probings on each variable by minimal number of probings */ 278 if( minnprobings > 0 ) 279 { 280 for( i = 0; i < nvars; ++i ) 281 { 282 SCIP_VAR* var; 283 284 var = vars[i]; 285 286 if( SCIPvarIsActive(var) ) 287 propdata->nprobed[SCIPvarGetIndex(var)] -= minnprobings; 288 } 289 } 290 291 for( i = 0; i < nsortedvars; ++i ) 292 { 293 SCIP_VAR* var; 294 var = sortedvars[i]; 295 296 assert(SCIPvarIsBinary(var)); 297 298 /* prefer variables that we did not already probe on */ 299 if( SCIPvarIsActive(var) ) 300 { 301 SCIP_Real randomoffset; 302 nlocksdown = SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL); 303 nlocksup = SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL); 304 nimplzero = SCIPvarGetNImpls(var, FALSE); 305 nimplone = SCIPvarGetNImpls(var, TRUE); 306 nclqzero = SCIPvarGetNCliques(var, FALSE); 307 nclqone = SCIPvarGetNCliques(var, TRUE); 308 309 assert(propdata->noldtotalvars > SCIPvarGetIndex(var)); 310 assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0); 311 312 /* use a random offset to break possible ties arbitrarily */ 313 randomoffset = SCIPrandomGetReal(propdata->randnumgen, 0.0, 0.5); 314 315 #ifndef VARIANT_B 316 scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)] 317 - MAX(nlocksdown, nlocksup) 318 + 10.0 * MIN(nimplzero, nimplone) 319 + 100.0 * MIN(nclqzero, nclqone) /*lint !e790*/ 320 - randomoffset; /* to break ties randomly */ 321 #else 322 scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)] 323 - ABS(nlocksdown - nlocksup) 324 + MIN(nlocksdown, nlocksup) 325 + 500.0 * nimplzero + 50.0 * nimplone /*lint !e790*/ 326 + 50000.0 * nclqzero + 5000.0 * nclqone /*lint !e790*/ 327 - randomoffset; /* to break ties randomly */ 328 #endif 329 } 330 else 331 scores[i] = -SCIPinfinity(scip); 332 } 333 334 SCIPsortDownRealPtr(scores, (void**) sortedvars, nsortedvars); 335 336 SCIPfreeBufferArray(scip, &scores); 337 338 return SCIP_OKAY; 339 } 340 341 /** the main probing loop */ 342 static 343 SCIP_RETCODE applyProbing( 344 SCIP* scip, /**< SCIP data structure */ 345 SCIP_PROPDATA* propdata, /**< propagator data */ 346 SCIP_VAR** vars, /**< problem variables */ 347 int nvars, /**< number of problem variables */ 348 int nbinvars, /**< number of binary variables */ 349 int* startidx, /**< pointer to store starting variable index of next call */ 350 int* nfixedvars, /**< pointer to store number of fixed variables */ 351 int* naggrvars, /**< pointer to store number of aggregated variables */ 352 int* nchgbds, /**< pointer to store number of changed bounds */ 353 int oldnfixedvars, /**< number of previously fixed variables */ 354 int oldnaggrvars, /**< number of previously aggregated variables */ 355 SCIP_Bool* delay, /**< pointer to store whether propagator should be delayed */ 356 SCIP_Bool* cutoff /**< pointer to store whether cutoff occured */ 357 ) 358 { 359 SCIP_Real* zeroimpllbs; 360 SCIP_Real* zeroimplubs; 361 SCIP_Real* zeroproplbs; 362 SCIP_Real* zeropropubs; 363 SCIP_Real* oneimpllbs; 364 SCIP_Real* oneimplubs; 365 SCIP_Real* oneproplbs; 366 SCIP_Real* onepropubs; 367 int localnfixedvars; 368 int localnaggrvars; 369 int localnchgbds; 370 int localnimplications; 371 int maxfixings; 372 int maxuseless; 373 int maxtotaluseless; 374 int maxsumuseless; 375 int i; 376 int oldstartidx; 377 SCIP_Bool aborted; 378 SCIP_Bool looped; 379 380 assert(vars != NULL); 381 assert(nbinvars > 0); 382 383 maxfixings = (propdata->maxfixings > 0 ? propdata->maxfixings : INT_MAX); 384 maxuseless = (propdata->maxuseless > 0 ? propdata->maxuseless : INT_MAX); 385 maxtotaluseless = (propdata->maxtotaluseless > 0 ? propdata->maxtotaluseless : INT_MAX); 386 maxsumuseless = (propdata->maxsumuseless > 0 ? propdata->maxsumuseless : INT_MAX); 387 aborted = FALSE; 388 looped = FALSE; 389 oldstartidx = *startidx; 390 i = *startidx; 391 392 /* get temporary memory for storing probing results */ 393 SCIP_CALL( SCIPallocBufferArray(scip, &zeroimpllbs, nvars) ); 394 SCIP_CALL( SCIPallocBufferArray(scip, &zeroimplubs, nvars) ); 395 SCIP_CALL( SCIPallocBufferArray(scip, &zeroproplbs, nvars) ); 396 SCIP_CALL( SCIPallocBufferArray(scip, &zeropropubs, nvars) ); 397 SCIP_CALL( SCIPallocBufferArray(scip, &oneimpllbs, nvars) ); 398 SCIP_CALL( SCIPallocBufferArray(scip, &oneimplubs, nvars) ); 399 SCIP_CALL( SCIPallocBufferArray(scip, &oneproplbs, nvars) ); 400 SCIP_CALL( SCIPallocBufferArray(scip, &onepropubs, nvars) ); 401 402 /* for each binary variable, probe fixing the variable to zero and one */ 403 *delay = FALSE; 404 *cutoff = FALSE; 405 do 406 { 407 for( ; i < nbinvars && !(*cutoff); ++i ) 408 { 409 SCIP_Bool localcutoff; 410 SCIP_Bool probingzero; 411 SCIP_Bool probingone; 412 413 /* check whether probing should be aborted */ 414 if( propdata->nuseless >= maxuseless || propdata->ntotaluseless >= maxtotaluseless || propdata->nsumuseless >= maxsumuseless || SCIPisStopped(scip) ) 415 { 416 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 417 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n", 418 SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars, 419 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs); 420 421 aborted = TRUE; 422 423 if( propdata->nuseless >= maxuseless ) 424 { 425 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 426 " (%.1fs) probing aborted: %d/%d successive useless probings\n", SCIPgetSolvingTime(scip), 427 propdata->nuseless, maxuseless); 428 } 429 else if( propdata->ntotaluseless >= maxtotaluseless ) 430 { 431 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 432 " (%.1fs) probing aborted: %d/%d successive totally useless probings\n", SCIPgetSolvingTime(scip), 433 propdata->ntotaluseless, maxtotaluseless); 434 } 435 else if( propdata->nsumuseless >= maxsumuseless ) 436 { 437 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 438 " (%.1fs) probing aborted: %d/%d useless probings in total\n", SCIPgetSolvingTime(scip), 439 propdata->nsumuseless, maxsumuseless); 440 } 441 else 442 { 443 assert(SCIPisStopped(scip)); 444 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 445 " (%.1fs) probing aborted: solving stopped\n", SCIPgetSolvingTime(scip)); 446 } 447 break; 448 } 449 450 /* check if we already fixed enough variables for this round, or probed on all variables */ 451 if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars >= maxfixings || (looped && oldstartidx == i) ) 452 { 453 if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars > 0 ) 454 *delay = TRUE; 455 else 456 aborted = TRUE; 457 break; 458 } 459 460 /* display probing status */ 461 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING && (i+1) % 100 == 0 ) 462 { 463 SCIP_VERBLEVEL verblevel; 464 465 verblevel = ((i+1) % 1000 == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL); 466 SCIPverbMessage(scip, verblevel, NULL, 467 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n", 468 SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars, 469 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs); 470 } 471 472 /* ignore variables, that were fixed, aggregated, or deleted in prior probings */ 473 if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i]) 474 || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 ) 475 continue; 476 477 if( propdata->nuseless > 0 ) 478 propdata->nsumuseless++; 479 else 480 propdata->nsumuseless = MAX(propdata->nsumuseless-1, 0); 481 propdata->nuseless++; 482 propdata->ntotaluseless++; 483 484 /* determine whether one probing should happen */ 485 probingone = TRUE; 486 if( SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) == 0 ) 487 probingone = FALSE; 488 489 if( probingone ) 490 { 491 /* apply probing for fixing the variable to one */ 492 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_LOWER, 1.0, propdata->proprounds, 493 oneimpllbs, oneimplubs, oneproplbs, onepropubs, &localcutoff) ); 494 495 if( localcutoff ) 496 { 497 SCIP_Bool fixed; 498 499 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 ) 500 { 501 /* the variable can be fixed to FALSE */ 502 SCIP_CALL( SCIPfixVar(scip, vars[i], 0.0, cutoff, &fixed) ); 503 assert(fixed); 504 } 505 else 506 { 507 SCIP_CALL( SCIPtightenVarUb(scip, vars[i], 0.0, TRUE, cutoff, &fixed) ); 508 } 509 510 if( fixed ) 511 { 512 SCIPdebugMsg(scip, "fixed probing variable <%s> to 0.0, nlocks=(%d/%d)\n", 513 SCIPvarGetName(vars[i]), SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL), 514 SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL)); 515 (*nfixedvars)++; 516 propdata->nfixings++; 517 propdata->nuseless = 0; 518 propdata->ntotaluseless = 0; 519 } 520 else if( *cutoff ) 521 { 522 SCIPdebugMsg(scip, "tightening upper bound of probing variable <%s> to 0.0 led to a cutoff\n", 523 SCIPvarGetName(vars[i])); 524 } 525 continue; /* don't try downwards direction, because the variable is already fixed */ 526 } 527 528 /* ignore variables, that were fixed, aggregated, or deleted in prior probings 529 * (propagators in one-probe might have found global fixings but did not trigger the localcutoff) 530 */ 531 if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i]) 532 || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 ) 533 continue; 534 } 535 536 /* determine whether zero probing should happen */ 537 probingzero = TRUE; 538 if( SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) == 0 ) 539 probingzero = FALSE; 540 541 if( probingzero ) 542 { 543 /* apply probing for fixing the variable to zero */ 544 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_UPPER, 0.0, propdata->proprounds, 545 zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, &localcutoff) ); 546 547 if( localcutoff ) 548 { 549 SCIP_Bool fixed; 550 551 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 ) 552 { 553 /* the variable can be fixed to TRUE */ 554 SCIP_CALL( SCIPfixVar(scip, vars[i], 1.0, cutoff, &fixed) ); 555 } 556 else 557 { 558 SCIP_CALL( SCIPtightenVarLb(scip, vars[i], 1.0, TRUE, cutoff, &fixed) ); 559 } 560 561 if( fixed ) 562 { 563 SCIPdebugMsg(scip, "fixed probing variable <%s> to 1.0, nlocks=(%d/%d)\n", 564 SCIPvarGetName(vars[i]), SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL), 565 SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL)); 566 (*nfixedvars)++; 567 propdata->nfixings++; 568 propdata->nuseless = 0; 569 propdata->ntotaluseless = 0; 570 } 571 else if( *cutoff ) 572 { 573 SCIPdebugMsg(scip, "tightening lower bound of probing variable <%s> to 1.0 led to a cutoff\n", 574 SCIPvarGetName(vars[i])); 575 } 576 continue; /* don't analyze probing deductions, because the variable is already fixed */ 577 } 578 } 579 580 /* not have to check deductions if only one probing direction has been checked */ 581 if( !probingzero || !probingone ) 582 continue; 583 584 assert(propdata->noldtotalvars > SCIPvarGetIndex(vars[i])); 585 586 /* count number of probings on each variable */ 587 propdata->nprobed[SCIPvarGetIndex(vars[i])] += 1; 588 589 /* analyze probing deductions */ 590 localnfixedvars = 0; 591 localnaggrvars = 0; 592 localnimplications = 0; 593 localnchgbds = 0; 594 SCIP_CALL( SCIPanalyzeDeductionsProbing(scip, vars[i], 0.0, 1.0, 595 nvars, vars, zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, oneimpllbs, oneimplubs, oneproplbs, onepropubs, 596 &localnfixedvars, &localnaggrvars, &localnimplications, &localnchgbds, cutoff) ); 597 598 *nfixedvars += localnfixedvars; 599 *naggrvars += localnaggrvars; 600 *nchgbds += localnchgbds; 601 propdata->nfixings += localnfixedvars; 602 propdata->naggregations += localnaggrvars; 603 propdata->nbdchgs += localnchgbds; 604 propdata->nimplications += localnimplications; 605 606 if( localnfixedvars > 0 || localnaggrvars > 0 ) 607 { 608 SCIPdebugMsg(scip, "probing on <%s> led to %d fixed and %d aggregated variables\n", SCIPvarGetName(vars[i]), 609 localnfixedvars, localnaggrvars); 610 propdata->nuseless = 0; 611 propdata->ntotaluseless = 0; 612 } 613 if( localnimplications > 0 || localnchgbds > 0 ) 614 propdata->ntotaluseless = 0; 615 } 616 617 looped = TRUE; 618 619 /* check if we reached the end of all binary variables but did not stop, so we start from the beginning */ 620 if( i == nbinvars && !(*cutoff) && !(*delay) && !aborted ) 621 { 622 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 623 " (%.1fs) probing cycle finished: starting next cycle\n", SCIPgetSolvingTime(scip)); 624 i = 0; 625 626 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING ) 627 { 628 SCIP_VAR** newvars; 629 int nnewvars; 630 int nnewbinvars; 631 int nnewintvars; 632 int nnewimplvars; 633 int lastidx; 634 int v; 635 636 assert(vars == propdata->sortedvars); 637 assert(nbinvars == propdata->nsortedbinvars); 638 639 /* release old variables and free memory */ 640 for( v = propdata->nsortedvars - 1; v >= 0; --v ) 641 { 642 SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[v]) ); 643 } 644 SCIPfreeMemoryArray(scip, &propdata->sortedvars); 645 propdata->nsortedvars = 0; 646 propdata->nsortedbinvars = 0; 647 648 /* get new variables */ 649 nnewvars = SCIPgetNVars(scip); 650 newvars = SCIPgetVars(scip); 651 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), newvars, nnewvars) ); /*lint !e666*/ 652 propdata->nsortedvars = nnewvars; 653 654 nnewbinvars = SCIPgetNBinVars(scip); 655 nnewintvars = SCIPgetNIntVars(scip); 656 nnewimplvars = SCIPgetNImplVars(scip); 657 658 /* determine implicit binary variables */ 659 lastidx = nnewbinvars + nnewintvars + nnewimplvars; 660 for( v = nnewbinvars; v < lastidx; ++v ) 661 { 662 if( SCIPvarIsBinary(propdata->sortedvars[v]) ) 663 { 664 SCIPswapPointers((void**) &(propdata->sortedvars[nnewbinvars]), (void**) &(propdata->sortedvars[v])); 665 ++nnewbinvars; 666 } 667 } 668 propdata->nsortedbinvars = nnewbinvars; 669 670 nbinvars = nnewbinvars; 671 vars = propdata->sortedvars; 672 nvars = propdata->nsortedvars; 673 674 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimpllbs, nvars) ); 675 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimplubs, nvars) ); 676 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroproplbs, nvars) ); 677 SCIP_CALL( SCIPreallocBufferArray(scip, &zeropropubs, nvars) ); 678 SCIP_CALL( SCIPreallocBufferArray(scip, &oneimpllbs, nvars) ); 679 SCIP_CALL( SCIPreallocBufferArray(scip, &oneimplubs, nvars) ); 680 SCIP_CALL( SCIPreallocBufferArray(scip, &oneproplbs, nvars) ); 681 SCIP_CALL( SCIPreallocBufferArray(scip, &onepropubs, nvars) ); 682 683 /* correct oldstartidx which is used for early termination */ 684 if( oldstartidx >= nbinvars ) 685 oldstartidx = nbinvars - 1; 686 687 /* capture variables to make sure, the variables are not deleted */ 688 for( v = propdata->nsortedvars - 1; v >= 0; --v ) 689 { 690 SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) ); 691 } 692 693 if( nnewbinvars == 0 ) 694 { 695 *startidx = 0; 696 propdata->lastsortstartidx = -1; 697 propdata->nuseless = 0; 698 propdata->ntotaluseless = 0; 699 700 goto TERMINATE; 701 } 702 703 /* resorting here might lead to probing a second time on the same variable */ 704 SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, 0) ); 705 propdata->lastsortstartidx = 0; 706 } 707 } 708 } 709 while( i == 0 && !(*cutoff) && !(*delay) && !aborted ); 710 711 *startidx = i; 712 713 TERMINATE: 714 /* free temporary memory */ 715 SCIPfreeBufferArray(scip, &onepropubs); 716 SCIPfreeBufferArray(scip, &oneproplbs); 717 SCIPfreeBufferArray(scip, &oneimplubs); 718 SCIPfreeBufferArray(scip, &oneimpllbs); 719 SCIPfreeBufferArray(scip, &zeropropubs); 720 SCIPfreeBufferArray(scip, &zeroproplbs); 721 SCIPfreeBufferArray(scip, &zeroimplubs); 722 SCIPfreeBufferArray(scip, &zeroimpllbs); 723 724 return SCIP_OKAY; 725 } 726 727 728 /* 729 * Callback methods of propagator 730 */ 731 732 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 733 static 734 SCIP_DECL_PROPCOPY(propCopyProbing) 735 { /*lint --e{715}*/ 736 assert(scip != NULL); 737 assert(prop != NULL); 738 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 739 740 /* call inclusion method for propagator */ 741 SCIP_CALL( SCIPincludePropProbing(scip) ); 742 743 return SCIP_OKAY; 744 } 745 746 747 /** destructor of propagator to free user data (called when SCIP is exiting) */ 748 static 749 SCIP_DECL_PROPFREE(propFreeProbing) 750 { /*lint --e{715}*/ 751 SCIP_PROPDATA* propdata; 752 753 /* free propagator data */ 754 propdata = SCIPpropGetData(prop); 755 assert(propdata != NULL); 756 assert(propdata->sortedvars == NULL); 757 assert(propdata->nsortedvars == 0); 758 assert(propdata->nsortedbinvars == 0); 759 760 SCIPfreeBlockMemory(scip, &propdata); 761 SCIPpropSetData(prop, NULL); 762 763 return SCIP_OKAY; 764 } 765 766 767 /** initialization method of propagator (called after problem was transformed) */ 768 static 769 SCIP_DECL_PROPINIT(propInitProbing) 770 { /*lint --e{715}*/ 771 SCIP_PROPDATA* propdata; 772 773 propdata = SCIPpropGetData(prop); 774 assert(propdata != NULL); 775 776 SCIP_CALL( initPropdata(propdata) ); 777 778 /* create random number generator */ 779 SCIP_CALL( SCIPcreateRandom(scip, &propdata->randnumgen, 780 DEFAULT_RANDSEED, TRUE) ); 781 782 return SCIP_OKAY; 783 } 784 785 786 /** deinitialization method of propagator (called before transformed problem is freed) */ 787 static 788 SCIP_DECL_PROPEXIT(propExitProbing) 789 { /*lint --e{715}*/ 790 SCIP_PROPDATA* propdata; 791 792 propdata = SCIPpropGetData(prop); 793 assert(propdata != NULL); 794 795 SCIP_CALL( freeSortedvars(scip, propdata) ); 796 assert(propdata->sortedvars == NULL); 797 assert(propdata->nsortedvars == 0); 798 assert(propdata->nsortedbinvars == 0); 799 800 /* free random number generator */ 801 SCIPfreeRandom(scip, &propdata->randnumgen); 802 803 return SCIP_OKAY; 804 } 805 806 /** presolving initialization method of propagator (called when presolving is about to begin) */ 807 static 808 SCIP_DECL_PROPINITPRE(propInitpreProbing) 809 { /*lint --e{715}*/ 810 SCIP_PROPDATA* propdata; 811 812 propdata = SCIPpropGetData(prop); 813 assert(propdata != NULL); 814 815 propdata->lastnode = -2; 816 817 return SCIP_OKAY; 818 } 819 820 821 /** presolving deinitialization method of propagator (called after presolving has been finished) */ 822 static 823 SCIP_DECL_PROPEXITPRE(propExitpreProbing) 824 { /*lint --e{715}*/ 825 SCIP_PROPDATA* propdata; 826 827 propdata = SCIPpropGetData(prop); 828 assert(propdata != NULL); 829 830 /* delete the vars array, if the maximal number of runs are exceeded */ 831 if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) >= propdata->maxruns ) 832 { 833 SCIP_CALL( freeSortedvars(scip, propdata) ); 834 assert(propdata->sortedvars == NULL); 835 assert(propdata->nsortedvars == 0); 836 assert(propdata->nsortedbinvars == 0); 837 } 838 839 return SCIP_OKAY; 840 } 841 842 843 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */ 844 static 845 SCIP_DECL_PROPINITSOL(propInitsolProbing) 846 { 847 /*lint --e{715}*/ 848 SCIP_PROPDATA* propdata; 849 850 propdata = SCIPpropGetData(prop); 851 assert(propdata != NULL); 852 853 /* reset all propdata elements for stopping propagation earlier */ 854 propdata->nuseless = 0; 855 propdata->ntotaluseless = 0; 856 propdata->nsumuseless = 0; 857 858 return SCIP_OKAY; 859 } 860 861 862 /** presolve method of propagator */ 863 static 864 SCIP_DECL_PROPPRESOL(propPresolProbing) 865 { /*lint --e{715}*/ 866 SCIP_PROPDATA* propdata; 867 int nvars; 868 int nbinvars; 869 int nintvars; 870 int nimplvars; 871 int oldnfixedvars; 872 int oldnaggrvars; 873 int oldnchgbds; 874 int oldnimplications; 875 int ntotalvars; 876 SCIP_Bool delay; 877 SCIP_Bool cutoff; 878 879 assert(result != NULL); 880 881 *result = SCIP_DIDNOTRUN; 882 883 nbinvars = SCIPgetNBinVars(scip); 884 nintvars = SCIPgetNIntVars(scip); 885 nimplvars = SCIPgetNImplVars(scip); 886 887 /* if we have no binary variable anymore, we stop probing */ 888 if( nbinvars + nintvars + nimplvars == 0 ) 889 return SCIP_OKAY; 890 891 /* get propagator data */ 892 propdata = SCIPpropGetData(prop); 893 assert(propdata != NULL); 894 895 /* check, if probing should be applied in the current run */ 896 if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) > propdata->maxruns ) 897 return SCIP_OKAY; 898 899 /* if no domains changed since the last call, we don't need to probe */ 900 if( propdata->lastnode == -1 && nnewfixedvars == 0 && nnewaggrvars == 0 && nnewchgbds == 0 && nnewholes == 0 ) 901 return SCIP_OKAY; 902 903 SCIPdebugMsg(scip, "executing probing (used %.1f sec)\n", SCIPpropGetTime(prop)); 904 905 *result = SCIP_DIDNOTFIND; 906 907 /* allow some additional probings */ 908 propdata->nuseless -= propdata->nuseless/10; 909 propdata->ntotaluseless -= propdata->ntotaluseless/10; 910 911 /* get variable data */ 912 if( propdata->sortedvars == NULL ) 913 { 914 SCIP_VAR** vars = SCIPgetVars(scip); 915 int lastidx; 916 int v; 917 918 assert(propdata->startidx == 0); 919 920 nvars = SCIPgetNVars(scip); 921 922 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), vars, nvars) ); 923 propdata->nsortedvars = nvars; 924 925 /* determine implicit binary variables */ 926 lastidx = nbinvars + nintvars + nimplvars; 927 for( v = nbinvars; v < lastidx; ++v ) 928 { 929 if( SCIPvarIsBinary(propdata->sortedvars[v]) ) 930 { 931 SCIPswapPointers((void**) &(propdata->sortedvars[nbinvars]), (void**) &(propdata->sortedvars[v])); 932 ++nbinvars; 933 } 934 } 935 propdata->nsortedbinvars = nbinvars; 936 937 /* capture variables to make sure, the variables are not deleted */ 938 for( v = propdata->nsortedvars - 1; v >= 0 ; --v ) 939 { 940 SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) ); 941 } 942 } 943 944 if( propdata->nsortedbinvars == 0 ) 945 return SCIP_OKAY; 946 947 /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate 948 * enough space 949 */ 950 ntotalvars = SCIPgetNTotalVars(scip); 951 if( propdata->noldtotalvars < ntotalvars ) 952 { 953 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) ); 954 BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/ 955 propdata->noldtotalvars = ntotalvars; 956 } 957 958 propdata->lastnode = -1; 959 960 /* sort the binary variables by number of rounding locks, if at least 100 variables were probed since last sort */ 961 if( propdata->lastsortstartidx < 0 || propdata->startidx - propdata->lastsortstartidx >= 100 ) 962 { 963 SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, propdata->startidx) ); 964 propdata->lastsortstartidx = propdata->startidx; 965 } 966 967 oldnfixedvars = *nfixedvars; 968 oldnaggrvars = *naggrvars; 969 oldnchgbds = *nchgbds; 970 oldnimplications = propdata->nimplications; 971 972 /* start probing on variables */ 973 SCIP_CALL( applyProbing(scip, propdata, propdata->sortedvars, propdata->nsortedvars, propdata->nsortedbinvars, 974 &(propdata->startidx), nfixedvars, naggrvars, nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) ); 975 976 /* adjust result code */ 977 if( cutoff ) 978 *result = SCIP_CUTOFF; 979 else 980 { 981 if( delay ) 982 { 983 /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */ 984 propdata->lastnode = -2; 985 } 986 987 if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds 988 || propdata->nimplications > oldnimplications ) 989 *result = SCIP_SUCCESS; 990 } 991 992 return SCIP_OKAY; 993 } 994 995 996 /** execution method of propagator */ 997 static 998 SCIP_DECL_PROPEXEC(propExecProbing) 999 { /*lint --e{715}*/ 1000 SCIP_PROPDATA* propdata; 1001 SCIP_VAR** vars; 1002 SCIP_VAR** binvars; 1003 int nvars; 1004 int nbinvars; 1005 int i; 1006 int nfixedvars; 1007 int naggrvars; 1008 int nchgbds; 1009 int oldnfixedvars; 1010 int oldnaggrvars; 1011 int oldnchgbds; 1012 SCIPdebug( int oldnimplications; ) 1013 int startidx; 1014 int ntotalvars; 1015 SCIP_Bool delay; 1016 SCIP_Bool cutoff; 1017 1018 assert(result != NULL); 1019 1020 *result = SCIP_DIDNOTRUN; 1021 1022 /* avoid recursive infinity loop */ 1023 if( SCIPinProbing(scip) ) 1024 return SCIP_OKAY; 1025 1026 /* only call propagation on branching candidates, if an optimal LP solution is at hand */ 1027 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1028 return SCIP_OKAY; 1029 1030 /* get propagator data */ 1031 propdata = SCIPpropGetData(prop); 1032 assert(propdata != NULL); 1033 1034 /* if already called stop */ 1035 if( propdata->lastnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) ) 1036 return SCIP_OKAY; 1037 1038 /* if maximal depth for propagation is reached, stop */ 1039 if( propdata->maxdepth >= 0 && propdata->maxdepth < SCIPgetDepth(scip) ) 1040 return SCIP_OKAY; 1041 1042 propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)); 1043 1044 /* get (number of) fractional variables that should be integral */ 1045 /* todo check if integrating fractional implicit integer variables is beneficial for probing */ 1046 SCIP_CALL( SCIPgetLPBranchCands(scip, &vars, NULL, NULL, &nvars, NULL, NULL) ); 1047 nbinvars = 0; 1048 1049 /* alloc array for fractional binary variables */ 1050 SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) ); 1051 1052 /* copy binary variables to array binvars */ 1053 for( i = 0; i < nvars; ++i ) 1054 { 1055 SCIP_VAR* var; 1056 var = vars[i]; 1057 1058 assert(var != NULL); 1059 if( SCIPvarIsBinary(var) ) 1060 { 1061 assert(SCIPvarGetLbLocal(var) < 0.5); 1062 assert(SCIPvarGetUbLocal(var) > 0.5); 1063 1064 binvars[nbinvars] = var; 1065 ++nbinvars; 1066 } 1067 } 1068 SCIPdebugMsg(scip, "problem <%s> node %" SCIP_LONGINT_FORMAT " probing propagation found %d of %d possible probing candidates\n", SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nbinvars, nvars); 1069 1070 if( nbinvars == 0 ) 1071 { 1072 *result = SCIP_DIDNOTFIND; 1073 goto TERMINATE; 1074 } 1075 1076 /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate 1077 * enough space 1078 */ 1079 ntotalvars = SCIPgetNTotalVars(scip); 1080 if( propdata->noldtotalvars < ntotalvars ) 1081 { 1082 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) ); 1083 BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/ 1084 propdata->noldtotalvars = ntotalvars; 1085 } 1086 1087 /* sort binary variables */ 1088 SCIP_CALL( sortVariables(scip, propdata, binvars, nbinvars, 0) ); 1089 1090 oldnfixedvars = 0; 1091 oldnaggrvars = 0; 1092 oldnchgbds = 0; 1093 nfixedvars = 0; 1094 naggrvars = 0; 1095 nchgbds = 0; 1096 startidx = 0; 1097 SCIPdebug( oldnimplications = propdata->nimplications; ) 1098 1099 /* start probing on found variables */ 1100 SCIP_CALL( applyProbing(scip, propdata, binvars, nbinvars, nbinvars, &startidx, &nfixedvars, &naggrvars, &nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) ); 1101 SCIPdebug( SCIPdebugMsg(scip, "probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n", 1102 nfixedvars, naggrvars, nchgbds, (propdata->nimplications) - oldnimplications); ) 1103 1104 if( delay ) 1105 { 1106 /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */ 1107 propdata->lastnode = -2; 1108 } 1109 1110 /* adjust result code */ 1111 if( cutoff ) 1112 *result = SCIP_CUTOFF; 1113 else if( nfixedvars > oldnfixedvars || naggrvars > oldnaggrvars || nchgbds > oldnchgbds ) 1114 *result = SCIP_REDUCEDDOM; 1115 1116 TERMINATE: 1117 SCIPfreeBufferArray(scip, &binvars); 1118 1119 return SCIP_OKAY; /*lint !e438*/ 1120 } 1121 1122 1123 /** propagation conflict resolving method of propagator */ 1124 static 1125 SCIP_DECL_PROPRESPROP(propRespropProbing) 1126 { /*lint --e{715}*/ 1127 *result = SCIP_DIDNOTRUN; 1128 1129 return SCIP_OKAY; 1130 } 1131 1132 1133 /* 1134 * propagator specific interface methods 1135 */ 1136 1137 /** creates the probing propagator and includes it in SCIP */ 1138 SCIP_RETCODE SCIPincludePropProbing( 1139 SCIP* scip /**< SCIP data structure */ 1140 ) 1141 { 1142 SCIP_PROPDATA* propdata; 1143 SCIP_PROP* prop; 1144 1145 /* create probing propagator data */ 1146 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) ); 1147 SCIP_CALL( initPropdata(propdata) ); 1148 1149 /* include propagator */ 1150 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, 1151 propExecProbing, propdata) ); 1152 1153 assert(prop != NULL); 1154 1155 /* set optional callbacks via setter functions */ 1156 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyProbing) ); 1157 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeProbing) ); 1158 SCIP_CALL( SCIPsetPropInit(scip, prop, propInitProbing) ); 1159 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitProbing) ); 1160 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolProbing) ); 1161 SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreProbing) ); 1162 SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreProbing) ); 1163 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolProbing, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, 1164 PROP_PRESOLTIMING) ); 1165 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropProbing) ); 1166 1167 /* add probing propagator parameters */ 1168 SCIP_CALL( SCIPaddIntParam(scip, 1169 "propagating/" PROP_NAME "/maxruns", 1170 "maximal number of runs, probing participates in (-1: no limit)", 1171 &propdata->maxruns, FALSE, DEFAULT_MAXRUNS, -1, INT_MAX, NULL, NULL) ); 1172 SCIP_CALL( SCIPaddIntParam(scip, 1173 "propagating/" PROP_NAME "/proprounds", 1174 "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)", 1175 &propdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) ); 1176 SCIP_CALL( SCIPaddIntParam(scip, 1177 "propagating/" PROP_NAME "/maxfixings", 1178 "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)", 1179 &propdata->maxfixings, TRUE, DEFAULT_MAXFIXINGS, 0, INT_MAX, NULL, NULL) ); 1180 SCIP_CALL( SCIPaddIntParam(scip, 1181 "propagating/" PROP_NAME "/maxuseless", 1182 "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)", 1183 &propdata->maxuseless, TRUE, DEFAULT_MAXUSELESS, 0, INT_MAX, NULL, NULL) ); 1184 SCIP_CALL( SCIPaddIntParam(scip, 1185 "propagating/" PROP_NAME "/maxtotaluseless", 1186 "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)", 1187 &propdata->maxtotaluseless, TRUE, DEFAULT_MAXTOTALUSELESS, 0, INT_MAX, NULL, NULL) ); 1188 SCIP_CALL( SCIPaddIntParam(scip, 1189 "propagating/" PROP_NAME "/maxsumuseless", 1190 "maximal number of probings without fixings, until probing is aborted (0: don't abort)", 1191 &propdata->maxsumuseless, TRUE, DEFAULT_MAXSUMUSELESS, 0, INT_MAX, NULL, NULL) ); 1192 SCIP_CALL( SCIPaddIntParam(scip, 1193 "propagating/" PROP_NAME "/maxdepth", 1194 "maximal depth until propagation is executed(-1: no limit)", 1195 &propdata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) ); 1196 1197 return SCIP_OKAY; 1198 } 1199 1200 1201 /** applies and evaluates probing of a single variable in the given direction and bound */ 1202 SCIP_RETCODE SCIPapplyProbingVar( 1203 SCIP* scip, /**< SCIP data structure */ 1204 SCIP_VAR** vars, /**< problem variables */ 1205 int nvars, /**< number of problem variables */ 1206 int probingpos, /**< variable number to apply probing on */ 1207 SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */ 1208 SCIP_Real bound, /**< which bound should be set */ 1209 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ 1210 SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */ 1211 SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */ 1212 SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */ 1213 SCIP_Real* propubs, /**< array to store upper bounds after full propagation */ 1214 SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */ 1215 ) 1216 { 1217 assert(impllbs != NULL); 1218 assert(implubs != NULL); 1219 assert(proplbs != NULL); 1220 assert(propubs != NULL); 1221 assert(cutoff != NULL); 1222 assert(0 <= probingpos && probingpos < nvars); 1223 assert(SCIPisGE(scip, bound, SCIPvarGetLbLocal(vars[probingpos]))); 1224 assert(SCIPisLE(scip, bound, SCIPvarGetUbLocal(vars[probingpos]))); 1225 1226 SCIPdebugMsg(scip, "applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n", 1227 SCIPvarGetName(vars[probingpos]), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", bound, 1228 SCIPvarGetNLocksDownType(vars[probingpos], SCIP_LOCKTYPE_MODEL), 1229 SCIPvarGetNLocksUpType(vars[probingpos], SCIP_LOCKTYPE_MODEL), 1230 SCIPvarGetNImpls(vars[probingpos], FALSE), SCIPvarGetNImpls(vars[probingpos], TRUE), 1231 SCIPvarGetNCliques(vars[probingpos], FALSE), SCIPvarGetNCliques(vars[probingpos], TRUE)); 1232 1233 /* in debug mode we assert above that this trivial infeasibility does not occur (for performance reasons), but in 1234 * optimized mode we return safely 1235 */ 1236 if( SCIPisLT(scip, bound, SCIPvarGetLbLocal(vars[probingpos])) 1237 || SCIPisGT(scip, bound, SCIPvarGetUbLocal(vars[probingpos])) ) 1238 { 1239 SCIPdebugMsg(scip, " -> trivial infeasibility detected\n"); 1240 *cutoff = TRUE; 1241 return SCIP_OKAY; 1242 } 1243 1244 /* start probing mode */ 1245 SCIP_CALL( SCIPstartProbing(scip) ); 1246 1247 /* enables collection of variable statistics during probing */ 1248 SCIPenableVarHistory(scip); 1249 1250 /* fix variable */ 1251 if( boundtype == SCIP_BOUNDTYPE_UPPER ) 1252 { 1253 SCIP_CALL( SCIPchgVarUbProbing(scip, vars[probingpos], bound) ); 1254 } 1255 else 1256 { 1257 assert(boundtype == SCIP_BOUNDTYPE_LOWER); 1258 SCIP_CALL( SCIPchgVarLbProbing(scip, vars[probingpos], bound) ); 1259 } 1260 1261 /* @todo it might pay off to catch the bounds-tightened event on all variables and then only get the implied and 1262 * propagated bounds on those variables which where really changed on propagation 1263 */ 1264 1265 /* apply propagation of implication graph and clique table */ 1266 SCIP_CALL( SCIPpropagateProbingImplications(scip, cutoff) ); 1267 if( !(*cutoff) ) 1268 { 1269 int i; 1270 1271 for( i = 0; i < nvars; ++i ) 1272 { 1273 impllbs[i] = SCIPvarGetLbLocal(vars[i]); 1274 implubs[i] = SCIPvarGetUbLocal(vars[i]); 1275 } 1276 1277 /* apply propagation */ 1278 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) ); 1279 } 1280 else 1281 { 1282 SCIPdebugMsg(scip, "propagating probing implications after <%s> to %g led to a cutoff\n", 1283 SCIPvarGetName(vars[probingpos]), bound); 1284 } 1285 1286 /* evaluate propagation */ 1287 if( !(*cutoff) ) 1288 { 1289 int i; 1290 1291 for( i = 0; i < nvars; ++i ) 1292 { 1293 proplbs[i] = SCIPvarGetLbLocal(vars[i]); 1294 propubs[i] = SCIPvarGetUbLocal(vars[i]); 1295 #if 0 1296 #ifdef SCIP_DEBUG 1297 if( SCIPisGT(scip, proplbs[i], SCIPvarGetLbGlobal(vars[i])) ) 1298 { 1299 SCIPdebugMsg(scip, " -> <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[i]), 1300 SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), proplbs[i]); 1301 } 1302 if( SCIPisLT(scip, propubs[i], SCIPvarGetUbGlobal(vars[i])) ) 1303 { 1304 SCIPdebugMsg(scip, " -> <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[i]), 1305 SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), propubs[i]); 1306 } 1307 #endif 1308 #endif 1309 } 1310 } 1311 1312 /* exit probing mode */ 1313 SCIP_CALL( SCIPendProbing(scip) ); 1314 1315 return SCIP_OKAY; 1316 } 1317 1318 /** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings 1319 * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain 1320 * once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations, 1321 * implications, and bound changes. Variable probingvar does not need to be binary. 1322 * The whole domain of probingvar need to be covered by the left and right branches, i.e., 1323 * we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables. 1324 * Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable, 1325 * then already existing implications may be added. 1326 */ 1327 SCIP_RETCODE SCIPanalyzeDeductionsProbing( 1328 SCIP* scip, /**< SCIP data structure */ 1329 SCIP_VAR* probingvar, /**< the probing variable */ 1330 SCIP_Real leftub, /**< upper bound of probing variable in left branch */ 1331 SCIP_Real rightlb, /**< lower bound of probing variable in right branch */ 1332 int nvars, /**< number of variables which bound changes should be analyzed */ 1333 SCIP_VAR** vars, /**< variables which bound changes should be analyzed */ 1334 SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */ 1335 SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */ 1336 SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */ 1337 SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */ 1338 SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */ 1339 SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */ 1340 SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */ 1341 SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */ 1342 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */ 1343 int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */ 1344 int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */ 1345 int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */ 1346 SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */ 1347 ) 1348 { 1349 SCIP_Bool fixedleft; 1350 SCIP_Bool fixedright; 1351 SCIP_Bool probingvarisbinary; 1352 SCIP_Bool probingvarisinteger; 1353 int j; 1354 1355 assert(scip != NULL); 1356 assert(probingvar != NULL); 1357 assert(SCIPisGE(scip, leftub, SCIPvarGetLbLocal(probingvar))); /* left branch should not be empty by default */ 1358 assert(SCIPisLE(scip, rightlb, SCIPvarGetUbLocal(probingvar))); /* right branch should not be empty by default */ 1359 assert(vars != NULL || nvars == 0); 1360 assert(leftproplbs != NULL); 1361 assert(leftpropubs != NULL); 1362 assert(rightproplbs != NULL); 1363 assert(rightpropubs != NULL); 1364 assert(nfixedvars != NULL); 1365 assert(naggrvars != NULL); 1366 assert(nimplications != NULL); 1367 assert(nchgbds != NULL); 1368 assert(cutoff != NULL); 1369 1370 /* @todo the asserts below could be relaxed by taking domain holes into account */ 1371 if( SCIPvarGetType(probingvar) != SCIP_VARTYPE_CONTINUOUS ) 1372 { 1373 /* adjust bounds to actually used ones */ 1374 leftub = SCIPfloor(scip, leftub); 1375 rightlb = SCIPceil(scip, rightlb); 1376 1377 probingvarisinteger = TRUE; 1378 probingvarisbinary = SCIPvarIsBinary(probingvar); 1379 } 1380 else 1381 { 1382 /* assert dichotomy in case of continuous var: leftub >= rightlb */ 1383 assert(SCIPisGE(scip, leftub, rightlb)); 1384 probingvarisbinary = FALSE; 1385 probingvarisinteger = FALSE; 1386 } 1387 1388 /* check if probing variable was fixed in the branches */ 1389 fixedleft = SCIPisEQ(scip, SCIPvarGetLbLocal(probingvar), leftub); 1390 fixedright = SCIPisEQ(scip, SCIPvarGetUbLocal(probingvar), rightlb); 1391 1392 *cutoff = FALSE; 1393 1394 for( j = 0; j < nvars && !*cutoff; ++j ) 1395 { 1396 SCIP_VAR* var; 1397 SCIP_Bool varisinteger; 1398 SCIP_Real newlb; 1399 SCIP_Real newub; 1400 1401 assert(vars != NULL); /* for flexelint */ 1402 1403 var = vars[j]; 1404 assert(var != NULL); 1405 1406 /* @todo: add holes, and even add holes if x was the probing variable and it followed a better bound on x itself */ 1407 /* @todo: check if we probed on an integer variable, that this maybe led to aggregation on two other variables, i.e 1408 * probing on x <= 1 and x >= 2 led to y = 1, z = 1 and y = 0, z = 0 resp., which means y = Z 1409 */ 1410 1411 /* if probing variable is binary, then there is nothing we could deduce here (variable should be fixed in both branches) 1412 * if it is not binary, we want to see if we found bound tightenings, even though it seems quite unlikely */ 1413 if( var == probingvar && probingvarisbinary ) 1414 continue; 1415 1416 /* new bounds of the variable is the union of the propagated bounds of the left and right case */ 1417 newlb = MIN(leftproplbs[j], rightproplbs[j]); 1418 newub = MAX(leftpropubs[j], rightpropubs[j]); 1419 varisinteger = (SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS); 1420 1421 /* check for fixed variables */ 1422 if( SCIPisEQ(scip, newlb, newub) ) 1423 { 1424 SCIP_Real fixval; 1425 SCIP_Bool fixed; 1426 1427 if( !varisinteger ) 1428 { 1429 /* in both probings, variable j is deduced to the same value: fix variable to this value */ 1430 fixval = SCIPselectSimpleValue(newlb - 0.9 * SCIPepsilon(scip), newub + 0.9 * SCIPepsilon(scip), MAXDNOM); 1431 } 1432 else 1433 { 1434 fixval = newlb; 1435 } 1436 1437 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 ) 1438 { 1439 SCIP_CALL( SCIPfixVar(scip, var, fixval, cutoff, &fixed) ); 1440 } 1441 else 1442 { 1443 SCIP_CALL( SCIPtightenVarLb(scip, var, fixval, TRUE, cutoff, &fixed) ); 1444 if( !*cutoff ) 1445 { 1446 SCIP_Bool tightened; 1447 1448 SCIP_CALL( SCIPtightenVarUb(scip, var, fixval, TRUE, cutoff, &tightened) ); 1449 fixed &= tightened; 1450 } 1451 } 1452 1453 if( fixed ) 1454 { 1455 SCIPdebugMsg(scip, "fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n", 1456 SCIPvarGetName(var), fixval, 1457 SCIPvarGetName(probingvar), SCIPvarGetNLocksDownType(probingvar, SCIP_LOCKTYPE_MODEL), 1458 SCIPvarGetNLocksUpType(probingvar, SCIP_LOCKTYPE_MODEL)); 1459 (*nfixedvars)++; 1460 } 1461 else if( *cutoff ) 1462 { 1463 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible fixing of variable <%s> to %g\n", 1464 SCIPvarGetName(probingvar), SCIPvarGetName(var), fixval); 1465 } 1466 1467 continue; 1468 } 1469 else 1470 { 1471 /* check for bound tightenings */ 1472 SCIP_Real oldlb; 1473 SCIP_Real oldub; 1474 SCIP_Bool tightened; 1475 SCIP_Bool tightenlb; 1476 SCIP_Bool tightenub; 1477 SCIP_Bool force; 1478 1479 oldlb = SCIPvarGetLbLocal(var); 1480 oldub = SCIPvarGetUbLocal(var); 1481 1482 if( varisinteger ) 1483 { 1484 force = TRUE; 1485 tightenlb = (newlb > oldlb + 0.5); 1486 tightenub = (newub < oldub - 0.5); 1487 } 1488 else 1489 { 1490 force = TRUE; 1491 tightenlb = SCIPisLbBetter(scip, newlb, oldlb, oldub); 1492 tightenub = SCIPisUbBetter(scip, newub, oldlb, oldub); 1493 } 1494 1495 if( tightenlb ) 1496 { 1497 /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */ 1498 SCIP_CALL( SCIPtightenVarLb(scip, var, newlb, force, cutoff, &tightened) ); 1499 if( tightened ) 1500 { 1501 SCIPdebugMsg(scip, "tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n", 1502 SCIPvarGetName(var), oldlb, oldub, newlb, 1503 SCIPvarGetName(probingvar), SCIPvarGetNLocksDownType(probingvar, SCIP_LOCKTYPE_MODEL), 1504 SCIPvarGetNLocksUpType(probingvar, SCIP_LOCKTYPE_MODEL)); 1505 (*nchgbds)++; 1506 } 1507 else if( *cutoff ) 1508 { 1509 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n", 1510 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb); 1511 } 1512 } 1513 1514 if( tightenub && !*cutoff ) 1515 { 1516 /* in both probings, variable j is deduced to be at most newub: tighten upper bound */ 1517 SCIP_CALL( SCIPtightenVarUb(scip, var, newub, force, cutoff, &tightened) ); 1518 if( tightened ) 1519 { 1520 SCIPdebugMsg(scip, "tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n", 1521 SCIPvarGetName(var), oldlb, oldub, newub, 1522 SCIPvarGetName(probingvar), SCIPvarGetNLocksDownType(probingvar, SCIP_LOCKTYPE_MODEL), 1523 SCIPvarGetNLocksUpType(probingvar, SCIP_LOCKTYPE_MODEL)); 1524 (*nchgbds)++; 1525 } 1526 else if( *cutoff ) 1527 { 1528 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n", 1529 SCIPvarGetName(probingvar), SCIPvarGetName(var), newub); 1530 } 1531 } 1532 if( *cutoff ) 1533 break; 1534 } 1535 1536 /* below we add aggregations and implications between probingvar and var, 1537 * we don't want this if both variables are the same 1538 */ 1539 if( var == probingvar ) 1540 continue; 1541 1542 /* check for aggregations and implications */ 1543 if( fixedleft && fixedright && 1544 SCIPisEQ(scip, leftproplbs[j], leftpropubs[j]) && SCIPisEQ(scip, rightproplbs[j], rightpropubs[j]) ) 1545 { 1546 /* var is fixed whenever probingvar is fixed, i.e., 1547 * var = leftproplbs[j] + (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub) * (probingvar - leftub) 1548 * -> both variables can be aggregated: 1549 * (rightlb - leftub) * (var - leftproplbs[j]) = (rightproplbs[j] - leftproplbs[j]) * (probingvar - leftub) 1550 * -> (rightlb - leftub) * var - (rightproplbs[j] - leftproplbs[j]) * probingvar = leftproplbs[j] * rightlb - rightproplbs[j] * leftub 1551 * 1552 * check for case where both variables are binary: leftub = 1, rightlb = 0 1553 * case leftproplbs[j] = 0, rightproplbs[j] = 1, i.e., var and probingvar are fixed to same value 1554 * -> aggregation is 1 * var - 1 * probingvar = 0 * 1 - 1 * 0 = 0 -> correct 1555 * case leftproplbs[j] = 1, rightproblbs[j] = 0, i.e., var and probingvar are fixed to opposite values 1556 * -> aggregation is 1 * var + 1 * probingvar = 1 * 1 - 0 * 0 = 0 -> correct 1557 */ 1558 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING ) 1559 { 1560 SCIP_Bool aggregated; 1561 SCIP_Bool redundant; 1562 1563 SCIP_CALL( SCIPaggregateVars(scip, var, probingvar, 1564 rightlb - leftub, -(rightproplbs[j] - leftproplbs[j]), leftproplbs[j] * rightlb - rightproplbs[j] * leftub, 1565 cutoff, &redundant, &aggregated) ); 1566 1567 if( aggregated ) 1568 { 1569 SCIPdebugMsg(scip, "aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n", 1570 rightlb - leftub, SCIPvarGetName(var), 1571 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar), 1572 leftproplbs[j] * rightlb - rightproplbs[j] * leftub, 1573 SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL), 1574 SCIPvarGetNLocksUpType(probingvar, SCIP_LOCKTYPE_MODEL)); 1575 (*naggrvars)++; 1576 } 1577 if( *cutoff ) 1578 { 1579 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible aggregation: %g<%s> - %g<%s> == %g\n", 1580 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var), 1581 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar), 1582 leftproplbs[j] * rightlb - rightproplbs[j] * leftub); 1583 } 1584 } 1585 else if( probingvarisinteger && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 ) 1586 { 1587 /* if we are not in presolving, then we cannot do aggregations 1588 * but we can use variable bounds to code the same equality 1589 * var == ((leftproplbs[j] * rightlb - rightproplbs[j] * leftub) + (rightproplbs[j] - leftproplbs[j]) * probingvar) / (rightlb - leftub) 1590 */ 1591 int nboundchanges; 1592 1593 assert(!SCIPisEQ(scip, leftub, rightlb)); 1594 1595 SCIP_CALL( SCIPaddVarVlb(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) ); 1596 (*nchgbds) += nboundchanges; 1597 1598 if( *cutoff ) 1599 { 1600 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vlb: %g<%s> - %g<%s> == %g\n", 1601 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var), 1602 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar), 1603 leftproplbs[j] * rightlb - rightproplbs[j] * leftub); 1604 } 1605 else 1606 { 1607 SCIP_CALL( SCIPaddVarVub(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) ); 1608 (*nchgbds) += nboundchanges; 1609 1610 if( *cutoff ) 1611 { 1612 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vub: %g<%s> - %g<%s> == %g\n", 1613 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var), 1614 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar), 1615 leftproplbs[j] * rightlb - rightproplbs[j] * leftub); 1616 } 1617 } 1618 (*nimplications)++; 1619 } 1620 /* if probingvar is continuous and we are in solving stage, then we do nothing, but it's unlikely that we get 1621 * here (fixedleft && fixedright) with a continuous variable 1622 */ 1623 } 1624 /* @todo: check if we can add variable lowerbounds/upperbounds on integer variables */ 1625 /* can only add implications on binary variables which are globally valid */ 1626 else if( probingvarisbinary && (SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0) ) 1627 { 1628 /* implications can be added only for binary variables */ 1629 int nboundchanges; 1630 1631 /* since probing var is binary variable, probing should have fixed variable in both branches, 1632 * which is to 0.0 in the left branch and to 1.0 in the right branch */ 1633 assert(fixedleft); 1634 assert(fixedright); 1635 assert(SCIPisZero(scip, leftub)); 1636 assert(SCIPisEQ(scip, rightlb, 1.0)); 1637 1638 if( SCIPisEQ(scip, newlb, leftpropubs[j]) && (leftimplubs == NULL || leftimplubs[j] > leftpropubs[j]) ) 1639 { 1640 /* var is fixed to lower bound whenever probingvar is fixed to 0.0 1641 * and implication is not already known 1642 * -> insert implication: probingvar == 0 => var <= leftpropubs[j] 1643 */ 1644 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n", 1645 SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);*/ 1646 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j], 1647 cutoff, &nboundchanges) ); 1648 (*nimplications)++; 1649 (*nchgbds) += nboundchanges; 1650 1651 if( *cutoff ) 1652 { 1653 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n", 1654 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]); 1655 } 1656 } 1657 else if( SCIPisEQ(scip, newub, leftproplbs[j]) && (leftimpllbs == NULL || leftimpllbs[j] < leftproplbs[j]) ) 1658 { 1659 /* var is fixed to upper bound whenever probingvar is fixed to 0.0 1660 * and implication is not already known 1661 * -> insert implication: probingvar == 0 => var >= leftproplbs[j] 1662 */ 1663 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n", 1664 SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);*/ 1665 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j], 1666 cutoff, &nboundchanges) ); 1667 (*nimplications)++; 1668 (*nchgbds) += nboundchanges; 1669 1670 if( *cutoff ) 1671 { 1672 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n", 1673 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]); 1674 } 1675 } 1676 /* we can do an else here, since the case where var is fixed for both fixings of probingvar had been handled as aggregation */ 1677 else if( SCIPisEQ(scip, newlb, rightpropubs[j]) && (rightimplubs == NULL || rightimplubs[j] > rightpropubs[j]) ) 1678 { 1679 /* var is fixed to lower bound whenever probingvar is fixed to 1.0 1680 * and implication is not already known 1681 * -> insert implication: probingvar == 1 => var <= rightpropubs[j] 1682 */ 1683 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n", 1684 SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);*/ 1685 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j], 1686 cutoff, &nboundchanges) ); 1687 (*nimplications)++; 1688 (*nchgbds) += nboundchanges; 1689 1690 if( *cutoff ) 1691 { 1692 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n", 1693 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]); 1694 } 1695 } 1696 else if( SCIPisEQ(scip, newub, rightproplbs[j]) && (rightimpllbs == NULL || rightimpllbs[j] < rightproplbs[j]) ) 1697 { 1698 /* var is fixed to upper bound whenever probingvar is fixed to 1.0 1699 * and implication is not already known 1700 * -> insert implication: probingvar == 1 => var >= leftproplbs[j] 1701 */ 1702 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n", 1703 SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);*/ 1704 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j], 1705 cutoff, &nboundchanges) ); 1706 (*nimplications)++; 1707 (*nchgbds) += nboundchanges; 1708 1709 if( *cutoff ) 1710 { 1711 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n", 1712 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]); 1713 } 1714 } 1715 else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY ) 1716 { 1717 /* check for implications for lower or upper bounds (only store implications with bounds tightened at least by 0.5) 1718 * in case of binary variables, this should have been handled in the previous cases, since every boundchange also fixes the variable 1719 */ 1720 if( leftpropubs[j] < newub - 0.5 && (leftimplubs == NULL || leftpropubs[j] < leftimplubs[j]) ) 1721 { 1722 /* insert implication: probingvar == 0 => var <= leftpropubs[j] */ 1723 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] <= %g\n", 1724 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftpropubs[j]);*/ 1725 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j], 1726 cutoff, &nboundchanges) ); 1727 (*nimplications)++; 1728 (*nchgbds) += nboundchanges; 1729 1730 if( *cutoff ) 1731 { 1732 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> <= %g\n", 1733 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]); 1734 } 1735 } 1736 if( leftproplbs[j] > newlb + 0.5 && (leftimpllbs == NULL || leftproplbs[j] > leftimpllbs[j]) && !*cutoff ) 1737 { 1738 /* insert implication: probingvar == 0 => var >= leftproplbs[j] */ 1739 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] >= %g\n", 1740 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftproplbs[j]);*/ 1741 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j], 1742 cutoff, &nboundchanges) ); 1743 (*nimplications)++; 1744 (*nchgbds) += nboundchanges; 1745 1746 if( *cutoff ) 1747 { 1748 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> >= %g\n", 1749 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]); 1750 } 1751 } 1752 if( rightpropubs[j] < newub - 0.5 && (rightimplubs == NULL || rightpropubs[j] < rightimplubs[j]) && !*cutoff ) 1753 { 1754 /* insert implication: probingvar == 1 => var <= rightpropubs[j] */ 1755 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] <= %g\n", 1756 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightpropubs[j]);*/ 1757 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j], 1758 cutoff, &nboundchanges) ); 1759 (*nimplications)++; 1760 (*nchgbds) += nboundchanges; 1761 1762 if( *cutoff ) 1763 { 1764 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n", 1765 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]); 1766 } 1767 } 1768 if( rightproplbs[j] > newlb + 0.5 && (rightimpllbs == NULL || rightproplbs[j] > rightimpllbs[j]) && !*cutoff ) 1769 { 1770 /* insert implication: probingvar == 1 => var >= rightproplbs[j] */ 1771 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] >= %g\n", 1772 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightproplbs[j]);*/ 1773 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j], 1774 cutoff, &nboundchanges) ); 1775 (*nimplications)++; 1776 (*nchgbds) += nboundchanges; 1777 1778 if( *cutoff ) 1779 { 1780 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n", 1781 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]); 1782 } 1783 } 1784 } 1785 } 1786 } 1787 1788 return SCIP_OKAY; 1789 } 1790