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 scip_probing.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for the probing mode 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Leona Gottwald 32 * @author Stefan Heinz 33 * @author Gregor Hendel 34 * @author Thorsten Koch 35 * @author Alexander Martin 36 * @author Marc Pfetsch 37 * @author Michael Winkler 38 * @author Kati Wolter 39 * 40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "blockmemshell/memory.h" 46 #include "scip/conflict.h" 47 #include "scip/cons.h" 48 #include "scip/debug.h" 49 #include "scip/heur.h" 50 #include "scip/lp.h" 51 #include "scip/prob.h" 52 #include "scip/pub_message.h" 53 #include "scip/pub_misc.h" 54 #include "scip/pub_relax.h" 55 #include "scip/pub_tree.h" 56 #include "scip/pub_var.h" 57 #include "scip/relax.h" 58 #include "scip/scip_general.h" 59 #include "scip/scip_lp.h" 60 #include "scip/scip_mem.h" 61 #include "scip/scip_message.h" 62 #include "scip/scip_numerics.h" 63 #include "scip/scip_prob.h" 64 #include "scip/scip_probing.h" 65 #include "scip/scip_solvingstats.h" 66 #include "scip/scip_tree.h" 67 #include "scip/sepastore.h" 68 #include "scip/set.h" 69 #include "scip/solve.h" 70 #include "scip/stat.h" 71 #include "scip/struct_lp.h" 72 #include "scip/struct_mem.h" 73 #include "scip/struct_scip.h" 74 #include "scip/struct_set.h" 75 #include "scip/struct_stat.h" 76 #include "scip/struct_tree.h" 77 #include "scip/struct_var.h" 78 #include "scip/tree.h" 79 #include "scip/var.h" 80 81 /** returns whether we are in probing mode; probing mode is activated via SCIPstartProbing() and stopped 82 * via SCIPendProbing() 83 * 84 * @return TRUE, if SCIP is currently in probing mode, otherwise FALSE 85 * 86 * @pre This method can be called if @p scip is in one of the following stages: 87 * - \ref SCIP_STAGE_TRANSFORMED 88 * - \ref SCIP_STAGE_INITPRESOLVE 89 * - \ref SCIP_STAGE_PRESOLVING 90 * - \ref SCIP_STAGE_EXITPRESOLVE 91 * - \ref SCIP_STAGE_PRESOLVED 92 * - \ref SCIP_STAGE_INITSOLVE 93 * - \ref SCIP_STAGE_SOLVING 94 * - \ref SCIP_STAGE_SOLVED 95 * - \ref SCIP_STAGE_EXITSOLVE 96 */ 97 SCIP_Bool SCIPinProbing( 98 SCIP* scip /**< SCIP data structure */ 99 ) 100 { 101 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) ); 102 103 return SCIPtreeProbing(scip->tree); 104 } 105 106 /** initiates probing, making methods SCIPnewProbingNode(), SCIPbacktrackProbing(), SCIPchgVarLbProbing(), 107 * SCIPchgVarUbProbing(), SCIPfixVarProbing(), SCIPpropagateProbing(), and SCIPsolveProbingLP() available 108 * 109 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 110 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 111 * 112 * @pre This method can be called if @p scip is in one of the following stages: 113 * - \ref SCIP_STAGE_PRESOLVING 114 * - \ref SCIP_STAGE_SOLVING 115 * 116 * @note The collection of variable statistics is turned off during probing. If these statistics should be collected 117 * during probing use the method SCIPenableVarHistory() to turn the collection explicitly on. 118 */ 119 SCIP_RETCODE SCIPstartProbing( 120 SCIP* scip /**< SCIP data structure */ 121 ) 122 { 123 SCIP_CALL( SCIPcheckStage(scip, "SCIPstartProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 124 125 if( SCIPtreeProbing(scip->tree) ) 126 { 127 SCIPerrorMessage("already in probing mode\n"); 128 return SCIP_INVALIDCALL; 129 } 130 131 if( scip->lp != NULL && SCIPlpDiving(scip->lp) ) 132 { 133 SCIPerrorMessage("cannot start probing while in diving mode\n"); 134 return SCIP_INVALIDCALL; 135 } 136 137 /* use a different separation storage for probing mode; otherwise SCIP will remove the cuts that are currently in the 138 * separation storage after solving an LP in probing mode 139 */ 140 if( scip->sepastore != NULL ) 141 { 142 assert(scip->sepastoreprobing != NULL); 143 SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing); 144 } 145 146 SCIP_CALL( SCIPtreeStartProbing(scip->tree, scip->mem->probmem, scip->set, scip->lp, scip->relaxation, scip->transprob, FALSE) ); 147 148 /* disables the collection of any statistic for a variable */ 149 SCIPstatDisableVarHistory(scip->stat); 150 151 return SCIP_OKAY; 152 } 153 154 /** creates a new probing sub node, whose changes can be undone by backtracking to a higher node in the probing path 155 * with a call to SCIPbacktrackProbing(); 156 * using a sub node for each set of probing bound changes can improve conflict analysis 157 * 158 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 159 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 160 * 161 * @pre This method can be called if @p scip is in one of the following stages: 162 * - \ref SCIP_STAGE_PRESOLVING 163 * - \ref SCIP_STAGE_SOLVING 164 */ 165 SCIP_RETCODE SCIPnewProbingNode( 166 SCIP* scip /**< SCIP data structure */ 167 ) 168 { 169 SCIP_RETCODE retcode; 170 171 SCIP_CALL( SCIPcheckStage(scip, "SCIPnewProbingNode", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 172 173 if( !SCIPtreeProbing(scip->tree) ) 174 { 175 SCIPerrorMessage("not in probing mode\n"); 176 return SCIP_INVALIDCALL; 177 } 178 179 retcode = SCIPtreeCreateProbingNode(scip->tree, scip->mem->probmem, scip->set, scip->lp); 180 181 if( retcode == SCIP_MAXDEPTHLEVEL ) 182 { 183 SCIPwarningMessage(scip, "probing reached maximal depth; it should be stopped\n"); 184 } 185 SCIP_CALL( retcode ); 186 187 return SCIP_OKAY; 188 } 189 190 /** returns the current probing depth 191 * 192 * @return the probing depth, i.e. the number of probing sub nodes existing in the probing path 193 * 194 * @pre This method can be called if @p scip is in one of the following stages: 195 * - \ref SCIP_STAGE_PRESOLVING 196 * - \ref SCIP_STAGE_SOLVING 197 */ 198 int SCIPgetProbingDepth( 199 SCIP* scip /**< SCIP data structure */ 200 ) 201 { 202 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetProbingDepth", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 203 204 if( !SCIPtreeProbing(scip->tree) ) 205 { 206 SCIPerrorMessage("not in probing mode\n"); 207 SCIPABORT(); 208 return -1; /*lint !e527*/ 209 } 210 211 return SCIPtreeGetProbingDepth(scip->tree); 212 } 213 214 /** undoes all changes to the problem applied in probing up to the given probing depth; 215 * the changes of the probing node of the given probing depth are the last ones that remain active; 216 * changes that were applied before calling SCIPnewProbingNode() cannot be undone 217 * 218 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 219 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 220 * 221 * @pre This method can be called if @p scip is in one of the following stages: 222 * - \ref SCIP_STAGE_PRESOLVING 223 * - \ref SCIP_STAGE_SOLVING 224 */ 225 SCIP_RETCODE SCIPbacktrackProbing( 226 SCIP* scip, /**< SCIP data structure */ 227 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */ 228 ) 229 { 230 SCIP_CALL( SCIPcheckStage(scip, "SCIPbacktrackProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 231 232 if( !SCIPtreeProbing(scip->tree) ) 233 { 234 SCIPerrorMessage("not in probing mode\n"); 235 return SCIP_INVALIDCALL; 236 } 237 if( probingdepth < 0 || probingdepth > SCIPtreeGetProbingDepth(scip->tree) ) 238 { 239 SCIPerrorMessage("backtracking probing depth %d out of current probing range [0,%d]\n", 240 probingdepth, SCIPtreeGetProbingDepth(scip->tree)); 241 return SCIP_INVALIDDATA; 242 } 243 244 SCIP_CALL( SCIPtreeBacktrackProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 245 scip->origprob, scip->lp, scip->primal, scip->branchcand, scip->eventqueue, scip->eventfilter, 246 scip->cliquetable, probingdepth) ); 247 248 return SCIP_OKAY; 249 } 250 251 /** quits probing and resets bounds and constraints to the focus node's environment 252 * 253 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 254 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 255 * 256 * @pre This method can be called if @p scip is in one of the following stages: 257 * - \ref SCIP_STAGE_PRESOLVING 258 * - \ref SCIP_STAGE_SOLVING 259 */ 260 SCIP_RETCODE SCIPendProbing( 261 SCIP* scip /**< SCIP data structure */ 262 ) 263 { 264 SCIP_CALL( SCIPcheckStage(scip, "SCIPendProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 265 266 if( !SCIPtreeProbing(scip->tree) ) 267 { 268 SCIPerrorMessage("not in probing mode\n"); 269 return SCIP_INVALIDCALL; 270 } 271 272 /* switch back from probing to normal operation mode and restore variables and constraints to focus node */ 273 SCIP_CALL( SCIPtreeEndProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, 274 scip->transprob, scip->origprob, scip->lp, scip->relaxation, scip->primal, 275 scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable) ); 276 277 /* enables the collection of statistics for a variable */ 278 SCIPstatEnableVarHistory(scip->stat); 279 280 /* switch to the original separation storage */ 281 if( scip->sepastore != NULL ) 282 { 283 assert(scip->sepastoreprobing != NULL); 284 SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing); 285 assert(SCIPsepastoreGetNCuts(scip->sepastoreprobing) == 0); 286 } 287 288 return SCIP_OKAY; 289 } 290 291 /** injects a change of variable's lower bound into current probing node; the same can also be achieved with a call to 292 * SCIPchgVarLb(), but in this case, the bound change would be treated like a deduction instead of a branching decision 293 * 294 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 295 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 296 * 297 * @pre This method can be called if @p scip is in one of the following stages: 298 * - \ref SCIP_STAGE_PRESOLVING 299 * - \ref SCIP_STAGE_SOLVING 300 */ 301 SCIP_RETCODE SCIPchgVarLbProbing( 302 SCIP* scip, /**< SCIP data structure */ 303 SCIP_VAR* var, /**< variable to change the bound for */ 304 SCIP_Real newbound /**< new value for bound */ 305 ) 306 { 307 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarLbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 308 309 if( !SCIPtreeProbing(scip->tree) ) 310 { 311 SCIPerrorMessage("not in probing mode\n"); 312 return SCIP_INVALIDCALL; 313 } 314 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE); 315 316 SCIPvarAdjustLb(var, scip->set, &newbound); 317 318 /* ignore tightenings of lower bounds to +infinity during solving process */ 319 if( SCIPisInfinity(scip, newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING ) 320 { 321 #ifndef NDEBUG 322 SCIPwarningMessage(scip, "ignore lower bound tightening for %s from %e to +infinity\n", SCIPvarGetName(var), 323 SCIPvarGetLbLocal(var)); 324 #endif 325 return SCIP_OKAY; 326 } 327 328 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat, 329 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, 330 var, newbound, SCIP_BOUNDTYPE_LOWER, TRUE) ); 331 332 return SCIP_OKAY; 333 } 334 335 /** injects a change of variable's upper bound into current probing node; the same can also be achieved with a call to 336 * SCIPchgVarUb(), but in this case, the bound change would be treated like a deduction instead of a branching decision 337 * 338 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 339 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 340 * 341 * @pre This method can be called if @p scip is in one of the following stages: 342 * - \ref SCIP_STAGE_PRESOLVING 343 * - \ref SCIP_STAGE_SOLVING 344 */ 345 SCIP_RETCODE SCIPchgVarUbProbing( 346 SCIP* scip, /**< SCIP data structure */ 347 SCIP_VAR* var, /**< variable to change the bound for */ 348 SCIP_Real newbound /**< new value for bound */ 349 ) 350 { 351 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarUbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 352 353 if( !SCIPtreeProbing(scip->tree) ) 354 { 355 SCIPerrorMessage("not in probing mode\n"); 356 return SCIP_INVALIDCALL; 357 } 358 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE); 359 360 SCIPvarAdjustUb(var, scip->set, &newbound); 361 362 /* ignore tightenings of upper bounds to -infinity during solving process */ 363 if( SCIPisInfinity(scip, -newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING ) 364 { 365 #ifndef NDEBUG 366 SCIPwarningMessage(scip, "ignore upper bound tightening for %s from %e to -infinity\n", SCIPvarGetName(var), 367 SCIPvarGetUbLocal(var)); 368 #endif 369 return SCIP_OKAY; 370 } 371 372 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat, 373 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, 374 var, newbound, SCIP_BOUNDTYPE_UPPER, TRUE) ); 375 376 return SCIP_OKAY; 377 } 378 379 /** gets variable's objective value in current probing 380 * 381 * @return the variable's objective value in current probing. 382 * 383 * @pre This method can be called if @p scip is in one of the following stages: 384 * - \ref SCIP_STAGE_SOLVING 385 * 386 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 387 */ 388 SCIP_Real SCIPgetVarObjProbing( 389 SCIP* scip, /**< SCIP data structure */ 390 SCIP_VAR* var /**< variable to get the bound for */ 391 ) 392 { 393 assert(scip != NULL); 394 assert(var != NULL); 395 396 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 397 398 if( !SCIPtreeProbing(scip->tree) ) 399 { 400 SCIPerrorMessage("not in probing mode\n"); 401 return SCIP_INVALID; 402 } 403 404 return SCIPvarGetObjLP(var); 405 } 406 407 /** injects a change of variable's bounds into current probing node to fix the variable to the specified value; 408 * the same can also be achieved with a call to SCIPfixVar(), but in this case, the bound changes would be treated 409 * like deductions instead of branching decisions 410 * 411 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 412 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 413 * 414 * @pre This method can be called if @p scip is in one of the following stages: 415 * - \ref SCIP_STAGE_PRESOLVING 416 * - \ref SCIP_STAGE_SOLVING 417 */ 418 SCIP_RETCODE SCIPfixVarProbing( 419 SCIP* scip, /**< SCIP data structure */ 420 SCIP_VAR* var, /**< variable to change the bound for */ 421 SCIP_Real fixedval /**< value to fix variable to */ 422 ) 423 { 424 SCIP_Real fixlb; 425 SCIP_Real fixub; 426 427 SCIP_CALL( SCIPcheckStage(scip, "SCIPfixVarProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 428 429 if( !SCIPtreeProbing(scip->tree) ) 430 { 431 SCIPerrorMessage("not in probing mode\n"); 432 return SCIP_INVALIDCALL; 433 } 434 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE); 435 436 /* we adjust the fixing value here and compare the old bound with the adjusted values because otherwise, 437 * it might happen that the unadjusted value is better and we add the boundchange, 438 * but within SCIPnodeAddBoundchg() the bounds are adjusted - using the feasibility epsilon for integer variables - 439 * and it is asserted, that the bound is still better than the old one which might then be incorrect. 440 */ 441 fixlb = fixedval; 442 fixub = fixedval; 443 SCIPvarAdjustLb(var, scip->set, &fixlb); 444 SCIPvarAdjustUb(var, scip->set, &fixub); 445 assert(SCIPsetIsEQ(scip->set, fixlb, fixub)); 446 447 if( SCIPsetIsGT(scip->set, fixlb, SCIPvarGetLbLocal(var)) ) 448 { 449 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat, 450 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, 451 scip->cliquetable, var, fixlb, SCIP_BOUNDTYPE_LOWER, TRUE) ); 452 } 453 if( SCIPsetIsLT(scip->set, fixub, SCIPvarGetUbLocal(var)) ) 454 { 455 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat, 456 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, 457 var, fixub, SCIP_BOUNDTYPE_UPPER, TRUE) ); 458 } 459 460 return SCIP_OKAY; 461 } 462 463 /** changes (column) variable's objective value during probing mode 464 * 465 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 466 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 467 * 468 * @pre This method can be called if @p scip is in one of the following stages: 469 * - \ref SCIP_STAGE_PRESOLVING 470 * - \ref SCIP_STAGE_SOLVING 471 * 472 * @pre The variable needs to be a column variable. 473 */ 474 SCIP_RETCODE SCIPchgVarObjProbing( 475 SCIP* scip, /**< SCIP data structure */ 476 SCIP_VAR* var, /**< variable to change the objective for */ 477 SCIP_Real newobj /**< new objective function value */ 478 ) 479 { 480 SCIP_NODE* node; 481 SCIP_Real oldobj; 482 483 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 484 485 if( !SCIPtreeProbing(scip->tree) ) 486 { 487 SCIPerrorMessage("not in probing mode\n"); 488 return SCIP_INVALIDCALL; 489 } 490 491 /* get current probing node */ 492 node = SCIPtreeGetCurrentNode(scip->tree); 493 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE); 494 495 /* get old objective function value */ 496 oldobj = SCIPvarGetObj(var); 497 498 if( SCIPisEQ(scip, oldobj, newobj) ) 499 return SCIP_OKAY; 500 501 if( node->data.probingnode->nchgdobjs == 0 ) 502 { 503 SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvars, 1) ); /*lint !e506*/ 504 SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvals, 1) ); /*lint !e506*/ 505 } 506 else 507 { 508 SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvars, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/ 509 SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvals, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/ 510 } 511 512 node->data.probingnode->origobjvars[node->data.probingnode->nchgdobjs] = var; 513 node->data.probingnode->origobjvals[node->data.probingnode->nchgdobjs] = oldobj; 514 ++node->data.probingnode->nchgdobjs; 515 ++scip->tree->probingsumchgdobjs; 516 517 assert(SCIPtreeProbingObjChanged(scip->tree) == SCIPlpDivingObjChanged(scip->lp)); 518 519 /* inform tree and LP that the objective was changed and invalidate the LP's cutoff bound, since this has nothing to 520 * do with the current objective value anymore; the cutoff bound is reset in SCIPendProbing() 521 */ 522 if( !SCIPtreeProbingObjChanged(scip->tree) ) 523 { 524 SCIP_CALL( SCIPlpSetCutoffbound(scip->lp, scip->set, scip->transprob, SCIPsetInfinity(scip->set)) ); 525 526 SCIPtreeMarkProbingObjChanged(scip->tree); 527 SCIPlpMarkDivingObjChanged(scip->lp); 528 } 529 assert(SCIPisInfinity(scip, scip->lp->cutoffbound)); 530 531 /* perform the objective change */ 532 SCIP_CALL( SCIPvarChgObj(var, scip->mem->probmem, scip->set, scip->transprob, scip->primal, scip->lp, scip->eventqueue, newobj) ); 533 534 return SCIP_OKAY; 535 } 536 537 /** returns whether the objective function has changed during probing mode 538 * 539 * @return \ref TRUE if objective has changed, \ref FALSE otherwise 540 * 541 * @pre This method can be called if @p scip is in one of the following stages: 542 * - \ref SCIP_STAGE_TRANSFORMED 543 * - \ref SCIP_STAGE_INITPRESOLVE 544 * - \ref SCIP_STAGE_PRESOLVING 545 * - \ref SCIP_STAGE_EXITPRESOLVE 546 * - \ref SCIP_STAGE_PRESOLVED 547 * - \ref SCIP_STAGE_INITSOLVE 548 * - \ref SCIP_STAGE_SOLVING 549 * - \ref SCIP_STAGE_SOLVED 550 * - \ref SCIP_STAGE_EXITSOLVE 551 */ 552 SCIP_Bool SCIPisObjChangedProbing( 553 SCIP* scip /**< SCIP data structure */ 554 ) 555 { 556 assert(scip != NULL); 557 558 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisObjChangedProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) ); 559 560 return scip->tree != NULL && SCIPinProbing(scip) && SCIPtreeProbingObjChanged(scip->tree); 561 } 562 563 /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called; 564 * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal() 565 * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed 566 * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation 567 * 568 * @note Conflict analysis can run if the propagation finds infeasibilities. SCIPpropagateProbing can even find 569 * globally valid bound changes. For this reason, the function restores the original objective (i.e. undoes the changes 570 * done by SCIPchgVarObjProbing before performing the propagation, as the propagators don't know that the objective 571 * might have changed. Thus, SCIPpropagateProbing can have an effect on the problem after probing ends. 572 * 573 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 574 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 575 * 576 * @pre This method can be called if @p scip is in one of the following stages: 577 * - \ref SCIP_STAGE_PRESOLVING 578 * - \ref SCIP_STAGE_SOLVING 579 */ 580 SCIP_RETCODE SCIPpropagateProbing( 581 SCIP* scip, /**< SCIP data structure */ 582 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ 583 SCIP_Bool* cutoff, /**< pointer to store whether the probing node can be cut off */ 584 SCIP_Longint* ndomredsfound /**< pointer to store the number of domain reductions found, or NULL */ 585 ) 586 { 587 SCIP_VAR** objchgvars; 588 SCIP_Real* objchgvals; 589 SCIP_Bool changedobj; 590 int nobjchg; 591 592 SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 593 594 if( !SCIPtreeProbing(scip->tree) ) 595 { 596 SCIPerrorMessage("not in probing mode\n"); 597 return SCIP_INVALIDCALL; 598 } 599 600 objchgvars = NULL; 601 objchgvals = NULL; 602 changedobj = FALSE; 603 nobjchg = 0; 604 605 /* undo objective changes if we want to propagate during probing */ 606 if( scip->tree->probingobjchanged ) 607 { 608 SCIP_VAR** vars; 609 int nvars; 610 int i; 611 612 vars = SCIPgetVars(scip); 613 nvars = SCIPgetNVars(scip); 614 615 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, MIN(nvars, scip->tree->probingsumchgdobjs)) ); 616 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvars, MIN(nvars, scip->tree->probingsumchgdobjs)) ); 617 nobjchg = 0; 618 619 for( i = 0; i < nvars; ++i ) 620 { 621 if( !SCIPisEQ(scip, vars[i]->unchangedobj, SCIPgetVarObjProbing(scip, vars[i])) ) 622 { 623 objchgvars[nobjchg] = vars[i]; 624 objchgvals[nobjchg] = SCIPgetVarObjProbing(scip, vars[i]); 625 ++nobjchg; 626 627 SCIP_CALL( SCIPvarChgObj(vars[i], scip->mem->probmem, scip->set, scip->transprob, scip->primal, scip->lp, 628 scip->eventqueue, vars[i]->unchangedobj) ); 629 } 630 } 631 assert(nobjchg <= scip->tree->probingsumchgdobjs); 632 633 SCIPlpUnmarkDivingObjChanged(scip->lp); 634 scip->tree->probingobjchanged = FALSE; 635 changedobj = TRUE; 636 } 637 638 if( ndomredsfound != NULL ) 639 *ndomredsfound = -(scip->stat->nprobboundchgs + scip->stat->nprobholechgs); 640 641 SCIP_CALL( SCIPpropagateDomains(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 642 scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->conflict, scip->cliquetable, 643 SCIPgetDepth(scip), maxproprounds, SCIP_PROPTIMING_ALWAYS, cutoff) ); 644 645 if( ndomredsfound != NULL ) 646 *ndomredsfound += scip->stat->nprobboundchgs + scip->stat->nprobholechgs; 647 648 /* restore old objective function */ 649 if( changedobj ) 650 { 651 int i; 652 653 assert(objchgvars != NULL); 654 assert(objchgvals != NULL); 655 656 SCIPlpMarkDivingObjChanged(scip->lp); 657 scip->tree->probingobjchanged = TRUE; 658 659 for( i = 0; i < nobjchg; ++i ) 660 { 661 SCIP_CALL( SCIPvarChgObj(objchgvars[i], scip->mem->probmem, scip->set, scip->transprob, scip->primal, 662 scip->lp, scip->eventqueue, objchgvals[i]) ); 663 } 664 665 SCIPfreeBufferArray(scip, &objchgvars); 666 SCIPfreeBufferArray(scip, &objchgvals); 667 } 668 669 return SCIP_OKAY; 670 } 671 672 /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called; 673 * only propagations of the binary variables fixed at the current probing node that are triggered by the implication 674 * graph and the clique table are applied; 675 * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal() 676 * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed 677 * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation 678 * 679 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 680 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 681 * 682 * @pre This method can be called if @p scip is in one of the following stages: 683 * - \ref SCIP_STAGE_PRESOLVING 684 * - \ref SCIP_STAGE_SOLVING 685 */ 686 SCIP_RETCODE SCIPpropagateProbingImplications( 687 SCIP* scip, /**< SCIP data structure */ 688 SCIP_Bool* cutoff /**< pointer to store whether the probing node can be cut off */ 689 ) 690 { 691 SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbingImplications", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 692 693 if( !SCIPtreeProbing(scip->tree) ) 694 { 695 SCIPerrorMessage("not in probing mode\n"); 696 return SCIP_INVALIDCALL; 697 } 698 699 SCIP_CALL( SCIPnodePropagateImplics(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat, 700 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, cutoff) ); 701 702 return SCIP_OKAY; 703 } 704 705 /** solves the LP at the current probing node (cannot be applied at preprocessing stage) with or without pricing */ 706 static 707 SCIP_RETCODE solveProbingLP( 708 SCIP* scip, /**< SCIP data structure */ 709 int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */ 710 SCIP_Bool pricing, /**< should pricing be applied? */ 711 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */ 712 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */ 713 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit) */ 714 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */ 715 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective 716 * limit was reached (or NULL, if not needed) */ 717 ) 718 { 719 SCIP_Bool initcutoff; 720 721 assert(lperror != NULL); 722 assert(SCIPtreeIsFocusNodeLPConstructed(scip->tree)); 723 724 if( !SCIPtreeProbing(scip->tree) ) 725 { 726 SCIPerrorMessage("not in probing mode\n"); 727 return SCIP_INVALIDCALL; 728 } 729 assert(SCIPtreeGetCurrentDepth(scip->tree) > 0); 730 731 SCIP_CALL( SCIPinitConssLP(scip->mem->probmem, scip->set, scip->sepastore, scip->cutpool, scip->stat, scip->transprob, 732 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter, 733 scip->cliquetable, FALSE, FALSE, &initcutoff) ); 734 735 if( initcutoff ) 736 { 737 if( cutoff != NULL ) 738 *cutoff = TRUE; 739 740 return SCIP_OKAY; 741 } 742 else if( cutoff != NULL ) 743 *cutoff = FALSE; 744 745 /* load the LP state (if necessary) */ 746 SCIP_CALL( SCIPtreeLoadProbingLPState(scip->tree, scip->mem->probmem, scip->set, scip->transprob, scip->eventqueue, scip->lp) ); 747 748 SCIPlpSetIsRelax(scip->lp, TRUE); 749 750 /* solve probing LP */ 751 SCIP_CALL( SCIPlpSolveAndEval(scip->lp, scip->set, scip->messagehdlr, scip->mem->probmem, scip->stat, 752 scip->eventqueue, scip->eventfilter, scip->transprob, (SCIP_Longint)itlim, FALSE, FALSE, FALSE, lperror) ); 753 754 assert((*lperror) || SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_NOTSOLVED); 755 756 /* mark the probing node to have a solved LP */ 757 if( !(*lperror) ) 758 { 759 SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) ); 760 761 /* call pricing */ 762 if( pricing ) 763 { 764 SCIP_Bool mustsepa; 765 int npricedcolvars; 766 SCIP_Bool result; 767 768 mustsepa = FALSE; 769 SCIP_CALL( SCIPpriceLoop(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob, 770 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->pricestore, scip->sepastore, scip->cutpool, 771 scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable, pretendroot, displayinfo, 772 maxpricerounds, &npricedcolvars, &mustsepa, lperror, &result) ); 773 774 /* mark the probing node again to update the LP size in the node and the tree path */ 775 if( !(*lperror) ) 776 { 777 SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) ); 778 } 779 } 780 } 781 782 /* remember that probing might have changed the LPi state; this holds even if solving returned with an LP error */ 783 scip->tree->probingsolvedlp = TRUE; 784 785 /* the LP is infeasible or the objective limit was reached */ 786 if( !(*lperror) && (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_INFEASIBLE 787 || SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OBJLIMIT || 788 (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OPTIMAL 789 && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))) ) 790 { 791 /* analyze the infeasible LP (only if all columns are in the LP and no external pricers exist) */ 792 if( !scip->set->misc_exactsolve && SCIPprobAllColsInLP(scip->transprob, scip->set, scip->lp) && !scip->tree->probingobjchanged ) 793 { 794 SCIP_CALL( SCIPconflictAnalyzeLP(scip->conflict, scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 795 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, NULL) ); 796 } 797 798 if( cutoff != NULL ) 799 *cutoff = TRUE; 800 } 801 802 return SCIP_OKAY; 803 } 804 805 /** solves the LP at the current probing node (cannot be applied at preprocessing stage); 806 * no separation or pricing is applied 807 * 808 * The LP has to be constructed before (you can use SCIPisLPConstructed() or SCIPconstructLP()). 809 * 810 * @note if the LP is infeasible or the objective limit is reached, and if all columns are in the LP and no external 811 * pricers exist then conflict analysis will be run. This can have an effect on the problem after probing ends. 812 * 813 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 814 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 815 * 816 * @pre This method can be called if @p scip is in one of the following stages: 817 * - \ref SCIP_STAGE_SOLVING 818 */ 819 SCIP_RETCODE SCIPsolveProbingLP( 820 SCIP* scip, /**< SCIP data structure */ 821 int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */ 822 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */ 823 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective 824 * limit was reached (or NULL, if not needed) */ 825 ) 826 { 827 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 828 829 SCIP_CALL( solveProbingLP(scip, itlim, FALSE, FALSE, FALSE, -1, lperror, cutoff) ); 830 831 return SCIP_OKAY; 832 } 833 834 /** solves the LP at the current probing node (cannot be applied at preprocessing stage) and applies pricing 835 * until the LP is solved to optimality; no separation is applied 836 * 837 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 838 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 839 * 840 * @pre This method can be called if @p scip is in one of the following stages: 841 * - \ref SCIP_STAGE_SOLVING 842 */ 843 SCIP_RETCODE SCIPsolveProbingLPWithPricing( 844 SCIP* scip, /**< SCIP data structure */ 845 SCIP_Bool pretendroot, /**< should the pricers be called as if we were at the root node? */ 846 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */ 847 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit); 848 * a finite limit means that the LP might not be solved to optimality! */ 849 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */ 850 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective 851 * limit was reached (or NULL, if not needed) */ 852 ) 853 { 854 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLPWithPricing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 855 856 SCIP_CALL( solveProbingLP(scip, -1, TRUE, pretendroot, displayinfo, maxpricerounds, lperror, cutoff) ); 857 858 return SCIP_OKAY; 859 } 860 861 /** sets the LP state for the current probing node 862 * 863 * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set 864 * to NULL by the method 865 * 866 * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the 867 * respective information should not be set 868 * 869 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 870 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 871 * 872 * @pre This method can be called if @p scip is in one of the following stages: 873 * - \ref SCIP_STAGE_PRESOLVING 874 * - \ref SCIP_STAGE_SOLVING 875 */ 876 SCIP_RETCODE SCIPsetProbingLPState( 877 SCIP* scip, /**< SCIP data structure */ 878 SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */ 879 SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */ 880 SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */ 881 SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */ 882 ) 883 { 884 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetProbingLPState", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 885 886 if( !SCIPtreeProbing(scip->tree) ) 887 { 888 SCIPerrorMessage("not in probing mode\n"); 889 return SCIP_INVALIDCALL; 890 } 891 892 SCIP_CALL( SCIPtreeSetProbingLPState(scip->tree, scip->mem->probmem, scip->lp, lpistate, lpinorms, primalfeas, dualfeas) ); 893 894 return SCIP_OKAY; 895 } 896 897 /** adds a row to the LP in the current probing node 898 * 899 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 900 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 901 * 902 * @pre This method can be called if @p scip is in one of the following stages: 903 * - \ref SCIP_STAGE_SOLVING 904 * 905 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 906 */ 907 SCIP_RETCODE SCIPaddRowProbing( 908 SCIP* scip, /**< SCIP data structure */ 909 SCIP_ROW* row /**< row to be added */ 910 ) 911 { 912 SCIP_NODE* node; 913 int depth; 914 915 assert(scip != NULL); 916 assert(row != NULL); 917 918 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddRowProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 919 920 if( !SCIPtreeProbing(scip->tree) ) 921 { 922 SCIPerrorMessage("not in probing mode\n"); 923 return SCIP_INVALIDCALL; 924 } 925 926 /* get depth of current node */ 927 node = SCIPtreeGetCurrentNode(scip->tree); 928 assert(node != NULL); 929 depth = SCIPnodeGetDepth(node); 930 931 SCIP_CALL( SCIPlpAddRow(scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter, row, depth) ); 932 933 return SCIP_OKAY; 934 } 935 936 937 /** applies the cuts in the separation storage to the LP and clears the storage afterwards; 938 * this method can only be applied during probing; the user should resolve the probing LP afterwards 939 * in order to get a new solution 940 * 941 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 942 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 943 * 944 * @pre This method can be called if @p scip is in one of the following stages: 945 * - \ref SCIP_STAGE_SOLVING 946 */ 947 SCIP_RETCODE SCIPapplyCutsProbing( 948 SCIP* scip, /**< SCIP data structure */ 949 SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */ 950 ) 951 { 952 SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyCutsProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 953 954 if( !SCIPtreeProbing(scip->tree) ) 955 { 956 SCIPerrorMessage("not in probing mode\n"); 957 return SCIP_INVALIDCALL; 958 } 959 960 SCIP_CALL( SCIPsepastoreApplyCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 961 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter, 962 scip->cliquetable, FALSE, SCIP_EFFICIACYCHOICE_LP, cutoff) ); 963 964 return SCIP_OKAY; 965 } 966 967 /** solves relaxation(s) at the current probing node (cannot be applied at preprocessing stage); 968 * no separation or pricing is applied 969 * 970 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 971 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 972 * 973 * @pre This method can be called if @p scip is in one of the following stages: 974 * - \ref SCIP_STAGE_SOLVING 975 */ 976 SCIP_RETCODE SCIPsolveProbingRelax( 977 SCIP* scip, /**< SCIP data structure */ 978 SCIP_Bool* cutoff /**< pointer to store whether a relaxation was infeasible or the objective 979 * limit was reached (or NULL, if not needed) */ 980 ) 981 { 982 SCIP_SET* set; 983 int r; 984 985 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingRelax", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 986 987 if ( ! SCIPtreeProbing(scip->tree) ) 988 { 989 SCIPerrorMessage("not in probing mode\n"); 990 return SCIP_INVALIDCALL; 991 } 992 assert( SCIPtreeGetCurrentDepth(scip->tree) > 0 ); 993 994 assert( cutoff != NULL ); 995 *cutoff = FALSE; 996 997 set = scip->set; 998 999 /* sort relaxators by priority */ 1000 SCIPsetSortRelaxs(set); 1001 1002 /* solve relaxations */ 1003 for (r = 0; r < set->nrelaxs && !(*cutoff); ++r) 1004 { 1005 SCIP_RELAX* relax; 1006 SCIP_Real lowerbound; 1007 SCIP_RESULT result; 1008 1009 lowerbound = -SCIPinfinity(scip); 1010 1011 relax = set->relaxs[r]; 1012 assert( relax != NULL ); 1013 1014 SCIP_CALL( SCIPrelaxExec(relax, set, scip->tree, scip->stat, SCIPtreeGetCurrentDepth(scip->tree), &lowerbound, &result) ); 1015 1016 switch( result ) 1017 { 1018 case SCIP_CUTOFF: 1019 *cutoff = TRUE; 1020 SCIPdebugMsg(scip, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(relax)); 1021 break; 1022 1023 case SCIP_CONSADDED: 1024 case SCIP_REDUCEDDOM: 1025 case SCIP_SEPARATED: 1026 case SCIP_SUSPENDED: 1027 SCIPerrorMessage("The relaxator should not return <%d> within probing mode.\n", result); 1028 break; 1029 1030 case SCIP_SUCCESS: 1031 case SCIP_DIDNOTRUN: 1032 break; 1033 1034 default: 1035 SCIPerrorMessage("Invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(relax)); 1036 return SCIP_INVALIDRESULT; 1037 } /*lint !e788*/ 1038 } 1039 1040 return SCIP_OKAY; 1041 } 1042 1043 /** print statistics of probing */ 1044 char* SCIPsnprintfProbingStats( 1045 SCIP* scip, /**< SCIP data structure */ 1046 char* strbuf, /**< string buffer */ 1047 int len /**< length of string buffer */ 1048 ) 1049 { 1050 char* ptr = strbuf; 1051 const int nvartypes = 4; 1052 1053 assert(scip != NULL); 1054 assert(strbuf != NULL); 1055 1056 if( SCIPinProbing(scip) ) 1057 { 1058 SCIP_VAR** vars; 1059 int nbinvars = SCIPgetNBinVars(scip); 1060 int nintvars = SCIPgetNIntVars(scip); 1061 int nimplvars = SCIPgetNImplVars(scip); 1062 int nvars = SCIPgetNVars(scip); 1063 int vartypeend[] = { 1064 nbinvars, 1065 nbinvars + nintvars, 1066 nbinvars + nintvars + nimplvars, 1067 nvars 1068 }; 1069 const char* vartypenames[] = { 1070 "binary", 1071 "integer", 1072 "implicit integer", 1073 "continuous" 1074 }; 1075 int nvartypefixed[4]; 1076 int nvarsfixed = 0; 1077 int depth; 1078 int probingdepth; 1079 int vartypestart = 0; 1080 int v; 1081 int p; 1082 1083 vars = SCIPgetVars(scip); 1084 BMSclearMemoryArray(nvartypefixed, nvartypes); 1085 1086 /* loop over vartypes and count fixings */ 1087 for( p = 0; p < nvartypes; ++p ) 1088 { 1089 for( v = vartypestart; v < vartypeend[p]; ++v ) 1090 { 1091 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) ) 1092 ++nvartypefixed[p]; 1093 } 1094 nvarsfixed += nvartypefixed[p]; 1095 vartypestart = vartypeend[p]; 1096 } 1097 1098 depth = SCIPgetDepth(scip); 1099 probingdepth = SCIPgetProbingDepth(scip); 1100 1101 ptr += SCIPsnprintf(ptr, len, "Depth: (%d total, %d probing) ", depth, probingdepth); 1102 ptr += SCIPsnprintf(ptr, len, "Fixed/Variables: %d / %d (", nvarsfixed, vartypeend[nvartypes - 1]); 1103 1104 for( p = 0; p < nvartypes; ++p ) 1105 { 1106 int ntypevars = vartypeend[p] - (p == 0 ? 0 : vartypeend[p - 1]); 1107 ptr += SCIPsnprintf(ptr, len, "%d / %d %s%s", nvartypefixed[p], ntypevars, vartypenames[p], p < (nvartypes - 1) ? ", " : ")"); 1108 } 1109 } 1110 else 1111 { 1112 (void) SCIPsnprintf(strbuf, len, "Not in probing"); 1113 } 1114 1115 return strbuf; 1116 } 1117 1118 /** gets the candidate score and preferred rounding direction for a candidate variable */ 1119 SCIP_RETCODE SCIPgetDivesetScore( 1120 SCIP* scip, /**< SCIP data structure */ 1121 SCIP_DIVESET* diveset, /**< general diving settings */ 1122 SCIP_DIVETYPE divetype, /**< represents different methods for a dive set to explore the next children */ 1123 SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */ 1124 SCIP_Real divecandsol, /**< LP solution value of the candidate */ 1125 SCIP_Real divecandfrac, /**< fractionality of the candidate */ 1126 SCIP_Real* candscore, /**< pointer to store the candidate score */ 1127 SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */ 1128 ) 1129 { 1130 assert(scip != NULL); 1131 assert(candscore != NULL); 1132 assert(roundup != NULL); 1133 assert(divecand != NULL); 1134 1135 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDivesetScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1136 1137 SCIP_CALL( SCIPdivesetGetScore(diveset, scip->set, divetype, divecand, divecandsol, divecandfrac, candscore, 1138 roundup) ); 1139 1140 return SCIP_OKAY; 1141 } 1142 1143 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */ 1144 void SCIPupdateDivesetLPStats( 1145 SCIP* scip, /**< SCIP data structure */ 1146 SCIP_DIVESET* diveset, /**< diving settings */ 1147 SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */ 1148 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 1149 ) 1150 { 1151 assert(scip != NULL); 1152 assert(diveset != NULL); 1153 1154 SCIPdivesetUpdateLPStats(diveset, scip->stat, niterstoadd, divecontext); 1155 } 1156 1157 /** update diveset statistics and global diveset statistics */ 1158 void SCIPupdateDivesetStats( 1159 SCIP* scip, /**< SCIP data structure */ 1160 SCIP_DIVESET* diveset, /**< diveset to be reset */ 1161 int nprobingnodes, /**< the number of probing nodes explored this time */ 1162 int nbacktracks, /**< the number of backtracks during probing this time */ 1163 SCIP_Longint nsolsfound, /**< the number of solutions found */ 1164 SCIP_Longint nbestsolsfound, /**< the number of best solutions found */ 1165 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */ 1166 SCIP_Bool leavewassol, /**< was a solution found at the leaf? */ 1167 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */ 1168 ) 1169 { 1170 assert(scip != NULL); 1171 assert(diveset != NULL); 1172 assert(SCIPinProbing(scip)); 1173 1174 SCIPdivesetUpdateStats(diveset, scip->stat, SCIPgetDepth(scip), nprobingnodes, nbacktracks, nsolsfound, 1175 nbestsolsfound, nconflictsfound, leavewassol, divecontext); 1176 } 1177 1178 /** enforces a probing/diving solution by suggesting bound changes that maximize the score w.r.t. the current diving settings 1179 * 1180 * the process is guided by the enforcement priorities of the constraint handlers and the scoring mechanism provided by 1181 * the dive set. 1182 * Constraint handlers may suggest diving bound changes in decreasing order of their enforcement priority, based on the 1183 * solution values in the solution @p sol and the current local bounds of the variables. A diving bound change 1184 * is a triple (variable,branching direction,value) and is used inside SCIPperformGenericDivingAlgorithm(). 1185 * 1186 * After a successful call, SCIP holds two arrays of suggested dive bound changes, one for the preferred child 1187 * and one for the alternative. 1188 * 1189 * @see SCIPgetDiveBoundChangeData() for retrieving the dive bound change suggestions. 1190 * 1191 * The method stops after the first constraint handler was successful 1192 * 1193 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1194 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1195 * 1196 * @pre This method can be called if @p scip is in one of the following stages: 1197 * - \ref SCIP_STAGE_SOLVING 1198 * 1199 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1200 */ 1201 SCIP_RETCODE SCIPgetDiveBoundChanges( 1202 SCIP* scip, /**< SCIP data structure */ 1203 SCIP_DIVESET* diveset, /**< diving settings to control scoring */ 1204 SCIP_SOL* sol, /**< current solution of diving mode */ 1205 SCIP_Bool* success, /**< pointer to store whether constraint handler successfully found a variable */ 1206 SCIP_Bool* infeasible /**< pointer to store whether the current node was detected to be infeasible */ 1207 ) 1208 { 1209 int i; 1210 1211 assert(scip != NULL); 1212 assert(diveset != NULL); 1213 assert(SCIPinProbing(scip)); 1214 assert(infeasible != NULL); 1215 assert(success != NULL); 1216 1217 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1218 1219 *success = FALSE; 1220 *infeasible = FALSE; 1221 1222 /* we invalidate the previously stored bound changes */ 1223 SCIPclearDiveBoundChanges(scip); 1224 1225 /* loop over constraint handlers until a constraint handler successfully found a variable/value assignment for proceeding 1226 * or a constraint handler detected the infeasibility of the local node 1227 */ 1228 for( i = 0; i < scip->set->nconshdlrs && !(*success || *infeasible); ++i ) 1229 { 1230 SCIP_CALL( SCIPconshdlrGetDiveBoundChanges(scip->set->conshdlrs_enfo[i], scip->set, diveset, sol, 1231 success, infeasible) ); 1232 } 1233 1234 #ifndef NDEBUG 1235 /* check if the constraint handler correctly assigned values to the dive set */ 1236 if( *success ) 1237 { 1238 SCIP_VAR** bdchgvars; 1239 SCIP_BRANCHDIR* bdchgdirs; 1240 SCIP_Real* values; 1241 int nbdchanges; 1242 SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, TRUE); 1243 assert(nbdchanges > 0); 1244 SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, FALSE); 1245 assert(nbdchanges > 0); 1246 } 1247 #endif 1248 1249 return SCIP_OKAY; 1250 } 1251 1252 /** adds a diving bound change to the diving bound change storage of SCIP together with the information if this is a 1253 * bound change for the preferred direction or not 1254 * 1255 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1256 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1257 * 1258 * @pre This method can be called if @p scip is in one of the following stages: 1259 * - \ref SCIP_STAGE_SOLVING 1260 * 1261 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1262 */ 1263 SCIP_RETCODE SCIPaddDiveBoundChange( 1264 SCIP* scip, /**< SCIP data structure */ 1265 SCIP_VAR* var, /**< variable to apply the bound change to */ 1266 SCIP_BRANCHDIR dir, /**< direction of the bound change */ 1267 SCIP_Real value, /**< value to adjust this variable bound to */ 1268 SCIP_Bool preferred /**< is this a bound change for the preferred child? */ 1269 ) 1270 { 1271 assert(scip->tree != NULL); 1272 assert(scip->mem->probmem != NULL); 1273 assert(SCIPinProbing(scip)); 1274 1275 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDiveBoundChange", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1276 1277 SCIP_CALL( SCIPtreeAddDiveBoundChange(scip->tree, scip->mem->probmem, var, dir, value, preferred) ); 1278 1279 return SCIP_OKAY; 1280 } 1281 1282 /** get the dive bound change data for the preferred or the alternative direction 1283 * 1284 * @pre This method can be called if @p scip is in one of the following stages: 1285 * - \ref SCIP_STAGE_SOLVING 1286 * 1287 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1288 */ 1289 void SCIPgetDiveBoundChangeData( 1290 SCIP* scip, /**< SCIP data structure */ 1291 SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */ 1292 SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */ 1293 SCIP_Real** values, /**< pointer to store bound change values */ 1294 int* ndivebdchgs, /**< pointer to store the number of dive bound changes */ 1295 SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */ 1296 ) 1297 { 1298 assert(variables != NULL); 1299 assert(directions != NULL); 1300 assert(values != NULL); 1301 assert(ndivebdchgs != NULL); 1302 assert(SCIPinProbing(scip)); 1303 1304 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDiveBoundChangeData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1305 1306 SCIPtreeGetDiveBoundChangeData(scip->tree, variables, directions, values, ndivebdchgs, preferred); 1307 } 1308 1309 /** clear the dive bound change data structures 1310 * 1311 * @pre This method can be called if @p scip is in one of the following stages: 1312 * - \ref SCIP_STAGE_SOLVING 1313 * 1314 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1315 */ 1316 void SCIPclearDiveBoundChanges( 1317 SCIP* scip /**< SCIP data structure */ 1318 ) 1319 { 1320 assert(scip->tree != NULL); 1321 1322 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1323 1324 SCIPtreeClearDiveBoundChanges(scip->tree); 1325 } 1326