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 implics.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for implications, variable bounds, and clique tables 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/event.h" 34 #include "scip/implics.h" 35 #include "scip/misc.h" 36 #include "scip/pub_implics.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_misc_sort.h" 40 #include "scip/pub_var.h" 41 #include "scip/set.h" 42 #include "scip/struct_implics.h" 43 #include "scip/struct_set.h" 44 #include "scip/struct_stat.h" 45 #include "scip/var.h" 46 47 48 49 /* 50 * methods for variable bounds 51 */ 52 53 /** creates a variable bounds data structure */ 54 static 55 SCIP_RETCODE vboundsCreate( 56 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */ 57 BMS_BLKMEM* blkmem /**< block memory */ 58 ) 59 { 60 assert(vbounds != NULL); 61 62 SCIP_ALLOC( BMSallocBlockMemory(blkmem, vbounds) ); 63 (*vbounds)->vars = NULL; 64 (*vbounds)->coefs = NULL; 65 (*vbounds)->constants = NULL; 66 (*vbounds)->len = 0; 67 (*vbounds)->size = 0; 68 69 return SCIP_OKAY; 70 } 71 72 /** frees a variable bounds data structure */ 73 void SCIPvboundsFree( 74 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */ 75 BMS_BLKMEM* blkmem /**< block memory */ 76 ) 77 { 78 assert(vbounds != NULL); 79 80 if( *vbounds != NULL ) 81 { 82 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->vars, (*vbounds)->size); 83 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->coefs, (*vbounds)->size); 84 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->constants, (*vbounds)->size); 85 BMSfreeBlockMemory(blkmem, vbounds); 86 } 87 } 88 89 /** ensures, that variable bounds arrays can store at least num entries */ 90 static 91 SCIP_RETCODE vboundsEnsureSize( 92 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 93 BMS_BLKMEM* blkmem, /**< block memory */ 94 SCIP_SET* set, /**< global SCIP settings */ 95 int num /**< minimum number of entries to store */ 96 ) 97 { 98 assert(vbounds != NULL); 99 100 /* create variable bounds data structure, if not yet existing */ 101 if( *vbounds == NULL ) 102 { 103 SCIP_CALL( vboundsCreate(vbounds, blkmem) ); 104 } 105 assert(*vbounds != NULL); 106 assert((*vbounds)->len <= (*vbounds)->size); 107 108 if( num > (*vbounds)->size ) 109 { 110 int newsize; 111 112 newsize = SCIPsetCalcMemGrowSize(set, num); 113 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->vars, (*vbounds)->size, newsize) ); 114 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->coefs, (*vbounds)->size, newsize) ); 115 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->constants, (*vbounds)->size, newsize) ); 116 (*vbounds)->size = newsize; 117 } 118 assert(num <= (*vbounds)->size); 119 120 return SCIP_OKAY; 121 } 122 123 /** binary searches the insertion position of the given variable in the vbounds data structure */ 124 static 125 SCIP_RETCODE vboundsSearchPos( 126 SCIP_VBOUNDS* vbounds, /**< variable bounds data structure, or NULL */ 127 SCIP_VAR* var, /**< variable to search in vbounds data structure */ 128 SCIP_Bool negativecoef, /**< is coefficient b negative? */ 129 int* insertpos, /**< pointer to store position where to insert new entry */ 130 SCIP_Bool* found /**< pointer to store whether the same variable was found at the returned pos */ 131 ) 132 { 133 SCIP_Bool exists; 134 int pos; 135 136 assert(insertpos != NULL); 137 assert(found != NULL); 138 139 /* check for empty vbounds data */ 140 if( vbounds == NULL ) 141 { 142 *insertpos = 0; 143 *found = FALSE; 144 return SCIP_OKAY; 145 } 146 assert(vbounds->len >= 0); 147 148 /* binary search for the given variable */ 149 exists = SCIPsortedvecFindPtr((void**)vbounds->vars, SCIPvarComp, var, vbounds->len, &pos); 150 151 if( exists ) 152 { 153 /* we found the variable: check if the sign of the coefficient matches */ 154 assert(var == vbounds->vars[pos]); 155 if( (vbounds->coefs[pos] < 0.0) == negativecoef ) 156 { 157 /* the variable exists with the same sign at the current position */ 158 *insertpos = pos; 159 *found = TRUE; 160 } 161 else if( negativecoef ) 162 { 163 assert(vbounds->coefs[pos] > 0.0); 164 if( pos+1 < vbounds->len && vbounds->vars[pos+1] == var ) 165 { 166 /* the variable exists with the desired sign at the next position */ 167 assert(vbounds->coefs[pos+1] < 0.0); 168 *insertpos = pos+1; 169 *found = TRUE; 170 } 171 else 172 { 173 /* the negative coefficient should be inserted to the right of the positive one */ 174 *insertpos = pos+1; 175 *found = FALSE; 176 } 177 } 178 else 179 { 180 assert(vbounds->coefs[pos] < 0.0); 181 if( pos-1 >= 0 && vbounds->vars[pos-1] == var ) 182 { 183 /* the variable exists with the desired sign at the previous position */ 184 assert(vbounds->coefs[pos-1] > 0.0); 185 *insertpos = pos-1; 186 *found = TRUE; 187 } 188 else 189 { 190 /* the positive coefficient should be inserted to the left of the negative one */ 191 *insertpos = pos; 192 *found = FALSE; 193 } 194 } 195 } 196 else 197 { 198 *insertpos = pos; 199 *found = FALSE; 200 } 201 202 return SCIP_OKAY; 203 } 204 205 /** adds a variable bound to the variable bounds data structure */ 206 SCIP_RETCODE SCIPvboundsAdd( 207 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 208 BMS_BLKMEM* blkmem, /**< block memory */ 209 SCIP_SET* set, /**< global SCIP settings */ 210 SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */ 211 SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */ 212 SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */ 213 SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */ 214 SCIP_Bool* added /**< pointer to store whether the variable bound was added */ 215 ) 216 { 217 int insertpos; 218 SCIP_Bool found; 219 220 assert(vbounds != NULL); 221 assert(var != NULL); 222 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE); 223 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS); 224 assert(added != NULL); 225 assert(!SCIPsetIsZero(set, coef)); 226 227 *added = FALSE; 228 229 /* identify insertion position of variable */ 230 SCIP_CALL( vboundsSearchPos(*vbounds, var, (coef < 0.0), &insertpos, &found) ); 231 if( found ) 232 { 233 /* the same variable already exists in the vbounds data structure: use the better vbound */ 234 assert(*vbounds != NULL); 235 assert(0 <= insertpos && insertpos < (*vbounds)->len); 236 assert((*vbounds)->vars[insertpos] == var); 237 assert(((*vbounds)->coefs[insertpos] < 0.0) == (coef < 0.0)); 238 239 if( vboundtype == SCIP_BOUNDTYPE_UPPER ) 240 { 241 if( constant + MIN(coef, 0.0) < (*vbounds)->constants[insertpos] + MIN((*vbounds)->coefs[insertpos], 0.0) ) 242 { 243 (*vbounds)->coefs[insertpos] = coef; 244 (*vbounds)->constants[insertpos] = constant; 245 *added = TRUE; 246 } 247 } 248 else 249 { 250 if( constant + MAX(coef, 0.0) > (*vbounds)->constants[insertpos] + MAX((*vbounds)->coefs[insertpos], 0.0) ) 251 { 252 (*vbounds)->coefs[insertpos] = coef; 253 (*vbounds)->constants[insertpos] = constant; 254 *added = TRUE; 255 } 256 } 257 } 258 else 259 { 260 int i; 261 262 /* the given variable does not yet exist in the vbounds */ 263 SCIP_CALL( vboundsEnsureSize(vbounds, blkmem, set, *vbounds != NULL ? (*vbounds)->len+1 : 1) ); 264 assert(*vbounds != NULL); 265 assert(0 <= insertpos && insertpos <= (*vbounds)->len); 266 assert(0 <= insertpos && insertpos < (*vbounds)->size); 267 268 /* insert variable at the correct position */ 269 for( i = (*vbounds)->len; i > insertpos; --i ) 270 { 271 assert(!SCIPsetIsZero(set, (*vbounds)->coefs[i-1])); 272 (*vbounds)->vars[i] = (*vbounds)->vars[i-1]; 273 (*vbounds)->coefs[i] = (*vbounds)->coefs[i-1]; 274 (*vbounds)->constants[i] = (*vbounds)->constants[i-1]; 275 } 276 assert(!SCIPsetIsZero(set, coef)); 277 (*vbounds)->vars[insertpos] = var; 278 (*vbounds)->coefs[insertpos] = coef; 279 (*vbounds)->constants[insertpos] = constant; 280 (*vbounds)->len++; 281 *added = TRUE; 282 } 283 284 return SCIP_OKAY; 285 } 286 287 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */ 288 SCIP_RETCODE SCIPvboundsDel( 289 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 290 BMS_BLKMEM* blkmem, /**< block memory */ 291 SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */ 292 SCIP_Bool negativecoef /**< is coefficient b negative? */ 293 ) 294 { 295 SCIP_Bool found; 296 int pos; 297 int i; 298 299 assert(vbounds != NULL); 300 assert(*vbounds != NULL); 301 302 /* searches for variable z in variable bounds of x */ 303 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) ); 304 if( !found ) 305 return SCIP_OKAY; 306 307 assert(0 <= pos && pos < (*vbounds)->len); 308 assert((*vbounds)->vars[pos] == vbdvar); 309 assert(((*vbounds)->coefs[pos] < 0.0) == negativecoef); 310 311 /* removes z from variable bounds of x */ 312 for( i = pos; i < (*vbounds)->len - 1; i++ ) 313 { 314 (*vbounds)->vars[i] = (*vbounds)->vars[i+1]; 315 (*vbounds)->coefs[i] = (*vbounds)->coefs[i+1]; 316 (*vbounds)->constants[i] = (*vbounds)->constants[i+1]; 317 } 318 (*vbounds)->len--; 319 320 #ifndef NDEBUG 321 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) ); 322 assert(!found); 323 #endif 324 325 /* free vbounds data structure, if it is empty */ 326 if( (*vbounds)->len == 0 ) 327 SCIPvboundsFree(vbounds, blkmem); 328 329 return SCIP_OKAY; /*lint !e438*/ 330 } 331 332 /** reduces the number of variable bounds stored in the given variable bounds data structure */ 333 void SCIPvboundsShrink( 334 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */ 335 BMS_BLKMEM* blkmem, /**< block memory */ 336 int newnvbds /**< new number of variable bounds */ 337 ) 338 { 339 assert(vbounds != NULL); 340 assert(*vbounds != NULL); 341 assert(newnvbds <= (*vbounds)->len); 342 343 if( newnvbds == 0 ) 344 SCIPvboundsFree(vbounds, blkmem); 345 else 346 (*vbounds)->len = newnvbds; 347 } 348 349 350 351 352 /* 353 * methods for implications 354 */ 355 356 #ifndef NDEBUG 357 /** comparator function for implication variables in the implication data structure */ 358 static 359 SCIP_DECL_SORTPTRCOMP(compVars) 360 { /*lint --e{715}*/ 361 SCIP_VAR* var1; 362 SCIP_VAR* var2; 363 int var1idx; 364 int var2idx; 365 366 var1 = (SCIP_VAR*)elem1; 367 var2 = (SCIP_VAR*)elem2; 368 assert(var1 != NULL); 369 assert(var2 != NULL); 370 var1idx = SCIPvarGetIndex(var1); 371 var2idx = SCIPvarGetIndex(var2); 372 373 if( var1idx < var2idx ) 374 return -1; 375 else if( var1idx > var2idx ) 376 return +1; 377 else 378 return 0; 379 } 380 381 /** performs integrity check on implications data structure */ 382 static 383 void checkImplics( 384 SCIP_IMPLICS* implics /**< implications data structure */ 385 ) 386 { 387 SCIP_Bool varfixing; 388 389 if( implics == NULL ) 390 return; 391 392 varfixing = FALSE; 393 do 394 { 395 SCIP_VAR** vars; 396 SCIP_BOUNDTYPE* types; 397 int nimpls; 398 int i; 399 400 vars = implics->vars[varfixing]; 401 types = implics->types[varfixing]; 402 nimpls = implics->nimpls[varfixing]; 403 404 assert(0 <= nimpls && nimpls <= implics->size[varfixing]); 405 for( i = 1; i < nimpls; ++i ) 406 { 407 int cmp; 408 409 cmp = compVars(vars[i-1], vars[i]); 410 assert(cmp <= 0); 411 assert((cmp == 0) == (vars[i-1] == vars[i])); 412 assert(cmp < 0 || (types[i-1] == SCIP_BOUNDTYPE_LOWER && types[i] == SCIP_BOUNDTYPE_UPPER)); 413 } 414 415 varfixing = !varfixing; 416 } 417 while( varfixing == TRUE ); 418 } 419 #else 420 #define checkImplics(implics) /**/ 421 #endif 422 423 /** creates an implications data structure */ 424 static 425 SCIP_RETCODE implicsCreate( 426 SCIP_IMPLICS** implics, /**< pointer to store implications data structure */ 427 BMS_BLKMEM* blkmem /**< block memory */ 428 ) 429 { 430 assert(implics != NULL); 431 432 SCIP_ALLOC( BMSallocBlockMemory(blkmem, implics) ); 433 434 (*implics)->vars[0] = NULL; 435 (*implics)->types[0] = NULL; 436 (*implics)->bounds[0] = NULL; 437 (*implics)->ids[0] = NULL; 438 (*implics)->size[0] = 0; 439 (*implics)->nimpls[0] = 0; 440 (*implics)->vars[1] = NULL; 441 (*implics)->types[1] = NULL; 442 (*implics)->bounds[1] = NULL; 443 (*implics)->ids[1] = NULL; 444 (*implics)->size[1] = 0; 445 (*implics)->nimpls[1] = 0; 446 447 return SCIP_OKAY; 448 } 449 450 /** frees an implications data structure */ 451 void SCIPimplicsFree( 452 SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */ 453 BMS_BLKMEM* blkmem /**< block memory */ 454 ) 455 { 456 assert(implics != NULL); 457 458 if( *implics != NULL ) 459 { 460 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[0], (*implics)->size[0]); 461 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[0], (*implics)->size[0]); 462 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[0], (*implics)->size[0]); 463 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[0], (*implics)->size[0]); 464 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[1], (*implics)->size[1]); 465 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[1], (*implics)->size[1]); 466 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[1], (*implics)->size[1]); 467 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[1], (*implics)->size[1]); 468 BMSfreeBlockMemory(blkmem, implics); 469 } 470 } 471 472 /** ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries */ 473 static 474 SCIP_RETCODE implicsEnsureSize( 475 SCIP_IMPLICS** implics, /**< pointer to implications data structure */ 476 BMS_BLKMEM* blkmem, /**< block memory */ 477 SCIP_SET* set, /**< global SCIP settings */ 478 SCIP_Bool varfixing, /**< FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1 */ 479 int num /**< minimum number of entries to store */ 480 ) 481 { 482 assert(implics != NULL); 483 484 /* create implications data structure, if not yet existing */ 485 if( *implics == NULL ) 486 { 487 SCIP_CALL( implicsCreate(implics, blkmem) ); 488 } 489 assert(*implics != NULL); 490 assert((*implics)->nimpls[varfixing] <= (*implics)->size[varfixing]); 491 492 if( num > (*implics)->size[varfixing] ) 493 { 494 int newsize; 495 496 newsize = SCIPsetCalcMemGrowSize(set, num); 497 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->vars[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/ 498 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->types[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/ 499 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->bounds[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/ 500 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->ids[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/ 501 (*implics)->size[varfixing] = newsize; 502 } 503 assert(num <= (*implics)->size[varfixing]); 504 505 return SCIP_OKAY; 506 } 507 508 /** gets the positions of the implications y >= l and y <= u in the implications data structure; 509 * if no lower or upper bound implication for y was found, -1 is returned 510 */ 511 static 512 void implicsSearchVar( 513 SCIP_IMPLICS* implics, /**< implications data structure */ 514 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */ 515 SCIP_VAR* implvar, /**< variable y to search for */ 516 int* poslower, /**< pointer to store position of y_lower (-1 if not found) */ 517 int* posupper, /**< pointer to store position of y_upper (-1 if not found) */ 518 int* posadd /**< pointer to store position of first y entry, or where a new y entry 519 * should be placed */ 520 ) 521 { 522 SCIP_Bool found; 523 int right; 524 int pos; 525 526 assert(implics != NULL); 527 assert(poslower != NULL); 528 assert(posupper != NULL); 529 assert(posadd != NULL); 530 531 if( implics->nimpls[varfixing] == 0 ) 532 { 533 /* there are no implications with non-binary variable y */ 534 *posadd = 0; 535 *poslower = -1; 536 *posupper = -1; 537 return; 538 } 539 right = implics->nimpls[varfixing] - 1; 540 assert(0 <= right); 541 542 /* search for the position in the sorted array (via binary search) */ 543 found = SCIPsortedvecFindPtr((void**)(&(implics->vars[varfixing][0])), SCIPvarComp, (void*)implvar, right + 1, &pos); 544 545 if( !found ) 546 { 547 /* y was not found */ 548 assert(pos >= right || compVars((void*)implics->vars[varfixing][pos], (void*)implvar) > 0); 549 assert(pos == 0 || compVars((void*)implics->vars[varfixing][pos-1], (void*)implvar) < 0); 550 *poslower = -1; 551 *posupper = -1; 552 *posadd = pos; 553 } 554 else 555 { 556 /* y was found */ 557 assert(implvar == implics->vars[varfixing][pos]); 558 559 /* set poslower and posupper */ 560 if( implics->types[varfixing][pos] == SCIP_BOUNDTYPE_LOWER ) 561 { 562 /* y was found as y_lower (on position middle) */ 563 *poslower = pos; 564 if( pos + 1 < implics->nimpls[varfixing] && implics->vars[varfixing][pos+1] == implvar ) 565 { 566 assert(implics->types[varfixing][pos+1] == SCIP_BOUNDTYPE_UPPER); 567 *posupper = pos + 1; 568 } 569 else 570 *posupper = -1; 571 *posadd = pos; 572 } 573 else 574 { 575 /* y was found as y_upper (on position pos) */ 576 *posupper = pos; 577 if( pos - 1 >= 0 && implics->vars[varfixing][pos-1] == implvar ) 578 { 579 assert(implics->types[varfixing][pos-1] == SCIP_BOUNDTYPE_LOWER); 580 *poslower = pos - 1; 581 *posadd = pos - 1; 582 } 583 else 584 { 585 *poslower = -1; 586 *posadd = pos; 587 } 588 } 589 } 590 } 591 592 /** returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype 593 * y can be contained in structure with y >= b (y_lower) and y <= b (y_upper) 594 */ 595 static 596 SCIP_Bool implicsSearchImplic( 597 SCIP_IMPLICS* implics, /**< implications data structure */ 598 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */ 599 SCIP_VAR* implvar, /**< variable y to search for */ 600 SCIP_BOUNDTYPE impltype, /**< type of implication y <=/>= b to search for */ 601 int* poslower, /**< pointer to store position of y_lower (inf if not found) */ 602 int* posupper, /**< pointer to store position of y_upper (inf if not found) */ 603 int* posadd /**< pointer to store correct position (with respect to impltype) to add y */ 604 ) 605 { 606 assert(implics != NULL); 607 assert(poslower != NULL); 608 assert(posupper != NULL); 609 assert(posadd != NULL); 610 611 implicsSearchVar(implics, varfixing, implvar, poslower, posupper, posadd); 612 assert(*poslower == -1 || *posupper == -1 || *posupper == (*poslower)+1); 613 assert(*poslower == -1 || *posadd == *poslower); 614 assert(*poslower >= 0 || *posupper == -1 || *posadd == *posupper); 615 assert(0 <= *posadd && *posadd <= implics->nimpls[varfixing]); 616 617 if( impltype == SCIP_BOUNDTYPE_LOWER ) 618 return (*poslower >= 0); 619 else 620 { 621 if( *poslower >= 0 ) 622 { 623 assert(*posadd == *poslower); 624 (*posadd)++; 625 } 626 return (*posupper >= 0); 627 } 628 } 629 630 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure; 631 * the implication must be non-redundant 632 */ 633 SCIP_RETCODE SCIPimplicsAdd( 634 SCIP_IMPLICS** implics, /**< pointer to implications data structure */ 635 BMS_BLKMEM* blkmem, /**< block memory */ 636 SCIP_SET* set, /**< global SCIP settings */ 637 SCIP_STAT* stat, /**< problem statistics */ 638 SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */ 639 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */ 640 SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */ 641 SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */ 642 SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */ 643 SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */ 644 SCIP_Bool* added /**< pointer to store whether the implication was added */ 645 ) 646 { 647 int poslower; 648 int posupper; 649 int posadd; 650 SCIP_Bool found; 651 #ifndef NDEBUG 652 int k; 653 #endif 654 655 assert(implics != NULL); 656 assert(*implics == NULL || 0 <= (*implics)->nimpls[varfixing]); 657 assert(stat != NULL); 658 assert(SCIPvarIsActive(implvar)); 659 assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE); 660 assert((impltype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, implbound, SCIPvarGetLbGlobal(implvar))) 661 || (impltype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, implbound, SCIPvarGetUbGlobal(implvar)))); 662 assert(conflict != NULL); 663 assert(added != NULL); 664 665 SCIPsetDebugMsg(set, "adding implication to implics %p [%u]: <%s> %s %g\n", 666 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbound); 667 668 checkImplics(*implics); 669 670 *conflict = FALSE; 671 *added = FALSE; 672 673 /* check if variable is already contained in implications data structure */ 674 if( *implics != NULL ) 675 { 676 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); 677 assert(-1 <= poslower && poslower < (*implics)->nimpls[varfixing]); 678 assert(-1 <= posupper && posupper < (*implics)->nimpls[varfixing]); 679 assert(0 <= posadd && posadd <= (*implics)->nimpls[varfixing]); 680 assert(poslower == -1 || (*implics)->types[varfixing][poslower] == SCIP_BOUNDTYPE_LOWER); 681 assert(posupper == -1 || (*implics)->types[varfixing][posupper] == SCIP_BOUNDTYPE_UPPER); 682 } 683 else 684 { 685 found = FALSE; 686 poslower = -1; 687 posupper = -1; 688 posadd = 0; 689 } 690 691 if( impltype == SCIP_BOUNDTYPE_LOWER ) 692 { 693 assert(found == (poslower >= 0)); 694 695 /* check if y >= b is redundant */ 696 if( poslower >= 0 && SCIPsetIsFeasLE(set, implbound, (*implics)->bounds[varfixing][poslower]) ) 697 { 698 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]); 699 return SCIP_OKAY; 700 } 701 702 /* check if y >= b causes conflict for x (i.e. y <= a (with a < b) is also valid) */ 703 if( posupper >= 0 && SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][posupper]) ) 704 { 705 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]); 706 *conflict = TRUE; 707 return SCIP_OKAY; 708 } 709 710 *added = TRUE; 711 712 /* check if entry of the same type already exists */ 713 if( found ) 714 { 715 assert(poslower >= 0); 716 assert(posadd == poslower); 717 718 /* add y >= b by changing old entry on poslower */ 719 assert((*implics)->vars[varfixing][poslower] == implvar); 720 assert(SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][poslower])); 721 (*implics)->bounds[varfixing][poslower] = implbound; 722 } 723 else 724 { 725 assert(poslower == -1); 726 727 /* add y >= b by creating a new entry on posadd */ 728 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing, 729 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) ); 730 assert(*implics != NULL); 731 732 if( (*implics)->nimpls[varfixing] - posadd > 0 ) 733 { 734 int amount = ((*implics)->nimpls[varfixing] - posadd); 735 736 #ifndef NDEBUG 737 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- ) 738 { 739 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0); 740 } 741 #endif 742 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/ 743 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/ 744 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/ 745 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/ 746 } 747 748 (*implics)->vars[varfixing][posadd] = implvar; 749 (*implics)->types[varfixing][posadd] = impltype; 750 (*implics)->bounds[varfixing][posadd] = implbound; 751 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications); 752 (*implics)->nimpls[varfixing]++; 753 #ifndef NDEBUG 754 for( k = posadd-1; k >= 0; k-- ) 755 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0); 756 #endif 757 stat->nimplications++; 758 } 759 } 760 else 761 { 762 assert(found == (posupper >= 0)); 763 764 /* check if y <= b is redundant */ 765 if( posupper >= 0 && SCIPsetIsFeasGE(set, implbound, (*implics)->bounds[varfixing][posupper]) ) 766 { 767 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]); 768 return SCIP_OKAY; 769 } 770 771 /* check if y <= b causes conflict for x (i.e. y >= a (with a > b) is also valid) */ 772 if( poslower >= 0 && SCIPsetIsFeasLT(set, implbound, (*implics)->bounds[varfixing][poslower]) ) 773 { 774 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]); 775 *conflict = TRUE; 776 return SCIP_OKAY; 777 } 778 779 *added = TRUE; 780 781 /* check if entry of the same type already exists */ 782 if( found ) 783 { 784 assert(posupper >= 0); 785 assert(posadd == posupper); 786 787 /* add y <= b by changing old entry on posupper */ 788 assert((*implics)->vars[varfixing][posupper] == implvar); 789 assert(SCIPsetIsFeasLT(set, implbound,(*implics)->bounds[varfixing][posupper])); 790 (*implics)->bounds[varfixing][posupper] = implbound; 791 } 792 else 793 { 794 /* add y <= b by creating a new entry on posadd */ 795 assert(posupper == -1); 796 797 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing, 798 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) ); 799 assert(*implics != NULL); 800 801 if( (*implics)->nimpls[varfixing] - posadd > 0 ) 802 { 803 int amount = ((*implics)->nimpls[varfixing] - posadd); 804 805 #ifndef NDEBUG 806 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- ) 807 { 808 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0); 809 } 810 #endif 811 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/ 812 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/ 813 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/ 814 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/ 815 } 816 817 (*implics)->vars[varfixing][posadd] = implvar; 818 (*implics)->types[varfixing][posadd] = impltype; 819 (*implics)->bounds[varfixing][posadd] = implbound; 820 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications); 821 (*implics)->nimpls[varfixing]++; 822 #ifndef NDEBUG 823 for( k = posadd-1; k >= 0; k-- ) 824 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0); 825 #endif 826 stat->nimplications++; 827 } 828 } 829 830 checkImplics(*implics); 831 832 return SCIP_OKAY; 833 } 834 835 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */ 836 SCIP_RETCODE SCIPimplicsDel( 837 SCIP_IMPLICS** implics, /**< pointer to implications data structure */ 838 BMS_BLKMEM* blkmem, /**< block memory */ 839 SCIP_SET* set, /**< global SCIP settings */ 840 SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */ 841 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */ 842 SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */ 843 ) 844 { /*lint --e{715}*/ 845 int poslower; 846 int posupper; 847 int posadd; 848 SCIP_Bool found; 849 850 assert(implics != NULL); 851 assert(*implics != NULL); 852 assert(implvar != NULL); 853 854 SCIPsetDebugMsg(set, "deleting implication from implics %p [%u]: <%s> %s x\n", 855 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<="); 856 857 checkImplics(*implics); 858 859 /* searches for y in implications of x */ 860 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); 861 if( !found ) 862 { 863 SCIPsetDebugMsg(set, " -> implication was not found\n"); 864 return SCIP_OKAY; 865 } 866 867 assert((impltype == SCIP_BOUNDTYPE_LOWER && poslower >= 0 && posadd == poslower) 868 || (impltype == SCIP_BOUNDTYPE_UPPER && posupper >= 0 && posadd == posupper)); 869 assert(0 <= posadd && posadd < (*implics)->nimpls[varfixing]); 870 assert((*implics)->vars[varfixing][posadd] == implvar); 871 assert((*implics)->types[varfixing][posadd] == impltype); 872 873 /* removes y from implications of x */ 874 if( (*implics)->nimpls[varfixing] - posadd > 1 ) 875 { 876 int amount = ((*implics)->nimpls[varfixing] - posadd - 1); 877 878 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd]), &((*implics)->types[varfixing][posadd+1]), amount); /*lint !e866*/ 879 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd]), &((*implics)->vars[varfixing][posadd+1]), amount); /*lint !e866*/ 880 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd]), &((*implics)->bounds[varfixing][posadd+1]), amount); /*lint !e866*/ 881 } 882 (*implics)->nimpls[varfixing]--; 883 884 /* free implics data structure, if it is empty */ 885 if( (*implics)->nimpls[0] == 0 && (*implics)->nimpls[1] == 0 ) 886 SCIPimplicsFree(implics, blkmem); 887 888 checkImplics(*implics); 889 890 return SCIP_OKAY; 891 } 892 893 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */ 894 void SCIPimplicsGetVarImplics( 895 SCIP_IMPLICS* implics, /**< implications data structure */ 896 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 897 SCIP_VAR* implvar, /**< variable y to search for */ 898 SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */ 899 SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */ 900 ) 901 { 902 int poslower; 903 int posupper; 904 int posadd; 905 906 assert(haslowerimplic != NULL); 907 assert(hasupperimplic != NULL); 908 909 implicsSearchVar(implics, varfixing, implvar, &poslower, &posupper, &posadd); 910 911 *haslowerimplic = (poslower >= 0); 912 *hasupperimplic = (posupper >= 0); 913 } /*lint !e438*/ 914 915 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */ 916 void SCIPimplicsGetVarImplicPoss( 917 SCIP_IMPLICS* implics, /**< implications data structure */ 918 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 919 SCIP_VAR* implvar, /**< variable y to search for */ 920 int* lowerimplicpos, /**< pointer to store the position of an implication y >= l */ 921 int* upperimplicpos /**< pointer to store the position of an implication y <= u */ 922 ) 923 { 924 int posadd; 925 926 assert(lowerimplicpos != NULL); 927 assert(upperimplicpos != NULL); 928 929 implicsSearchVar(implics, varfixing, implvar, lowerimplicpos, upperimplicpos, &posadd); 930 } 931 932 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */ 933 SCIP_Bool SCIPimplicsContainsImpl( 934 SCIP_IMPLICS* implics, /**< implications data structure */ 935 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */ 936 SCIP_VAR* implvar, /**< variable y to search for */ 937 SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */ 938 ) 939 { 940 int poslower; 941 int posupper; 942 int posadd; 943 944 return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); /*lint !e438*/ 945 } /*lint !e638*/ 946 947 948 949 950 /* 951 * methods for cliques 952 */ 953 954 /* swaps cliques at positions first and second in cliques array of clique table */ 955 static 956 void cliquetableSwapCliques( 957 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 958 int first, /**< first index */ 959 int second /**< second index */ 960 ) 961 { 962 /* nothing to do if clique happens to be at the pole position of clean cliques */ 963 if( first != second ) 964 { 965 SCIP_CLIQUE* tmp; 966 967 tmp = cliquetable->cliques[first]; 968 assert(tmp->index == first); 969 assert(cliquetable->cliques[second]->index == second); 970 971 cliquetable->cliques[first] = cliquetable->cliques[second]; 972 cliquetable->cliques[second] = tmp; 973 974 /* change the indices accordingly */ 975 tmp->index = second; 976 cliquetable->cliques[first]->index = first; 977 } 978 } 979 980 /* moves clique to the last position of currently dirty cliques */ 981 static 982 void cliquetableMarkCliqueForCleanup( 983 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 984 SCIP_CLIQUE* clique /**< clique data structure */ 985 ) 986 { 987 assert(cliquetable->ndirtycliques <= clique->index); 988 assert(cliquetable->cliques[clique->index] == clique); 989 assert(cliquetable->ndirtycliques < cliquetable->ncliques); 990 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ndirtycliques])); 991 992 /* nothing to do if clique happens to be at the pole position of clean cliques */ 993 if( clique->index > cliquetable->ndirtycliques ) 994 { 995 cliquetableSwapCliques(cliquetable, clique->index, cliquetable->ndirtycliques); 996 } 997 998 ++cliquetable->ndirtycliques; 999 } 1000 1001 1002 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */ 1003 static 1004 SCIP_RETCODE cliqueCreateWithData( 1005 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */ 1006 BMS_BLKMEM* blkmem, /**< block memory */ 1007 int size, /**< initial size of clique */ 1008 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given 1009 * value */ 1010 SCIP_Bool* values, /**< values of the variables in the clique */ 1011 int nvars, /**< number of variables in the clique */ 1012 int id, /**< unique identifier of the clique */ 1013 SCIP_Bool isequation /**< is the clique an equation or an inequality? */ 1014 ) 1015 { 1016 assert(clique != NULL); 1017 assert(blkmem != NULL); 1018 assert(size >= nvars && nvars > 0); 1019 assert(vars != NULL); 1020 assert(values != NULL); 1021 1022 SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) ); 1023 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->vars, vars, size) ); 1024 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->values, values, size) ); 1025 (*clique)->nvars = nvars; 1026 (*clique)->size = size; 1027 (*clique)->startcleanup = -1; 1028 (*clique)->id = (unsigned int)id; 1029 (*clique)->eventsissued = FALSE; 1030 (*clique)->equation = isequation; 1031 (*clique)->index = -1; 1032 1033 return SCIP_OKAY; 1034 } 1035 1036 /** frees a clique data structure */ 1037 static 1038 void cliqueFree( 1039 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */ 1040 BMS_BLKMEM* blkmem /**< block memory */ 1041 ) 1042 { 1043 assert(clique != NULL); 1044 1045 if( *clique != NULL ) 1046 { 1047 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->vars, (*clique)->size); 1048 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->values, (*clique)->size); 1049 BMSfreeBlockMemory(blkmem, clique); 1050 } 1051 } 1052 1053 /** ensures, that clique arrays can store at least num entries */ 1054 static 1055 SCIP_RETCODE cliqueEnsureSize( 1056 SCIP_CLIQUE* clique, /**< clique data structure */ 1057 BMS_BLKMEM* blkmem, /**< block memory */ 1058 SCIP_SET* set, /**< global SCIP settings */ 1059 int num /**< minimum number of entries to store */ 1060 ) 1061 { 1062 assert(clique != NULL); 1063 1064 if( num > clique->size ) 1065 { 1066 int newsize; 1067 1068 newsize = SCIPsetCalcMemGrowSize(set, num); 1069 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->vars, clique->size, newsize) ); 1070 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->values, clique->size, newsize) ); 1071 clique->size = newsize; 1072 } 1073 assert(num <= clique->size); 1074 1075 return SCIP_OKAY; 1076 } 1077 1078 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member 1079 * of the clique 1080 */ 1081 int SCIPcliqueSearchVar( 1082 SCIP_CLIQUE* clique, /**< clique data structure */ 1083 SCIP_VAR* var, /**< variable to search for */ 1084 SCIP_Bool value /**< value of the variable in the clique */ 1085 ) 1086 { 1087 int varidx; 1088 int left; 1089 int right; 1090 1091 assert(clique != NULL); 1092 1093 varidx = SCIPvarGetIndex(var); 1094 left = -1; 1095 right = clique->nvars; 1096 while( left < right-1 ) 1097 { 1098 int middle; 1099 int idx; 1100 1101 middle = (left+right)/2; 1102 idx = SCIPvarGetIndex(clique->vars[middle]); 1103 assert(idx >= 0); 1104 if( varidx < idx ) 1105 right = middle; 1106 else if( varidx > idx ) 1107 left = middle; 1108 else 1109 { 1110 assert(var == clique->vars[middle]); 1111 1112 /* now watch out for the correct value */ 1113 if( clique->values[middle] < value ) 1114 { 1115 int i; 1116 for( i = middle+1; i < clique->nvars && clique->vars[i] == var; ++i ) 1117 { 1118 if( clique->values[i] == value ) 1119 return i; 1120 } 1121 return -1; 1122 } 1123 if( clique->values[middle] > value ) 1124 { 1125 int i; 1126 for( i = middle-1; i >= 0 && clique->vars[i] == var; --i ) 1127 { 1128 if( clique->values[i] == value ) 1129 return i; 1130 } 1131 return -1; 1132 } 1133 return middle; 1134 } 1135 } 1136 1137 return -1; 1138 } 1139 1140 /** returns whether the given variable/value pair is member of the given clique */ 1141 SCIP_Bool SCIPcliqueHasVar( 1142 SCIP_CLIQUE* clique, /**< clique data structure */ 1143 SCIP_VAR* var, /**< variable to remove from the clique */ 1144 SCIP_Bool value /**< value of the variable in the clique */ 1145 ) 1146 { 1147 return (SCIPcliqueSearchVar(clique, var, value) >= 0); 1148 } 1149 1150 /** adds a single variable to the given clique */ 1151 SCIP_RETCODE SCIPcliqueAddVar( 1152 SCIP_CLIQUE* clique, /**< clique data structure */ 1153 BMS_BLKMEM* blkmem, /**< block memory */ 1154 SCIP_SET* set, /**< global SCIP settings */ 1155 SCIP_VAR* var, /**< variable to add to the clique */ 1156 SCIP_Bool value, /**< value of the variable in the clique */ 1157 SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */ 1158 SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */ 1159 ) 1160 { 1161 int pos; 1162 int i; 1163 1164 assert(clique != NULL); 1165 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 1166 assert(SCIPvarIsBinary(var)); 1167 assert(doubleentry != NULL); 1168 assert(oppositeentry != NULL); 1169 1170 SCIPsetDebugMsg(set, "adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id); 1171 1172 *doubleentry = FALSE; 1173 *oppositeentry = FALSE; 1174 1175 /* allocate memory */ 1176 SCIP_CALL( cliqueEnsureSize(clique, blkmem, set, clique->nvars+1) ); 1177 1178 /* search for insertion position by binary variable, note that first the entries are order after variable index and 1179 * second after the bool value of the corresponding variable 1180 */ 1181 (void) SCIPsortedvecFindPtr((void**) clique->vars, SCIPvarComp, var, clique->nvars, &pos); 1182 1183 assert(pos >= 0 && pos <= clique->nvars); 1184 /* remember insertion position for later, pos might change */ 1185 i = pos; 1186 1187 if( pos < clique->nvars ) 1188 { 1189 const int amount = clique->nvars - pos; 1190 1191 /* moving elements to correct position */ 1192 BMSmoveMemoryArray(&(clique->vars[pos+1]), &(clique->vars[pos]), amount); /*lint !e866*/ 1193 BMSmoveMemoryArray(&(clique->values[pos+1]), &(clique->values[pos]), amount); /*lint !e866*/ 1194 clique->nvars++; 1195 1196 /* insertion for a variable with cliquevalue FALSE */ 1197 if( !value ) 1198 { 1199 /* find last entry with the same variable and value behind the insertion position */ 1200 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/ 1201 1202 /* check if the same variable with other value also exists */ 1203 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var ) 1204 { 1205 assert(clique->values[pos + 1] != value); 1206 *oppositeentry = TRUE; 1207 } 1208 1209 /* check if we found the same variable with the same value more than once */ 1210 if( pos != i ) 1211 *doubleentry = TRUE; 1212 else 1213 { 1214 /* find last entry with the same variable and different value before the insertion position */ 1215 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/ 1216 1217 /* check if we found the same variable with the same value more than once */ 1218 if( pos > 0 && clique->vars[pos - 1] == var ) 1219 { 1220 assert(clique->values[pos - 1] == value); 1221 1222 *doubleentry = TRUE; 1223 } 1224 /* if we found the same variable with different value, we need to order them correctly */ 1225 if( pos != i ) 1226 { 1227 assert(clique->vars[pos] == var); 1228 assert(clique->values[pos] != value); 1229 1230 clique->values[pos] = value; 1231 value = !value; 1232 } 1233 } 1234 } 1235 /* insertion for a variable with cliquevalue TRUE */ 1236 else 1237 { 1238 /* find last entry with the same variable and different value behind the insertion position */ 1239 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/ 1240 1241 /* check if the same variable with other value also exists */ 1242 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var ) 1243 { 1244 assert(clique->values[pos + 1] == value); 1245 *doubleentry = TRUE; 1246 } 1247 1248 /* check if we found the same variable with different value */ 1249 if( pos != i ) 1250 { 1251 *oppositeentry = TRUE; 1252 1253 /* if we found the same variable with different value, we need to order them correctly */ 1254 assert(clique->vars[pos] == var); 1255 assert(clique->values[pos] != value); 1256 1257 clique->values[pos] = value; 1258 value = !value; 1259 } 1260 else 1261 { 1262 /* find last entry with the same variable and value before the insertion position */ 1263 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/ 1264 1265 if( pos != i ) 1266 *doubleentry = TRUE; 1267 1268 /* check if we found the same variable with different value up front */ 1269 if( pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value ) 1270 *oppositeentry = TRUE; 1271 } 1272 } 1273 } 1274 else 1275 clique->nvars++; 1276 1277 clique->vars[i] = var; 1278 clique->values[i] = value; 1279 clique->eventsissued = FALSE; 1280 1281 return SCIP_OKAY; 1282 } 1283 1284 /** removes a single variable from the given clique */ 1285 void SCIPcliqueDelVar( 1286 SCIP_CLIQUE* clique, /**< clique data structure */ 1287 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1288 SCIP_VAR* var, /**< variable to remove from the clique */ 1289 SCIP_Bool value /**< value of the variable in the clique */ 1290 ) 1291 { 1292 int pos; 1293 1294 assert(clique != NULL); 1295 assert(SCIPvarIsBinary(var)); 1296 assert(cliquetable != NULL); 1297 1298 /* if the clique is the leading clique during the cleanup step, we do not need to insert it again */ 1299 if( cliquetable->incleanup && clique->index == 0 ) 1300 return; 1301 1302 SCIPdebugMessage("marking variable <%s> == %u from clique %u for deletion\n", SCIPvarGetName(var), value, clique->id); 1303 1304 /* find variable in clique */ 1305 pos = SCIPcliqueSearchVar(clique, var, value); 1306 1307 assert(0 <= pos && pos < clique->nvars); 1308 assert(clique->vars[pos] == var); 1309 assert(clique->values[pos] == value); 1310 1311 /* inform the clique table that this clique should be cleaned up */ 1312 if( clique->startcleanup == -1 ) 1313 cliquetableMarkCliqueForCleanup(cliquetable, clique); 1314 1315 if( clique->startcleanup == -1 || pos < clique->startcleanup ) 1316 clique->startcleanup = pos; 1317 1318 #ifdef SCIP_MORE_DEBUG 1319 { 1320 int v; 1321 /* all variables prior to the one marked for startcleanup should be unfixed */ 1322 for( v = clique->startcleanup - 1; v >= 0; --v ) 1323 { 1324 assert(SCIPvarGetUbGlobal(clique->vars[v]) > 0.5); 1325 assert(SCIPvarGetLbGlobal(clique->vars[v]) < 0.5); 1326 } 1327 } 1328 #endif 1329 } 1330 1331 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */ 1332 static 1333 int cliquesSearchClique( 1334 SCIP_CLIQUE** cliques, /**< array of cliques */ 1335 int ncliques, /**< number of cliques in the cliques array */ 1336 SCIP_CLIQUE* clique /**< clique to search for */ 1337 ) 1338 { 1339 unsigned int cliqueid; 1340 int left; 1341 int right; 1342 1343 assert(cliques != NULL || ncliques == 0); 1344 assert(clique != NULL); 1345 1346 cliqueid = clique->id; /*lint !e732*/ 1347 left = -1; 1348 right = ncliques; 1349 while( left < right-1 ) 1350 { 1351 unsigned int id; 1352 int middle; 1353 1354 assert(cliques != NULL); 1355 middle = (left+right)/2; 1356 id = cliques[middle]->id; /*lint !e732*/ 1357 if( cliqueid < id ) 1358 right = middle; 1359 else if( cliqueid > id ) 1360 left = middle; 1361 else 1362 { 1363 assert(clique == cliques[middle]); 1364 return middle; 1365 } 1366 } 1367 1368 return -1; 1369 } 1370 1371 #ifdef SCIP_MORE_DEBUG 1372 /** checks whether clique appears in all clique lists of the involved variables */ 1373 static 1374 void cliqueCheck( 1375 SCIP_CLIQUE* clique /**< clique data structure */ 1376 ) 1377 { 1378 int i; 1379 1380 assert(clique != NULL); 1381 1382 for( i = 0; i < clique->nvars; ++i ) 1383 { 1384 SCIP_CLIQUE** cliques; 1385 int ncliques; 1386 int pos; 1387 SCIP_VAR* var; 1388 1389 var = clique->vars[i]; 1390 assert(i == 0 || SCIPvarGetIndex(clique->vars[i-1]) <= SCIPvarGetIndex(var)); 1391 assert(i == 0 || clique->vars[i-1] != var || clique->values[i-1] <= clique->values[i]); 1392 ncliques = SCIPvarGetNCliques(var, clique->values[i]); 1393 1394 assert(SCIPvarIsActive(var) || ncliques == 0); 1395 1396 /* cliquelist of inactive variables are already destroyed */ 1397 if( ncliques == 0 ) 1398 continue; 1399 1400 cliques = SCIPvarGetCliques(var, clique->values[i]); 1401 pos = cliquesSearchClique(cliques, ncliques, clique); 1402 1403 /* assert that the clique is correctly listed in all clique lists of unfixed variables. For fixed variables, 1404 * we require that a clean up has been correctly scheduled, but not yet been processed 1405 */ 1406 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) > 0.5 ) 1407 { 1408 assert(0 <= pos && pos < ncliques); 1409 assert(cliques[pos] == clique); 1410 } 1411 else 1412 assert(0 <= clique->startcleanup && clique->startcleanup <= i); 1413 } 1414 assert(clique->index >= 0); 1415 } 1416 #else 1417 #define cliqueCheck(clique) /**/ 1418 #endif 1419 1420 /** creates a clique list data structure */ 1421 static 1422 SCIP_RETCODE cliquelistCreate( 1423 SCIP_CLIQUELIST** cliquelist, /**< pointer to store clique list data structure */ 1424 BMS_BLKMEM* blkmem /**< block memory */ 1425 ) 1426 { 1427 assert(cliquelist != NULL); 1428 1429 SCIP_ALLOC( BMSallocBlockMemory(blkmem, cliquelist) ); 1430 (*cliquelist)->cliques[0] = NULL; 1431 (*cliquelist)->cliques[1] = NULL; 1432 (*cliquelist)->ncliques[0] = 0; 1433 (*cliquelist)->ncliques[1] = 0; 1434 (*cliquelist)->size[0] = 0; 1435 (*cliquelist)->size[1] = 0; 1436 1437 return SCIP_OKAY; 1438 } 1439 1440 /** frees a clique list data structure */ 1441 void SCIPcliquelistFree( 1442 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 1443 BMS_BLKMEM* blkmem /**< block memory */ 1444 ) 1445 { 1446 assert(cliquelist != NULL); 1447 1448 if( *cliquelist != NULL ) 1449 { 1450 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[0], (*cliquelist)->size[0]); 1451 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[1], (*cliquelist)->size[1]); 1452 BMSfreeBlockMemory(blkmem, cliquelist); 1453 } 1454 } 1455 1456 /** ensures, that clique list arrays can store at least num entries */ 1457 static 1458 SCIP_RETCODE cliquelistEnsureSize( 1459 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 1460 BMS_BLKMEM* blkmem, /**< block memory */ 1461 SCIP_SET* set, /**< global SCIP settings */ 1462 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */ 1463 int num /**< minimum number of entries to store */ 1464 ) 1465 { 1466 assert(cliquelist != NULL); 1467 1468 if( num > cliquelist->size[value] ) 1469 { 1470 int newsize; 1471 1472 newsize = SCIPsetCalcMemGrowSize(set, num); 1473 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/ 1474 cliquelist->size[value] = newsize; 1475 } 1476 assert(num <= cliquelist->size[value]); 1477 1478 return SCIP_OKAY; 1479 } 1480 1481 /** adds a clique to the clique list */ 1482 SCIP_RETCODE SCIPcliquelistAdd( 1483 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 1484 BMS_BLKMEM* blkmem, /**< block memory */ 1485 SCIP_SET* set, /**< global SCIP settings */ 1486 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */ 1487 SCIP_CLIQUE* clique /**< clique that should be added to the clique list */ 1488 ) 1489 { 1490 unsigned int id; 1491 int i = 0; 1492 1493 assert(cliquelist != NULL); 1494 1495 /* insert clique into list, sorted by clique id */ 1496 id = clique->id; /*lint !e732*/ 1497 1498 /* allocate memory */ 1499 if( *cliquelist == NULL ) 1500 { 1501 SCIP_CALL( cliquelistCreate(cliquelist, blkmem) ); 1502 } 1503 else 1504 { 1505 if( (*cliquelist)->cliques[value] != NULL ) 1506 { 1507 for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i - 1]->id > id; --i ); /*lint !e574 !e722*/ 1508 /* do not put the same clique twice in the cliquelist */ 1509 if( i > 0 && (*cliquelist)->cliques[value][i - 1]->id == id ) 1510 return SCIP_OKAY; 1511 } 1512 } 1513 SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value] + 1) ); 1514 1515 SCIPsetDebugMsg(set, "adding clique %u to cliquelist %p value %u (length: %d)\n", 1516 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]); 1517 1518 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][i+1]), &((*cliquelist)->cliques[value][i]), (*cliquelist)->ncliques[value] - i); /*lint !e866*/ 1519 1520 (*cliquelist)->cliques[value][i] = clique; 1521 (*cliquelist)->ncliques[value]++; 1522 1523 return SCIP_OKAY; 1524 } 1525 1526 /** removes a clique from the clique list */ 1527 SCIP_RETCODE SCIPcliquelistDel( 1528 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */ 1529 BMS_BLKMEM* blkmem, /**< block memory */ 1530 SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */ 1531 SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */ 1532 ) 1533 { 1534 int pos; 1535 1536 assert(cliquelist != NULL); 1537 1538 /* if a variable appeared twice in its last clique and is now removed both times, the cliquelist is already cleaned 1539 up after the first removal call of this "doubleton" */ 1540 if( *cliquelist == NULL ) 1541 return SCIP_OKAY; 1542 1543 SCIPdebugMessage("deleting clique %u from cliquelist %p value %u (length: %d)\n", 1544 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]); 1545 1546 pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique); 1547 1548 /* clique does not exist in cliquelist, the clique should contain multiple entries of the same variable */ 1549 if( pos < 0 ) 1550 { 1551 #ifdef SCIP_MORE_DEBUG 1552 SCIP_VAR** clqvars; 1553 SCIP_Bool* clqvalues; 1554 int nclqvars = SCIPcliqueGetNVars(clique); 1555 int v; 1556 1557 assert(nclqvars >= 2); 1558 assert(SCIPcliqueGetVars(clique) != NULL); 1559 assert(SCIPcliqueGetValues(clique) != NULL); 1560 1561 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, SCIPcliqueGetVars(clique), nclqvars) ); 1562 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, SCIPcliqueGetValues(clique), nclqvars) ); 1563 1564 /* sort variables and corresponding clique values after variables indices */ 1565 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, nclqvars); 1566 1567 for( v = nclqvars - 1; v > 0; --v ) 1568 { 1569 if( clqvars[v] == clqvars[v - 1] ) 1570 { 1571 if( clqvalues[v] == clqvalues[v - 1] || (v > 1 && clqvars[v] == clqvars[v - 2]) ) 1572 break; 1573 } 1574 } 1575 assert(v > 0); 1576 1577 BMSfreeBlockMemoryArray(blkmem, &clqvalues, nclqvars); 1578 BMSfreeBlockMemoryArray(blkmem, &clqvars, nclqvars); 1579 #endif 1580 return SCIP_OKAY; 1581 } 1582 1583 assert(0 <= pos && pos < (*cliquelist)->ncliques[value]); 1584 assert((*cliquelist)->cliques[value][pos] == clique); 1585 1586 /* remove clique from list */ 1587 /* @todo maybe buffered deletion */ 1588 (*cliquelist)->ncliques[value]--; 1589 if( pos < (*cliquelist)->ncliques[value] ) 1590 { 1591 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]), 1592 (*cliquelist)->ncliques[value] - pos); /*lint !e866*/ 1593 } 1594 1595 /* free cliquelist if it is empty */ 1596 if( (*cliquelist)->ncliques[0] == 0 && (*cliquelist)->ncliques[1] == 0 ) 1597 SCIPcliquelistFree(cliquelist, blkmem); 1598 1599 return SCIP_OKAY; 1600 } 1601 1602 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears 1603 * in both lists 1604 */ 1605 SCIP_Bool SCIPcliquelistsHaveCommonClique( 1606 SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */ 1607 SCIP_Bool value1, /**< value of first variable */ 1608 SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */ 1609 SCIP_Bool value2 /**< value of second variable */ 1610 ) 1611 { 1612 SCIP_CLIQUE** cliques1; 1613 SCIP_CLIQUE** cliques2; 1614 int ncliques1; 1615 int ncliques2; 1616 int i1; 1617 int i2; 1618 1619 if( cliquelist1 == NULL || cliquelist2 == NULL ) 1620 return FALSE; 1621 1622 ncliques1 = cliquelist1->ncliques[value1]; 1623 cliques1 = cliquelist1->cliques[value1]; 1624 ncliques2 = cliquelist2->ncliques[value2]; 1625 cliques2 = cliquelist2->cliques[value2]; 1626 1627 i1 = 0; 1628 i2 = 0; 1629 1630 if( i1 < ncliques1 && i2 < ncliques2 ) 1631 { 1632 unsigned int cliqueid; 1633 1634 /* make the bigger clique the first one */ 1635 if( ncliques2 > ncliques1 ) 1636 { 1637 SCIP_CLIQUE** tmpc; 1638 int tmpi; 1639 1640 tmpc = cliques1; 1641 tmpi = ncliques1; 1642 cliques1 = cliques2; 1643 ncliques1 = ncliques2; 1644 cliques2 = tmpc; 1645 ncliques2 = tmpi; 1646 } 1647 1648 /* check whether both clique lists have a same clique */ 1649 while( TRUE ) /*lint !e716*/ 1650 { 1651 cliqueid = SCIPcliqueGetId(cliques2[i2]); 1652 1653 /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order 1654 * there will be no same item and we can stop */ 1655 if( SCIPcliqueGetId(cliques1[ncliques1 - 1]) < cliqueid ) 1656 break; 1657 1658 while( SCIPcliqueGetId(cliques1[i1]) < cliqueid ) 1659 { 1660 ++i1; 1661 assert(i1 < ncliques1); 1662 } 1663 cliqueid = SCIPcliqueGetId(cliques1[i1]); 1664 1665 /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order 1666 * there will be no same item and we can stop */ 1667 if( SCIPcliqueGetId(cliques2[ncliques2 - 1]) < cliqueid ) 1668 break; 1669 1670 while( SCIPcliqueGetId(cliques2[i2]) < cliqueid ) 1671 { 1672 ++i2; 1673 assert(i2 < ncliques2); 1674 } 1675 if( SCIPcliqueGetId(cliques2[i2]) == cliqueid ) 1676 return TRUE; 1677 } 1678 } 1679 return FALSE; 1680 } 1681 1682 /** removes all listed entries from the cliques */ 1683 void SCIPcliquelistRemoveFromCliques( 1684 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 1685 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1686 SCIP_VAR* var, /**< active problem variable the clique list belongs to */ 1687 SCIP_Bool irrelevantvar /**< has the variable become irrelevant, meaning that equality 1688 * cliques need to be relaxed? */ 1689 ) 1690 { 1691 assert(SCIPvarIsBinary(var)); 1692 1693 if( cliquelist != NULL ) 1694 { 1695 int value; 1696 1697 SCIPdebugMessage("removing variable <%s> from cliques (%d with value 0, %d with value 1)\n", 1698 SCIPvarGetName(var), cliquelist->ncliques[0], cliquelist->ncliques[1]); 1699 1700 for( value = 0; value < 2; ++value ) 1701 { 1702 int i; 1703 1704 assert(SCIPvarGetCliques(var, (SCIP_Bool)value) == cliquelist->cliques[value]); 1705 assert(SCIPvarGetNCliques(var, (SCIP_Bool)value) == cliquelist->ncliques[value]); 1706 1707 /* it is important to iterate from the end of the array because otherwise, each removal causes 1708 * a memory move of the entire array 1709 */ 1710 for( i = cliquelist->ncliques[value] - 1; i >= 0; --i ) 1711 { 1712 SCIP_CLIQUE* clique; 1713 1714 clique = cliquelist->cliques[value][i]; 1715 assert(clique != NULL); 1716 1717 SCIPdebugMessage(" -> removing variable <%s> == %d from clique %u (size %d)\n", 1718 SCIPvarGetName(var), value, clique->id, clique->nvars); 1719 1720 SCIPcliqueDelVar(clique, cliquetable, var, (SCIP_Bool)value); 1721 1722 if( irrelevantvar ) 1723 clique->equation = FALSE; 1724 1725 #ifdef SCIP_MORE_DEBUG 1726 /* during the cleanup step, we skip the consistency check because clique may be temporarily inconsistent */ 1727 if( ! cliquetable->incleanup || clique->index > 0 ) 1728 { 1729 cliqueCheck(clique); 1730 } 1731 #endif 1732 } 1733 } 1734 } 1735 } 1736 1737 /** gets the key of the given element */ 1738 static 1739 SCIP_DECL_HASHGETKEY(hashgetkeyClique) 1740 { /*lint --e{715}*/ 1741 return elem; 1742 } 1743 1744 /** returns TRUE iff both keys are equal */ 1745 static 1746 SCIP_DECL_HASHKEYEQ(hashkeyeqClique) 1747 { /*lint --e{715}*/ 1748 SCIP_CLIQUE* clique1; 1749 SCIP_CLIQUE* clique2; 1750 int i; 1751 1752 clique1 = (SCIP_CLIQUE*)key1; 1753 clique2 = (SCIP_CLIQUE*)key2; 1754 assert(clique1 != NULL); 1755 assert(clique2 != NULL); 1756 1757 if( clique1->nvars != clique2->nvars ) 1758 return FALSE; 1759 1760 /* the variables are sorted: we can simply check the equality of each pair of variable/values */ 1761 for( i = 0; i < clique1->nvars; ++i ) 1762 { 1763 if( clique1->vars[i] != clique2->vars[i] || clique1->values[i] != clique2->values[i] ) 1764 return FALSE; 1765 } 1766 1767 return TRUE; 1768 } 1769 1770 /** returns the hash value of the key */ 1771 static 1772 SCIP_DECL_HASHKEYVAL(hashkeyvalClique) 1773 { /*lint --e{715}*/ 1774 SCIP_CLIQUE* clique; 1775 1776 clique = (SCIP_CLIQUE*)key; 1777 1778 return clique->nvars == 0 ? 0 : SCIPhashFour(SCIPvarGetIndex(clique->vars[0]), \ 1779 SCIPvarGetIndex(clique->vars[clique->nvars-1]), \ 1780 clique->nvars, 2*clique->values[0] + clique->values[clique->nvars-1]); 1781 } 1782 1783 #define HASHTABLE_CLIQUETABLE_SIZE 100 1784 1785 /** creates a clique table data structure */ 1786 SCIP_RETCODE SCIPcliquetableCreate( 1787 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */ 1788 SCIP_SET* set, /**< global SCIP settings */ 1789 BMS_BLKMEM* blkmem /**< block memory */ 1790 ) 1791 { 1792 int hashtablesize; 1793 1794 assert(cliquetable != NULL); 1795 1796 SCIP_ALLOC( BMSallocMemory(cliquetable) ); 1797 1798 /* create hash table to test for multiple cliques */ 1799 hashtablesize = HASHTABLE_CLIQUETABLE_SIZE; 1800 hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES)); 1801 SCIP_CALL( SCIPhashtableCreate(&((*cliquetable)->hashtable), blkmem, hashtablesize, 1802 hashgetkeyClique, hashkeyeqClique, hashkeyvalClique, NULL) ); 1803 1804 (*cliquetable)->varidxtable = NULL; 1805 (*cliquetable)->djset = NULL; 1806 (*cliquetable)->cliques = NULL; 1807 (*cliquetable)->ncliques = 0; 1808 (*cliquetable)->size = 0; 1809 (*cliquetable)->ncreatedcliques = 0; 1810 (*cliquetable)->ncleanupfixedvars = 0; 1811 (*cliquetable)->ncleanupaggrvars = 0; 1812 (*cliquetable)->ndirtycliques = 0; 1813 (*cliquetable)->nentries = 0; 1814 (*cliquetable)->incleanup = FALSE; 1815 (*cliquetable)->compsfromscratch = FALSE; 1816 (*cliquetable)->ncliquecomponents = -1; 1817 1818 return SCIP_OKAY; 1819 } 1820 1821 /** frees a clique table data structure */ 1822 SCIP_RETCODE SCIPcliquetableFree( 1823 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */ 1824 BMS_BLKMEM* blkmem /**< block memory */ 1825 ) 1826 { 1827 int i; 1828 1829 assert(cliquetable != NULL); 1830 assert(*cliquetable != NULL); 1831 1832 /* free all cliques */ 1833 for( i = (*cliquetable)->ncliques - 1; i >= 0; --i ) 1834 { 1835 cliqueFree(&(*cliquetable)->cliques[i], blkmem); 1836 } 1837 1838 /* free disjoint set (union find) data structure */ 1839 if( (*cliquetable)->djset != NULL ) 1840 SCIPdisjointsetFree(&(*cliquetable)->djset, blkmem); 1841 1842 /* free hash table for variable indices */ 1843 if( (*cliquetable)->varidxtable != NULL ) 1844 SCIPhashmapFree(&(*cliquetable)->varidxtable); 1845 1846 /* free clique table data */ 1847 BMSfreeMemoryArrayNull(&(*cliquetable)->cliques); 1848 1849 /* free hash table */ 1850 SCIPhashtableFree(&((*cliquetable)->hashtable)); 1851 1852 BMSfreeMemory(cliquetable); 1853 1854 return SCIP_OKAY; 1855 } 1856 1857 /** ensures, that clique table arrays can store at least num entries */ 1858 static 1859 SCIP_RETCODE cliquetableEnsureSize( 1860 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1861 SCIP_SET* set, /**< global SCIP settings */ 1862 int num /**< minimum number of entries to store */ 1863 ) 1864 { 1865 assert(cliquetable != NULL); 1866 1867 if( num > cliquetable->size ) 1868 { 1869 int newsize; 1870 1871 newsize = SCIPsetCalcMemGrowSize(set, num); 1872 SCIP_ALLOC( BMSreallocMemoryArray(&cliquetable->cliques, newsize) ); 1873 cliquetable->size = newsize; 1874 } 1875 assert(num <= cliquetable->size); 1876 1877 return SCIP_OKAY; 1878 } 1879 1880 /** sort variables regarding their index and remove multiple entries of the same variable */ 1881 static 1882 SCIP_RETCODE sortAndMergeClique( 1883 SCIP_VAR** clqvars, /**< variables of a clique */ 1884 SCIP_Bool* clqvalues, /**< clique values, active or negated, for the variables in a clique */ 1885 int* nclqvars, /**< number of clique variables */ 1886 SCIP_Bool* isequation, /**< do we have an equation clique at hand? */ 1887 SCIP_CLIQUE* clique, /**< clique data structure or NULL */ 1888 BMS_BLKMEM* blkmem, /**< block memory */ 1889 SCIP_SET* set, /**< global SCIP settings */ 1890 SCIP_STAT* stat, /**< problem statistics */ 1891 SCIP_PROB* transprob, /**< transformed problem */ 1892 SCIP_PROB* origprob, /**< original problem */ 1893 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 1894 SCIP_REOPT* reopt, /**< reoptimization data structure */ 1895 SCIP_LP* lp, /**< current LP data */ 1896 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1897 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 1898 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 1899 int* nbdchgs, /**< pointer to store number of fixed variables */ 1900 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */ 1901 ) 1902 { 1903 int noldbdchgs; 1904 int startidx; 1905 1906 assert(nclqvars != NULL); 1907 1908 SCIPsetDebugMsg(set, "starting merging %d variables in clique %d\n", *nclqvars, (clique == NULL) ? -1 : (int) clique->id); 1909 1910 if( *nclqvars <= 1 ) 1911 return SCIP_OKAY; 1912 1913 assert(clqvars != NULL); 1914 assert(clqvalues != NULL); 1915 assert(blkmem != NULL); 1916 assert(set != NULL); 1917 assert(stat != NULL); 1918 assert(transprob != NULL); 1919 assert(origprob != NULL); 1920 assert(tree != NULL); 1921 assert(eventqueue != NULL); 1922 assert(nbdchgs != NULL); 1923 assert(infeasible != NULL); 1924 1925 /* sort variables and corresponding clique values regarding variables indices before merging multiples */ 1926 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, *nclqvars); 1927 1928 noldbdchgs = *nbdchgs; 1929 /* check for multiple occurences or pairs of negations in the variable array, this should be very rare when creating a 1930 * new clique */ 1931 startidx = *nclqvars - 1; 1932 while( startidx >= 0 ) 1933 { 1934 SCIP_VAR* var; 1935 int nones; 1936 int nzeros; 1937 int curr; 1938 1939 var = clqvars[startidx]; 1940 /* only column and loose variables can exist now */ 1941 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE); 1942 assert(SCIPvarIsBinary(var)); 1943 1944 /* the counters denote the occurrences of the variable var with value TRUE and FALSE as clqvalues, respectively */ 1945 if( clqvalues[startidx] ) 1946 { 1947 nones = 1; 1948 nzeros = 0; 1949 } 1950 else 1951 { 1952 nzeros = 1; 1953 nones = 0; 1954 } 1955 curr = startidx - 1; 1956 1957 /* loop and increase the counter based on the clique value */ 1958 while( curr >= 0 ) 1959 { 1960 if( clqvars[curr] == var ) 1961 { 1962 if( clqvalues[curr] ) 1963 nones++; 1964 else 1965 nzeros++; 1966 } 1967 else 1968 /* var is different from variable at index curr */ 1969 break; 1970 1971 --curr; 1972 } 1973 assert(nzeros + nones <= *nclqvars); 1974 1975 /* single occurrence of the variable */ 1976 if( nones + nzeros == 1 ) 1977 { 1978 startidx = curr; 1979 continue; 1980 } 1981 /* at least two occurrences of both the variable and its negation; infeasible */ 1982 if( nones >= 2 && nzeros >= 2 ) 1983 { 1984 *infeasible = TRUE; 1985 break; 1986 } 1987 1988 /* do we have the same variable with the same clique value twice? */ 1989 if( nones >= 2 || nzeros >= 2 ) 1990 { 1991 SCIP_Bool fixvalue; 1992 1993 /* other cases should be handled as infeasible */ 1994 assert(nones <= 1 || nzeros <= 1); 1995 1996 /* ensure that the variable is removed from both clique lists before fixing it */ 1997 if( clique != NULL ) 1998 { 1999 if( nones >= 1 ) 2000 { 2001 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) ); 2002 } 2003 if( nzeros >= 1 ) 2004 { 2005 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) ); 2006 } 2007 } 2008 2009 /* we fix the variable into the direction of fewer occurrences */ 2010 fixvalue = nones >= 2 ? FALSE : TRUE; 2011 2012 /* a variable multiple times in one clique forces this variable to be zero */ 2013 SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 2014 cliquetable, fixvalue, infeasible, nbdchgs) ); 2015 2016 SCIPsetDebugMsg(set, "same var %s twice in a clique with value %d fixed to %d (was %s)\n", SCIPvarGetName(var), fixvalue ? 0 : 1, 2017 fixvalue ? 1 : 0, *infeasible ? "infeasible" : "feasible"); 2018 2019 if( *infeasible ) 2020 break; 2021 } 2022 2023 /* do we have a pair of negated variables? */ 2024 if( nones >= 1 && nzeros >= 1 ) 2025 { 2026 SCIPsetDebugMsg(set, "var %s is paired with its negation in one clique -> fix all other variables\n", SCIPvarGetName(var)); 2027 2028 /* a pair of negated variables in one clique forces all other variables in the clique to be zero */ 2029 if( nzeros + nones < *nclqvars ) 2030 { 2031 int w; 2032 2033 w = *nclqvars - 1; 2034 while( w >= 0 ) 2035 { 2036 /* skip all occurrences of variable var itself, these are between curr and startidx */ 2037 if( w == startidx ) 2038 { 2039 if( curr == -1 ) 2040 break; 2041 2042 w = curr; 2043 } 2044 assert(clqvars[w] != var); 2045 2046 /* if one of the other variables occurs multiple times, we can 2047 * 1) deduce infeasibility if it occurs with different values 2048 * 2) wait for the last occurence to fix it 2049 */ 2050 while( w > 0 && clqvars[w-1] == clqvars[w] ) 2051 { 2052 if( clqvalues[w-1] != clqvalues[w] ) 2053 { 2054 *infeasible = TRUE; 2055 break; 2056 } 2057 --w; 2058 } 2059 2060 if( *infeasible ) 2061 break; 2062 2063 if( clique != NULL ) 2064 { 2065 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[w], blkmem, clqvalues[w], clique) ); 2066 } 2067 SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2068 branchcand, eventqueue, cliquetable, !clqvalues[w], infeasible, nbdchgs) ); 2069 2070 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[w]), clqvalues[w], 2071 clqvalues[w] ? 0 : 1, *infeasible ? "infeasible" : "feasible"); 2072 2073 if( *infeasible ) 2074 break; 2075 2076 --w; 2077 } 2078 } 2079 /* all variables except for var were fixed */ 2080 if( clique != NULL ) 2081 { 2082 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) ); 2083 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) ); 2084 } 2085 *nclqvars = 0; 2086 *isequation = FALSE; 2087 2088 /* break main loop */ 2089 break; 2090 } 2091 2092 /* otherwise, we would have an endless loop */ 2093 assert(curr < startidx); 2094 startidx = curr; 2095 } 2096 2097 /* we might have found an infeasibility or reduced the clique to size 0 */ 2098 if( *infeasible || *nclqvars == 0 ) 2099 return SCIP_OKAY; 2100 2101 /* we fixed a variable because it appears at least twice, now we need to remove the fixings 2102 * 2103 * @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet, 2104 * because it was contradicting a local bound 2105 */ 2106 if( *nbdchgs > noldbdchgs ) 2107 { 2108 SCIP_VAR* onefixedvar; 2109 SCIP_Bool onefixedvalue; 2110 int w; 2111 2112 /* we initialize the former value only to please gcc */ 2113 onefixedvalue = TRUE; 2114 onefixedvar = NULL; 2115 2116 /* remove all inactive variables, thereby checking for a variable that is fixed to one */ 2117 startidx = 0; 2118 w = 0; 2119 while( startidx < *nclqvars ) 2120 { 2121 SCIP_VAR* var; 2122 2123 var = clqvars[startidx]; 2124 2125 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN 2126 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE); 2127 2128 /* check if we have a variable fixed to one for this clique */ 2129 if( (clqvalues[startidx] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[startidx] && SCIPvarGetUbGlobal(var) < 0.5) ) 2130 { 2131 if( onefixedvar != NULL ) 2132 { 2133 *infeasible = TRUE; 2134 2135 SCIPsetDebugMsg(set, "two variables in clique %d fixed to one %s%s and %s%s\n", (clique != NULL) ? (int) clique->id : -1, 2136 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clqvalues[startidx] ? "" : "~", SCIPvarGetName(clqvars[startidx])); 2137 return SCIP_OKAY; 2138 } 2139 onefixedvar = var; 2140 onefixedvalue = clqvalues[startidx]; 2141 } 2142 /* only keep active variables */ 2143 else if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 ) 2144 { 2145 /* we remove all fixed variables */ 2146 if( startidx > w ) 2147 { 2148 clqvars[w] = clqvars[startidx]; 2149 clqvalues[w] = clqvalues[startidx]; 2150 } 2151 ++w; 2152 } 2153 else 2154 { 2155 /* can we have some variable fixed to one? */ 2156 assert((SCIPvarGetUbGlobal(var) < 0.5 && clqvalues[startidx]) || (SCIPvarGetLbGlobal(var) > 0.5 && !clqvalues[startidx])); 2157 2158 if( clique != NULL ) 2159 { 2160 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, clqvalues[startidx], clique) ); 2161 } 2162 } 2163 ++startidx; 2164 } 2165 2166 /* the clique has been reduced to w active (unfixed) variables */ 2167 *nclqvars = w; 2168 2169 /* in rare cases, a variable fixed to one is only detected in the merging step */ 2170 if( onefixedvar != NULL ) 2171 { 2172 SCIPsetDebugMsg(set, "variable %s%s in clique %d fixed to one, fixing all other variables to zero\n", 2173 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), (clique != NULL) ? (int) clique->id : -1); 2174 2175 /* handle all active variables by fixing them */ 2176 for( startidx = *nclqvars; startidx >= 0; --startidx ) 2177 { 2178 assert(SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_COLUMN 2179 || SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_LOOSE); 2180 2181 /* delete the variable from its clique lists and fix it */ 2182 if( onefixedvalue != clqvalues[startidx] || clqvars[startidx] != onefixedvar ) 2183 { 2184 if( clique != NULL ) 2185 { 2186 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[startidx], blkmem, clqvalues[startidx], clique) ); 2187 } 2188 2189 /* if one of the other variables occurs multiple times, we can 2190 * 1) deduce infeasibility if it occurs with different values 2191 * 2) wait for the last occurence to fix it 2192 */ 2193 while( startidx > 0 && clqvars[startidx - 1] == clqvars[startidx] ) 2194 { 2195 if( clqvalues[startidx - 1] != clqvalues[startidx] ) 2196 { 2197 *infeasible = TRUE; 2198 return SCIP_OKAY; 2199 } 2200 --startidx; /*lint !e850*/ 2201 } 2202 2203 SCIPsetDebugMsg(set, "fixing variable %s in clique %d to %d\n", SCIPvarGetName(clqvars[startidx]), (clique != NULL) ? (int) clique->id : -1, 2204 clqvalues[startidx] ? 0 : 1); 2205 2206 /* note that the variable status will remain unchanged */ 2207 SCIP_CALL( SCIPvarFixBinary(clqvars[startidx], blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2208 branchcand, eventqueue, cliquetable, !clqvalues[startidx], infeasible, nbdchgs) ); 2209 2210 if( *infeasible ) 2211 return SCIP_OKAY; 2212 } 2213 } 2214 2215 /* delete clique from onefixedvars clique list */ 2216 if( clique != NULL ) /*lint !e850*/ 2217 { 2218 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) ); 2219 } 2220 2221 *nclqvars = 0; 2222 *isequation = FALSE; 2223 } 2224 } 2225 2226 assert(!(*infeasible)); 2227 2228 if( *isequation ) 2229 { 2230 if( *nclqvars == 0 ) 2231 { 2232 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n"); 2233 2234 *infeasible = TRUE; 2235 } 2236 else if( *nclqvars == 1 ) 2237 { 2238 assert(SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_COLUMN 2239 || SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_LOOSE); 2240 /* clearing data and removing variable from its clique list */ 2241 if( clique != NULL ) 2242 { 2243 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[0], blkmem, clqvalues[0], clique) ); 2244 } 2245 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 2246 eventqueue, cliquetable, clqvalues[0], infeasible, nbdchgs) ); 2247 2248 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0], 2249 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible"); 2250 2251 *nclqvars = 0; 2252 *isequation = FALSE; 2253 } 2254 } 2255 2256 return SCIP_OKAY; 2257 } 2258 2259 /** helper function that returns the graph node index for a variable during connected component detection */ 2260 static 2261 int cliquetableGetNodeIndexBinvar( 2262 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2263 SCIP_VAR* binvar /**< binary (or binary integer or implicit binary) variable */ 2264 ) 2265 { 2266 SCIP_VAR* activevar; 2267 int nodeindex; 2268 2269 assert(binvar != NULL); 2270 assert(SCIPvarIsBinary(binvar)); 2271 2272 if( cliquetable->varidxtable == NULL ) 2273 return -1; 2274 2275 /* get active representative of variable */ 2276 if( !SCIPvarIsActive(binvar) ) 2277 { 2278 activevar = SCIPvarGetProbvar(binvar); 2279 if( !SCIPvarIsActive(activevar) ) 2280 return -1; 2281 } 2282 else 2283 activevar = binvar; 2284 2285 assert(SCIPvarIsBinary(activevar)); 2286 2287 /* if the map does not contain an index for this variable, return -1 and mark that the components must be 2288 * recomputed from scratch 2289 */ 2290 if( SCIPhashmapExists(cliquetable->varidxtable, (void*)activevar) ) 2291 nodeindex = SCIPhashmapGetImageInt(cliquetable->varidxtable, (void *)activevar); 2292 else 2293 { 2294 nodeindex = -1; 2295 cliquetable->compsfromscratch = TRUE; 2296 } 2297 2298 return nodeindex; 2299 } 2300 2301 2302 /** updates connectedness information for the \p clique */ 2303 static 2304 void cliquetableUpdateConnectednessClique( 2305 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2306 SCIP_CLIQUE* clique /**< clique that should be added */ 2307 ) 2308 { 2309 int i; 2310 int lastnode; 2311 SCIP_VAR** clqvars; 2312 int nclqvars; 2313 2314 assert(cliquetable != NULL); 2315 assert(clique != NULL); 2316 2317 /* check if disjoint set (union find) data structure has not been allocated yet */ 2318 if( cliquetable->djset == NULL ) 2319 cliquetable->compsfromscratch = TRUE; 2320 2321 /* return immediately if a component update is already pending */ 2322 if( cliquetable->compsfromscratch ) 2323 return; 2324 2325 lastnode = -1; 2326 clqvars = clique->vars; 2327 nclqvars = clique->nvars; 2328 2329 /* loop over variables in the clique and connect the corresponding components */ 2330 for( i = 0; i < nclqvars && !cliquetable->compsfromscratch; ++i ) 2331 { 2332 /* this method may also detect that the clique table must entirely recompute connectedness */ 2333 int currnode = cliquetableGetNodeIndexBinvar(cliquetable, clqvars[i]); 2334 2335 /* skip inactive variables */ 2336 if( currnode == - 1 ) 2337 continue; 2338 2339 /* connect this and the last active variable */ 2340 if( lastnode != -1 ) 2341 SCIPdisjointsetUnion(cliquetable->djset, lastnode, currnode, FALSE); 2342 2343 lastnode = currnode; 2344 } 2345 } 2346 2347 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */ 2348 int SCIPcliquetableGetVarComponentIdx( 2349 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2350 SCIP_VAR* var /**< problem variable */ 2351 ) 2352 { 2353 int cmpidx = -1; 2354 assert(var != NULL); 2355 assert(cliquetable->djset != NULL); 2356 2357 /* only binary variables can have a component index 2358 *(both integer and implicit integer variables can be binary) 2359 */ 2360 if( SCIPvarIsBinary(var) ) 2361 { 2362 int nodeindex = cliquetableGetNodeIndexBinvar(cliquetable, var); 2363 assert(nodeindex < SCIPdisjointsetGetSize(cliquetable->djset)); 2364 2365 if( nodeindex >= 0 ) 2366 cmpidx = SCIPdisjointsetFind(cliquetable->djset, nodeindex); 2367 } 2368 2369 return cmpidx; 2370 } 2371 2372 2373 /** adds a clique to the clique table, using the given values for the given variables; 2374 * performs implications if the clique contains the same variable twice 2375 */ 2376 SCIP_RETCODE SCIPcliquetableAdd( 2377 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2378 BMS_BLKMEM* blkmem, /**< block memory */ 2379 SCIP_SET* set, /**< global SCIP settings */ 2380 SCIP_STAT* stat, /**< problem statistics */ 2381 SCIP_PROB* transprob, /**< transformed problem */ 2382 SCIP_PROB* origprob, /**< original problem */ 2383 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 2384 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2385 SCIP_LP* lp, /**< current LP data */ 2386 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2387 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2388 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */ 2389 SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */ 2390 int nvars, /**< number of variables in the clique */ 2391 SCIP_Bool isequation, /**< is the clique an equation or an inequality? */ 2392 SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */ 2393 int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */ 2394 ) 2395 { 2396 SCIP_VAR** clqvars; 2397 SCIP_Bool* clqvalues; 2398 SCIP_CLIQUE* clique; 2399 SCIP_VAR* var; 2400 int size; 2401 int nlocalbdchgs = 0; 2402 int v; 2403 int w; 2404 2405 assert(cliquetable != NULL); 2406 assert(vars != NULL); 2407 2408 SCIPsetDebugMsg(set, "trying to add clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars); 2409 2410 /* check clique on debugging solution */ 2411 SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/ 2412 2413 *infeasible = FALSE; 2414 size = nvars; 2415 2416 /* copy clique data */ 2417 if( values == NULL ) 2418 { 2419 SCIP_CALL( SCIPsetAllocBufferArray(set, &clqvalues, size) ); 2420 2421 /* initialize clique values data */ 2422 for( v = nvars - 1; v >= 0; --v ) 2423 clqvalues[v] = TRUE; 2424 } 2425 else 2426 { 2427 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvalues, values, size) ); 2428 } 2429 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvars, vars, size) ); 2430 2431 /* get active variables */ 2432 SCIP_CALL( SCIPvarsGetProbvarBinary(&clqvars, &clqvalues, nvars) ); 2433 2434 /* remove all inactive vars */ 2435 for( v = nvars - 1; v >= 0; --v ) 2436 { 2437 var = clqvars[v]; 2438 2439 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN 2440 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE 2441 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED 2442 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR); 2443 assert(SCIPvarIsBinary(var)); 2444 2445 /* if we have a variables already fixed to one in the clique, fix all other to zero */ 2446 if( ! SCIPvarIsMarkedDeleteGlobalStructures(var) && 2447 ((clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5)) ) 2448 { 2449 SCIPsetDebugMsg(set, "in a clique var %s with value %u is fixed to %d -> fix the rest\n", SCIPvarGetName(var), clqvalues[v], clqvalues[v] ? 1 : 0); 2450 2451 for( w = nvars - 1; w >= 0; --w ) 2452 { 2453 SCIP_VAR* clqvar = clqvars[w]; 2454 2455 /* the rare case where the same variable appears several times is handled later during sort and merge */ 2456 if( clqvar != var ) 2457 { 2458 SCIP_Bool clqval = clqvalues[w]; 2459 2460 /* check if variable is fixed already and terminate with infeasible if this fixing contradicts the clique info */ 2461 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 ) 2462 { 2463 /* check if fixing contradicts clique constraint */ 2464 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5) 2465 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) ) 2466 { 2467 *infeasible = TRUE; 2468 2469 goto FREEMEM; 2470 } 2471 2472 continue; 2473 } 2474 2475 /* the following piece of code is disabled because it assumes the clqvars to be sorted which they aren't until the method 2476 * sortAndMergeClique() is called 2477 */ 2478 #ifdef SCIP_DISABLED_CODE 2479 /* if one of the other variables occurs multiple times, we can 2480 * 1) deduce infeasibility if it occurs with different values 2481 * 2) wait for the last occurence to fix it 2482 */ 2483 while( w > 0 && clqvars[w - 1] == clqvars[w] ) 2484 { 2485 if( clqvalues[w - 1] != clqvalues[w] ) 2486 { 2487 *infeasible = TRUE; 2488 return SCIP_OKAY; 2489 } 2490 --w; 2491 } 2492 #endif 2493 2494 /* fix the variable */ 2495 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2496 branchcand, eventqueue, cliquetable, !clqval, infeasible, &nlocalbdchgs) ); 2497 2498 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvar), clqval, 2499 clqval ? 0 : 1, *infeasible ? "infeasible" : "feasible"); 2500 2501 if( *infeasible ) 2502 break; 2503 } 2504 } 2505 2506 /* all variables are fixed so we can stop */ 2507 break; /*lint !e850*/ 2508 } 2509 2510 /* only unfixed column and loose variables may be member of a clique */ 2511 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) < 0.5 || 2512 (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE) || 2513 SCIPvarIsMarkedDeleteGlobalStructures(var) ) 2514 { 2515 --nvars; 2516 clqvars[v] = clqvars[nvars]; 2517 clqvalues[v] = clqvalues[nvars]; 2518 isequation = isequation && !(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) && ! SCIPvarIsMarkedDeleteGlobalStructures(var); 2519 } 2520 } 2521 2522 if( nbdchgs != NULL ) 2523 *nbdchgs += nlocalbdchgs; 2524 2525 /* did we fix all variables or are we infeasible? */ 2526 if( v >= 0 ) 2527 goto FREEMEM; 2528 2529 assert(!*infeasible); 2530 2531 /* check if only one or less variables are left */ 2532 if( v < 0 && nvars <= 1) 2533 { 2534 if( isequation ) 2535 { 2536 if( nvars == 1 ) 2537 { 2538 nlocalbdchgs = 0; 2539 2540 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2541 branchcand, eventqueue, cliquetable, clqvalues[0], infeasible, &nlocalbdchgs) ); 2542 2543 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0], 2544 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible"); 2545 2546 if( nbdchgs != NULL ) 2547 *nbdchgs += nlocalbdchgs; 2548 } 2549 else if( nvars == 0 ) 2550 { 2551 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n"); 2552 2553 *infeasible = TRUE; 2554 } 2555 } 2556 2557 goto FREEMEM; 2558 } 2559 2560 nlocalbdchgs = 0; 2561 2562 /* sort the variables and values and remove multiple entries of the same variable */ 2563 SCIP_CALL( sortAndMergeClique(clqvars, clqvalues, &nvars, &isequation, NULL, blkmem, set, stat, transprob, origprob, tree, 2564 reopt, lp, branchcand, eventqueue, cliquetable, &nlocalbdchgs, infeasible) ); 2565 2566 if( nbdchgs != NULL ) 2567 *nbdchgs += nlocalbdchgs; 2568 2569 /* did we stop early due to a pair of negated variables? */ 2570 if( nvars == 0 || *infeasible ) 2571 goto FREEMEM; 2572 2573 if( !SCIPsetIsInfinity(set, set->presol_clqtablefac) && SCIPcliquetableGetNEntries(cliquetable) + nvars > set->presol_clqtablefac * stat->nnz ) 2574 { 2575 SCIPsetDebugMsg(set, "reject %d-variable clique to keep clique table entries below threshold of %g entries\n", 2576 nvars, set->presol_clqtablefac * stat->nnz); 2577 2578 goto FREEMEM; 2579 } 2580 2581 /* if less than two variables are left over, the clique is redundant */ 2582 if( nvars > 1 ) 2583 { 2584 SCIP_CLIQUE* sameclique; 2585 2586 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */ 2587 2588 /* create the clique data structure */ 2589 SCIP_CALL( cliqueCreateWithData(&clique, blkmem, nvars, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques, isequation) ); 2590 2591 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique); 2592 2593 if( sameclique == NULL ) 2594 { 2595 SCIPsetDebugMsg(set, "adding clique %u with %d vars to clique table\n", clique->id, nvars); 2596 2597 cliquetable->ncreatedcliques++; 2598 2599 /* add clique to clique table */ 2600 SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) ); 2601 cliquetable->cliques[cliquetable->ncliques] = clique; 2602 clique->index = cliquetable->ncliques; 2603 cliquetable->ncliques++; 2604 cliquetable->nentries += nvars; 2605 cliquetableUpdateConnectednessClique(cliquetable, clique); 2606 2607 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) ); 2608 2609 /* add filled clique to the cliquelists of all corresponding variables */ 2610 SCIP_CALL( SCIPvarsAddClique(clqvars, clqvalues, nvars, blkmem, set, clique) ); 2611 } 2612 else 2613 { 2614 SCIPsetDebugMsg(set, "same clique %p (id: %d) already found in cliquetable -> discard new one\n", (void*) sameclique, sameclique->id); 2615 2616 /* update equation status of clique */ 2617 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove 2618 * the sameclique from the hashmap while adding the new clique 2619 */ 2620 if( !sameclique->equation && clique->equation ) 2621 sameclique->equation = TRUE; 2622 2623 cliqueFree(&clique, blkmem); 2624 2625 goto FREEMEM; 2626 } 2627 } 2628 else 2629 { 2630 assert(!isequation); 2631 assert(nvars == 1); 2632 2633 goto FREEMEM; 2634 } 2635 cliqueCheck(clique); 2636 2637 FREEMEM: 2638 SCIPsetFreeBufferArray(set, &clqvars); 2639 SCIPsetFreeBufferArray(set, &clqvalues); 2640 2641 return SCIP_OKAY; 2642 } 2643 2644 /** clean up given clique by removing fixed variables */ 2645 static 2646 SCIP_RETCODE cliqueCleanup( 2647 SCIP_CLIQUE* clique, /**< clique data structure */ 2648 BMS_BLKMEM* blkmem, /**< block memory */ 2649 SCIP_SET* set, /**< global SCIP settings */ 2650 SCIP_STAT* stat, /**< problem statistics */ 2651 SCIP_PROB* transprob, /**< transformed problem */ 2652 SCIP_PROB* origprob, /**< original problem */ 2653 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 2654 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2655 SCIP_LP* lp, /**< current LP data */ 2656 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2657 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2658 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2659 int* nchgbds, /**< pointer to store number of fixed variables */ 2660 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */ 2661 ) 2662 { 2663 assert(clique != NULL); 2664 assert(blkmem != NULL); 2665 assert(set != NULL); 2666 assert(nchgbds != NULL); 2667 assert(infeasible != NULL); 2668 2669 /* do we need to clean up fixed variables? */ 2670 if( !SCIPcliqueIsCleanedUp(clique) ) 2671 { 2672 SCIP_VAR* onefixedvar = NULL; 2673 SCIP_Bool onefixedvalue = FALSE; 2674 SCIP_Bool needsorting = FALSE; 2675 int v; 2676 int w; 2677 2678 w = clique->startcleanup; 2679 2680 SCIPsetDebugMsg(set, "Starting clean up of clique %u (size %d) from position %d\n", clique->id, clique->nvars, w); 2681 2682 /* exchange inactive by active variables */ 2683 for( v = w; v < clique->nvars; ++v ) 2684 { 2685 SCIP_Bool addvartoclique; /* has the variable status changed such that it needs to be replaced by an active representative? */ 2686 2687 addvartoclique = FALSE; 2688 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_AGGREGATED 2689 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED 2690 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR ) 2691 { 2692 needsorting = TRUE; 2693 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[v], blkmem, clique->values[v], clique) ); 2694 SCIP_CALL( SCIPvarGetProbvarBinary(&(clique->vars[v]), &(clique->values[v])) ); 2695 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED ) 2696 { 2697 clique->vars[v] = SCIPvarGetNegationVar(clique->vars[v]); 2698 clique->values[v] = !clique->values[v]; 2699 } 2700 else if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR ) 2701 { 2702 clique->equation = FALSE; 2703 continue; 2704 } 2705 2706 addvartoclique = TRUE; 2707 } 2708 2709 assert(SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_COLUMN 2710 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_LOOSE 2711 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_FIXED); 2712 2713 /* check for variables that are either fixed to zero or marked for deletion from global structures */ 2714 if( (clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) || 2715 (!clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5) || 2716 SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) ) 2717 { 2718 if( !addvartoclique ) 2719 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[v], blkmem, clique->values[v], clique) ); 2720 2721 if( clique->equation && SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) ) 2722 clique->equation = FALSE; 2723 2724 /* the variable will be overwritten by subsequent active variables */ 2725 continue; 2726 } 2727 2728 /* check for a variable fixed to one in the clique */ 2729 else if( (clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5) 2730 || (!clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) ) 2731 { 2732 if( onefixedvar != NULL ) 2733 { 2734 *infeasible = TRUE; 2735 2736 SCIPsetDebugMsg(set, "two variables in clique %u fixed to one %s%s and %s%s\n", clique->id, 2737 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->values[v] ? "" : "~", 2738 SCIPvarGetName(clique->vars[v])); /*lint !e530*/ 2739 return SCIP_OKAY; 2740 } 2741 onefixedvar = clique->vars[v]; 2742 onefixedvalue = clique->values[v]; 2743 } 2744 else 2745 { 2746 assert(SCIPvarGetStatus(clique->vars[v]) != SCIP_VARSTATUS_FIXED); 2747 assert(w <= v); 2748 2749 if( w < v ) 2750 { 2751 clique->vars[w] = clique->vars[v]; 2752 clique->values[w] = clique->values[v]; 2753 } 2754 2755 /* add clique to active variable if it replaced a aggregated or negated var */ 2756 if( addvartoclique ) 2757 { 2758 SCIP_CALL( SCIPvarAddCliqueToList(clique->vars[w], blkmem, set, clique->values[w], clique) ); 2759 } 2760 /* increase indexer of last active, i.e. unfixed, variable in clique */ 2761 ++w; 2762 } 2763 } 2764 clique->nvars = w; 2765 2766 if( onefixedvar != NULL ) 2767 { 2768 SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n", 2769 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->id); 2770 2771 for( v = 0; v < clique->nvars ; ++v ) 2772 { 2773 SCIP_VAR* clqvar = clique->vars[v]; 2774 SCIP_Bool clqval = clique->values[v]; 2775 2776 assert(SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_COLUMN 2777 || SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_LOOSE); 2778 2779 if( onefixedvalue != clqval || clqvar != onefixedvar ) 2780 { 2781 /* the variable could have been fixed already because it appears more than once in the clique */ 2782 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 ) 2783 { 2784 /* the fixing must have occurred previously inside this loop. It may happen that 2785 * the variable occurs together with its negation in that clique, which is usually 2786 * handled during the merge step, but leads to a direct infeasibility because it 2787 * contradicts any other variable fixed to one in this clique 2788 */ 2789 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5) 2790 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) ) 2791 { 2792 /* impossible because we would have detected this in the previous cleanup loop */ 2793 assert(clqvar != onefixedvar); 2794 *infeasible = TRUE; 2795 2796 return SCIP_OKAY; 2797 } 2798 continue; 2799 } 2800 2801 SCIP_CALL( SCIPvarDelCliqueFromList(clqvar, blkmem, clqval, clique) ); 2802 2803 /* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting 2804 * of variables is performed earlier than it is now 2805 */ 2806 #ifdef SCIP_DISABLED_CODE 2807 /* if one of the other variables occurs multiple times, we can 2808 * 1) deduce infeasibility if it occurs with different values 2809 * 2) wait for the last occurence to fix it 2810 */ 2811 while( v < clique->nvars - 1 && clique->vars[v + 1] == clqvar ) 2812 { 2813 if( clique->values[v + 1] != clique->values[v] ) 2814 { 2815 *infeasible = TRUE; 2816 return SCIP_OKAY; 2817 } 2818 ++v; 2819 } 2820 #endif 2821 SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1); 2822 2823 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, 2824 eventqueue, cliquetable, !clqval, infeasible, nchgbds) ); 2825 2826 if( *infeasible ) 2827 return SCIP_OKAY; 2828 } 2829 } 2830 2831 if( SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_COLUMN /*lint !e850*/ 2832 || SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_LOOSE ) 2833 { 2834 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) ); 2835 } 2836 2837 clique->nvars = 0; 2838 clique->equation = FALSE; 2839 clique->startcleanup = -1; 2840 2841 return SCIP_OKAY; 2842 } 2843 2844 if( clique->equation ) 2845 { 2846 if( clique->nvars == 0 ) 2847 { 2848 *infeasible = TRUE; 2849 return SCIP_OKAY; 2850 } 2851 else if( clique->nvars == 1 ) 2852 { 2853 assert(SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_COLUMN 2854 || SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_LOOSE); 2855 2856 /* clearing data and removing variable from its clique list */ 2857 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[0], blkmem, clique->values[0], clique) ); 2858 2859 SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id, 2860 clique->values[0] ? 1 : 0); 2861 2862 SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, 2863 branchcand, eventqueue, cliquetable, clique->values[0], infeasible, nchgbds) ); 2864 2865 clique->nvars = 0; 2866 clique->equation = FALSE; 2867 clique->startcleanup = -1; 2868 2869 return SCIP_OKAY; 2870 } 2871 } 2872 2873 if( needsorting ) 2874 { 2875 SCIP_Bool isequation = clique->equation; 2876 2877 /* remove multiple entries of the same variable */ 2878 SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat, 2879 transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) ); 2880 2881 clique->equation = isequation; 2882 } 2883 2884 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */ 2885 2886 clique->startcleanup = -1; 2887 } 2888 assert(SCIPcliqueIsCleanedUp(clique)); 2889 2890 return SCIP_OKAY; 2891 } 2892 2893 #ifdef SCIP_MORE_DEBUG 2894 /** checks whether clique appears in all clique lists of the involved variables */ 2895 static 2896 SCIP_Bool checkNEntries( 2897 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 2898 ) 2899 { 2900 SCIP_Longint nentries = 0; 2901 int c; 2902 2903 assert(cliquetable != NULL); 2904 2905 for( c = cliquetable->ncliques - 1; c >= 0; --c ) 2906 nentries += cliquetable->cliques[c]->nvars; 2907 2908 return (nentries == cliquetable->nentries); 2909 } 2910 #else 2911 #define checkNEntries(cliquetable) TRUE 2912 #endif 2913 2914 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table 2915 * 2916 * @note cliques can be processed several times by this method 2917 * 2918 * @todo try to detect infeasible implications, e.g., x = 1 => (y = 0 && y = 1) 2919 */ 2920 SCIP_RETCODE SCIPcliquetableCleanup( 2921 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 2922 BMS_BLKMEM* blkmem, /**< block memory */ 2923 SCIP_SET* set, /**< global SCIP settings */ 2924 SCIP_STAT* stat, /**< problem statistics */ 2925 SCIP_PROB* transprob, /**< transformed problem */ 2926 SCIP_PROB* origprob, /**< original problem */ 2927 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */ 2928 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2929 SCIP_LP* lp, /**< current LP data */ 2930 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2931 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2932 int* nchgbds, /**< pointer to store number of fixed variables */ 2933 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */ 2934 ) 2935 { 2936 assert(cliquetable != NULL); 2937 assert(stat != NULL); 2938 assert(infeasible != NULL); 2939 2940 *infeasible = FALSE; 2941 2942 /* check if we have anything to do */ 2943 if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars 2944 && stat->npresolaggrvars == cliquetable->ncleanupaggrvars 2945 && cliquetable->ndirtycliques == 0 ) 2946 return SCIP_OKAY; 2947 2948 SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries); 2949 2950 /* delay events */ 2951 SCIP_CALL( SCIPeventqueueDelay(eventqueue) ); 2952 2953 cliquetable->incleanup = TRUE; 2954 while( cliquetable->ndirtycliques > 0 && !(*infeasible) ) 2955 { 2956 SCIP_CLIQUE* clique; 2957 SCIP_CLIQUE* sameclique; 2958 2959 clique = cliquetable->cliques[0]; 2960 2961 assert(!SCIPcliqueIsCleanedUp(clique)); 2962 2963 /* remove not clean up clique from hastable */ 2964 SCIP_CALL( SCIPhashtableRemove(cliquetable->hashtable, (void*)clique) ); 2965 cliquetable->nentries -= clique->nvars; 2966 assert(cliquetable->nentries >= 0); 2967 2968 SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, 2969 cliquetable, nchgbds, infeasible) ); 2970 2971 if( *infeasible ) 2972 break; 2973 2974 assert(SCIPcliqueIsCleanedUp(clique)); 2975 2976 /* swap freshly cleaned clique with last dirty clique */ 2977 cliquetable->ndirtycliques--; 2978 cliquetableSwapCliques(cliquetable, 0, cliquetable->ndirtycliques); 2979 cliqueCheck(clique); 2980 2981 /* @todo check if we can/want to aggregate variables with the following code */ 2982 #ifdef SCIP_DISABLED_CODE 2983 if( clique->nvars == 2 && clique->equation && SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING ) 2984 { 2985 SCIP_VAR* var0; 2986 SCIP_VAR* var1; 2987 SCIP_Real scalarx; 2988 SCIP_Real scalary; 2989 SCIP_Real rhs = 1.0; 2990 SCIP_Bool aggregated; 2991 2992 printf("aggr vars, clique %u\n", clique->id); 2993 2994 if( SCIPvarGetType(clique->vars[0]) >= SCIPvarGetType(clique->vars[1]) ) 2995 { 2996 var0 = clique->vars[0]; 2997 var1 = clique->vars[1]; 2998 2999 if( !clique->values[0] ) 3000 { 3001 scalarx = -1.0; 3002 rhs -= 1.0; 3003 } 3004 else 3005 scalarx = 1.0; 3006 3007 if( !clique->values[1] ) 3008 { 3009 scalary = -1.0; 3010 rhs -= 1.0; 3011 } 3012 else 3013 scalary = 1.0; 3014 } 3015 else 3016 { 3017 var0 = clique->vars[1]; 3018 var1 = clique->vars[0]; 3019 3020 if( !clique->values[0] ) 3021 { 3022 scalary = -1.0; 3023 rhs -= 1.0; 3024 } 3025 else 3026 scalary = 1.0; 3027 3028 if( !clique->values[1] ) 3029 { 3030 scalarx = -1.0; 3031 rhs -= 1.0; 3032 } 3033 else 3034 scalarx = 1.0; 3035 } 3036 3037 assert((SCIPvarGetStatus(var0) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var0) == SCIP_VARSTATUS_COLUMN) 3038 && (SCIPvarGetStatus(var1) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_COLUMN)); 3039 3040 /* aggregate the variable */ 3041 SCIP_CALL( SCIPvarTryAggregateVars(set, blkmem, stat, transprob, origprob, primal, 3042 tree, lp, cliquetable, branchcand, eventfilter, eventqueue, 3043 var0, var1, scalarx, scalary, rhs, infeasible, &aggregated) ); 3044 3045 assert(aggregated || *infeasible); 3046 } 3047 #endif 3048 3049 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique); 3050 3051 /* check if the clique is already contained in the clique table, or if it is redundant (too small) */ 3052 if( clique->nvars <= 1 || sameclique != NULL ) 3053 { 3054 int j; 3055 3056 /* infeasible or fixing should be performed already on trivial clique */ 3057 assert(clique->nvars > 1 || !clique->equation); 3058 3059 /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we 3060 * update the equation status of the old one 3061 */ 3062 if( clique->nvars > 1 && clique->equation && !sameclique->equation ) 3063 { 3064 assert(sameclique->nvars >= 2); 3065 3066 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove 3067 * the sameclique from the hashmap while adding the new clique 3068 */ 3069 sameclique->equation = TRUE; 3070 } 3071 3072 /* delete the clique from the variables' clique lists */ 3073 for( j = 0; j < clique->nvars; ++j ) 3074 { 3075 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) ); 3076 } 3077 3078 /* free clique and remove it from clique table */ 3079 cliqueFree(&clique, blkmem); 3080 cliquetable->ncliques--; 3081 /* insert a clean clique from the end of the array */ 3082 if( cliquetable->ndirtycliques < cliquetable->ncliques ) 3083 { 3084 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ncliques])); 3085 cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques]; 3086 cliquetable->cliques[cliquetable->ndirtycliques]->index = cliquetable->ndirtycliques; 3087 } 3088 } 3089 else 3090 { 3091 cliquetable->nentries += clique->nvars; 3092 3093 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) ); 3094 if( !clique->eventsissued ) 3095 { 3096 int j; 3097 3098 /* issue IMPLADDED event on each variable in the clique */ 3099 for( j = 0; j < clique->nvars; ++j ) 3100 { 3101 SCIP_EVENT* event; 3102 3103 SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) ); 3104 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) ); 3105 } 3106 clique->eventsissued = TRUE; 3107 } 3108 } 3109 } 3110 cliquetable->incleanup = FALSE; 3111 3112 /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */ 3113 cliquetable->ncleanupfixedvars = stat->npresolfixedvars; 3114 cliquetable->ncleanupaggrvars = stat->npresolaggrvars; 3115 assert(*infeasible || cliquetable->ndirtycliques == 0); 3116 3117 assert(*infeasible || checkNEntries(cliquetable)); /*lint !e506*/ 3118 3119 SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries); 3120 3121 /* process events */ 3122 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) ); 3123 3124 return SCIP_OKAY; 3125 } 3126 3127 /** computes connected components of the clique table 3128 * 3129 * an update becomes necessary if a clique gets added with variables from different components 3130 */ 3131 SCIP_RETCODE SCIPcliquetableComputeCliqueComponents( 3132 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 3133 SCIP_SET* set, /**< global SCIP settings */ 3134 BMS_BLKMEM* blkmem, /**< block memory */ 3135 SCIP_VAR** vars, /**< array of problem variables, sorted by variable type */ 3136 int nbinvars, /**< number of binary variables */ 3137 int nintvars, /**< number of integer variables */ 3138 int nimplvars /**< number of implicit integer variables */ 3139 ) 3140 { 3141 SCIP_DISJOINTSET* djset; 3142 int nimplbinvars; 3143 int v; 3144 int c; 3145 int nbinvarstotal; 3146 int ndiscvars; 3147 int nnonbinvars; 3148 3149 SCIP_CLIQUE** cliques; 3150 3151 assert(cliquetable != NULL); 3152 assert(vars != NULL); 3153 3154 nimplbinvars = 0; 3155 cliquetable->compsfromscratch = FALSE; 3156 ndiscvars = nbinvars + nintvars + nimplvars; 3157 3158 /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */ 3159 for( v = nbinvars; v < ndiscvars; ++v ) 3160 { 3161 if( SCIPvarIsBinary(vars[v]) ) 3162 ++nimplbinvars; 3163 } 3164 3165 /* count binary and implicit binary variables */ 3166 nbinvarstotal = nbinvars + nimplbinvars; 3167 3168 /* if there are no binary variables, return */ 3169 if( nbinvarstotal == 0 ) 3170 { 3171 SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table"); 3172 cliquetable->ncliquecomponents = 0; 3173 return SCIP_OKAY; 3174 } 3175 3176 /* no cliques are present */ 3177 if( cliquetable->ncliques == 0 ) 3178 { 3179 SCIPsetDebugMsg(set, "0 cliques --> Clique table has %d isolated nodes", nbinvarstotal); 3180 cliquetable->ncliquecomponents = nbinvarstotal; 3181 return SCIP_OKAY; 3182 } 3183 3184 /* create or clear the variable index mapping */ 3185 if( cliquetable->varidxtable == NULL ) 3186 { 3187 SCIP_CALL( SCIPhashmapCreate(&(cliquetable)->varidxtable, blkmem, ndiscvars) ); 3188 } 3189 else 3190 { 3191 SCIP_CALL( SCIPhashmapRemoveAll(cliquetable->varidxtable) ); 3192 } 3193 3194 /* loop through variables and store their respective positions in the hash map if they are binary */ 3195 for( v = 0; v < ndiscvars; ++v ) 3196 { 3197 SCIP_VAR* var = vars[v]; 3198 if( SCIPvarIsBinary(var) ) 3199 { 3200 /* consider only active representatives */ 3201 if( SCIPvarIsActive(var) ) 3202 { 3203 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) ); 3204 } 3205 else 3206 { 3207 var = SCIPvarGetProbvar(var); 3208 if( SCIPvarIsActive(var) ) 3209 { 3210 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) ); 3211 } 3212 } 3213 } 3214 } 3215 3216 /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */ 3217 if( cliquetable->djset != NULL ) 3218 SCIPdisjointsetFree(&cliquetable->djset, blkmem); 3219 3220 /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE. 3221 * These may be scattered across the ninteger + nimplvars implicit integer variables. 3222 * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract 3223 * the amount of nonbinary integer and implicit integer variables afterwards. 3224 */ 3225 SCIP_CALL( SCIPdisjointsetCreate(&cliquetable->djset, blkmem, ndiscvars) ); 3226 djset = cliquetable->djset; 3227 3228 /* subtract all (implicit) integer for which SCIPvarIsBinary() returns FALSE */ 3229 nnonbinvars = (nintvars + nimplvars) - nimplbinvars; 3230 3231 cliques = cliquetable->cliques; 3232 3233 /* for every clique, we connect clique variable components, treating a clique as a path 3234 * 3235 * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */ 3236 for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c ) 3237 { 3238 SCIP_CLIQUE* clique; 3239 3240 clique = cliques[c]; 3241 cliquetableUpdateConnectednessClique(cliquetable, clique); 3242 } 3243 3244 /* subtract superfluous integer and implicit integer variables added to the auxiliary graph */ 3245 cliquetable->ncliquecomponents = SCIPdisjointsetGetComponentCount(djset) - nnonbinvars; 3246 assert(cliquetable->ncliquecomponents >= 0); 3247 assert(cliquetable->ncliquecomponents <= nbinvarstotal); 3248 3249 SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal); 3250 3251 return SCIP_OKAY; 3252 } 3253 3254 /* 3255 * simple functions implemented as defines 3256 */ 3257 3258 /* In debug mode, the following methods are implemented as function calls to ensure 3259 * type validity. 3260 * In optimized mode, the methods are implemented as defines to improve performance. 3261 * However, we want to have them in the library anyways, so we have to undef the defines. 3262 */ 3263 3264 #undef SCIPvboundsGetNVbds 3265 #undef SCIPvboundsGetVars 3266 #undef SCIPvboundsGetCoefs 3267 #undef SCIPvboundsGetConstants 3268 #undef SCIPimplicsGetNImpls 3269 #undef SCIPimplicsGetVars 3270 #undef SCIPimplicsGetTypes 3271 #undef SCIPimplicsGetBounds 3272 #undef SCIPimplicsGetIds 3273 #undef SCIPcliqueGetNVars 3274 #undef SCIPcliqueGetVars 3275 #undef SCIPcliqueGetValues 3276 #undef SCIPcliqueGetId 3277 #undef SCIPcliqueGetIndex 3278 #undef SCIPcliqueIsCleanedUp 3279 #undef SCIPcliqueIsEquation 3280 #undef SCIPcliquelistGetNCliques 3281 #undef SCIPcliquelistGetCliques 3282 #undef SCIPcliquelistCheck 3283 #undef SCIPcliquetableGetNCliques 3284 #undef SCIPcliquetableGetCliques 3285 #undef SCIPcliquetableGetNEntries 3286 #undef SCIPcliquetableGetNCliqueComponents 3287 #undef SCIPcliquetableNeedsComponentUpdate 3288 3289 /** gets number of variable bounds contained in given variable bounds data structure */ 3290 int SCIPvboundsGetNVbds( 3291 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 3292 ) 3293 { 3294 return vbounds != NULL ? vbounds->len : 0; 3295 } 3296 3297 /** gets array of variables contained in given variable bounds data structure */ 3298 SCIP_VAR** SCIPvboundsGetVars( 3299 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 3300 ) 3301 { 3302 return vbounds != NULL ? vbounds->vars : NULL; 3303 } 3304 3305 /** gets array of coefficients contained in given variable bounds data structure */ 3306 SCIP_Real* SCIPvboundsGetCoefs( 3307 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 3308 ) 3309 { 3310 return vbounds != NULL ? vbounds->coefs : NULL; 3311 } 3312 3313 /** gets array of constants contained in given variable bounds data structure */ 3314 SCIP_Real* SCIPvboundsGetConstants( 3315 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */ 3316 ) 3317 { 3318 return vbounds != NULL ? vbounds->constants : NULL; 3319 } 3320 3321 /** gets number of implications for a given binary variable fixing */ 3322 int SCIPimplicsGetNImpls( 3323 SCIP_IMPLICS* implics, /**< implication data */ 3324 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 3325 ) 3326 { 3327 return implics != NULL ? implics->nimpls[varfixing] : 0; 3328 } 3329 3330 /** gets array with implied variables for a given binary variable fixing */ 3331 SCIP_VAR** SCIPimplicsGetVars( 3332 SCIP_IMPLICS* implics, /**< implication data */ 3333 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 3334 ) 3335 { 3336 return implics != NULL ? implics->vars[varfixing] : NULL; 3337 } 3338 3339 /** gets array with implication types for a given binary variable fixing */ 3340 SCIP_BOUNDTYPE* SCIPimplicsGetTypes( 3341 SCIP_IMPLICS* implics, /**< implication data */ 3342 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 3343 ) 3344 { 3345 return implics != NULL ? implics->types[varfixing] : NULL; 3346 } 3347 3348 /** gets array with implication bounds for a given binary variable fixing */ 3349 SCIP_Real* SCIPimplicsGetBounds( 3350 SCIP_IMPLICS* implics, /**< implication data */ 3351 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 3352 ) 3353 { 3354 return implics != NULL ? implics->bounds[varfixing] : NULL; 3355 } 3356 3357 /** Gets array with unique implication identifiers for a given binary variable fixing. 3358 * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication, 3359 * its id is negative, otherwise it is nonnegative. 3360 */ 3361 int* SCIPimplicsGetIds( 3362 SCIP_IMPLICS* implics, /**< implication data */ 3363 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */ 3364 ) 3365 { 3366 return implics != NULL ? implics->ids[varfixing] : NULL; 3367 } 3368 3369 /** gets number of variables in the cliques */ 3370 int SCIPcliqueGetNVars( 3371 SCIP_CLIQUE* clique /**< clique data structure */ 3372 ) 3373 { 3374 assert(clique != NULL); 3375 3376 return clique->nvars; 3377 } 3378 3379 /** gets array of active problem variables in the cliques */ 3380 SCIP_VAR** SCIPcliqueGetVars( 3381 SCIP_CLIQUE* clique /**< clique data structure */ 3382 ) 3383 { 3384 assert(clique != NULL); 3385 3386 return clique->vars; 3387 } 3388 3389 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or 3390 * to TRUE in the clique 3391 */ 3392 SCIP_Bool* SCIPcliqueGetValues( 3393 SCIP_CLIQUE* clique /**< clique data structure */ 3394 ) 3395 { 3396 assert(clique != NULL); 3397 3398 return clique->values; 3399 } 3400 3401 /** gets unique identifier of the clique */ 3402 unsigned int SCIPcliqueGetId( 3403 SCIP_CLIQUE* clique /**< clique data structure */ 3404 ) 3405 { 3406 unsigned int id; 3407 3408 assert(clique != NULL); 3409 3410 id = clique->id; /*lint !e732*/ 3411 3412 return id; 3413 } 3414 3415 /** gets index of the clique in the clique table */ 3416 int SCIPcliqueGetIndex( 3417 SCIP_CLIQUE* clique /**< clique data structure */ 3418 ) 3419 { 3420 assert(clique != NULL); 3421 3422 return clique->index; 3423 } 3424 3425 /** gets unique identifier of the clique */ 3426 SCIP_Bool SCIPcliqueIsCleanedUp( 3427 SCIP_CLIQUE* clique /**< clique data structure */ 3428 ) 3429 { 3430 assert(clique != NULL); 3431 3432 return (clique->startcleanup == -1); 3433 } 3434 3435 /** return whether the given clique is an equation */ 3436 SCIP_Bool SCIPcliqueIsEquation( 3437 SCIP_CLIQUE* clique /**< clique data structure */ 3438 ) 3439 { 3440 assert(clique != NULL); 3441 3442 return (SCIP_Bool)(clique->equation); /*lint !e571*/ 3443 } 3444 3445 /** returns the number of cliques stored in the clique list */ 3446 int SCIPcliquelistGetNCliques( 3447 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 3448 SCIP_Bool value /**< value of the variable for which the cliques should be returned */ 3449 ) 3450 { 3451 return cliquelist != NULL ? cliquelist->ncliques[value] : 0; 3452 } 3453 3454 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */ 3455 SCIP_CLIQUE** SCIPcliquelistGetCliques( 3456 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 3457 SCIP_Bool value /**< value of the variable for which the cliques should be returned */ 3458 ) 3459 { 3460 return cliquelist != NULL ? cliquelist->cliques[value] : NULL; 3461 } 3462 3463 /** checks whether variable is contained in all cliques of the cliquelist */ 3464 void SCIPcliquelistCheck( 3465 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */ 3466 SCIP_VAR* var /**< variable, the clique list belongs to */ 3467 ) 3468 { 3469 /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for 3470 * correctness 3471 */ 3472 #ifndef NDEBUG 3473 int value; 3474 3475 assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE)); 3476 assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE)); 3477 assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE)); 3478 assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE)); 3479 3480 for( value = 0; value < 2; ++value ) 3481 { 3482 SCIP_CLIQUE** cliques; 3483 int ncliques; 3484 int i; 3485 3486 ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value); 3487 cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value); 3488 for( i = 0; i < ncliques; ++i ) 3489 { 3490 SCIP_CLIQUE* clique; 3491 int pos; 3492 3493 clique = cliques[i]; 3494 assert(clique != NULL); 3495 3496 pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value); 3497 assert(0 <= pos && pos < clique->nvars); 3498 assert(clique->vars[pos] == var); 3499 assert(clique->values[pos] == (SCIP_Bool)value); 3500 } 3501 } 3502 #endif 3503 } 3504 3505 /** gets the number of cliques stored in the clique table */ 3506 int SCIPcliquetableGetNCliques( 3507 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3508 ) 3509 { 3510 assert(cliquetable != NULL); 3511 3512 return cliquetable->ncliques; 3513 } 3514 3515 /** gets the number of cliques created so far by the clique table */ 3516 int SCIPcliquetableGetNCliquesCreated( 3517 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3518 ) 3519 { 3520 assert(cliquetable != NULL); 3521 3522 return cliquetable->ncreatedcliques; 3523 } 3524 3525 /** gets the array of cliques stored in the clique table */ 3526 SCIP_CLIQUE** SCIPcliquetableGetCliques( 3527 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3528 ) 3529 { 3530 assert(cliquetable != NULL); 3531 3532 return cliquetable->cliques; 3533 } 3534 3535 /** gets the number of entries in the whole clique table */ 3536 SCIP_Longint SCIPcliquetableGetNEntries( 3537 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3538 ) 3539 { 3540 assert(cliquetable != NULL); 3541 3542 return cliquetable->nentries; 3543 } 3544 3545 /** returns the number of clique components, or -1 if update is necessary first */ 3546 int SCIPcliquetableGetNCliqueComponents( 3547 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3548 ) 3549 { 3550 return cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents; 3551 } 3552 3553 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */ 3554 SCIP_Bool SCIPcliquetableNeedsComponentUpdate( 3555 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */ 3556 ) 3557 { 3558 return cliquetable->compsfromscratch || cliquetable->djset == NULL; 3559 } 3560