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 sepa.c 26 * @ingroup OTHER_CFILES 27 * @brief methods and datastructures for separators 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include <assert.h> 35 #include <string.h> 36 37 #include "scip/def.h" 38 #include "scip/set.h" 39 #include "scip/stat.h" 40 #include "scip/clock.h" 41 #include "scip/paramset.h" 42 #include "scip/sepastore.h" 43 #include "scip/scip.h" 44 #include "scip/sepa.h" 45 #include "scip/pub_message.h" 46 #include "scip/pub_misc.h" 47 48 #include "scip/struct_sepa.h" 49 50 51 /** compares two separators w. r. to their priority */ 52 SCIP_DECL_SORTPTRCOMP(SCIPsepaComp) 53 { /*lint --e{715}*/ 54 return ((SCIP_SEPA*)elem2)->priority - ((SCIP_SEPA*)elem1)->priority; 55 } 56 57 /** comparison method for sorting separators w.r.t. to their name */ 58 SCIP_DECL_SORTPTRCOMP(SCIPsepaCompName) 59 { 60 return strcmp(SCIPsepaGetName((SCIP_SEPA*)elem1), SCIPsepaGetName((SCIP_SEPA*)elem2)); 61 } 62 63 /** method to call, when the priority of a separator was changed */ 64 static 65 SCIP_DECL_PARAMCHGD(paramChgdSepaPriority) 66 { /*lint --e{715}*/ 67 SCIP_PARAMDATA* paramdata; 68 69 paramdata = SCIPparamGetData(param); 70 assert(paramdata != NULL); 71 72 /* use SCIPsetSepaPriority() to mark the sepas unsorted */ 73 SCIP_CALL( SCIPsetSepaPriority(scip, (SCIP_SEPA*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/ 74 75 return SCIP_OKAY; 76 } 77 78 /** copies the given separator to a new scip */ 79 SCIP_RETCODE SCIPsepaCopyInclude( 80 SCIP_SEPA* sepa, /**< separator */ 81 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 82 ) 83 { 84 assert(sepa != NULL); 85 assert(set != NULL); 86 assert(set->scip != NULL); 87 88 if( sepa->sepacopy != NULL ) 89 { 90 SCIPsetDebugMsg(set, "including separator %s in subscip %p\n", SCIPsepaGetName(sepa), (void*)set->scip); 91 SCIP_CALL( sepa->sepacopy(set->scip, sepa) ); 92 } 93 return SCIP_OKAY; 94 } 95 96 /** internal method for creating a separator */ 97 static 98 SCIP_RETCODE doSepaCreate( 99 SCIP_SEPA** sepa, /**< pointer to separator data structure */ 100 SCIP_SET* set, /**< global SCIP settings */ 101 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 102 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 103 const char* name, /**< name of separator */ 104 const char* desc, /**< description of separator */ 105 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */ 106 int freq, /**< frequency for calling separator */ 107 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared 108 * to best node's dual bound for applying separation */ 109 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */ 110 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */ 111 SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */ 112 SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */ 113 SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */ 114 SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */ 115 SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */ 116 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */ 117 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */ 118 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */ 119 SCIP_SEPADATA* sepadata /**< separator data */ 120 ) 121 { 122 char paramname[SCIP_MAXSTRLEN]; 123 char paramdesc[SCIP_MAXSTRLEN]; 124 125 assert(sepa != NULL); 126 assert(name != NULL); 127 assert(desc != NULL); 128 assert(freq >= -1); 129 assert(0.0 <= maxbounddist && maxbounddist <= 1.0); 130 assert(sepaexeclp != NULL || sepaexecsol != NULL); 131 132 SCIP_ALLOC( BMSallocMemory(sepa) ); 133 BMSclearMemory(*sepa); 134 135 SCIP_ALLOC( BMSduplicateMemoryArray(&(*sepa)->name, name, strlen(name)+1) ); 136 SCIP_ALLOC( BMSduplicateMemoryArray(&(*sepa)->desc, desc, strlen(desc)+1) ); 137 (*sepa)->priority = priority; 138 (*sepa)->freq = freq; 139 (*sepa)->maxbounddist = maxbounddist; 140 (*sepa)->usessubscip = usessubscip; 141 (*sepa)->sepacopy = sepacopy; 142 (*sepa)->sepafree = sepafree; 143 (*sepa)->sepainit = sepainit; 144 (*sepa)->sepaexit = sepaexit; 145 (*sepa)->sepainitsol = sepainitsol; 146 (*sepa)->sepaexitsol = sepaexitsol; 147 (*sepa)->sepaexeclp = sepaexeclp; 148 (*sepa)->sepaexecsol = sepaexecsol; 149 (*sepa)->sepadata = sepadata; 150 SCIP_CALL( SCIPclockCreate(&(*sepa)->setuptime, SCIP_CLOCKTYPE_DEFAULT) ); 151 SCIP_CALL( SCIPclockCreate(&(*sepa)->sepaclock, SCIP_CLOCKTYPE_DEFAULT) ); 152 (*sepa)->lastsepanode = -1; 153 (*sepa)->ncalls = 0; 154 (*sepa)->ncutoffs = 0; 155 (*sepa)->ncutsfound = 0; 156 (*sepa)->ncutsadded = 0; 157 (*sepa)->ncutsaddedviapool = 0; 158 (*sepa)->ncutsaddeddirect = 0; 159 (*sepa)->ncutsappliedviapool = 0; 160 (*sepa)->ncutsapplieddirect = 0; 161 (*sepa)->nconssfound = 0; 162 (*sepa)->ndomredsfound = 0; 163 (*sepa)->ncallsatnode = 0; 164 (*sepa)->ncutsfoundatnode = 0; 165 (*sepa)->lpwasdelayed = FALSE; 166 (*sepa)->solwasdelayed = FALSE; 167 (*sepa)->initialized = FALSE; 168 (*sepa)->isparentsepa = FALSE; 169 (*sepa)->parentsepa = NULL; 170 171 /* add parameters */ 172 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/priority", name); 173 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of separator <%s>", name); 174 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 175 &(*sepa)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4, 176 paramChgdSepaPriority, (SCIP_PARAMDATA*)(*sepa)) ); /*lint !e740*/ 177 178 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/freq", name); 179 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling separator <%s> (-1: never, 0: only in root node)", name); 180 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 181 &(*sepa)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) ); 182 183 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/maxbounddist", name); 184 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying separator <%s> (0.0: only on current best node, 1.0: on all nodes)", 185 name); 186 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc, 187 &(*sepa)->maxbounddist, TRUE, maxbounddist, 0.0, 1.0, NULL, NULL) ); 188 189 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/delay", name); 190 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname, 191 "should separator be delayed, if other separators found cuts?", 192 &(*sepa)->delay, TRUE, delay, NULL, NULL) ); /*lint !e740*/ 193 194 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "separating/%s/expbackoff", name); 195 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "base for exponential increase of frequency at which separator <%s> is called (1: call at each multiple of frequency)", name); 196 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 197 &(*sepa)->expbackoff, TRUE, 4, 1, 100, NULL, NULL) ); /*lint !e740*/ 198 199 return SCIP_OKAY; 200 } 201 202 /** creates a separator */ 203 SCIP_RETCODE SCIPsepaCreate( 204 SCIP_SEPA** sepa, /**< pointer to separator data structure */ 205 SCIP_SET* set, /**< global SCIP settings */ 206 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 207 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 208 const char* name, /**< name of separator */ 209 const char* desc, /**< description of separator */ 210 int priority, /**< priority of separator (>= 0: before, < 0: after constraint handlers) */ 211 int freq, /**< frequency for calling separator */ 212 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound compared 213 * to best node's dual bound for applying separation */ 214 SCIP_Bool usessubscip, /**< does the separator use a secondary SCIP instance? */ 215 SCIP_Bool delay, /**< should separator be delayed, if other separators found cuts? */ 216 SCIP_DECL_SEPACOPY ((*sepacopy)), /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */ 217 SCIP_DECL_SEPAFREE ((*sepafree)), /**< destructor of separator */ 218 SCIP_DECL_SEPAINIT ((*sepainit)), /**< initialize separator */ 219 SCIP_DECL_SEPAEXIT ((*sepaexit)), /**< deinitialize separator */ 220 SCIP_DECL_SEPAINITSOL ((*sepainitsol)), /**< solving process initialization method of separator */ 221 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)), /**< solving process deinitialization method of separator */ 222 SCIP_DECL_SEPAEXECLP ((*sepaexeclp)), /**< LP solution separation method of separator */ 223 SCIP_DECL_SEPAEXECSOL ((*sepaexecsol)), /**< arbitrary primal solution separation method of separator */ 224 SCIP_SEPADATA* sepadata /**< separator data */ 225 ) 226 { 227 assert(sepa != NULL); 228 assert(name != NULL); 229 assert(desc != NULL); 230 assert(freq >= -1); 231 assert(0.0 <= maxbounddist && maxbounddist <= 1.0); 232 assert(sepaexeclp != NULL || sepaexecsol != NULL); 233 234 SCIP_CALL_FINALLY( doSepaCreate(sepa, set, messagehdlr, blkmem, name, desc, priority, freq, maxbounddist, 235 usessubscip, delay, sepacopy, sepafree, sepainit, sepaexit, sepainitsol, sepaexitsol, sepaexeclp, 236 sepaexecsol, sepadata), (void) SCIPsepaFree(sepa, set) ); 237 238 return SCIP_OKAY; 239 } 240 241 /** calls destructor and frees memory of separator */ 242 SCIP_RETCODE SCIPsepaFree( 243 SCIP_SEPA** sepa, /**< pointer to separator data structure */ 244 SCIP_SET* set /**< global SCIP settings */ 245 ) 246 { 247 assert(sepa != NULL); 248 if( *sepa == NULL ) 249 return SCIP_OKAY; 250 assert(!(*sepa)->initialized); 251 assert(set != NULL); 252 253 /* call destructor of separator */ 254 if( (*sepa)->sepafree != NULL ) 255 { 256 SCIP_CALL( (*sepa)->sepafree(set->scip, *sepa) ); 257 } 258 259 SCIPclockFree(&(*sepa)->sepaclock); 260 SCIPclockFree(&(*sepa)->setuptime); 261 BMSfreeMemoryArrayNull(&(*sepa)->name); 262 BMSfreeMemoryArrayNull(&(*sepa)->desc); 263 BMSfreeMemory(sepa); 264 265 return SCIP_OKAY; 266 } 267 268 /** initializes separator */ 269 SCIP_RETCODE SCIPsepaInit( 270 SCIP_SEPA* sepa, /**< separator */ 271 SCIP_SET* set /**< global SCIP settings */ 272 ) 273 { 274 assert(sepa != NULL); 275 assert(set != NULL); 276 277 if( sepa->initialized ) 278 { 279 SCIPerrorMessage("separator <%s> already initialized\n", sepa->name); 280 return SCIP_INVALIDCALL; 281 } 282 283 if( set->misc_resetstat ) 284 { 285 SCIPclockReset(sepa->setuptime); 286 SCIPclockReset(sepa->sepaclock); 287 288 sepa->lastsepanode = -1; 289 sepa->ncalls = 0; 290 sepa->nrootcalls = 0; 291 sepa->ncutoffs = 0; 292 sepa->ncutsfound = 0; 293 sepa->ncutsadded = 0; 294 sepa->ncutsaddedviapool = 0; 295 sepa->ncutsaddeddirect = 0; 296 sepa->ncutsappliedviapool = 0; 297 sepa->ncutsapplieddirect = 0; 298 sepa->nconssfound = 0; 299 sepa->ndomredsfound = 0; 300 sepa->ncallsatnode = 0; 301 sepa->ncutsfoundatnode = 0; 302 sepa->lpwasdelayed = FALSE; 303 sepa->solwasdelayed = FALSE; 304 } 305 306 if( sepa->sepainit != NULL ) 307 { 308 /* start timing */ 309 SCIPclockStart(sepa->setuptime, set); 310 311 SCIP_CALL( sepa->sepainit(set->scip, sepa) ); 312 313 /* stop timing */ 314 SCIPclockStop(sepa->setuptime, set); 315 } 316 sepa->initialized = TRUE; 317 318 return SCIP_OKAY; 319 } 320 321 /** calls exit method of separator */ 322 SCIP_RETCODE SCIPsepaExit( 323 SCIP_SEPA* sepa, /**< separator */ 324 SCIP_SET* set /**< global SCIP settings */ 325 ) 326 { 327 assert(sepa != NULL); 328 assert(set != NULL); 329 330 if( !sepa->initialized ) 331 { 332 SCIPerrorMessage("separator <%s> not initialized\n", sepa->name); 333 return SCIP_INVALIDCALL; 334 } 335 336 if( sepa->sepaexit != NULL ) 337 { 338 /* start timing */ 339 SCIPclockStart(sepa->setuptime, set); 340 341 SCIP_CALL( sepa->sepaexit(set->scip, sepa) ); 342 343 /* stop timing */ 344 SCIPclockStop(sepa->setuptime, set); 345 } 346 sepa->initialized = FALSE; 347 348 return SCIP_OKAY; 349 } 350 351 /** informs separator that the branch and bound process is being started */ 352 SCIP_RETCODE SCIPsepaInitsol( 353 SCIP_SEPA* sepa, /**< separator */ 354 SCIP_SET* set /**< global SCIP settings */ 355 ) 356 { 357 assert(sepa != NULL); 358 assert(set != NULL); 359 360 sepa->lpwasdelayed = FALSE; 361 sepa->solwasdelayed = FALSE; 362 363 /* call solving process initialization method of separator */ 364 if( sepa->sepainitsol != NULL ) 365 { 366 /* start timing */ 367 SCIPclockStart(sepa->setuptime, set); 368 369 SCIP_CALL( sepa->sepainitsol(set->scip, sepa) ); 370 371 /* stop timing */ 372 SCIPclockStop(sepa->setuptime, set); 373 } 374 375 return SCIP_OKAY; 376 } 377 378 /** informs separator that the branch and bound process data is being freed */ 379 SCIP_RETCODE SCIPsepaExitsol( 380 SCIP_SEPA* sepa, /**< separator */ 381 SCIP_SET* set /**< global SCIP settings */ 382 ) 383 { 384 assert(sepa != NULL); 385 assert(set != NULL); 386 387 /* call solving process deinitialization method of separator */ 388 if( sepa->sepaexitsol != NULL ) 389 { 390 /* start timing */ 391 SCIPclockStart(sepa->setuptime, set); 392 393 SCIP_CALL( sepa->sepaexitsol(set->scip, sepa) ); 394 395 /* stop timing */ 396 SCIPclockStop(sepa->setuptime, set); 397 } 398 399 return SCIP_OKAY; 400 } 401 402 /** calls LP separation method of separator */ 403 SCIP_RETCODE SCIPsepaExecLP( 404 SCIP_SEPA* sepa, /**< separator */ 405 SCIP_SET* set, /**< global SCIP settings */ 406 SCIP_STAT* stat, /**< dynamic problem statistics */ 407 SCIP_SEPASTORE* sepastore, /**< separation storage */ 408 int depth, /**< depth of current node */ 409 SCIP_Real bounddist, /**< current relative distance of local dual bound to global dual bound */ 410 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */ 411 SCIP_Bool execdelayed, /**< execute separator even if it is marked to be delayed */ 412 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 413 ) 414 { 415 assert(sepa != NULL); 416 assert(sepa->freq >= -1); 417 assert(0.0 <= sepa->maxbounddist && sepa->maxbounddist <= 1.0); 418 assert(0.0 <= bounddist && bounddist <= 1.0); 419 assert(set != NULL); 420 assert(set->scip != NULL); 421 assert(stat != NULL); 422 assert(depth >= 0); 423 assert(result != NULL); 424 425 if( sepa->sepaexeclp != NULL && SCIPsetIsLE(set, bounddist, sepa->maxbounddist) && 426 ( (depth == 0 && sepa->freq != -1) || 427 (sepa->freq > 0 && depth % sepa->freq == 0 && 428 (sepa->expbackoff == 1 || SCIPsetIsIntegral(set, LOG2(depth * (1.0 / sepa->freq)) / LOG2((SCIP_Real)sepa->expbackoff)))) || 429 sepa->lpwasdelayed ) 430 ) 431 { 432 if( (!sepa->delay && !sepa->lpwasdelayed) || execdelayed ) 433 { 434 SCIP_CUTPOOL* cutpool; 435 SCIP_CUTPOOL* delayedcutpool; 436 SCIP_Longint oldndomchgs; 437 SCIP_Longint oldnprobdomchgs; 438 int oldncutsfound; 439 int oldnactiveconss; 440 int ncutsfound; 441 442 SCIPsetDebugMsg(set, "executing separator <%s> on LP solution\n", sepa->name); 443 444 cutpool = SCIPgetGlobalCutpool(set->scip); 445 delayedcutpool = SCIPgetDelayedGlobalCutpool(set->scip); 446 oldndomchgs = stat->nboundchgs + stat->nholechgs; 447 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs; 448 oldncutsfound = SCIPsepastoreGetNCuts(sepastore) + SCIPcutpoolGetNCuts(cutpool) + SCIPcutpoolGetNCuts(delayedcutpool); 449 450 oldnactiveconss = stat->nactiveconss; 451 452 /* reset the statistics for current node */ 453 if( sepa->lastsepanode != stat->ntotalnodes ) 454 { 455 sepa->ncallsatnode = 0; 456 sepa->ncutsfoundatnode = 0; 457 } 458 459 /* start timing */ 460 SCIPclockStart(sepa->sepaclock, set); 461 462 /* call external separation method */ 463 SCIP_CALL( sepa->sepaexeclp(set->scip, sepa, result, allowlocal, depth) ); 464 465 /* stop timing */ 466 SCIPclockStop(sepa->sepaclock, set); 467 468 /* update statistics */ 469 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED ) 470 { 471 sepa->ncalls++; 472 if( depth == 0 ) 473 sepa->nrootcalls++; 474 sepa->ncallsatnode++; 475 sepa->lastsepanode = stat->ntotalnodes; 476 } 477 if( *result == SCIP_CUTOFF ) 478 sepa->ncutoffs++; 479 480 ncutsfound = SCIPsepastoreGetNCuts(sepastore) + SCIPcutpoolGetNCuts(cutpool) + SCIPcutpoolGetNCuts(delayedcutpool) - oldncutsfound; 481 sepa->ncutsfound += ncutsfound; 482 sepa->ncutsfoundatnode += ncutsfound; 483 sepa->nconssfound += MAX(stat->nactiveconss - oldnactiveconss, 0); /*lint !e776*/ 484 485 /* update domain reductions; therefore remove the domain 486 * reduction counts which were generated in probing mode */ 487 sepa->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs; 488 sepa->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs); 489 490 /* evaluate result */ 491 if( *result != SCIP_CUTOFF 492 && *result != SCIP_CONSADDED 493 && *result != SCIP_REDUCEDDOM 494 && *result != SCIP_SEPARATED 495 && *result != SCIP_NEWROUND 496 && *result != SCIP_DIDNOTFIND 497 && *result != SCIP_DIDNOTRUN 498 && *result != SCIP_DELAYED ) 499 { 500 SCIPerrorMessage("execution method of separator <%s> returned invalid result <%d>\n", 501 sepa->name, *result); 502 return SCIP_INVALIDRESULT; 503 } 504 } 505 else 506 { 507 SCIPsetDebugMsg(set, "separator <%s> was delayed\n", sepa->name); 508 *result = SCIP_DELAYED; 509 } 510 511 /* remember whether separator was delayed */ 512 sepa->lpwasdelayed = (*result == SCIP_DELAYED); 513 } 514 else 515 *result = SCIP_DIDNOTRUN; 516 517 return SCIP_OKAY; 518 } 519 520 /** calls primal solution separation method of separator */ 521 SCIP_RETCODE SCIPsepaExecSol( 522 SCIP_SEPA* sepa, /**< separator */ 523 SCIP_SET* set, /**< global SCIP settings */ 524 SCIP_STAT* stat, /**< dynamic problem statistics */ 525 SCIP_SEPASTORE* sepastore, /**< separation storage */ 526 SCIP_SOL* sol, /**< primal solution that should be separated */ 527 int depth, /**< depth of current node */ 528 SCIP_Bool allowlocal, /**< should the separator allow local cuts */ 529 SCIP_Bool execdelayed, /**< execute separator even if it is marked to be delayed */ 530 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 531 ) 532 { 533 assert(sepa != NULL); 534 assert(sepa->freq >= -1); 535 assert(set != NULL); 536 assert(set->scip != NULL); 537 assert(stat != NULL); 538 assert(depth >= 0); 539 assert(result != NULL); 540 541 if( sepa->sepaexecsol != NULL && 542 ( (depth == 0 && sepa->freq != -1) || 543 (sepa->freq > 0 && depth % sepa->freq == 0 && 544 (sepa->expbackoff == 1 || SCIPsetIsIntegral(set, LOG2(depth * (1.0 / sepa->freq) / LOG2((SCIP_Real)sepa->expbackoff))))) || 545 sepa->solwasdelayed ) 546 ) 547 { 548 if( (!sepa->delay && !sepa->solwasdelayed) || execdelayed ) 549 { 550 SCIP_Longint oldndomchgs; 551 SCIP_Longint oldnprobdomchgs; 552 int oldncutsfound; 553 int oldnactiveconss; 554 int ncutsfound; 555 556 SCIPsetDebugMsg(set, "executing separator <%s> on solution %p\n", sepa->name, (void*)sol); 557 558 oldndomchgs = stat->nboundchgs + stat->nholechgs; 559 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs; 560 oldncutsfound = SCIPsepastoreGetNCuts(sepastore); 561 oldnactiveconss = stat->nactiveconss; 562 563 /* reset the statistics for current node */ 564 if( sepa->lastsepanode != stat->ntotalnodes ) 565 { 566 sepa->ncallsatnode = 0; 567 sepa->ncutsfoundatnode = 0; 568 } 569 570 /* start timing */ 571 SCIPclockStart(sepa->sepaclock, set); 572 573 /* call external separation method */ 574 SCIP_CALL( sepa->sepaexecsol(set->scip, sepa, sol, result, allowlocal, depth) ); 575 576 /* stop timing */ 577 SCIPclockStop(sepa->sepaclock, set); 578 579 /* update statistics */ 580 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED ) 581 { 582 sepa->ncalls++; 583 if( depth == 0 ) 584 sepa->nrootcalls++; 585 sepa->ncallsatnode++; 586 sepa->lastsepanode = stat->ntotalnodes; 587 } 588 if( *result == SCIP_CUTOFF ) 589 sepa->ncutoffs++; 590 591 ncutsfound = SCIPsepastoreGetNCuts(sepastore) - oldncutsfound; 592 593 sepa->ncutsfound += ncutsfound; 594 sepa->ncutsfoundatnode += ncutsfound; 595 sepa->nconssfound += MAX(stat->nactiveconss - oldnactiveconss, 0); /*lint !e776*/ 596 597 /* update domain reductions; therefore remove the domain 598 * reduction counts which were generated in probing mode */ 599 sepa->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs; 600 sepa->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs); 601 602 /* evaluate result */ 603 if( *result != SCIP_CUTOFF 604 && *result != SCIP_CONSADDED 605 && *result != SCIP_REDUCEDDOM 606 && *result != SCIP_SEPARATED 607 && *result != SCIP_NEWROUND 608 && *result != SCIP_DIDNOTFIND 609 && *result != SCIP_DIDNOTRUN 610 && *result != SCIP_DELAYED ) 611 { 612 SCIPerrorMessage("execution method of separator <%s> returned invalid result <%d>\n", 613 sepa->name, *result); 614 return SCIP_INVALIDRESULT; 615 } 616 } 617 else 618 { 619 SCIPsetDebugMsg(set, "separator <%s> was delayed\n", sepa->name); 620 *result = SCIP_DELAYED; 621 } 622 623 /* remember whether separator was delayed */ 624 sepa->solwasdelayed = (*result == SCIP_DELAYED); 625 } 626 else 627 *result = SCIP_DIDNOTRUN; 628 629 return SCIP_OKAY; 630 } 631 632 /** gets user data of separator */ 633 SCIP_SEPADATA* SCIPsepaGetData( 634 SCIP_SEPA* sepa /**< separator */ 635 ) 636 { 637 assert(sepa != NULL); 638 639 return sepa->sepadata; 640 } 641 642 /** sets user data of separator; user has to free old data in advance! */ 643 void SCIPsepaSetData( 644 SCIP_SEPA* sepa, /**< separator */ 645 SCIP_SEPADATA* sepadata /**< new separator user data */ 646 ) 647 { 648 assert(sepa != NULL); 649 650 sepa->sepadata = sepadata; 651 } 652 653 /* new callback/method setter methods */ 654 655 /** sets copy method of separator */ 656 void SCIPsepaSetCopy( 657 SCIP_SEPA* sepa, /**< separator */ 658 SCIP_DECL_SEPACOPY ((*sepacopy)) /**< copy method of separator or NULL if you don't want to copy your plugin into sub-SCIPs */ 659 ) 660 { 661 assert(sepa != NULL); 662 663 sepa->sepacopy = sepacopy; 664 } 665 666 /** sets destructor method of separator */ 667 void SCIPsepaSetFree( 668 SCIP_SEPA* sepa, /**< separator */ 669 SCIP_DECL_SEPAFREE ((*sepafree)) /**< destructor of separator */ 670 ) 671 { 672 assert(sepa != NULL); 673 674 sepa->sepafree = sepafree; 675 } 676 677 /** sets initialization method of separator */ 678 void SCIPsepaSetInit( 679 SCIP_SEPA* sepa, /**< separator */ 680 SCIP_DECL_SEPAINIT ((*sepainit)) /**< initialize separator */ 681 ) 682 { 683 assert(sepa != NULL); 684 685 sepa->sepainit = sepainit; 686 } 687 688 /** sets deinitialization method of separator */ 689 void SCIPsepaSetExit( 690 SCIP_SEPA* sepa, /**< separator */ 691 SCIP_DECL_SEPAEXIT ((*sepaexit)) /**< deinitialize separator */ 692 ) 693 { 694 assert(sepa != NULL); 695 696 sepa->sepaexit = sepaexit; 697 } 698 699 /** sets solving process initialization method of separator */ 700 void SCIPsepaSetInitsol( 701 SCIP_SEPA* sepa, /**< separator */ 702 SCIP_DECL_SEPAINITSOL ((*sepainitsol)) /**< solving process initialization method of separator */ 703 ) 704 { 705 assert(sepa != NULL); 706 707 sepa->sepainitsol = sepainitsol; 708 } 709 710 /** sets solving process deinitialization method of separator */ 711 void SCIPsepaSetExitsol( 712 SCIP_SEPA* sepa, /**< separator */ 713 SCIP_DECL_SEPAEXITSOL ((*sepaexitsol)) /**< solving process deinitialization method of separator */ 714 ) 715 { 716 assert(sepa != NULL); 717 718 sepa->sepaexitsol = sepaexitsol; 719 } 720 721 /** declares separator to be a parent separator */ 722 void SCIPsepaSetIsParentsepa( 723 SCIP_SEPA* sepa /**< separator */ 724 ) 725 { 726 assert(sepa != NULL); 727 728 sepa->isparentsepa = TRUE; 729 } 730 731 /** sets the parent separator */ 732 void SCIPsepaSetParentsepa( 733 SCIP_SEPA* sepa, /**< separator */ 734 SCIP_SEPA* parentsepa /**< parent separator */ 735 ) 736 { 737 assert(sepa != NULL); 738 739 sepa->parentsepa = parentsepa; 740 } 741 742 /** gets name of separator */ 743 const char* SCIPsepaGetName( 744 SCIP_SEPA* sepa /**< separator */ 745 ) 746 { 747 assert(sepa != NULL); 748 749 return sepa->name; 750 } 751 752 /** gets description of separator */ 753 const char* SCIPsepaGetDesc( 754 SCIP_SEPA* sepa /**< separator */ 755 ) 756 { 757 assert(sepa != NULL); 758 759 return sepa->desc; 760 } 761 762 /** gets priority of separator */ 763 int SCIPsepaGetPriority( 764 SCIP_SEPA* sepa /**< separator */ 765 ) 766 { 767 assert(sepa != NULL); 768 769 return sepa->priority; 770 } 771 772 /** sets priority of separator */ 773 void SCIPsepaSetPriority( 774 SCIP_SEPA* sepa, /**< separator */ 775 SCIP_SET* set, /**< global SCIP settings */ 776 int priority /**< new priority of the separator */ 777 ) 778 { 779 assert(sepa != NULL); 780 assert(set != NULL); 781 782 sepa->priority = priority; 783 set->sepassorted = FALSE; 784 } 785 786 /** gets frequency of separator */ 787 int SCIPsepaGetFreq( 788 SCIP_SEPA* sepa /**< separator */ 789 ) 790 { 791 assert(sepa != NULL); 792 793 return sepa->freq; 794 } 795 796 /** sets frequency of separator */ 797 void SCIPsepaSetFreq( 798 SCIP_SEPA* sepa, /**< separator */ 799 int freq /**< new frequency of separator */ 800 ) 801 { 802 assert(sepa != NULL); 803 804 sepa->freq = freq; 805 } 806 807 /** get maximal bound distance at which the separator is called */ 808 SCIP_Real SCIPsepaGetMaxbounddist( 809 SCIP_SEPA* sepa /**< separator */ 810 ) 811 { 812 assert(sepa != NULL); 813 814 return sepa->maxbounddist; 815 } 816 817 /** does the separator use a secondary SCIP instance? */ 818 SCIP_Bool SCIPsepaUsesSubscip( 819 SCIP_SEPA* sepa /**< separator */ 820 ) 821 { 822 assert(sepa != NULL); 823 824 return sepa->usessubscip; 825 } 826 827 /** enables or disables all clocks of \p sepa, depending on the value of the flag */ 828 void SCIPsepaEnableOrDisableClocks( 829 SCIP_SEPA* sepa, /**< the separator for which all clocks should be enabled or disabled */ 830 SCIP_Bool enable /**< should the clocks of the separator be enabled? */ 831 ) 832 { 833 assert(sepa != NULL); 834 835 SCIPclockEnableOrDisable(sepa->setuptime, enable); 836 SCIPclockEnableOrDisable(sepa->sepaclock, enable); 837 } 838 839 /** gets time in seconds used in this separator for setting up for next stages */ 840 SCIP_Real SCIPsepaGetSetupTime( 841 SCIP_SEPA* sepa /**< separator */ 842 ) 843 { 844 assert(sepa != NULL); 845 846 return SCIPclockGetTime(sepa->setuptime); 847 } 848 849 /** gets time in seconds used in this separator */ 850 SCIP_Real SCIPsepaGetTime( 851 SCIP_SEPA* sepa /**< separator */ 852 ) 853 { 854 assert(sepa != NULL); 855 856 return SCIPclockGetTime(sepa->sepaclock); 857 } 858 859 /** gets the total number of times the separator was called */ 860 SCIP_Longint SCIPsepaGetNCalls( 861 SCIP_SEPA* sepa /**< separator */ 862 ) 863 { 864 assert(sepa != NULL); 865 866 return sepa->ncalls; 867 } 868 869 /** gets the total number of times the separator was called at the root */ 870 SCIP_Longint SCIPsepaGetNRootCalls( 871 SCIP_SEPA* sepa /**< separator */ 872 ) 873 { 874 assert(sepa != NULL); 875 876 return sepa->nrootcalls; 877 } 878 879 /** gets the number of times, the separator was called at the current node */ 880 int SCIPsepaGetNCallsAtNode( 881 SCIP_SEPA* sepa /**< separator */ 882 ) 883 { 884 assert(sepa != NULL); 885 886 return sepa->ncallsatnode; 887 } 888 889 /** gets total number of times, the separator detected a cutoff */ 890 SCIP_Longint SCIPsepaGetNCutoffs( 891 SCIP_SEPA* sepa /**< separator */ 892 ) 893 { 894 assert(sepa != NULL); 895 896 return sepa->ncutoffs; 897 } 898 899 /** gets the total number of cutting planes added from the separator to the cut pool */ 900 SCIP_Longint SCIPsepaGetNCutsFound( 901 SCIP_SEPA* sepa /**< separator */ 902 ) 903 { 904 assert(sepa != NULL); 905 906 return sepa->ncutsfound; 907 } 908 909 /** gets the total number of cutting planes added from the separator to the sepastore; 910 * equal to the sum of added cuts directly and via the pool. */ 911 SCIP_Longint SCIPsepaGetNCutsAdded( 912 SCIP_SEPA* sepa /**< separator */ 913 ) 914 { 915 assert(sepa != NULL); 916 917 return sepa->ncutsadded; 918 } 919 920 /** gets the number of cutting planes found by the separator added to the sepastore via the cut pool */ 921 SCIP_Longint SCIPsepaGetNCutsAddedViaPool( 922 SCIP_SEPA* sepa /**< separator */ 923 ) 924 { 925 assert(sepa != NULL); 926 927 return sepa->ncutsaddedviapool; 928 } 929 930 /** gets the number of cutting planes found by the separator added directly to the sepastore */ 931 SCIP_Longint SCIPsepaGetNCutsAddedDirect( 932 SCIP_SEPA* sepa /**< separator */ 933 ) 934 { 935 assert(sepa != NULL); 936 937 return sepa->ncutsaddeddirect; 938 } 939 940 /** gets the total number of cutting planes of the separator finally applied to the LP */ 941 SCIP_Longint SCIPsepaGetNCutsApplied( 942 SCIP_SEPA* sepa /**< separator */ 943 ) 944 { 945 assert(sepa != NULL); 946 947 return sepa->ncutsappliedviapool + sepa->ncutsapplieddirect; 948 } 949 950 /** gets the total number of cutting planes of the separator applied to the LP via the cutpool */ 951 SCIP_Longint SCIPsepaGetNCutsAppliedViaPool( 952 SCIP_SEPA* sepa /**< separator */ 953 ) 954 { 955 assert(sepa != NULL); 956 957 return sepa->ncutsappliedviapool; 958 } 959 960 /** gets the total number of cutting planes of the separator applied to the LP via the sepastore directly */ 961 SCIP_Longint SCIPsepaGetNCutsAppliedDirect( 962 SCIP_SEPA* sepa /**< separator */ 963 ) 964 { 965 assert(sepa != NULL); 966 967 return sepa->ncutsapplieddirect; 968 } 969 970 /** increase count of applied cuts by one */ 971 void SCIPsepaIncNCutsApplied( 972 SCIP_SEPA* sepa, /**< separator */ 973 SCIP_Bool fromcutpool /**< whether the cuts were added from the cutpool to sepastore */ 974 ) 975 { 976 SCIP_SEPA* parentsepa; 977 978 assert( sepa != NULL ); 979 980 if( fromcutpool ) 981 ++sepa->ncutsappliedviapool; 982 else 983 ++sepa->ncutsapplieddirect; 984 985 parentsepa = SCIPsepaGetParentsepa(sepa); 986 if( parentsepa != NULL ) 987 { 988 SCIPsepaIncNCutsApplied(parentsepa, fromcutpool); 989 } 990 } 991 992 /** increase count of added cuts by one */ 993 void SCIPsepaIncNCutsAdded( 994 SCIP_SEPA* sepa, /**< separator */ 995 SCIP_Bool fromcutpool /**< whether the cuts were added from the cutpool to sepastore */ 996 ) 997 { 998 SCIP_SEPA* parentsepa; 999 1000 assert( sepa != NULL ); 1001 1002 ++sepa->ncutsadded; 1003 if( fromcutpool ) 1004 sepa->ncutsaddedviapool++; 1005 else 1006 sepa->ncutsaddeddirect++; 1007 1008 parentsepa = SCIPsepaGetParentsepa(sepa); 1009 if( parentsepa != NULL ) 1010 { 1011 SCIPsepaIncNCutsAdded(parentsepa, fromcutpool); 1012 } 1013 } 1014 1015 /** decrease the count of added cuts by one */ 1016 void SCIPsepaDecNCutsAdded( 1017 SCIP_SEPA* sepa, /**< separator */ 1018 SCIP_Bool fromcutpool /**< whether the cuts were added from the cutpool to sepastore */ 1019 ) 1020 { 1021 SCIP_SEPA* parentsepa; 1022 1023 assert( sepa != NULL ); 1024 1025 sepa->ncutsadded--; 1026 if( fromcutpool ) 1027 sepa->ncutsaddedviapool--; 1028 else 1029 sepa->ncutsaddeddirect--; 1030 1031 parentsepa = SCIPsepaGetParentsepa(sepa); 1032 if( parentsepa != NULL ) 1033 { 1034 SCIPsepaDecNCutsAdded(parentsepa, fromcutpool); 1035 } 1036 } 1037 1038 /** increase count of found cuts by one */ 1039 void SCIPsepaIncNCutsFound( 1040 SCIP_SEPA* sepa /**< separator */ 1041 ) 1042 { 1043 assert( sepa != NULL ); 1044 1045 ++sepa->ncutsfound; 1046 } 1047 1048 /** increase count of found cuts at current node by one */ 1049 void SCIPsepaIncNCutsFoundAtNode( 1050 SCIP_SEPA* sepa /**< separator */ 1051 ) 1052 { 1053 assert( sepa != NULL ); 1054 1055 ++sepa->ncutsfoundatnode; 1056 } 1057 1058 /** gets the number of cutting planes found by this separator at the current node */ 1059 SCIP_Longint SCIPsepaGetNCutsFoundAtNode( 1060 SCIP_SEPA* sepa /**< separator */ 1061 ) 1062 { 1063 assert(sepa != NULL); 1064 1065 return sepa->ncutsfoundatnode; 1066 } 1067 1068 /** gets total number of additional constraints added by this separator */ 1069 SCIP_Longint SCIPsepaGetNConssFound( 1070 SCIP_SEPA* sepa /**< separator */ 1071 ) 1072 { 1073 assert(sepa != NULL); 1074 1075 return sepa->nconssfound; 1076 } 1077 1078 /** gets total number of domain reductions found by this separator */ 1079 SCIP_Longint SCIPsepaGetNDomredsFound( 1080 SCIP_SEPA* sepa /**< separator */ 1081 ) 1082 { 1083 assert(sepa != NULL); 1084 1085 return sepa->ndomredsfound; 1086 } 1087 1088 /** should separator be delayed, if other separators found cuts? */ 1089 SCIP_Bool SCIPsepaIsDelayed( 1090 SCIP_SEPA* sepa /**< separator */ 1091 ) 1092 { 1093 assert(sepa != NULL); 1094 1095 return sepa->delay; 1096 } 1097 1098 /** was separation of the LP solution delayed at the last call? */ 1099 SCIP_Bool SCIPsepaWasLPDelayed( 1100 SCIP_SEPA* sepa /**< separator */ 1101 ) 1102 { 1103 assert(sepa != NULL); 1104 1105 return sepa->lpwasdelayed; 1106 } 1107 1108 /** was separation of the primal solution delayed at the last call? */ 1109 SCIP_Bool SCIPsepaWasSolDelayed( 1110 SCIP_SEPA* sepa /**< separator */ 1111 ) 1112 { 1113 assert(sepa != NULL); 1114 1115 return sepa->solwasdelayed; 1116 } 1117 1118 /** is separator initialized? */ 1119 SCIP_Bool SCIPsepaIsInitialized( 1120 SCIP_SEPA* sepa /**< separator */ 1121 ) 1122 { 1123 assert(sepa != NULL); 1124 1125 return sepa->initialized; 1126 } 1127 1128 /** gets whether separator is a parent separator */ 1129 SCIP_Bool SCIPsepaIsParentsepa( 1130 SCIP_SEPA* sepa /**< separator */ 1131 ) 1132 { 1133 assert(sepa != NULL); 1134 1135 return sepa->isparentsepa; 1136 } 1137 1138 /** gets parent separator (or NULL) */ 1139 SCIP_SEPA* SCIPsepaGetParentsepa( 1140 SCIP_SEPA* sepa /**< separator */ 1141 ) 1142 { 1143 assert(sepa != NULL); 1144 1145 return sepa->parentsepa; 1146 } 1147