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_largestrepr.c 26 * @ingroup OTHER_CFILES 27 * @brief largestrepr tree compression 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/compr_largestrepr.h" 35 #include "scip/pub_compr.h" 36 #include "scip/pub_message.h" 37 #include "scip/pub_misc.h" 38 #include "scip/pub_reopt.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_compr.h" 41 #include "scip/scip_general.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_numerics.h" 45 #include "scip/scip_param.h" 46 #include "scip/scip_prob.h" 47 #include "scip/scip_reopt.h" 48 #include <string.h> 49 50 #define COMPR_NAME "largestrepr" 51 #define COMPR_DESC "heuristic searching for large common representatives" 52 #define COMPR_PRIORITY 2000 53 #define COMPR_MINNNODES 20 54 55 #define DEFAUL_MEM_REPR 10 56 #define DEFAULT_ITERS 5 57 #define DEFAULT_MINCOMMONVARS 3 58 59 /* 60 * Data structures 61 */ 62 63 /** tree compression data */ 64 struct SCIP_ComprData 65 { 66 /* representative data */ 67 SCIP_REOPTNODE** representatives; /**< list of representatives */ 68 int nrepresentatives; /**< number of representatives */ 69 int representativessize;/**< allocated memory for representatives */ 70 SCIP_Bool initialized; /**< was compressor data initialized? */ 71 72 /* statictics */ 73 SCIP_Real rate; /**< rate of compression */ 74 SCIP_Real score; /**< score of the best representation found */ 75 int nnodes; /**< number of nodes after compressing */ 76 77 /* parameters */ 78 int mincomvars; /**< minimal number of common variables */ 79 int niters; /**< number of runs in the constrained part */ 80 }; 81 82 83 /* 84 * Local methods 85 */ 86 87 /** calculate a bit signature of variables fixed to 0 and 1 on the basis of SCIPvarGetProbindex() 88 */ 89 static 90 void calcSignature( 91 SCIP_VAR** vars, /**< variable array */ 92 SCIP_Real* vals, /**< value array */ 93 int nvars, /**< number of variables */ 94 uint64_t* signature0, /**< pointer to store the signatures of variables fixed to 0 */ 95 uint64_t* signature1 /**< pointer to store the signatures of variables fixed to 1 */ 96 ) 97 { 98 uint64_t varsignature; 99 int v; 100 101 (*signature0) = 0; 102 (*signature1) = 0; 103 104 for( v = nvars - 1; v >= 0; --v ) 105 { 106 varsignature = SCIPhashSignature64(SCIPvarGetProbindex(vars[v])); 107 if( vals[v] < 0.5 ) 108 (*signature0) |= varsignature; 109 else 110 (*signature1) |= varsignature; 111 } 112 113 return; 114 } 115 116 /** try to find a representation of the current search frontier. 117 * 118 * We use the signatures of variables fixed to 0 and 1 to decide if there is 119 * definitely no intersection or if the intersection is potentially non-empty. 120 * 121 * To find a good representation we start the procedure with a node and choose the best one. 122 * the heuristic tries to find a representation of size 2 in each iteration, i.e., runs in the 123 * constrained part. 124 */ 125 static 126 SCIP_RETCODE constructCompression( 127 SCIP* scip, /**< SCIP data structure */ 128 SCIP_COMPR* compr, /**< compression method */ 129 SCIP_COMPRDATA* comprdata, /**< compression data */ 130 SCIP_RESULT* result /**< result pointer */ 131 ) 132 { 133 SCIP_NODE* currentnode; 134 SCIP_VAR*** repvars; 135 SCIP_Real** repvals; 136 int* nrepvars; 137 SCIP_VAR*** vars; 138 SCIP_Real** vals; 139 SCIP_BOUNDTYPE** bounds; 140 SCIP_Real* lowerbounds; 141 SCIP_Bool* covered; 142 const char** varnames; 143 SCIP_Real score; 144 int nreps; 145 uint64_t* signature0; 146 uint64_t* signature1; 147 int* common_vars; 148 unsigned int* leaveids; 149 int* nvars; 150 int nids; 151 int nleaveids; 152 int k; 153 int current_id; 154 int start_id; 155 156 assert(scip != NULL); 157 assert(comprdata != NULL); 158 159 *result = SCIP_DIDNOTRUN; 160 161 assert(SCIPgetStage(scip) <= SCIP_STAGE_PRESOLVED); 162 163 currentnode = NULL; 164 nleaveids = SCIPgetNReoptLeaves(scip, currentnode); 165 166 SCIPdebugMsg(scip, ">> start <%s> (nleaves: %d)\n", COMPR_NAME, nleaveids); 167 168 if( SCIPcomprGetMinNodes(compr) > nleaveids ) 169 { 170 SCIPdebugMsg(scip, "-> skip compression (min. leaves = %d)\n", SCIPcomprGetMinNodes(compr)); 171 return SCIP_OKAY; 172 } 173 174 *result = SCIP_DIDNOTFIND; 175 176 SCIPdebugMsg(scip, "-> try compression with %d node(s)\n", nleaveids); 177 178 /* collect the nodes to compress */ 179 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &leaveids, nleaveids) ); 180 181 SCIP_CALL( SCIPgetReoptLeaveIDs(scip, currentnode, leaveids, nleaveids, &nids) ); 182 assert(nids == nleaveids); 183 184 /* allocate memory to store the old tree */ 185 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nleaveids) ); 186 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nleaveids) ); 187 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nleaveids) ); 188 SCIP_CALL( SCIPallocBufferArray(scip, &nvars, nleaveids) ); 189 SCIP_CALL( SCIPallocBufferArray(scip, &lowerbounds, nleaveids) ); 190 SCIP_CALL( SCIPallocBufferArray(scip, &varnames, SCIPgetNOrigVars(scip)) ); 191 192 /* allocate memory to store the signatures */ 193 SCIP_CALL( SCIPallocBufferArray(scip, &signature0, nleaveids) ); 194 SCIP_CALL( SCIPallocBufferArray(scip, &signature1, nleaveids) ); 195 196 /* get data of nodes */ 197 for( k = 0; k < nleaveids; k++ ) 198 { 199 SCIP_REOPTNODE* reoptnode; 200 int mem_vars; 201 int nvars2; 202 int nafterdualvars; 203 204 mem_vars = SCIPgetNBinVars(scip); 205 206 /* allocate memory */ 207 SCIP_CALL( SCIPallocBufferArray(scip, &vars[k], mem_vars) ); /*lint !e866*/ 208 SCIP_CALL( SCIPallocBufferArray(scip, &vals[k], mem_vars) ); /*lint !e866*/ 209 SCIP_CALL( SCIPallocBufferArray(scip, &bounds[k], mem_vars) ); /*lint !e866*/ 210 211 /* get the branching path */ 212 reoptnode = SCIPgetReoptnode(scip, leaveids[k]); 213 SCIPgetReoptnodePath(scip, reoptnode, vars[k], vals[k], bounds[k], mem_vars, &nvars2, &nafterdualvars); 214 lowerbounds[k] = SCIPreoptnodeGetLowerbound(reoptnode); 215 nvars[k] = nvars2 + nafterdualvars; 216 217 /* calculate the signature*/ 218 calcSignature(vars[k], vals[k], nvars[k], &signature0[k], &signature1[k]); 219 } 220 221 for( start_id = 0; start_id < nleaveids; start_id++ ) 222 { 223 nreps = -1; 224 score = 0.0; 225 226 /* we want to find an intersection that merges at least 3 nodes */ 227 if( nvars[start_id] <= comprdata->mincomvars + 1 ) 228 continue; 229 230 /* initialize the covered-array with FALSE */ 231 SCIP_CALL( SCIPallocClearBufferArray(scip, &covered, nleaveids) ); 232 233 current_id = start_id; 234 235 /* initialize storage for representatives */ 236 SCIP_CALL( SCIPallocBufferArray(scip, &repvars, 2+comprdata->niters) ); 237 SCIP_CALL( SCIPallocBufferArray(scip, &repvals, 2+comprdata->niters) ); 238 SCIP_CALL( SCIPallocBufferArray(scip, &nrepvars, 2+comprdata->niters) ); 239 240 SCIPdebugMsg(scip, "+---+ start round %d +---+\n", start_id + 1); 241 242 /* try to find common representatives */ 243 while( nreps-1 <= comprdata->niters && (nreps == -1 || (current_id % nleaveids) != start_id) ) 244 { 245 int* idx_common_vars; 246 int* idx_non_zero; 247 int* covered_ids; 248 int ncovered; 249 int ncommon_vars; 250 int nnon_zero_vars; 251 int next_id; 252 int nnemptyinters; 253 int v; 254 255 /* find the first id which is not covered */ 256 while( covered[current_id % nleaveids] && (nreps == -1 || (current_id % nleaveids) != start_id) ) 257 current_id++; 258 259 current_id %= nleaveids; 260 261 if( nreps > 0 && current_id == start_id ) 262 goto TERMINATE; 263 264 /* if the this is the fist round with a new start_id we set the number of representatives to 0 */ 265 nreps = MAX(0, nreps); 266 267 nnemptyinters = 0; 268 269 /* mark the node as covered */ 270 covered[current_id] = TRUE; 271 272 /* find the next not covered id */ 273 next_id = (current_id + 1) % nleaveids ; 274 while( covered[next_id] && next_id != current_id ) 275 next_id = (next_id + 1) % nleaveids; 276 277 if( next_id == current_id ) 278 goto TERMINATE; 279 280 /* we want to find an intersection that merges at least 3 nodes */ 281 if( nvars[next_id] <= comprdata->mincomvars + 1 ) 282 continue; 283 284 /* get a clear array of size SCIPgetNOrigVars */ 285 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &common_vars, SCIPgetNOrigVars(scip)) ); 286 287 /* allocate buffer */ 288 nnon_zero_vars = 0; 289 SCIP_CALL( SCIPallocBufferArray(scip, &idx_common_vars, nvars[current_id]) ); 290 SCIP_CALL( SCIPallocBufferArray(scip, &idx_non_zero, nvars[current_id]) ); 291 SCIP_CALL( SCIPallocBufferArray(scip, &covered_ids, nleaveids) ); 292 ncovered = 0; 293 294 /* initialize common vars: 295 * vars[i] = 0 -> variable with idx i is not fixed 296 * vars[i] = 1 -> variable with idx i is fixed to zero 297 * vars[i] = 2 -> variable with idx i is fixed to one */ 298 for( v = 0; v < nvars[current_id]; v++ ) 299 { 300 if( SCIPisFeasEQ(scip, vals[current_id][v], 0.0) ) 301 common_vars[SCIPvarGetProbindex(vars[current_id][v])] = 1; 302 else 303 { 304 assert(SCIPisFeasEQ(scip, vals[current_id][v], 1.0)); 305 common_vars[SCIPvarGetProbindex(vars[current_id][v])] = 2; 306 } 307 308 varnames[SCIPvarGetProbindex(vars[current_id][v])] = SCIPvarGetName(vars[current_id][v]); 309 310 idx_non_zero[nnon_zero_vars] = SCIPvarGetProbindex(vars[current_id][v]); 311 nnon_zero_vars++; 312 } 313 314 SCIPdebugMsg(scip, "start with ID %u, %d fixed variables\n", leaveids[current_id], nnon_zero_vars); 315 316 covered_ids[ncovered] = current_id; 317 ncovered++; 318 319 while( nnon_zero_vars >= comprdata->mincomvars ) 320 { 321 /* find the next id which is not covered */ 322 while( covered[next_id % nleaveids] && (next_id % nleaveids) != current_id ) 323 { 324 /* go to the next node if the intersection is empty */ 325 if( (signature0[current_id] & signature0[next_id % nleaveids]) == 0 326 && (signature1[current_id] & signature1[next_id % nleaveids]) == 0 ) 327 next_id++; 328 else 329 break; 330 } 331 332 if( (next_id % nleaveids) == current_id ) 333 break; 334 335 next_id %= nleaveids; 336 337 if( covered[next_id] ) 338 goto EMPTY; 339 340 ncommon_vars = 0; 341 342 /* calculate the intersection */ 343 for( v = 0; v < nvars[next_id]; v++ ) 344 { 345 if( common_vars[SCIPvarGetProbindex(vars[next_id][v])] == (vals[next_id][v] == 0 ? 1 : 2) ) 346 { 347 idx_common_vars[ncommon_vars] = SCIPvarGetProbindex(vars[next_id][v]); 348 ncommon_vars++; 349 } 350 } 351 352 /* the number of common variables should be at least mincomvars */ 353 if( ncommon_vars < comprdata->mincomvars ) 354 goto EMPTY; 355 356 /* clear all non-zero entries which are not part of the intersection */ 357 for( v = 0; v < nnon_zero_vars; ) 358 { 359 int v2; 360 for( v2 = 0; v2 < ncommon_vars; v2++ ) 361 { 362 if( idx_non_zero[v] == idx_common_vars[v2] ) 363 break; 364 } 365 366 /* the variable is not part of the intersection */ 367 if( v2 == ncommon_vars ) 368 { 369 common_vars[idx_non_zero[v]] = 0; 370 371 /* replace the idx with the last */ 372 idx_non_zero[v] = idx_non_zero[nnon_zero_vars-1]; 373 nnon_zero_vars--; 374 } 375 else 376 v++; 377 } 378 379 /* mark the node as covered */ 380 if( nnon_zero_vars > 0 ) 381 { 382 covered[next_id] = TRUE; 383 nnemptyinters++; 384 385 SCIPdebugMessage("-> found intersection with ID %u, %d/%d common variables\n", leaveids[next_id], 386 nnon_zero_vars, MAX(nvars[current_id], nvars[next_id])); 387 388 covered_ids[ncovered] = next_id; 389 ncovered++; 390 } 391 392 EMPTY: 393 next_id++; 394 395 if( next_id % nleaveids == (current_id-1) % nleaveids ) 396 break; 397 } 398 399 if( nnemptyinters > 0 ) 400 { 401 /* increase the number of representatives */ 402 if( nreps == 0 ) 403 nreps += 2; 404 else 405 nreps++; 406 407 SCIP_CALL( SCIPallocBufferArray(scip, &repvars[nreps-2], nnon_zero_vars) ); /*lint !e866*/ 408 SCIP_CALL( SCIPallocBufferArray(scip, &repvals[nreps-2], nnon_zero_vars) ); /*lint !e866*/ 409 nrepvars[nreps-2] = nnon_zero_vars; 410 411 /* set the common variables and bounds (use non-zero idx)*/ 412 for( k = 0; k < nnon_zero_vars; k++ ) 413 { 414 repvars[nreps-2][k] = SCIPfindVar(scip, varnames[idx_non_zero[k]]); 415 repvals[nreps-2][k] = common_vars[idx_non_zero[k]] - 1; 416 assert(repvals[nreps-2][k] == 0 || repvals[nreps-2][k] == 1); 417 } 418 } 419 else 420 { 421 SCIPdebugMsg(scip, "-> did not found a intersection larger than %d\n", comprdata->mincomvars); 422 covered[current_id] = FALSE; 423 } 424 425 /* calculate the score */ 426 score += (SCIP_Real) ncovered * nnon_zero_vars; 427 428 SCIPdebugMessage("-> current representation is of size %d with score = %.1f\n", nreps, score); 429 430 current_id = (current_id + 1) % nleaveids; 431 432 /* free memory */ 433 SCIPfreeBlockMemoryArray(scip, &common_vars, SCIPgetNOrigVars(scip)); 434 435 SCIPfreeBufferArray(scip, &covered_ids); 436 SCIPfreeBufferArray(scip, &idx_non_zero); 437 SCIPfreeBufferArray(scip, &idx_common_vars); 438 } 439 440 TERMINATE: 441 442 /* add the number of variables of uncovered nodes to the loss of information */ 443 SCIPdebugMessage("-> final representation is of size %d with score = %.1f\n", nreps, score); 444 445 /* We found a better representation, i.e., with less loss of information. 446 * 1. reset the previous represenation 447 * 2. check if we need to reallocate the memory 448 * 3. set the new representation 449 */ 450 if( nreps > 0 && SCIPisSumGT(scip, score, comprdata->score) ) 451 { 452 /* reset the current representation */ 453 SCIP_CALL( SCIPresetRepresentation(scip, comprdata->representatives, comprdata->nrepresentatives) ); 454 455 /* ensure that enough memory is allocated */ 456 if( comprdata->representativessize < nreps ) 457 { 458 /* free the representatoin */ 459 SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->nrepresentatives) ); 460 461 /* reallocate memory */ 462 SCIP_CALL( SCIPreallocMemoryArray(scip, &comprdata->representatives, nreps) ); 463 comprdata->representativessize = nreps; 464 465 /* initialize the representation */ 466 SCIP_CALL( SCIPinitRepresentation(scip, comprdata->representatives, comprdata->representativessize) ); 467 } 468 469 /* set the new representation 470 * 471 * copy the new representation. we skip the last representative because it is implicitly given by the union of 472 * the logic-or constraints of all previous representatives. 473 */ 474 comprdata->score = score; 475 comprdata->nrepresentatives = nreps; 476 477 for( k = 0; k < nreps-1; k++ ) 478 { 479 int v; 480 481 for( v = 0; v < nrepvars[k]; v++ ) 482 { 483 SCIP_CALL( SCIPaddReoptnodeBndchg(scip, comprdata->representatives[k], repvars[k][v], 484 repvals[k][v], repvals[k][v] == 0 ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER) ); 485 } 486 } 487 488 *result = SCIP_SUCCESS; 489 } 490 491 /* free representatives storage */ 492 for( k = 0; k <= nreps-2; k++ ) 493 { 494 SCIPfreeBufferArray(scip, &repvals[k]); 495 SCIPfreeBufferArray(scip, &repvars[k]); 496 } 497 498 SCIPfreeBufferArray(scip, &nrepvars); 499 SCIPfreeBufferArray(scip, &repvals); 500 SCIPfreeBufferArray(scip, &repvars); 501 502 /* free covered array */ 503 SCIPfreeBufferArray(scip, &covered); 504 } 505 506 /* check if we have found a representation and construct the missing constraints */ 507 if( comprdata->nrepresentatives > 0 ) 508 { 509 SCIPdebugMessage("best representation found has %d leaf nodes and score = %g\n", comprdata->nrepresentatives, comprdata->score); 510 511 /* iterate over all representatives */ 512 for( k = 0; k < comprdata->nrepresentatives-1; k++ ) 513 { 514 int r; 515 516 /* add a constraint (corresponding to the branching path of k) to all representatives 517 * in the subtree induced by the sibling of k 518 */ 519 for( r = k + 1; r < comprdata->nrepresentatives; r++ ) 520 { 521 SCIP_VAR** pathvars; 522 SCIP_Real* pathvals; 523 SCIP_BOUNDTYPE* pathboundtypes; 524 SCIP_Real lhs; 525 SCIP_Bool linear; 526 int pathvarssize; 527 int npathvars; 528 int npathafterdualvars; 529 int i; 530 531 pathvarssize = SCIPreoptnodeGetNVars(comprdata->representatives[k]); 532 533 /* allocate buffer */ 534 SCIP_CALL( SCIPallocBufferArray(scip, &pathvars, pathvarssize) ); 535 SCIP_CALL( SCIPallocBufferArray(scip, &pathvals, pathvarssize) ); 536 SCIP_CALL( SCIPallocBufferArray(scip, &pathboundtypes, pathvarssize) ); 537 538 /* get the stored path */ 539 SCIPgetReoptnodePath(scip, comprdata->representatives[k], pathvars, pathvals, pathboundtypes, pathvarssize, 540 &npathvars, &npathafterdualvars); 541 542 lhs = 1.0; 543 linear = TRUE; /* todo: we have to adapt the compression to handle integer variables */ 544 545 /* negate the branching path */ 546 for( i = 0; i < npathvars; i++ ) 547 { 548 assert(SCIPvarIsOriginal(pathvars[i])); 549 550 /* we have to construct a linear constraint that can be upgraded to a logic-or constraint 551 * 552 * each variable i with pathvals[i] == 0 and pathboundtypes[i] == SCIP_BOUNDTYPE_UPPER needs a coefficient 553 * of 1.0, all remaining variables (i.e., pathvals[i] == 1 and pathboundtypes[i] == SCIP_BOUNDTYPE_LOWER) 554 * need a -1.0 and we have to reduce the lhs by -1.0. 555 * 556 * sum_{i : pathvals[i] == 0.0} x_i + sum_{j : pathvals[j] == 1.0} (1.0-x_{j}) >= 1.0 557 * <==> sum_{i : pathvals[i] == 0.0} x_i + sum_{j : pathvals[j] == 1.0} -x_{j} >= 1.0 - sum_{j : pathvals[j] == 1.0} 1.0 558 */ 559 if( SCIPisEQ(scip, pathvals[i], 0.0) ) 560 { 561 assert(pathboundtypes[i] == SCIP_BOUNDTYPE_UPPER); 562 563 pathvals[i] = 1.0; 564 } 565 else 566 { 567 assert(SCIPisEQ(scip, pathvals[i], 1.0)); 568 assert(pathboundtypes[i] == SCIP_BOUNDTYPE_LOWER); 569 570 pathvals[i] = -1.0; 571 lhs -= 1.0; 572 } 573 } 574 575 SCIP_CALL( SCIPaddReoptnodeCons(scip, comprdata->representatives[r], pathvars, pathvals, NULL, lhs, 576 SCIPinfinity(scip), npathvars, REOPT_CONSTYPE_DUALREDS, linear) ); 577 578 /* free buffer */ 579 SCIPfreeBufferArray(scip, &pathboundtypes); 580 SCIPfreeBufferArray(scip, &pathvals); 581 SCIPfreeBufferArray(scip, &pathvars); 582 } 583 } 584 } 585 586 /* free memory */ 587 for( k = nleaveids-1; k >= 0; k-- ) 588 { 589 SCIPfreeBufferArray(scip, &bounds[k]); 590 SCIPfreeBufferArray(scip, &vals[k]); 591 SCIPfreeBufferArray(scip, &vars[k]); 592 } 593 594 SCIPfreeBufferArray(scip, &signature1); 595 SCIPfreeBufferArray(scip, &signature0); 596 597 SCIPfreeBufferArray(scip, &varnames); 598 SCIPfreeBufferArray(scip, &lowerbounds); 599 SCIPfreeBufferArray(scip, &nvars); 600 SCIPfreeBufferArray(scip, &bounds); 601 SCIPfreeBufferArray(scip, &vals); 602 SCIPfreeBufferArray(scip, &vars); 603 604 SCIPfreeBlockMemoryArray(scip, &leaveids, nleaveids); 605 606 return SCIP_OKAY; 607 } 608 609 /** apply the found representation to the reopttree. */ 610 static 611 SCIP_RETCODE applyCompression( 612 SCIP* scip, /**< SCIP data structure */ 613 SCIP_COMPR* compr, /**< compression method */ 614 SCIP_COMPRDATA* comprdata, /**< compression data */ 615 SCIP_RESULT* result /**< result pointer */ 616 ) 617 { 618 SCIP_Bool success; 619 int r; 620 621 assert(scip != NULL); 622 assert(compr != NULL); 623 assert(comprdata != NULL); 624 625 *result = SCIP_DIDNOTRUN; 626 627 if( comprdata->nrepresentatives == 0 ) 628 return SCIP_OKAY; 629 630 /* set references to the root node */ 631 for( r = 0; r < comprdata->nrepresentatives; r++ ) 632 SCIPreoptnodeSetParentID(comprdata->representatives[r], 0); 633 634 success = FALSE; 635 SCIP_CALL( SCIPsetReoptCompression(scip, comprdata->representatives, comprdata->nrepresentatives, &success) ); 636 637 SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->representativessize) ); 638 639 if( success ) 640 *result = SCIP_SUCCESS; 641 642 return SCIP_OKAY; 643 } 644 645 /* 646 * Callback methods of tree compression 647 */ 648 649 /** copy method for tree compression plugins (called when SCIP copies plugins) */ 650 static 651 SCIP_DECL_COMPRCOPY(comprCopyLargestrepr) 652 { /*lint --e{715}*/ 653 assert(scip != NULL); 654 assert(compr != NULL); 655 assert(strcmp(SCIPcomprGetName(compr), COMPR_NAME) == 0); 656 657 /* call inclusion method of primal heuristic */ 658 SCIP_CALL( SCIPincludeComprLargestrepr(scip) ); 659 660 return SCIP_OKAY; 661 } 662 663 /** destructor of tree compression to free user data (called when SCIP is exiting) */ 664 static 665 SCIP_DECL_COMPRFREE(comprFreeLargestrepr) 666 { 667 SCIP_COMPRDATA* comprdata; 668 669 assert(scip != NULL); 670 assert(compr != NULL); 671 672 comprdata = SCIPcomprGetData(compr); 673 assert(comprdata != NULL); 674 675 SCIPfreeBlockMemory(scip, &comprdata); 676 SCIPcomprSetData(compr, NULL); 677 678 return SCIP_OKAY; 679 } 680 681 /** deinitialization method of tree compression (called before transformed problem is freed) */ 682 static 683 SCIP_DECL_COMPREXIT(comprExitLargestrepr) 684 { 685 SCIP_COMPRDATA* comprdata; 686 687 assert(scip != NULL); 688 assert(compr != NULL); 689 690 comprdata = SCIPcomprGetData(compr); 691 assert(comprdata != NULL); 692 693 if( comprdata->initialized ) 694 { 695 if( comprdata->representativessize > 0 ) 696 { 697 SCIPfreeMemoryArray(scip, &comprdata->representatives); 698 } 699 700 comprdata->representatives = NULL; 701 comprdata->representativessize = 0; 702 comprdata->nrepresentatives = 0; 703 comprdata->initialized = FALSE; 704 } 705 706 return SCIP_OKAY; 707 } 708 709 /** execution method of tree compression */ 710 static 711 SCIP_DECL_COMPREXEC(comprExecLargestrepr) 712 { 713 SCIP_COMPRDATA* comprdata; 714 715 comprdata = SCIPcomprGetData(compr); 716 assert(comprdata != NULL); 717 718 if( !comprdata->initialized ) 719 { 720 SCIPdebugMsg(scip, ">> initializing <%s>\n", COMPR_NAME); 721 722 comprdata->representativessize = DEFAUL_MEM_REPR; 723 comprdata->nrepresentatives = 0; 724 comprdata->rate = 0.0; 725 comprdata->score = 0.0; 726 comprdata->nnodes = 0; 727 SCIP_CALL( SCIPallocClearMemoryArray(scip, &comprdata->representatives, comprdata->representativessize) ); 728 729 /* initialize the representation */ 730 SCIP_CALL( SCIPinitRepresentation(scip, comprdata->representatives, comprdata->representativessize) ); 731 732 comprdata->initialized = TRUE; 733 } 734 735 *result = SCIP_DIDNOTRUN; 736 737 /* try to find a representation */ 738 SCIP_CALL( constructCompression(scip, compr, comprdata, result) ); 739 740 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND || *result == SCIP_SUCCESS); 741 742 /* apply the representation, if some was found */ 743 if( *result == SCIP_SUCCESS ) 744 { 745 SCIP_CALL( applyCompression(scip, compr, comprdata, result) ); 746 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_SUCCESS); 747 748 SCIPdebugMsg(scip, "->%s apply compression.\n", *result == SCIP_DIDNOTRUN ? " did not" : ""); 749 } 750 else 751 { 752 SCIP_CALL( SCIPfreeRepresentation(scip, comprdata->representatives, comprdata->representativessize) ); 753 } 754 755 return SCIP_OKAY; 756 } 757 758 /* 759 * tree compression specific interface methods 760 */ 761 762 /** creates the largestrepr tree compression and includes it in SCIP */ 763 SCIP_RETCODE SCIPincludeComprLargestrepr( 764 SCIP* scip /**< SCIP data structure */ 765 ) 766 { 767 SCIP_COMPRDATA* comprdata; 768 SCIP_COMPR* compr; 769 770 /* create largestrepr tree compression data */ 771 SCIP_CALL( SCIPallocBlockMemory(scip, &comprdata) ); 772 assert(comprdata != NULL); 773 comprdata->initialized = FALSE; 774 775 /* include tree compression */ 776 SCIP_CALL( SCIPincludeComprBasic(scip, &compr, COMPR_NAME, COMPR_DESC, COMPR_PRIORITY, COMPR_MINNNODES, 777 comprExecLargestrepr, comprdata) ); 778 779 assert(compr != NULL); 780 781 /* set non fundamental callbacks via setter functions */ 782 SCIP_CALL( SCIPsetComprCopy(scip, compr, comprCopyLargestrepr) ); 783 SCIP_CALL( SCIPsetComprExit(scip, compr, comprExitLargestrepr) ); 784 SCIP_CALL( SCIPsetComprFree(scip, compr, comprFreeLargestrepr) ); 785 786 /* add largestrepr tree compression parameters */ 787 SCIP_CALL( SCIPaddIntParam(scip, "compression/" COMPR_NAME "/iterations", "number of runs in the constrained part.", 788 &comprdata->niters, FALSE, DEFAULT_ITERS, 1, INT_MAX, NULL, NULL) ); 789 SCIP_CALL( SCIPaddIntParam(scip, "compression/" COMPR_NAME "/mincommonvars", "minimal number of common variables.", 790 &comprdata->mincomvars, FALSE, DEFAULT_MINCOMMONVARS, 1, INT_MAX, NULL, NULL) ); 791 792 return SCIP_OKAY; 793 } 794