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 dcmp.c 26 * @ingroup OTHER_CFILES 27 * @brief internal methods for decompositions and the decomposition store 28 * @author Gregor Hendel 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 #include "scip/dcmp.h" 35 #include "scip/mem.h" 36 #include "scip/pub_cons.h" 37 #include "scip/pub_dcmp.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_cons.h" 41 #include "scip/scip_dcmp.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_prob.h" 44 #include "scip/scip_var.h" 45 #include "scip/scip_general.h" 46 #include "scip/scip_var.h" 47 #include "scip/scip_datastructures.h" 48 #include "scip/scip_message.h" 49 #include "scip/struct_dcmp.h" 50 #include "scip/struct_scip.h" 51 52 /* create and free a decomposition */ 53 #define INIT_MAP_SIZE 2000 54 55 /** creates a decomposition */ 56 SCIP_RETCODE SCIPdecompCreate( 57 SCIP_DECOMP** decomp, /**< pointer to store the decomposition data structure */ 58 BMS_BLKMEM* blkmem, /**< block memory */ 59 int nblocks, /**< the number of blocks (without the linking block) */ 60 SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */ 61 SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */ 62 ) 63 { 64 int memsize; 65 66 assert(decomp != NULL); 67 assert(blkmem != NULL); 68 69 SCIP_ALLOC( BMSallocBlockMemory(blkmem, decomp) ); 70 SCIP_CALL( SCIPhashmapCreate(&(*decomp)->var2block, blkmem, INIT_MAP_SIZE) ); 71 SCIP_CALL( SCIPhashmapCreate(&(*decomp)->cons2block, blkmem, INIT_MAP_SIZE) ); 72 73 /* we allocate one extra slot for the linking block */ 74 memsize = nblocks + 1; 75 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->varssize, memsize) ); 76 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->consssize, memsize) ); 77 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decomp)->labels, memsize) ); 78 79 (*decomp)->memsize = memsize; 80 (*decomp)->nblocks = nblocks; 81 (*decomp)->modularity = -1.0; 82 (*decomp)->idxsmallestblock = -1; 83 (*decomp)->idxlargestblock = -1; 84 (*decomp)->original = original; 85 (*decomp)->benderslabels = benderslabels; 86 (*decomp)->areascore = -1.0; 87 (*decomp)->nedges = 0; 88 (*decomp)->mindegree = 0; 89 (*decomp)->maxdegree = 0; 90 (*decomp)->ncomponents = 0; 91 (*decomp)->narticulations = 0; 92 (*decomp)->statscomplete = FALSE; 93 94 return SCIP_OKAY; 95 } 96 97 /** free a decomposition */ 98 void SCIPdecompFree( 99 SCIP_DECOMP** decomp, /**< pointer to free the decomposition data structure */ 100 BMS_BLKMEM* blkmem /**< block memory */ 101 ) 102 { 103 assert(decomp != NULL); 104 assert(blkmem != NULL); 105 106 if( *decomp == NULL ) 107 return; 108 109 assert((*decomp)->var2block != NULL); 110 SCIPhashmapFree(&(*decomp)->var2block); 111 SCIPhashmapFree(&(*decomp)->cons2block); 112 113 BMSfreeBlockMemoryArray(blkmem, &(*decomp)->varssize, (*decomp)->memsize); 114 BMSfreeBlockMemoryArray(blkmem, &(*decomp)->consssize, (*decomp)->memsize); 115 BMSfreeBlockMemoryArray(blkmem, &(*decomp)->labels, (*decomp)->memsize); 116 117 BMSfreeBlockMemory(blkmem, decomp); 118 } 119 120 /* getter and setter for variable labels */ 121 122 /** sets labels for an array of variables */ 123 SCIP_RETCODE SCIPdecompSetVarsLabels( 124 SCIP_DECOMP* decomp, /**< decomposition data structure */ 125 SCIP_VAR** vars, /**< array of variables */ 126 int* labels, /**< array of labels, one per variable */ 127 int nvars /**< length of variables array */ 128 ) 129 { 130 int i; 131 132 assert(decomp != NULL); 133 assert(vars != NULL); 134 assert(labels != NULL); 135 136 /* store each label in hash map */ 137 for( i = 0; i < nvars; ++i ) 138 { 139 assert(labels[i] == SCIP_DECOMP_LINKVAR || labels[i] >= 0); 140 141 SCIP_CALL( SCIPhashmapSetImageInt(decomp->var2block, (void *)vars[i], labels[i]) ); 142 } 143 144 return SCIP_OKAY; 145 } 146 147 /** queries labels for an array of variables */ 148 void SCIPdecompGetVarsLabels( 149 SCIP_DECOMP* decomp, /**< decomposition data structure */ 150 SCIP_VAR** vars, /**< array of variables */ 151 int* labels, /**< buffer to store labels, one per variable */ 152 int nvars /**< length of variables array */ 153 ) 154 { 155 int i; 156 157 assert(decomp != NULL); 158 assert(vars != NULL); 159 assert(labels != NULL); 160 161 /* store variable labels in buffer array */ 162 for( i = 0; i < nvars; ++i ) 163 { 164 if( SCIPhashmapExists(decomp->var2block, (void *)vars[i]) ) 165 labels[i] = SCIPhashmapGetImageInt(decomp->var2block, (void *)vars[i]); 166 else 167 labels[i] = SCIP_DECOMP_LINKVAR; 168 } 169 } 170 171 /** sets labels for an array of constraints */ 172 SCIP_RETCODE SCIPdecompSetConsLabels( 173 SCIP_DECOMP* decomp, /**< decomposition data structure */ 174 SCIP_CONS** conss, /**< array of constraints */ 175 int* labels, /**< array of labels, one per constraint */ 176 int nconss /**< length of constraints array */ 177 ) 178 { 179 int i; 180 181 assert(decomp != NULL); 182 assert(conss != NULL); 183 assert(labels != NULL); 184 185 /* store each label in hash map */ 186 for( i = 0; i < nconss; ++i ) 187 { 188 assert(labels[i] == SCIP_DECOMP_LINKCONS || labels[i] >= 0); 189 190 SCIP_CALL( SCIPhashmapSetImageInt(decomp->cons2block, (void *)conss[i], labels[i]) ); 191 } 192 193 return SCIP_OKAY; 194 } 195 196 /** queries labels for an array of constraints */ 197 void SCIPdecompGetConsLabels( 198 SCIP_DECOMP* decomp, /**< decomposition data structure */ 199 SCIP_CONS** conss, /**< array of constraints */ 200 int* labels, /**< array of labels, one per constraint */ 201 int nconss /**< length of constraints array */ 202 ) 203 { 204 int i; 205 206 assert(decomp != NULL); 207 assert(conss != NULL); 208 assert(labels != NULL); 209 210 /* store variable labels in buffer array */ 211 for( i = 0; i < nconss; ++i ) 212 { 213 if( SCIPhashmapExists(decomp->cons2block, (void *)conss[i]) ) 214 { 215 labels[i] = SCIPhashmapGetImageInt(decomp->cons2block, (void *)conss[i]); 216 } 217 else 218 labels[i] = SCIP_DECOMP_LINKCONS; 219 } 220 } 221 222 /** clears the corresponding labeling (constraints, variables, or both) of this decomposition */ 223 SCIP_RETCODE SCIPdecompClear( 224 SCIP_DECOMP* decomp, /**< decomposition data structure */ 225 SCIP_Bool clearvarlabels, /**< should the variable labels be cleared? */ 226 SCIP_Bool clearconslabels /**< should the constraint labels be cleared? */ 227 ) 228 { 229 assert(decomp != NULL); 230 231 if( clearvarlabels ) 232 { 233 SCIP_CALL( SCIPhashmapRemoveAll(decomp->var2block) ); 234 } 235 236 if( clearconslabels ) 237 { 238 SCIP_CALL( SCIPhashmapRemoveAll(decomp->cons2block) ); 239 } 240 241 return SCIP_OKAY; 242 } 243 244 /** returns TRUE if decomposition is in the original space */ 245 SCIP_Bool SCIPdecompIsOriginal( 246 SCIP_DECOMP* decomp /**< decomposition data structure */ 247 ) 248 { 249 assert(decomp != NULL); 250 251 return decomp->original; 252 } 253 254 /** sets the parameter that indicates whether the variables must be labeled for the application of Benders' 255 * decomposition 256 */ 257 void SCIPdecompSetUseBendersLabels( 258 SCIP_DECOMP* decomp, /**< decomposition data structure */ 259 SCIP_Bool benderslabels /**< whether Benders' variable labels should be used */ 260 ) 261 { 262 assert(decomp != NULL); 263 264 decomp->benderslabels = benderslabels; 265 } 266 267 /** returns TRUE if the variables must be labeled for the application of Benders' decomposition */ 268 SCIP_Bool SCIPdecompUseBendersLabels( 269 SCIP_DECOMP* decomp /**< decomposition data structure */ 270 ) 271 { 272 assert(decomp != NULL); 273 274 return decomp->benderslabels; 275 } 276 277 /** gets number of blocks of this decomposition */ 278 int SCIPdecompGetNBlocks( 279 SCIP_DECOMP* decomp /**< decomposition data structure */ 280 ) 281 { 282 assert(decomp != NULL); 283 284 return decomp->nblocks; 285 } 286 287 /** gets area score of this decomposition */ 288 SCIP_Real SCIPdecompGetAreaScore( 289 SCIP_DECOMP* decomp /**< decomposition data structure */ 290 ) 291 { 292 assert(decomp != NULL); 293 294 return decomp->areascore; 295 } 296 297 /** gets modularity of this decomposition */ 298 SCIP_Real SCIPdecompGetModularity( 299 SCIP_DECOMP* decomp /**< decomposition data structure */ 300 ) 301 { 302 assert(decomp != NULL); 303 304 return decomp->modularity; 305 } 306 307 /** gets variable size for each block, sorted by increasing block label 308 * 309 * To get all variable sizes, set nlabels to SCIPdecompGetNBlocks() + 1. 310 * The first entry corresponds to the number of border variables. 311 * 312 * @note Ensure that SCIPcomputeDecompStats() has been called before. 313 * If the decomposition was read from a file, this was done automatically. 314 */ 315 SCIP_RETCODE SCIPdecompGetVarsSize( 316 SCIP_DECOMP* decomp, /**< decomposition data structure */ 317 int* varssize, /**< array to store variable sizes of blocks*/ 318 int nlabels /**< length of variable sizes array */ 319 ) 320 { 321 int i; 322 int nsizes; 323 324 assert(decomp != NULL); 325 assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR); 326 assert(varssize != NULL); 327 assert(nlabels >= 0); 328 329 nsizes = MIN(nlabels, decomp->nblocks + 1); 330 331 /* store variable sizes */ 332 for( i = 0; i < nsizes; ++i ) 333 { 334 varssize[i] = decomp->varssize[i]; 335 } 336 337 return SCIP_OKAY; 338 } 339 340 /** gets constraint size for each block, sorted by increasing block label 341 * 342 * To get all constraint sizes, set nlabels to SCIPdecompGetNBlocks() + 1. 343 * The first entry corresponds to the number of border constraints. 344 * 345 * @note Ensure that SCIPcomputeDecompStats() has been called before. 346 * If the decomposition was read from a file, this was done automatically. 347 */ 348 SCIP_RETCODE SCIPdecompGetConssSize( 349 SCIP_DECOMP* decomp, /**< decomposition data structure */ 350 int* consssize, /**< array to store constraint sizes of blocks*/ 351 int nlabels /**< length of constraint sizes array */ 352 ) 353 { 354 int i; 355 int nsizes; 356 357 assert(decomp != NULL); 358 assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR); 359 assert(consssize != NULL); 360 assert(nlabels >= 0); 361 362 nsizes = MIN(nlabels, decomp->nblocks + 1); 363 364 /* store constraint sizes */ 365 for( i = 0; i < nsizes; ++i ) 366 { 367 consssize[i] = decomp->consssize[i]; 368 } 369 370 return SCIP_OKAY; 371 } 372 373 /** gets number of border variables of this decomposition 374 * 375 * @note Ensure that SCIPcomputeDecompStats() has been called before. 376 * If the decomposition was read from a file, this was done automatically. 377 */ 378 int SCIPdecompGetNBorderVars( 379 SCIP_DECOMP* decomp /**< decomposition data structure */ 380 ) 381 { 382 assert(decomp != NULL); 383 assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR); 384 385 return decomp->varssize[0]; 386 } 387 388 /** gets number of border constraints of this decomposition 389 * 390 * @note Ensure that SCIPcomputeDecompStats() has been called before. 391 * If the decomposition was read from a file, this was done automatically. 392 */ 393 int SCIPdecompGetNBorderConss( 394 SCIP_DECOMP* decomp /**< decomposition data structure */ 395 ) 396 { 397 assert(decomp != NULL); 398 assert(decomp->labels[0] == SCIP_DECOMP_LINKVAR); 399 400 return decomp->consssize[0]; 401 } 402 403 /** gets number of edges in the block-decomposition graph of this decomposition */ 404 int SCIPdecompGetNBlockGraphEdges( 405 SCIP_DECOMP* decomp /**< decomposition data structure */ 406 ) 407 { 408 assert(decomp != NULL); 409 410 return decomp->nedges; 411 } 412 413 /** gets number of connected components in the block-decomposition graph of this decomposition */ 414 int SCIPdecompGetNBlockGraphComponents( 415 SCIP_DECOMP* decomp /**< decomposition data structure */ 416 ) 417 { 418 assert(decomp != NULL); 419 420 return decomp->ncomponents; 421 } 422 423 /** gets number of articulation points in the block-decomposition graph of this decomposition */ 424 int SCIPdecompGetNBlockGraphArticulations( 425 SCIP_DECOMP* decomp /**< decomposition data structure */ 426 ) 427 { 428 assert(decomp != NULL); 429 430 return decomp->narticulations; 431 } 432 433 /** gets the maximum degree of the block-decomposition graph of this decomposition */ 434 int SCIPdecompGetBlockGraphMaxDegree( 435 SCIP_DECOMP* decomp /**< decomposition data structure */ 436 ) 437 { 438 assert(decomp != NULL); 439 440 return decomp->maxdegree; 441 } 442 443 /** gets the minimum degree of the block-decomposition graph of this decomposition */ 444 int SCIPdecompGetBlockGraphMinDegree( 445 SCIP_DECOMP* decomp /**< decomposition data structure */ 446 ) 447 { 448 assert(decomp != NULL); 449 450 return decomp->mindegree; 451 } 452 453 /** prints decomposition statistics into string buffer */ 454 char* SCIPdecompPrintStats( 455 SCIP_DECOMP* decomp, /**< decomposition data structure */ 456 char* strbuf /**< string buffer storage */ 457 ) 458 { 459 char* ptr; 460 461 assert(decomp != NULL); 462 assert(strbuf != NULL); 463 464 ptr = strbuf; 465 466 ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 467 "Decomposition with %d blocks.\n", 468 decomp->nblocks); 469 ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 470 "Largest block: Block %d with %d constraints and %d variables\n", 471 decomp->nblocks == 0 ? -1 : decomp->labels[decomp->idxlargestblock], 472 decomp->nblocks == 0 ? 0 : decomp->consssize[decomp->idxlargestblock], 473 decomp->nblocks == 0 ? 0 : decomp->varssize[decomp->idxlargestblock]); 474 ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 475 "Smallest block: Block %d with %d constraints and %d variables\n", 476 decomp->nblocks == 0 ? -1 : decomp->labels[decomp->idxsmallestblock], 477 decomp->nblocks == 0 ? 0 : decomp->consssize[decomp->idxsmallestblock], 478 decomp->nblocks == 0 ? 0 : decomp->varssize[decomp->idxsmallestblock]); 479 ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 480 "Border has %d constraints and %d variables\n", 481 decomp->labels[0] == SCIP_DECOMP_LINKVAR ? decomp->consssize[0] : 0, 482 decomp->labels[0] == SCIP_DECOMP_LINKVAR ? decomp->varssize[0] : 0 483 ); 484 485 ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 486 "Modularity: %.3f, Area Score: %.3f\n", 487 decomp->modularity, decomp->areascore); 488 489 (void) SCIPsnprintf(ptr, SCIP_MAXSTRLEN, 490 "Constraint Block Graph: %d edges, %d articulation points, %d connected components, %d min., %d max. degree%s\n", 491 decomp->nedges, decomp->narticulations, decomp->ncomponents, decomp->mindegree, decomp->maxdegree, 492 decomp->statscomplete ? "" : 493 "(approximately: graph construction hit size limit)"); 494 495 return strbuf; 496 } 497 498 /** creates a decomposition storage */ 499 SCIP_RETCODE SCIPdecompstoreCreate( 500 SCIP_DECOMPSTORE** decompstore, /**< pointer to store decomposition storage */ 501 BMS_BLKMEM* blkmem, /**< block memory data structure */ 502 int nslots /**< maximum number of decomposition slots in storage */ 503 ) 504 { 505 assert(decompstore != NULL); 506 assert(blkmem != NULL); 507 assert(nslots > 0); 508 509 SCIP_ALLOC( BMSallocBlockMemory(blkmem, decompstore) ); 510 511 (*decompstore)->ndecomps = 0; 512 (*decompstore)->norigdecomps = 0; 513 (*decompstore)->decompssize = nslots; 514 515 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decompstore)->decomps, nslots) ); 516 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*decompstore)->origdecomps, nslots) ); 517 518 return SCIP_OKAY; 519 } 520 521 /** frees array of decompositions */ 522 static 523 void freeDecompositions( 524 BMS_BLKMEM* blkmem, /**< block memory data structure */ 525 SCIP_DECOMP** decomps, /**< decomposition array */ 526 int* ndecomps /**< pointer for initial number of decompositions, will be set to 0 */ 527 ) 528 { 529 int d; 530 531 assert(decomps != NULL); 532 assert(ndecomps != NULL); 533 534 /* delete all remaining decompositions from this store */ 535 for( d = 0; d < *ndecomps; ++d ) 536 SCIPdecompFree(&decomps[d], blkmem); 537 538 *ndecomps = 0; 539 } 540 541 /** frees all decompositions in transformed space */ 542 void SCIPexitSolveDecompstore( 543 SCIP* scip /**< SCIP data structure */ 544 ) 545 { 546 SCIP_DECOMPSTORE* decompstore = scip->decompstore; 547 548 assert(decompstore != NULL); 549 550 freeDecompositions(SCIPblkmem(scip), decompstore->decomps, &decompstore->ndecomps); 551 } 552 553 /** frees a decomposition storage */ 554 void SCIPdecompstoreFree( 555 SCIP_DECOMPSTORE** decompstore, /**< pointer to store decomposition storage */ 556 BMS_BLKMEM* blkmem /**< block memory data structure */ 557 ) 558 { 559 assert(decompstore != NULL); 560 561 if( *decompstore == NULL ) 562 return; 563 564 freeDecompositions(blkmem, (*decompstore)->origdecomps, &(*decompstore)->norigdecomps); 565 freeDecompositions(blkmem, (*decompstore)->decomps, &(*decompstore)->ndecomps); 566 567 BMSfreeBlockMemoryArray(blkmem, &(*decompstore)->decomps, (*decompstore)->decompssize); 568 BMSfreeBlockMemoryArray(blkmem, &(*decompstore)->origdecomps, (*decompstore)->decompssize); 569 570 BMSfreeBlockMemory(blkmem, decompstore); 571 } 572 573 /** adds decomposition to storage */ 574 SCIP_RETCODE SCIPdecompstoreAdd( 575 SCIP_DECOMPSTORE* decompstore, /**< decomposition storage */ 576 SCIP_DECOMP* decomp /**< decomposition to add */ 577 ) 578 { 579 SCIP_DECOMP** decomps; 580 int* ndecompsptr; 581 582 assert(decompstore != NULL); 583 assert(decomp != NULL); 584 585 /* distinguish between storage for original or transformed decompositions */ 586 if( SCIPdecompIsOriginal(decomp) ) 587 { 588 decomps = decompstore->origdecomps; 589 ndecompsptr = &decompstore->norigdecomps; 590 } 591 else 592 { 593 decomps = decompstore->decomps; 594 ndecompsptr = &decompstore->ndecomps; 595 } 596 597 /* ensure that storage capacity is not exceeded */ 598 if( *ndecompsptr == decompstore->decompssize ) 599 { 600 SCIPerrorMessage("Error: Decomposition storage size exceeded, maximum is %d decompositions\n", decompstore->decompssize); 601 return SCIP_ERROR; 602 } 603 604 decomps[(*ndecompsptr)++] = decomp; 605 606 return SCIP_OKAY; 607 } 608 609 /** gets decompositions from storage */ 610 SCIP_DECOMP** SCIPdecompstoreGetDecomps( 611 SCIP_DECOMPSTORE* decompstore /**< decomposition storage */ 612 ) 613 { 614 assert(decompstore != NULL); 615 616 return decompstore->decomps; 617 } 618 619 /** gets number of decompositions in storage */ 620 int SCIPdecompstoreGetNDecomps( 621 SCIP_DECOMPSTORE* decompstore /**< decomposition storage */ 622 ) 623 { 624 assert(decompstore != NULL); 625 return decompstore->ndecomps; 626 } 627 628 /** gets decompositions from storage */ 629 SCIP_DECOMP** SCIPdecompstoreGetOrigDecomps( 630 SCIP_DECOMPSTORE* decompstore /**< decomposition storage */ 631 ) 632 { 633 assert(decompstore != NULL); 634 635 return decompstore->origdecomps; 636 } 637 638 /** gets number of decompositions in storage */ 639 int SCIPdecompstoreGetNOrigDecomps( 640 SCIP_DECOMPSTORE* decompstore /**< decomposition storage */ 641 ) 642 { 643 assert(decompstore != NULL); 644 return decompstore->norigdecomps; 645 } 646 647 /** transforms all available original decompositions into transformed space */ 648 SCIP_RETCODE SCIPtransformDecompstore( 649 SCIP* scip /**< SCIP data structure */ 650 ) 651 { 652 int d; 653 int v; 654 SCIP_DECOMPSTORE* decompstore; 655 SCIP_VAR** vars; 656 SCIP_VAR** origvars; 657 SCIP_VAR** varssorted; 658 SCIP_CONS** conss; 659 int nconss; 660 int nvars; 661 int nvarsoriginal; 662 int nvarsintroduced; 663 int* varslabels; 664 SCIP_Bool original = FALSE; 665 666 assert(scip != NULL); 667 assert(scip->decompstore != NULL); 668 669 decompstore = scip->decompstore; 670 assert(decompstore->ndecomps == 0); 671 672 assert(SCIPgetStage(scip) >= SCIP_STAGE_PRESOLVED); 673 674 nvars = SCIPgetNVars(scip); 675 vars = SCIPgetVars(scip); 676 677 SCIP_CALL( SCIPallocBufferArray(scip, &varssorted, nvars) ); 678 SCIP_CALL( SCIPallocBufferArray(scip, &origvars, nvars) ); 679 SCIP_CALL( SCIPallocBufferArray(scip, &varslabels, nvars) ); 680 681 /* determine if variable has an original counterpart or not, and put it into varssorted array at the front or back */ 682 nvarsoriginal = nvarsintroduced = 0; 683 for( v = 0; v < nvars; ++v ) 684 { 685 SCIP_Real scalar; 686 SCIP_Real constant; 687 SCIP_VAR* origvar; 688 689 origvar = vars[v]; 690 scalar = 1.0; 691 constant = 0.0; 692 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) ); 693 694 /* the variable has no original counterpart and is therefore put at the end of the array */ 695 if( origvar == NULL ) 696 { 697 varssorted[nvars - 1 - nvarsintroduced] = vars[v]; 698 ++nvarsintroduced; 699 } 700 else 701 { 702 varssorted[nvarsoriginal] = vars[v]; 703 origvars[nvarsoriginal] = origvar; 704 ++nvarsoriginal; 705 } 706 707 assert(nvarsoriginal + nvarsintroduced <= nvars); 708 } 709 710 conss = SCIPgetConss(scip); 711 nconss = SCIPgetNConss(scip); 712 713 /* loop over available, original decompositions, transform and add them to the storage */ 714 for( d = 0; d < decompstore->norigdecomps; ++d ) 715 { 716 SCIP_DECOMP* origdecomp = decompstore->origdecomps[d]; 717 SCIP_DECOMP* decomp; 718 char strbuf[SCIP_MAXSTRLEN]; 719 720 /* 1. query the decomposition labels of the original variables and set them for the transformed variables 721 * that have original counterparts 722 */ 723 SCIP_CALL( SCIPcreateDecomp(scip, &decomp, SCIPdecompGetNBlocks(origdecomp), original, SCIPdecompUseBendersLabels(origdecomp)) ); 724 725 SCIPdecompGetVarsLabels(origdecomp, origvars, varslabels, nvarsoriginal); 726 727 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, varssorted, varslabels, nvarsoriginal) ); 728 729 /* 2. compute the constraint labels based on the preliminary variable labels */ 730 SCIP_CALL( SCIPcomputeDecompConsLabels(scip, decomp, conss, nconss) ); 731 732 /* 3. remove the variable labels now that we have constraint labels */ 733 SCIP_CALL( SCIPdecompClear(decomp, TRUE, FALSE) ); 734 735 /* 4. use the constraint labels for the final variable labeling */ 736 SCIP_CALL( SCIPcomputeDecompVarsLabels(scip, decomp, conss, nconss) ); 737 738 SCIP_CALL( SCIPcomputeDecompStats(scip, decomp, TRUE) ); 739 740 SCIP_CALL( SCIPdecompstoreAdd(decompstore, decomp) ); 741 742 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Transformed Decomposition statistics %d\n%s", d, SCIPdecompPrintStats(decomp, strbuf)); 743 } 744 745 SCIPfreeBufferArray(scip, &varslabels); 746 SCIPfreeBufferArray(scip, &origvars); 747 SCIPfreeBufferArray(scip, &varssorted); 748 749 return SCIP_OKAY; 750 } 751