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 compr.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for tree compressions 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 #include <string.h> 35 36 #include "scip/def.h" 37 #include "scip/set.h" 38 #include "scip/clock.h" 39 #include "scip/paramset.h" 40 #include "scip/scip.h" 41 #include "scip/compr.h" 42 #include "scip/reopt.h" 43 #include "scip/pub_message.h" 44 #include "scip/pub_misc.h" 45 46 #include "scip/struct_compr.h" 47 48 49 50 /** compares two compression methods w. r. to their delay positions and their priority */ 51 SCIP_DECL_SORTPTRCOMP(SCIPcomprComp) 52 { /*lint --e{715}*/ 53 SCIP_COMPR* compr1 = (SCIP_COMPR*)elem1; 54 SCIP_COMPR* compr2 = (SCIP_COMPR*)elem2; 55 56 assert(compr1 != NULL); 57 assert(compr2 != NULL); 58 59 return compr2->priority - compr1->priority; /* prefer higher priorities */ 60 } 61 62 /** comparison method for sorting heuristics w.r.t. to their name */ 63 SCIP_DECL_SORTPTRCOMP(SCIPcomprCompName) 64 { 65 return strcmp(SCIPcomprGetName((SCIP_COMPR*)elem1), SCIPcomprGetName((SCIP_COMPR*)elem2)); 66 } 67 68 /** method to call, when the priority of a compression was changed */ 69 static 70 SCIP_DECL_PARAMCHGD(paramChgdComprPriority) 71 { /*lint --e{715}*/ 72 SCIP_PARAMDATA* paramdata; 73 74 paramdata = SCIPparamGetData(param); 75 assert(paramdata != NULL); 76 77 /* use SCIPsetComprPriority() to mark the compressions unsorted */ 78 SCIP_CALL( SCIPsetComprPriority(scip, (SCIP_COMPR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/ 79 80 return SCIP_OKAY; 81 } 82 83 /** copies the given tree compression to a new scip */ 84 SCIP_RETCODE SCIPcomprCopyInclude( 85 SCIP_COMPR* compr, /**< tree compression */ 86 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 87 ) 88 { 89 assert(compr != NULL); 90 assert(set != NULL); 91 assert(set->scip != NULL); 92 93 if( compr->comprcopy != NULL ) 94 { 95 SCIPsetDebugMsg(set, "including compr %s in subscip %p\n", SCIPcomprGetName(compr), (void*)set->scip); 96 SCIP_CALL( compr->comprcopy(set->scip, compr) ); 97 } 98 99 return SCIP_OKAY; 100 } 101 102 /** internal method for creating a tree compression */ 103 static 104 SCIP_RETCODE doComprCreate( 105 SCIP_COMPR** compr, /**< pointer to tree compression data structure */ 106 SCIP_SET* set, /**< global SCIP settings */ 107 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 108 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 109 const char* name, /**< name of tree compression */ 110 const char* desc, /**< description of tree compression */ 111 int priority, /**< priority of the tree compression */ 112 int minnnodes, /**< minimal number of nodes for calling compression */ 113 SCIP_DECL_COMPRCOPY ((*comprcopy)), /**< copy method of tree compression or NULL if you don't want to copy your plugin into sub-SCIPs */ 114 SCIP_DECL_COMPRFREE ((*comprfree)), /**< destructor of tree compression */ 115 SCIP_DECL_COMPRINIT ((*comprinit)), /**< initialize tree compression */ 116 SCIP_DECL_COMPREXIT ((*comprexit)), /**< deinitialize tree compression */ 117 SCIP_DECL_COMPRINITSOL ((*comprinitsol)), /**< solving process initialization method of tree compression */ 118 SCIP_DECL_COMPREXITSOL ((*comprexitsol)), /**< solving process deinitialization method of tree compression */ 119 SCIP_DECL_COMPREXEC ((*comprexec)), /**< execution method of tree compression */ 120 SCIP_COMPRDATA* comprdata /**< tree compression data */ 121 ) 122 { 123 char paramname[SCIP_MAXSTRLEN]; 124 char paramdesc[SCIP_MAXSTRLEN]; 125 126 assert(compr != NULL); 127 assert(name != NULL); 128 assert(desc != NULL); 129 assert(comprexec != NULL); 130 131 SCIP_ALLOC( BMSallocMemory(compr) ); 132 BMSclearMemory(*compr); 133 134 SCIP_ALLOC( BMSduplicateMemoryArray(&(*compr)->name, name, strlen(name)+1) ); 135 SCIP_ALLOC( BMSduplicateMemoryArray(&(*compr)->desc, desc, strlen(desc)+1) ); 136 (*compr)->priority = priority; 137 (*compr)->minnnodes = minnnodes; 138 (*compr)->comprcopy = comprcopy; 139 (*compr)->comprfree = comprfree; 140 (*compr)->comprinit = comprinit; 141 (*compr)->comprexit = comprexit; 142 (*compr)->comprinitsol = comprinitsol; 143 (*compr)->comprexitsol = comprexitsol; 144 (*compr)->comprexec = comprexec; 145 (*compr)->comprdata = comprdata; 146 SCIP_CALL( SCIPclockCreate(&(*compr)->setuptime, SCIP_CLOCKTYPE_DEFAULT) ); 147 SCIP_CALL( SCIPclockCreate(&(*compr)->comprclock, SCIP_CLOCKTYPE_DEFAULT) ); 148 (*compr)->ncalls = 0; 149 (*compr)->nfound = 0; 150 (*compr)->rate = 0.0; 151 (*compr)->initialized = FALSE; 152 (*compr)->nnodes = 0; 153 (*compr)->loi = 0.0; 154 155 /* add parameters */ 156 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "compression/%s/priority", name); 157 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of compression <%s>", name); 158 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 159 &(*compr)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4, 160 paramChgdComprPriority, (SCIP_PARAMDATA*)(*compr)) ); /*lint !e740*/ 161 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "compression/%s/minnleaves", name); 162 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "minimal number of leave nodes for calling tree compression <%s>", name); 163 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 164 &(*compr)->minnnodes, FALSE, minnnodes, 1, INT_MAX, NULL, NULL) ); 165 166 return SCIP_OKAY; 167 } 168 169 /** creates a tree compression */ 170 SCIP_RETCODE SCIPcomprCreate( 171 SCIP_COMPR** compr, /**< pointer to tree compression data structure */ 172 SCIP_SET* set, /**< global SCIP settings */ 173 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 174 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 175 const char* name, /**< name of tree compression */ 176 const char* desc, /**< description of tree compression */ 177 int priority, /**< priority of the tree compression */ 178 int minnnodes, /**< minimal number of nodes for calling compression */ 179 SCIP_DECL_COMPRCOPY ((*comprcopy)), /**< copy method of tree compression or NULL if you don't want to copy 180 * your plugin into sub-SCIPs */ 181 SCIP_DECL_COMPRFREE ((*comprfree)), /**< destructor of tree compression */ 182 SCIP_DECL_COMPRINIT ((*comprinit)), /**< initialize tree compression */ 183 SCIP_DECL_COMPREXIT ((*comprexit)), /**< deinitialize tree compression */ 184 SCIP_DECL_COMPRINITSOL ((*comprinitsol)), /**< solving process initialization method of tree compression */ 185 SCIP_DECL_COMPREXITSOL ((*comprexitsol)), /**< solving process deinitialization method of tree compression */ 186 SCIP_DECL_COMPREXEC ((*comprexec)), /**< execution method of tree compression */ 187 SCIP_COMPRDATA* comprdata /**< tree compression data */ 188 ) 189 { 190 assert(compr != NULL); 191 assert(name != NULL); 192 assert(desc != NULL); 193 assert(comprexec != NULL); 194 195 SCIP_CALL_FINALLY( doComprCreate(compr, set, messagehdlr, blkmem, name, desc, priority, minnnodes, 196 comprcopy, comprfree, comprinit, comprexit, comprinitsol, comprexitsol, comprexec, comprdata), 197 (void) SCIPcomprFree(compr, set) ); 198 199 return SCIP_OKAY; 200 } 201 202 /** calls destructor and frees memory of tree compression */ 203 SCIP_RETCODE SCIPcomprFree( 204 SCIP_COMPR** compr, /**< pointer to tree compression data structure */ 205 SCIP_SET* set /**< global SCIP settings */ 206 ) 207 { 208 assert(compr != NULL); 209 if( *compr == NULL ) 210 return SCIP_OKAY; 211 assert(!(*compr)->initialized); 212 assert(set != NULL); 213 214 /* call destructor of tree compression */ 215 if( (*compr)->comprfree != NULL ) 216 { 217 SCIP_CALL( (*compr)->comprfree(set->scip, *compr) ); 218 } 219 220 SCIPclockFree(&(*compr)->comprclock); 221 SCIPclockFree(&(*compr)->setuptime); 222 BMSfreeMemoryArrayNull(&(*compr)->name); 223 BMSfreeMemoryArrayNull(&(*compr)->desc); 224 BMSfreeMemory(compr); 225 226 return SCIP_OKAY; 227 } 228 229 /** initializes tree compression */ 230 SCIP_RETCODE SCIPcomprInit( 231 SCIP_COMPR* compr, /**< tree compression */ 232 SCIP_SET* set /**< global SCIP settings */ 233 ) 234 { 235 assert(compr != NULL); 236 assert(set != NULL); 237 238 if( compr->initialized ) 239 { 240 SCIPerrorMessage("tree compression <%s> already initialized\n", compr->name); 241 return SCIP_INVALIDCALL; 242 } 243 244 if( set->misc_resetstat && !set->reopt_enable ) 245 { 246 SCIPclockReset(compr->setuptime); 247 SCIPclockReset(compr->comprclock); 248 249 compr->ncalls = 0; 250 compr->nfound = 0; 251 } 252 253 if( compr->comprinit != NULL ) 254 { 255 /* start timing */ 256 SCIPclockStart(compr->setuptime, set); 257 258 SCIP_CALL( compr->comprinit(set->scip, compr) ); 259 260 /* stop timing */ 261 SCIPclockStop(compr->setuptime, set); 262 } 263 compr->initialized = TRUE; 264 265 return SCIP_OKAY; 266 } 267 268 /** calls exit method of tree compression */ 269 SCIP_RETCODE SCIPcomprExit( 270 SCIP_COMPR* compr, /**< tree compression */ 271 SCIP_SET* set /**< global SCIP settings */ 272 ) 273 { 274 assert(compr != NULL); 275 assert(set != NULL); 276 277 if( !compr->initialized ) 278 { 279 SCIPerrorMessage("tree compression <%s> not initialized\n", compr->name); 280 return SCIP_INVALIDCALL; 281 } 282 283 if( compr->comprexit != NULL ) 284 { 285 /* start timing */ 286 SCIPclockStart(compr->setuptime, set); 287 288 SCIP_CALL( compr->comprexit(set->scip, compr) ); 289 290 /* stop timing */ 291 SCIPclockStop(compr->setuptime, set); 292 } 293 compr->initialized = FALSE; 294 295 return SCIP_OKAY; 296 } 297 298 /** calls execution method of tree compression */ 299 SCIP_RETCODE SCIPcomprExec( 300 SCIP_COMPR* compr, /**< tree compression */ 301 SCIP_SET* set, /**< global SCIP settings */ 302 SCIP_REOPT* reopt, /**< reoptimization data structure */ 303 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 304 ) 305 { 306 assert(compr != NULL); 307 assert(compr->comprexec != NULL); 308 assert(set != NULL); 309 assert(set->scip != NULL); 310 assert(result != NULL); 311 312 *result = SCIP_DIDNOTRUN; 313 314 /* do not run if reoptimization data structure is not initialized */ 315 if( reopt == NULL ) 316 return SCIP_OKAY; 317 318 /* do not run if the reoptimization tree is not large enough */ 319 if( SCIPreoptGetNLeaves(reopt, NULL) < compr->minnnodes ) 320 return SCIP_OKAY; 321 322 SCIPsetDebugMsg(set, "executing tree compression <%s>\n", compr->name); 323 324 /* start timing */ 325 SCIPclockStart(compr->comprclock, set); 326 327 /* call external method */ 328 SCIP_CALL( compr->comprexec(set->scip, compr, result) ); 329 330 /* stop timing */ 331 SCIPclockStop(compr->comprclock, set); 332 333 /* evaluate result */ 334 if( *result != SCIP_SUCCESS 335 && *result != SCIP_DIDNOTFIND 336 && *result != SCIP_DIDNOTRUN ) 337 { 338 SCIPerrorMessage("execution method of tree compression <%s> returned invalid result <%d>\n", 339 compr->name, *result); 340 return SCIP_INVALIDRESULT; 341 } 342 343 if( *result != SCIP_DIDNOTRUN ) 344 compr->ncalls++; 345 346 if( *result == SCIP_SUCCESS ) 347 compr->nfound++; 348 349 return SCIP_OKAY; 350 } 351 352 /** gets user data of tree compression */ 353 SCIP_COMPRDATA* SCIPcomprGetData( 354 SCIP_COMPR* compr /**< tree compression */ 355 ) 356 { 357 assert(compr != NULL); 358 359 return compr->comprdata; 360 } 361 362 /** sets user data of tree compression; user has to free old data in advance! */ 363 void SCIPcomprSetData( 364 SCIP_COMPR* compr, /**< tree compression */ 365 SCIP_COMPRDATA* comprdata /**< new tree compression user data */ 366 ) 367 { 368 assert(compr != NULL); 369 370 compr->comprdata = comprdata; 371 } 372 373 /* new callback setter methods */ 374 375 /** sets copy callback of tree compression */ 376 void SCIPcomprSetCopy( 377 SCIP_COMPR* compr, /**< tree compression */ 378 SCIP_DECL_COMPRCOPY ((*comprcopy)) /**< copy callback of tree compression or NULL if you don't want to copy your plugin into sub-SCIPs */ 379 ) 380 { 381 assert(compr != NULL); 382 383 compr->comprcopy = comprcopy; 384 } 385 386 /** sets destructor callback of tree compression */ 387 void SCIPcomprSetFree( 388 SCIP_COMPR* compr, /**< tree compression */ 389 SCIP_DECL_COMPRFREE ((*comprfree)) /**< destructor of tree compression */ 390 ) 391 { 392 assert(compr != NULL); 393 394 compr->comprfree = comprfree; 395 } 396 397 /** sets initialization callback of tree compression */ 398 void SCIPcomprSetInit( 399 SCIP_COMPR* compr, /**< tree compression */ 400 SCIP_DECL_COMPRINIT ((*comprinit)) /**< initialize tree compression */ 401 ) 402 { 403 assert(compr != NULL); 404 405 compr->comprinit = comprinit; 406 } 407 408 /** sets deinitialization callback of tree compression */ 409 void SCIPcomprSetExit( 410 SCIP_COMPR* compr, /**< tree compression */ 411 SCIP_DECL_COMPREXIT ((*comprexit)) /**< deinitialize tree compression */ 412 ) 413 { 414 assert(compr != NULL); 415 416 compr->comprexit = comprexit; 417 } 418 419 /** sets solving process initialization callback of tree compression */ 420 void SCIPcomprSetInitsol( 421 SCIP_COMPR* compr, /**< tree compression */ 422 SCIP_DECL_COMPRINITSOL ((*comprinitsol)) /**< solving process initialization callback of tree compression */ 423 ) 424 { 425 assert(compr != NULL); 426 427 compr->comprinitsol = comprinitsol; 428 } 429 430 /** sets solving process deinitialization callback of tree compression */ 431 void SCIPcomprSetExitsol( 432 SCIP_COMPR* compr, /**< tree compression */ 433 SCIP_DECL_COMPREXITSOL ((*comprexitsol)) /**< solving process deinitialization callback of tree compression */ 434 ) 435 { 436 assert(compr != NULL); 437 438 compr->comprexitsol = comprexitsol; 439 } 440 441 /** should the compression be executed at the given depth, number of nodes */ 442 SCIP_Bool SCIPcomprShouldBeExecuted( 443 SCIP_COMPR* compr, /**< tree compression */ 444 int depth, /**< depth of current node */ 445 int nnodes /**< number of open nodes */ 446 ) 447 { 448 assert(compr != NULL); 449 assert(depth >= 0); 450 assert(nnodes >= 0); 451 452 return nnodes >= compr->minnnodes; 453 } 454 455 /** gets name of tree compression */ 456 const char* SCIPcomprGetName( 457 SCIP_COMPR* compr /**< tree compression */ 458 ) 459 { 460 assert(compr != NULL); 461 462 return compr->name; 463 } 464 465 /** gets description of tree compression */ 466 const char* SCIPcomprGetDesc( 467 SCIP_COMPR* compr /**< tree compression */ 468 ) 469 { 470 assert(compr != NULL); 471 472 return compr->desc; 473 } 474 475 /** gets priority of tree compression */ 476 int SCIPcomprGetPriority( 477 SCIP_COMPR* compr /**< tree compression */ 478 ) 479 { 480 assert(compr != NULL); 481 482 return compr->priority; 483 } 484 485 /** sets priority of tree compression */ 486 void SCIPcomprSetPriority( 487 SCIP_COMPR* compr, /**< tree compression */ 488 SCIP_SET* set, /**< global SCIP settings */ 489 int priority /**< new priority of the tree compression */ 490 ) 491 { 492 assert(compr != NULL); 493 assert(set != NULL); 494 495 compr->priority = priority; 496 set->comprssorted = FALSE; 497 } 498 499 /** gets minimal number of nodes for calling tree compression (returns -1, if no node threshold exists) */ 500 int SCIPcomprGetMinNodes( 501 SCIP_COMPR* compr /**< tree compression */ 502 ) 503 { 504 assert(compr != NULL); 505 506 return compr->minnnodes; 507 } 508 509 /** gets the number of times, the heuristic was called and tried to find a solution */ 510 SCIP_Longint SCIPcomprGetNCalls( 511 SCIP_COMPR* compr /**< tree compression */ 512 ) 513 { 514 assert(compr != NULL); 515 516 return compr->ncalls; 517 } 518 519 /** gets the number of compressions found by this compression */ 520 SCIP_Longint SCIPcomprGetNFound( 521 SCIP_COMPR* compr /**< tree compression */ 522 ) 523 { 524 assert(compr != NULL); 525 526 return compr->nfound; 527 } 528 529 /** is tree compression initialized? */ 530 SCIP_Bool SCIPcomprIsInitialized( 531 SCIP_COMPR* compr /**< tree compression */ 532 ) 533 { 534 assert(compr != NULL); 535 536 return compr->initialized; 537 } 538 539 /** gets time in seconds used in this heuristic for setting up for next stages */ 540 SCIP_Real SCIPcomprGetSetupTime( 541 SCIP_COMPR* compr /**< tree compression */ 542 ) 543 { 544 assert(compr != NULL); 545 546 return SCIPclockGetTime(compr->setuptime); 547 } 548 549 /** gets time in seconds used in this heuristic */ 550 SCIP_Real SCIPcomprGetTime( 551 SCIP_COMPR* compr /**< tree compression */ 552 ) 553 { 554 assert(compr != NULL); 555 556 return SCIPclockGetTime(compr->comprclock); 557 } 558