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_conflict.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for conflict handler plugins and conflict analysis 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 "scip/conflict.h" 46 #include "scip/debug.h" 47 #include "scip/pub_cons.h" 48 #include "scip/pub_message.h" 49 #include "scip/pub_var.h" 50 #include "scip/scip_conflict.h" 51 #include "scip/scip_tree.h" 52 #include "scip/set.h" 53 #include "scip/struct_mem.h" 54 #include "scip/struct_scip.h" 55 #include "scip/struct_set.h" 56 #include "scip/struct_var.h" 57 58 /** creates a conflict handler and includes it in SCIP 59 * 60 * @note method has all conflict handler callbacks as arguments and is thus changed every time a new 61 * callback is added 62 * in future releases; consider using SCIPincludeConflicthdlrBasic() and setter functions 63 * if you seek for a method which is less likely to change in future releases 64 */ 65 SCIP_RETCODE SCIPincludeConflicthdlr( 66 SCIP* scip, /**< SCIP data structure */ 67 const char* name, /**< name of conflict handler */ 68 const char* desc, /**< description of conflict handler */ 69 int priority, /**< priority of the conflict handler */ 70 SCIP_DECL_CONFLICTCOPY((*conflictcopy)), /**< copy method of conflict handler or NULL if you don't want to copy your plugin into sub-SCIPs */ 71 SCIP_DECL_CONFLICTFREE((*conflictfree)), /**< destructor of conflict handler */ 72 SCIP_DECL_CONFLICTINIT((*conflictinit)), /**< initialize conflict handler */ 73 SCIP_DECL_CONFLICTEXIT((*conflictexit)), /**< deinitialize conflict handler */ 74 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol)),/**< solving process initialization method of conflict handler */ 75 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol)),/**< solving process deinitialization method of conflict handler */ 76 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */ 77 SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */ 78 ) 79 { 80 SCIP_CONFLICTHDLR* conflicthdlr; 81 82 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeConflicthdlr", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 83 84 /* check whether conflict handler is already present */ 85 if( SCIPfindConflicthdlr(scip, name) != NULL ) 86 { 87 SCIPerrorMessage("conflict handler <%s> already included.\n", name); 88 return SCIP_INVALIDDATA; 89 } 90 91 SCIP_CALL( SCIPconflicthdlrCreate(&conflicthdlr, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, 92 conflictcopy, 93 conflictfree, conflictinit, conflictexit, conflictinitsol, conflictexitsol, conflictexec, 94 conflicthdlrdata) ); 95 SCIP_CALL( SCIPsetIncludeConflicthdlr(scip->set, conflicthdlr) ); 96 97 return SCIP_OKAY; 98 } 99 100 /** creates a conflict handler and includes it in SCIP with its most fundamental callbacks. All non-fundamental 101 * (or optional) callbacks as, e.g., init and exit callbacks, will be set to NULL. 102 * Optional callbacks can be set via specific setter functions SCIPsetConflicthdlrCopy(), SCIPsetConflicthdlrFree(), 103 * SCIPsetConflicthdlrInit(), SCIPsetConflicthdlrExit(), SCIPsetConflicthdlrInitsol(), 104 * and SCIPsetConflicthdlrExitsol() 105 * 106 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeConflicthdlr() instead 107 */ 108 SCIP_RETCODE SCIPincludeConflicthdlrBasic( 109 SCIP* scip, /**< SCIP data structure */ 110 SCIP_CONFLICTHDLR** conflicthdlrptr, /**< reference to a conflict handler pointer, or NULL */ 111 const char* name, /**< name of conflict handler */ 112 const char* desc, /**< description of conflict handler */ 113 int priority, /**< priority of the conflict handler */ 114 SCIP_DECL_CONFLICTEXEC((*conflictexec)), /**< conflict processing method of conflict handler */ 115 SCIP_CONFLICTHDLRDATA* conflicthdlrdata /**< conflict handler data */ 116 ) 117 { 118 SCIP_CONFLICTHDLR* conflicthdlr; 119 120 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeConflicthdlrBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 121 122 /* check whether conflict handler is already present */ 123 if( SCIPfindConflicthdlr(scip, name) != NULL ) 124 { 125 SCIPerrorMessage("conflict handler <%s> already included.\n", name); 126 return SCIP_INVALIDDATA; 127 } 128 129 SCIP_CALL( SCIPconflicthdlrCreate(&conflicthdlr, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, 130 NULL, NULL, NULL, NULL, NULL, NULL, conflictexec, conflicthdlrdata) ); 131 SCIP_CALL( SCIPsetIncludeConflicthdlr(scip->set, conflicthdlr) ); 132 133 if( conflicthdlrptr != NULL ) 134 *conflicthdlrptr = conflicthdlr; 135 136 return SCIP_OKAY; 137 } 138 139 /** set copy method of conflict handler */ 140 SCIP_RETCODE SCIPsetConflicthdlrCopy( 141 SCIP* scip, /**< SCIP data structure */ 142 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 143 SCIP_DECL_CONFLICTCOPY((*conflictcopy)) /**< copy method of conflict handler */ 144 ) 145 { 146 assert(scip != NULL); 147 148 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 149 150 SCIPconflicthdlrSetCopy(conflicthdlr, conflictcopy); 151 152 return SCIP_OKAY; 153 } 154 155 /** set destructor of conflict handler */ 156 SCIP_RETCODE SCIPsetConflicthdlrFree( 157 SCIP* scip, /**< SCIP data structure */ 158 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 159 SCIP_DECL_CONFLICTFREE((*conflictfree)) /**< destructor of conflict handler */ 160 ) 161 { 162 assert(scip != NULL); 163 164 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 165 166 SCIPconflicthdlrSetFree(conflicthdlr, conflictfree); 167 168 return SCIP_OKAY; 169 } 170 171 /** set initialization method of conflict handler */ 172 SCIP_RETCODE SCIPsetConflicthdlrInit( 173 SCIP* scip, /**< SCIP data structure */ 174 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 175 SCIP_DECL_CONFLICTINIT((*conflictinit)) /**< initialize conflict handler */ 176 ) 177 { 178 assert(scip != NULL); 179 180 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 181 182 SCIPconflicthdlrSetInit(conflicthdlr, conflictinit); 183 184 return SCIP_OKAY; 185 } 186 187 /** set deinitialization method of conflict handler */ 188 SCIP_RETCODE SCIPsetConflicthdlrExit( 189 SCIP* scip, /**< SCIP data structure */ 190 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 191 SCIP_DECL_CONFLICTEXIT((*conflictexit)) /**< deinitialize conflict handler */ 192 ) 193 { 194 assert(scip != NULL); 195 196 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 197 198 SCIPconflicthdlrSetExit(conflicthdlr, conflictexit); 199 200 return SCIP_OKAY; 201 } 202 203 /** set solving process initialization method of conflict handler */ 204 SCIP_RETCODE SCIPsetConflicthdlrInitsol( 205 SCIP* scip, /**< SCIP data structure */ 206 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 207 SCIP_DECL_CONFLICTINITSOL((*conflictinitsol))/**< solving process initialization method of conflict handler */ 208 ) 209 { 210 assert(scip != NULL); 211 212 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 213 214 SCIPconflicthdlrSetInitsol(conflicthdlr, conflictinitsol); 215 216 return SCIP_OKAY; 217 } 218 219 /** set solving process deinitialization method of conflict handler */ 220 SCIP_RETCODE SCIPsetConflicthdlrExitsol( 221 SCIP* scip, /**< SCIP data structure */ 222 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 223 SCIP_DECL_CONFLICTEXITSOL((*conflictexitsol))/**< solving process deinitialization method of conflict handler */ 224 ) 225 { 226 assert(scip != NULL); 227 228 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetConflicthdlrExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 229 230 SCIPconflicthdlrSetExitsol(conflicthdlr, conflictexitsol); 231 232 return SCIP_OKAY; 233 } 234 235 /** returns the conflict handler of the given name, or NULL if not existing */ 236 SCIP_CONFLICTHDLR* SCIPfindConflicthdlr( 237 SCIP* scip, /**< SCIP data structure */ 238 const char* name /**< name of conflict handler */ 239 ) 240 { 241 assert(scip != NULL); 242 assert(scip->set != NULL); 243 assert(name != NULL); 244 245 return SCIPsetFindConflicthdlr(scip->set, name); 246 } 247 248 /** returns the array of currently available conflict handlers */ 249 SCIP_CONFLICTHDLR** SCIPgetConflicthdlrs( 250 SCIP* scip /**< SCIP data structure */ 251 ) 252 { 253 assert(scip != NULL); 254 assert(scip->set != NULL); 255 256 SCIPsetSortConflicthdlrs(scip->set); 257 258 return scip->set->conflicthdlrs; 259 } 260 261 /** returns the number of currently available conflict handlers */ 262 int SCIPgetNConflicthdlrs( 263 SCIP* scip /**< SCIP data structure */ 264 ) 265 { 266 assert(scip != NULL); 267 assert(scip->set != NULL); 268 269 return scip->set->nconflicthdlrs; 270 } 271 272 /** sets the priority of a conflict handler */ 273 SCIP_RETCODE SCIPsetConflicthdlrPriority( 274 SCIP* scip, /**< SCIP data structure */ 275 SCIP_CONFLICTHDLR* conflicthdlr, /**< conflict handler */ 276 int priority /**< new priority of the conflict handler */ 277 ) 278 { 279 assert(scip != NULL); 280 assert(scip->set != NULL); 281 282 SCIPconflicthdlrSetPriority(conflicthdlr, scip->set, priority); 283 284 return SCIP_OKAY; 285 } 286 287 /** return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the 288 * conflict analysis since it will not be applied 289 * 290 * @return return TRUE if conflict analysis is applicable; In case the function return FALSE there is no need to initialize the 291 * conflict analysis since it will not be applied 292 * 293 * @pre This method can be called if SCIP is in one of the following stages: 294 * - \ref SCIP_STAGE_INITPRESOLVE 295 * - \ref SCIP_STAGE_PRESOLVING 296 * - \ref SCIP_STAGE_EXITPRESOLVE 297 * - \ref SCIP_STAGE_SOLVING 298 * 299 * @note SCIP stage does not get changed 300 */ 301 SCIP_Bool SCIPisConflictAnalysisApplicable( 302 SCIP* scip /**< SCIP data structure */ 303 ) 304 { 305 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisConflictAnalysisApplicable", FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 306 307 return (SCIPgetDepth(scip) > 0 && SCIPconflictApplicable(scip->set)); 308 } 309 310 /** initializes the conflict analysis by clearing the conflict candidate queue; this method must be called before you 311 * enter the conflict variables by calling SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), 312 * SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar(); 313 * 314 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 315 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 316 * 317 * @pre This method can be called if SCIP is in one of the following stages: 318 * - \ref SCIP_STAGE_PRESOLVING 319 * - \ref SCIP_STAGE_SOLVING 320 * 321 * @note SCIP stage does not get changed 322 */ 323 SCIP_RETCODE SCIPinitConflictAnalysis( 324 SCIP* scip, /**< SCIP data structure */ 325 SCIP_CONFTYPE conftype, /**< type of conflict */ 326 SCIP_Bool iscutoffinvolved /**< is the current cutoff bound involved? */ 327 ) 328 { 329 SCIP_CALL( SCIPcheckStage(scip, "SCIPinitConflictAnalysis", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 330 331 SCIP_CALL( SCIPconflictInit(scip->conflict, scip->set, scip->stat, scip->transprob, conftype, iscutoffinvolved) ); 332 333 return SCIP_OKAY; 334 } 335 336 /** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage; 337 * this method should be called in one of the following two cases: 338 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictLb() should be called for each lower bound 339 * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 340 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictLb() should be called 341 * for each lower bound, whose current assignment led to the deduction of the given conflict bound. 342 * 343 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 344 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 345 * 346 * @pre This method can be called if SCIP is in one of the following stages: 347 * - \ref SCIP_STAGE_PRESOLVING 348 * - \ref SCIP_STAGE_SOLVING 349 * 350 * @note SCIP stage does not get changed 351 */ 352 SCIP_RETCODE SCIPaddConflictLb( 353 SCIP* scip, /**< SCIP data structure */ 354 SCIP_VAR* var, /**< variable whose lower bound should be added to conflict candidate queue */ 355 SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the 356 * conflicting bound was valid, NULL for current local bound */ 357 ) 358 { 359 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 360 361 assert( var->scip == scip ); 362 363 SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, bdchgidx) ); 364 365 return SCIP_OKAY; 366 } 367 368 /** adds lower bound of variable at the time of the given bound change index to the conflict analysis' candidate storage 369 * with the additional information of a relaxed lower bound; this relaxed lower bound is the one which would be enough 370 * to explain a certain bound change; 371 * this method should be called in one of the following two cases: 372 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedLb() should be called for each (relaxed) lower bound 373 * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 374 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelexedLb() should be called 375 * for each (relaxed) lower bound, whose current assignment led to the deduction of the given conflict bound. 376 * 377 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 378 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 379 * 380 * @pre This method can be called if SCIP is in one of the following stages: 381 * - \ref SCIP_STAGE_PRESOLVING 382 * - \ref SCIP_STAGE_SOLVING 383 * 384 * @note SCIP stage does not get changed 385 */ 386 SCIP_RETCODE SCIPaddConflictRelaxedLb( 387 SCIP* scip, /**< SCIP data structure */ 388 SCIP_VAR* var, /**< variable whose lower bound should be added to conflict candidate queue */ 389 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the 390 * conflicting bound was valid, NULL for current local bound */ 391 SCIP_Real relaxedlb /**< the relaxed lower bound */ 392 ) 393 { 394 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 395 396 assert( var->scip == scip ); 397 398 SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, bdchgidx, relaxedlb) ); 399 400 return SCIP_OKAY; 401 } 402 403 /** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage; 404 * this method should be called in one of the following two cases: 405 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictUb() should be called for each upper bound that 406 * led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 407 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictUb() should be called for 408 * each upper bound, whose current assignment led to the deduction of the given conflict bound. 409 * 410 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 411 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 412 * 413 * @pre This method can be called if SCIP is in one of the following stages: 414 * - \ref SCIP_STAGE_PRESOLVING 415 * - \ref SCIP_STAGE_SOLVING 416 * 417 * @note SCIP stage does not get changed 418 */ 419 SCIP_RETCODE SCIPaddConflictUb( 420 SCIP* scip, /**< SCIP data structure */ 421 SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ 422 SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the 423 * conflicting bound was valid, NULL for current local bound */ 424 ) 425 { 426 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 427 428 assert( var->scip == scip ); 429 430 SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, bdchgidx) ); 431 432 return SCIP_OKAY; 433 } 434 435 /** adds upper bound of variable at the time of the given bound change index to the conflict analysis' candidate storage 436 * with the additional information of a relaxed upper bound; this relaxed upper bound is the one which would be enough 437 * to explain a certain bound change; 438 * this method should be called in one of the following two cases: 439 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedUb() should be called for each (relaxed) upper 440 * bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 441 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedUb() should be 442 * called for each (relaxed) upper bound, whose current assignment led to the deduction of the given conflict 443 * bound. 444 * 445 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 446 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 447 * 448 * @pre This method can be called if SCIP is in one of the following stages: 449 * - \ref SCIP_STAGE_PRESOLVING 450 * - \ref SCIP_STAGE_SOLVING 451 * 452 * @note SCIP stage does not get changed 453 */ 454 SCIP_RETCODE SCIPaddConflictRelaxedUb( 455 SCIP* scip, /**< SCIP data structure */ 456 SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ 457 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the 458 * conflicting bound was valid, NULL for current local bound */ 459 SCIP_Real relaxedub /**< the relaxed upper bound */ 460 ) 461 { 462 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 463 464 assert( var->scip == scip ); 465 466 SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, bdchgidx, relaxedub) ); 467 468 return SCIP_OKAY; 469 } 470 471 /** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis' candidate 472 * storage; this method should be called in one of the following two cases: 473 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBd() should be called for each bound 474 * that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 475 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBd() should be called 476 * for each bound, whose current assignment led to the deduction of the given conflict bound. 477 * 478 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 479 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 480 * 481 * @pre This method can be called if SCIP is in one of the following stages: 482 * - \ref SCIP_STAGE_PRESOLVING 483 * - \ref SCIP_STAGE_SOLVING 484 * 485 * @note SCIP stage does not get changed 486 */ 487 SCIP_RETCODE SCIPaddConflictBd( 488 SCIP* scip, /**< SCIP data structure */ 489 SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ 490 SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ 491 SCIP_BDCHGIDX* bdchgidx /**< bound change index representing time on path to current node, when the 492 * conflicting bound was valid, NULL for current local bound */ 493 ) 494 { 495 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictBd", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 496 497 assert( var->scip == scip ); 498 499 SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, boundtype, bdchgidx) ); 500 501 return SCIP_OKAY; 502 } 503 504 /** adds lower or upper bound of variable at the time of the given bound change index to the conflict analysis' 505 * candidate storage; with the additional information of a relaxed upper bound; this relaxed upper bound is the one 506 * which would be enough to explain a certain bound change; 507 * this method should be called in one of the following two cases: 508 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictRelaxedBd() should be called for each (relaxed) 509 * bound that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 510 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictRelaxedBd() should be 511 * called for each (relaxed) bound, whose current assignment led to the deduction of the given conflict bound. 512 * 513 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 514 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 515 * 516 * @pre This method can be called if SCIP is in one of the following stages: 517 * - \ref SCIP_STAGE_PRESOLVING 518 * - \ref SCIP_STAGE_SOLVING 519 * 520 * @note SCIP stage does not get changed 521 */ 522 SCIP_RETCODE SCIPaddConflictRelaxedBd( 523 SCIP* scip, /**< SCIP data structure */ 524 SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ 525 SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ 526 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the 527 * conflicting bound was valid, NULL for current local bound */ 528 SCIP_Real relaxedbd /**< the relaxed bound */ 529 ) 530 { 531 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictRelaxedBd", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 532 533 assert( var->scip == scip ); 534 535 SCIP_CALL( SCIPconflictAddRelaxedBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, boundtype, bdchgidx, relaxedbd) ); 536 537 return SCIP_OKAY; 538 } 539 540 /** adds changed bound of fixed binary variable to the conflict analysis' candidate storage; 541 * this method should be called in one of the following two cases: 542 * 1. Before calling the SCIPanalyzeConflict() method, SCIPaddConflictBinvar() should be called for each fixed binary 543 * variable that led to the conflict (e.g. the infeasibility of globally or locally valid constraint). 544 * 2. In the propagation conflict resolving method of a constraint handler, SCIPaddConflictBinvar() should be called 545 * for each binary variable, whose current fixing led to the deduction of the given conflict bound. 546 * 547 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 548 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 549 * 550 * @pre This method can be called if SCIP is in one of the following stages: 551 * - \ref SCIP_STAGE_PRESOLVING 552 * - \ref SCIP_STAGE_SOLVING 553 * 554 * @note SCIP stage does not get changed 555 */ 556 SCIP_RETCODE SCIPaddConflictBinvar( 557 SCIP* scip, /**< SCIP data structure */ 558 SCIP_VAR* var /**< binary variable whose changed bound should be added to conflict queue */ 559 ) 560 { 561 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddConflictBinvar", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 562 563 assert(var->scip == scip); 564 assert(SCIPvarIsBinary(var)); 565 566 if( SCIPvarGetLbLocal(var) > 0.5 ) 567 { 568 SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_LOWER, NULL) ); 569 } 570 else if( SCIPvarGetUbLocal(var) < 0.5 ) 571 { 572 SCIP_CALL( SCIPconflictAddBound(scip->conflict, scip->mem->probmem, scip->set, scip->stat, var, SCIP_BOUNDTYPE_UPPER, NULL) ); 573 } 574 575 return SCIP_OKAY; 576 } 577 578 /** checks if the given variable is already part of the current conflict set or queued for resolving with the same or 579 * even stronger bound 580 * 581 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 582 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 583 * 584 * @pre This method can be called if SCIP is in one of the following stages: 585 * - \ref SCIP_STAGE_PRESOLVING 586 * - \ref SCIP_STAGE_SOLVING 587 * 588 * @note SCIP stage does not get changed 589 */ 590 SCIP_RETCODE SCIPisConflictVarUsed( 591 SCIP* scip, /**< SCIP data structure */ 592 SCIP_VAR* var, /**< variable whose upper bound should be added to conflict candidate queue */ 593 SCIP_BOUNDTYPE boundtype, /**< the type of the conflicting bound (lower or upper bound) */ 594 SCIP_BDCHGIDX* bdchgidx, /**< bound change index representing time on path to current node, when the 595 * conflicting bound was valid, NULL for current local bound */ 596 SCIP_Bool* used /**< pointer to store if the variable is already used */ 597 ) 598 { 599 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisConflictVarUsed", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 600 601 assert( var->scip == scip ); 602 603 return SCIPconflictIsVarUsed(scip->conflict, var, scip->set, boundtype, bdchgidx, used); 604 } 605 606 /** returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower 607 * bound 608 * 609 * @return returns the conflict lower bound if the variable is present in the current conflict set; otherwise the global lower 610 * bound 611 * 612 * @pre This method can be called if SCIP is in one of the following stages: 613 * - \ref SCIP_STAGE_PRESOLVING 614 * - \ref SCIP_STAGE_SOLVING 615 * 616 * @note SCIP stage does not get changed 617 */ 618 SCIP_Real SCIPgetConflictVarLb( 619 SCIP* scip, /**< SCIP data structure */ 620 SCIP_VAR* var /**< problem variable */ 621 ) 622 { 623 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetConflictVarLb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 624 625 assert( var->scip == scip ); 626 627 return SCIPconflictGetVarLb(scip->conflict, var); 628 } 629 630 /** returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global 631 * upper bound 632 * 633 * @return returns the conflict upper bound if the variable is present in the current conflict set; otherwise minus global 634 * upper bound 635 * 636 * @pre This method can be called if SCIP is in one of the following stages: 637 * - \ref SCIP_STAGE_PRESOLVING 638 * - \ref SCIP_STAGE_SOLVING 639 * 640 * @note SCIP stage does not get changed 641 */ 642 SCIP_Real SCIPgetConflictVarUb( 643 SCIP* scip, /**< SCIP data structure */ 644 SCIP_VAR* var /**< problem variable */ 645 ) 646 { 647 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetConflictVarUb", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 648 649 assert( var->scip == scip ); 650 651 return SCIPconflictGetVarUb(scip->conflict, var); 652 } 653 654 /** analyzes conflict bounds that were added after a call to SCIPinitConflictAnalysis() with calls to 655 * SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), 656 * SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or SCIPaddConflictBinvar(); on success, calls the conflict 657 * handlers to create a conflict constraint out of the resulting conflict set; the given valid depth must be a depth 658 * level, at which the conflict set defined by calls to SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPaddConflictBd(), 659 * SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar() is 660 * valid for the whole subtree; if the conflict was found by a violated constraint, use SCIPanalyzeConflictCons() 661 * instead of SCIPanalyzeConflict() to make sure, that the correct valid depth is used 662 * 663 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 664 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 665 * 666 * @pre This method can be called if SCIP is in one of the following stages: 667 * - \ref SCIP_STAGE_PRESOLVING 668 * - \ref SCIP_STAGE_SOLVING 669 * 670 * @note SCIP stage does not get changed 671 */ 672 SCIP_RETCODE SCIPanalyzeConflict( 673 SCIP* scip, /**< SCIP data structure */ 674 int validdepth, /**< minimal depth level at which the initial conflict set is valid */ 675 SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */ 676 ) 677 { 678 SCIP_CALL( SCIPcheckStage(scip, "SCIPanalyzeConflict", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 679 680 SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat, 681 scip->transprob, scip->tree, validdepth, success) ); 682 683 return SCIP_OKAY; 684 } 685 686 /** analyzes conflict bounds that were added with calls to SCIPaddConflictLb(), SCIPaddConflictUb(), 687 * SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), SCIPaddConflictRelaxedBd(), or 688 * SCIPaddConflictBinvar(); on success, calls the conflict handlers to create a conflict constraint out of the 689 * resulting conflict set; the given constraint must be the constraint that detected the conflict, i.e. the constraint 690 * that is infeasible in the local bounds of the initial conflict set (defined by calls to SCIPaddConflictLb(), 691 * SCIPaddConflictUb(), SCIPaddConflictBd(), SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), 692 * SCIPaddConflictRelaxedBd(), and SCIPaddConflictBinvar()) 693 * 694 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 695 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 696 * 697 * @pre This method can be called if SCIP is in one of the following stages: 698 * - \ref SCIP_STAGE_PRESOLVING 699 * - \ref SCIP_STAGE_SOLVING 700 * 701 * @note SCIP stage does not get changed 702 */ 703 SCIP_RETCODE SCIPanalyzeConflictCons( 704 SCIP* scip, /**< SCIP data structure */ 705 SCIP_CONS* cons, /**< constraint that detected the conflict */ 706 SCIP_Bool* success /**< pointer to store whether a conflict constraint was created, or NULL */ 707 ) 708 { 709 SCIP_CALL( SCIPcheckStage(scip, "SCIPanalyzeConflictCons", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 710 711 if( SCIPconsIsGlobal(cons) ) 712 { 713 SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat, 714 scip->transprob, scip->tree, 0, success) ); 715 } 716 else if( SCIPconsIsActive(cons) ) 717 { 718 SCIP_CALL( SCIPconflictAnalyze(scip->conflict, scip->mem->probmem, scip->set, scip->stat, 719 scip->transprob, scip->tree, SCIPconsGetValidDepth(cons), success) ); 720 } 721 722 return SCIP_OKAY; 723 } 724