1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file sepa_clique.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief clique separator 28 * @author Kati Wolter 29 * @author Tobias Achterberg 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/pub_implics.h" 36 #include "scip/pub_lp.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_sepa.h" 40 #include "scip/pub_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_cut.h" 43 #include "scip/scip_general.h" 44 #include "scip/scip_lp.h" 45 #include "scip/scip_mem.h" 46 #include "scip/scip_message.h" 47 #include "scip/scip_numerics.h" 48 #include "scip/scip_param.h" 49 #include "scip/scip_prob.h" 50 #include "scip/scip_sepa.h" 51 #include "scip/scip_sol.h" 52 #include "scip/scip_var.h" 53 #include "scip/sepa_clique.h" 54 #include "tclique/tclique.h" 55 #include <string.h> 56 #if defined(_WIN32) || defined(_WIN64) 57 #else 58 #include <strings.h> /*lint --e{766}*/ 59 #endif 60 61 62 #define SEPA_NAME "clique" 63 #define SEPA_DESC "clique separator of stable set relaxation" 64 #define SEPA_PRIORITY -5000 65 #define SEPA_FREQ 0 66 #define SEPA_MAXBOUNDDIST 0.0 67 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 68 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 69 70 #define DEFAULT_SCALEVAL 1000.0 /**< factor for scaling weights */ 71 #define DEFAULT_MAXTREENODES 10000 /**< maximal number of nodes in branch and bound tree (-1: no limit) */ 72 #define DEFAULT_BACKTRACKFREQ 1000 /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */ 73 #define DEFAULT_MAXSEPACUTS 10 /**< maximal number of clique cuts separated per separation round (-1: no limit) */ 74 #define DEFAULT_MAXZEROEXTENSIONS 1000 /**< maximal number of zero-valued variables extending the clique (-1: no limit) */ 75 #define DEFAULT_CLIQUETABLEMEM 20000.0 /**< maximal memory size of dense clique table (in kb) */ 76 #define DEFAULT_CLIQUEDENSITY 0.00 /**< minimal density of cliques to use a dense clique table */ 77 78 79 /* 80 * Data structures 81 */ 82 83 /** separator data */ 84 struct SCIP_SepaData 85 { 86 TCLIQUE_GRAPH* tcliquegraph; /**< tclique graph data structure */ 87 SCIP* scip; /**< SCIP data structure */ 88 SCIP_SEPA* sepa; /**< separator */ 89 SCIP_SOL* sol; /**< primal solution that is currently separated */ 90 SCIP_Real* varsolvals; /**< LP solution of binary variables (contained in a 3-clique in implgraph) */ 91 SCIP_Real scaleval; /**< factor for scaling weights */ 92 SCIP_Longint ncalls; /**< number of calls to the clique separator */ 93 int maxtreenodes; /**< maximal number of nodes in branch and bound tree (-1: no limit) */ 94 int backtrackfreq; /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */ 95 int maxsepacuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */ 96 int maxzeroextensions; /**< maximal number of zero-valued variables extending the clique (-1: no limit) */ 97 SCIP_Real cliquetablemem; /**< maximal memory size of dense clique table (in kb) */ 98 SCIP_Real cliquedensity; /**< minimal density of cliques to use a dense clique table */ 99 int ncuts; /**< number of cuts found */ 100 SCIP_Bool tcliquegraphloaded; /**< TRUE if tcliquegraph is already loaded (tcliquegraph can be NULL), 101 * FALSE otherwise */ 102 SCIP_Bool cutoff; /**< whether the clique algorithm detected a cutoff */ 103 SCIP_RETCODE retcode; /**< error code which might occur during the maximal clique algorithm */ 104 }; 105 106 /** tclique graph data */ 107 struct TCLIQUE_Graph 108 { 109 SCIP_VAR** vars; /**< active problem variables (or negated variables) the nodes belong to */ 110 TCLIQUE_WEIGHT* weights; /**< weight of nodes */ 111 int* adjnodesidxs; /**< indices in adjnodes array of first adjacent nodes for each node */ 112 int* cliqueidsidxs; /**< indices in cliqueids array of first clique the node is contained in */ 113 int* adjnodes; /**< adjacent nodes of edges */ 114 unsigned int* cliqueids; /**< unique ids of cliques */ 115 unsigned int* cliquetable; /**< dense bitvector clique table (array stored as a vector) */ 116 int adjnodessize; /**< size of adjnodes array */ 117 int cliqueidssize; /**< size of cliqueids array */ 118 int nnodes; /**< number of nodes in graph */ 119 int tablewidth; /**< number of unsigned ints per row in the table */ 120 121 int maxnnodes; /**< allocated memory for some arrays */ 122 }; 123 124 125 /* 126 * Methods for tclique graph 127 */ 128 129 /** creates an empty tclique graph data structure */ 130 static 131 SCIP_RETCODE tcliquegraphCreate( 132 SCIP* scip, /**< SCIP data structure */ 133 TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */ 134 ) 135 { 136 int maxnnodes; 137 138 assert(tcliquegraph != NULL); 139 140 SCIP_CALL( SCIPallocBlockMemory(scip, tcliquegraph) ); 141 142 /* there are at most 2*nbinvars nodes in the graph */ 143 maxnnodes = 2*SCIPgetNBinVars(scip); 144 assert(maxnnodes > 0); 145 146 /* allocate memory for tclique graph arrays */ 147 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->vars, maxnnodes) ); 148 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->weights, maxnnodes) ); 149 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, maxnnodes+1) ); 150 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, maxnnodes+1) ); 151 (*tcliquegraph)->adjnodesidxs[0] = 0; /* the last slot defines the end of the last node */ 152 (*tcliquegraph)->cliqueidsidxs[0] = 0; /* the last slot defines the end of the last node */ 153 (*tcliquegraph)->adjnodes = NULL; 154 (*tcliquegraph)->cliqueids = NULL; 155 (*tcliquegraph)->cliquetable = NULL; 156 (*tcliquegraph)->adjnodessize = 0; 157 (*tcliquegraph)->cliqueidssize = 0; 158 (*tcliquegraph)->nnodes = 0; 159 (*tcliquegraph)->tablewidth = 0; 160 (*tcliquegraph)->maxnnodes = maxnnodes; /* remember allocated memory */ 161 162 return SCIP_OKAY; 163 } 164 165 /** frees the tclique graph data structure and releases all captured variables */ 166 static 167 SCIP_RETCODE tcliquegraphFree( 168 SCIP* scip, /**< SCIP data structure */ 169 TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */ 170 ) 171 { 172 int v; 173 174 assert(tcliquegraph != NULL); 175 assert(*tcliquegraph != NULL); 176 177 /* release variables */ 178 for( v = 0; v < (*tcliquegraph)->nnodes; ++v ) 179 { 180 SCIP_CALL( SCIPreleaseVar(scip, &(*tcliquegraph)->vars[v]) ); 181 } 182 183 /* free memory */ 184 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->vars, (*tcliquegraph)->maxnnodes); 185 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->weights, (*tcliquegraph)->maxnnodes); 186 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, (*tcliquegraph)->maxnnodes + 1); 187 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, (*tcliquegraph)->maxnnodes + 1); 188 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->adjnodes); 189 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliqueids); 190 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliquetable); 191 SCIPfreeBlockMemory(scip, tcliquegraph); 192 193 return SCIP_OKAY; 194 } 195 196 197 /** ensures that the cliqueids array can store at least num entries */ 198 static 199 SCIP_RETCODE tcliquegraphEnsureCliqueidsSize( 200 SCIP* scip, /**< SCIP data structure */ 201 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */ 202 int num /**< minimal number of adjacent nodes to be able to store in the array */ 203 ) 204 { 205 assert(tcliquegraph != NULL); 206 207 if( num > tcliquegraph->cliqueidssize ) 208 { 209 tcliquegraph->cliqueidssize = SCIPcalcMemGrowSize(scip, num); 210 SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->cliqueids, tcliquegraph->cliqueidssize) ); 211 } 212 assert(num <= tcliquegraph->cliqueidssize); 213 214 return SCIP_OKAY; 215 } 216 217 /** adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the 218 * variable is contained in with the given value 219 */ 220 static 221 SCIP_RETCODE tcliquegraphAddNode( 222 SCIP* scip, /**< SCIP data structure */ 223 TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */ 224 SCIP_VAR* var, /**< active binary problem variable */ 225 SCIP_Bool value, /**< value of the variable in the node */ 226 int* nodeidx /**< pointer to store the index of the new node */ 227 ) 228 { 229 SCIP_VAR* nodevar; 230 unsigned int* cliqueids; 231 SCIP_CLIQUE** cliques; 232 int ncliques; 233 int nadjnodes; 234 int ncliqueids; 235 int i; 236 237 assert(tcliquegraph != NULL); 238 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY); 239 assert(SCIPvarIsActive(var)); 240 assert(nodeidx != NULL); 241 242 /* create tclique graph data if not yet existing */ 243 if( *tcliquegraph == NULL ) 244 { 245 SCIP_CALL( tcliquegraphCreate(scip, tcliquegraph) ); 246 } 247 assert(*tcliquegraph != NULL); 248 assert((*tcliquegraph)->nnodes < 2*SCIPgetNBinVars(scip)); 249 250 /* if the value is FALSE, use the negated variable for the node */ 251 if( !value ) 252 { 253 SCIP_CALL( SCIPgetNegatedVar(scip, var, &nodevar) ); 254 } 255 else 256 nodevar = var; 257 258 /* get the current number of used entries in adjnodes and cliqueids arrays */ 259 nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes]; 260 ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes]; 261 262 /* insert the variable into the tclique graph */ 263 *nodeidx = (*tcliquegraph)->nnodes; 264 SCIP_CALL( SCIPcaptureVar(scip, nodevar) ); 265 (*tcliquegraph)->vars[*nodeidx] = nodevar; 266 (*tcliquegraph)->weights[*nodeidx] = 0; 267 (*tcliquegraph)->nnodes++; 268 269 /* store the ids of the variable's cliques in the cliqueids array */ 270 ncliques = SCIPvarGetNCliques(var, value); 271 cliques = SCIPvarGetCliques(var, value); 272 SCIP_CALL( tcliquegraphEnsureCliqueidsSize(scip, *tcliquegraph, ncliqueids + ncliques) ); 273 cliqueids = (*tcliquegraph)->cliqueids; 274 for( i = 0; i < ncliques; ++i ) 275 { 276 assert(ncliqueids < (*tcliquegraph)->cliqueidssize); 277 cliqueids[ncliqueids] = SCIPcliqueGetId(cliques[i]); 278 assert(i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]); 279 ncliqueids++; 280 } 281 282 /* store the new number of used entries in adjnodes and cliqueids arrays */ 283 (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes; 284 (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids; 285 286 return SCIP_OKAY; 287 } 288 289 /** adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique */ 290 static 291 SCIP_RETCODE tcliquegraphAddCliqueVars( 292 SCIP* scip, /**< SCIP data structure */ 293 TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */ 294 int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */ 295 ) 296 { 297 SCIP_VAR** vars; 298 int nvars; 299 int i; 300 301 assert(tcliquegraph != NULL); 302 assert(cliquegraphidx != NULL); 303 assert(cliquegraphidx[0] != NULL); 304 assert(cliquegraphidx[1] != NULL); 305 306 /* get binary problem variables */ 307 vars = SCIPgetVars(scip); 308 nvars = SCIPgetNBinVars(scip); 309 310 for( i = 0; i < nvars; ++i ) 311 { 312 SCIP_VAR* var; 313 int value; 314 315 var = vars[i]; 316 317 for( value = 0; value < 2; ++value ) 318 { 319 assert(cliquegraphidx[value][i] == -1); 320 321 if( SCIPvarGetNCliques(var, (SCIP_Bool)value) >= 1 ) 322 { 323 /* all cliques stored in the clique table are at least 3-cliques */ 324 SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, var, (SCIP_Bool)value, &cliquegraphidx[value][i]) ); 325 } 326 } 327 } 328 329 return SCIP_OKAY; 330 } 331 332 /** constructs dense clique incidence matrix 333 * 334 * @todo add implicit and integer variables appearing in cliques also to the clique table 335 */ 336 static 337 SCIP_RETCODE tcliquegraphConstructCliqueTable( 338 SCIP* scip, /**< SCIP data structure */ 339 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */ 340 SCIP_Real cliquetablemem, /**< maximal memory size of dense clique table (in kb) */ 341 SCIP_Real cliquedensity /**< minimal density of cliques to store as dense table */ 342 ) 343 { 344 SCIP_CLIQUE** cliques; 345 int* varids; 346 unsigned int* cliquetable; 347 SCIP_Real density; 348 int nbits; 349 int tablesize; 350 int tablewidth; 351 int ncliques; 352 int nelems; 353 int i; 354 355 cliques = SCIPgetCliques(scip); 356 ncliques = SCIPgetNCliques(scip); 357 if( ncliques == 0 ) 358 return SCIP_OKAY; 359 360 assert(tcliquegraph != NULL); 361 362 /* calculate size of dense clique table */ 363 nbits = 8*sizeof(unsigned int); 364 tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits; /* number of ints needed */ 365 366 /* check if dense clique table is too large (calculate as Reals to avoid overflow) */ 367 if( (SCIP_Real)tcliquegraph->nnodes * (SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem ) 368 return SCIP_OKAY; 369 370 /* calculate clique entry density */ 371 nelems = 0; 372 for( i = 0; i < ncliques; ++i ) 373 nelems += SCIPcliqueGetNVars(cliques[i]); 374 density = (SCIP_Real)nelems / ((SCIP_Real)ncliques * (SCIP_Real)tcliquegraph->nnodes); 375 if( density < cliquedensity ) 376 return SCIP_OKAY; 377 378 /* allocate memory */ 379 tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth; 380 SCIPdebugMsg(scip, "clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n", 381 tablesize/1024, SCIPgetNCliques(scip), tcliquegraph->nnodes, density); 382 383 SCIP_CALL( SCIPallocMemoryArray(scip, &tcliquegraph->cliquetable, tablesize) ); 384 BMSclearMemoryArray(tcliquegraph->cliquetable, tablesize); 385 386 /* insert the cliques as complete graphs to the incidence matrix */ 387 SCIP_CALL( SCIPallocBufferArray(scip, &varids, tcliquegraph->nnodes) ); 388 cliquetable = tcliquegraph->cliquetable; 389 tablewidth = tcliquegraph->tablewidth; 390 for( i = 0; i < ncliques && !SCIPisStopped(scip); ++i ) 391 { 392 SCIP_VAR** vars; 393 SCIP_Bool* vals; 394 int nvars; 395 int u; 396 int v; 397 398 vars = SCIPcliqueGetVars(cliques[i]); 399 vals = SCIPcliqueGetValues(cliques[i]); 400 nvars = SCIPcliqueGetNVars(cliques[i]); 401 402 /* get the node numbers of the variables */ 403 for( u = 0; u < nvars && !SCIPisStopped(scip); ++u ) 404 { 405 SCIP_VAR* var; 406 407 /* implicit integer and integer variables are currently not present in the constructed tclique graph */ 408 if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY ) 409 continue; 410 411 var = (vals[u] ? vars[u] : SCIPvarGetNegatedVar(vars[u])); 412 assert(var != NULL); /* var must exist even if negated, since it is stored in the tcliquegraph */ 413 for( v = 0; v < tcliquegraph->nnodes && var != tcliquegraph->vars[v]; ++v ) 414 {} 415 assert(v < tcliquegraph->nnodes); 416 varids[u] = v; 417 } 418 419 /* flag the edges in the incidence matrix (excluding diagonal entries) */ 420 for( u = 0; u < nvars-1 && !SCIPisStopped(scip); ++u ) 421 { 422 int nu; 423 int rowstart; 424 int colofs; 425 unsigned int colmask; 426 427 /* implicit integer and integer variables are currently not present in the constructed tclique graph */ 428 if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY ) 429 continue; 430 431 nu = varids[u]; 432 rowstart = nu*tablewidth; 433 colofs = nu/nbits; 434 colmask = 1U << (nu % nbits); /*lint !e701*/ 435 for( v = u+1; v < nvars; ++v ) 436 { 437 int nv; 438 unsigned int mask; 439 440 /* implicit integer and integer variables are currently not present in the constructed tclique graph */ 441 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_BINARY ) 442 continue; 443 444 nv = varids[v]; 445 mask = 1U << (nv % nbits); /*lint !e701*/ 446 cliquetable[rowstart+nv/nbits] |= mask; 447 cliquetable[nv*tablewidth+colofs] |= colmask; 448 } 449 } 450 } 451 SCIPfreeBufferArray(scip, &varids); 452 453 SCIPdebugMsg(scip, "clique separator: finished constructing dense clique table\n"); 454 455 return SCIP_OKAY; 456 } 457 458 /** creates tclique data structure using the implication graph; 459 * only variables that are contained in a 3-clique are added as nodes to the clique graph 460 */ 461 static 462 SCIP_RETCODE loadTcliquegraph( 463 SCIP* scip, /**< SCIP data structure */ 464 SCIP_SEPADATA* sepadata /**< separator data */ 465 ) 466 { 467 int* cliquegraphidx[2]; 468 int nvars; 469 int i; 470 471 assert(sepadata != NULL); 472 assert(sepadata->tcliquegraph == NULL); 473 474 /* there is nothing to do, if no binary variables are present in the problem */ 475 nvars = SCIPgetNBinVars(scip); 476 if( nvars == 0 ) 477 return SCIP_OKAY; 478 479 /* get temporary memory for mapping variable/value pairs to clique graph nodes */ 480 SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[0], nvars) ); 481 SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[1], nvars) ); 482 for( i = 0; i < nvars; ++i ) 483 { 484 cliquegraphidx[0][i] = -1; 485 cliquegraphidx[1][i] = -1; 486 } 487 488 /* insert all variable/value pairs that are contained in an existing 3-clique */ 489 SCIP_CALL( tcliquegraphAddCliqueVars(scip, &sepadata->tcliquegraph, cliquegraphidx) ); 490 491 /* it occurs that it might be that some cliques were not yet removed from the global clique array, so SCIPgetNClique 492 * can be greater than 0, even if there is no clique with some variables left */ 493 /** @todo clean up empty cliques */ 494 if( sepadata->tcliquegraph != NULL ) 495 { 496 /* construct the dense clique table */ 497 SCIP_CALL( tcliquegraphConstructCliqueTable(scip, sepadata->tcliquegraph, sepadata->cliquetablemem, sepadata->cliquedensity) ); 498 } 499 500 /* free temporary memory */ 501 SCIPfreeBufferArray(scip, &cliquegraphidx[1]); 502 SCIPfreeBufferArray(scip, &cliquegraphidx[0]); 503 if( SCIPisStopped(scip) && sepadata->tcliquegraph != NULL ) 504 SCIP_CALL( tcliquegraphFree(scip,&sepadata->tcliquegraph) ); 505 return SCIP_OKAY; 506 } 507 508 /** updates the weights in the tclique graph data structure */ 509 static 510 void updateTcliquegraph( 511 SCIP* scip, /**< SCIP data structure */ 512 SCIP_SEPADATA* sepadata /**< separator data */ 513 ) 514 { 515 TCLIQUE_GRAPH* tcliquegraph; 516 int i; 517 518 assert(sepadata != NULL); 519 assert(sepadata->varsolvals != NULL); 520 521 tcliquegraph = sepadata->tcliquegraph; 522 assert(tcliquegraph != NULL); 523 524 /* updates weight of all nodes in tclique data structure */ 525 for( i = 0; i < tcliquegraph->nnodes; i++ ) 526 { 527 int weight; 528 529 weight = (TCLIQUE_WEIGHT)SCIPfeasFloor(scip, sepadata->varsolvals[i] * sepadata->scaleval); 530 tcliquegraph->weights[i] = MAX(weight, 0); 531 } 532 } 533 534 535 /* 536 * TClique Graph Callbacks 537 */ 538 539 /** gets number of nodes in the graph */ 540 static 541 TCLIQUE_GETNNODES(tcliqueGetnnodesClique) 542 { 543 assert(tcliquegraph != NULL); 544 545 return tcliquegraph->nnodes; 546 } 547 548 /** gets weight of nodes in the graph */ 549 static 550 TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique) 551 { 552 assert(tcliquegraph != NULL); 553 554 return tcliquegraph->weights; 555 } 556 557 /** returns whether the nodes are member of a common clique */ 558 static 559 SCIP_Bool nodesHaveCommonClique( 560 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */ 561 int node1, /**< first node */ 562 int node2 /**< second node */ 563 ) 564 { 565 assert(tcliquegraph != NULL); 566 567 /* return TRUE for equal nodes */ 568 if( node1 == node2 ) 569 return TRUE; 570 571 /* check whether the dense clique table was constructed */ 572 if( tcliquegraph->cliquetable != NULL ) 573 { 574 int nbits; 575 unsigned int mask; 576 int colofs; 577 578 /* check entry in the table */ 579 nbits = 8*sizeof(unsigned int); 580 mask = (1U << (node2 % nbits)); /*lint !e701*/ 581 colofs = node2 / nbits; 582 assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0) 583 == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1U << (node1 % nbits))) != 0)); /*lint !e701*/ 584 return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0); 585 } 586 else 587 { 588 unsigned int* cliqueids; 589 int i1; 590 int i2; 591 int endi1; 592 int endi2; 593 594 cliqueids = tcliquegraph->cliqueids; 595 i1 = tcliquegraph->cliqueidsidxs[node1]; 596 endi1 = tcliquegraph->cliqueidsidxs[node1+1]; 597 i2 = tcliquegraph->cliqueidsidxs[node2]; 598 endi2 = tcliquegraph->cliqueidsidxs[node2+1]; 599 while( i1 < endi1 && i2 < endi2 ) 600 { 601 while( i1 < endi1 && cliqueids[i1] < cliqueids[i2] ) 602 i1++; 603 if( i1 == endi1 ) 604 break; 605 606 while( i2 < endi2 && cliqueids[i2] < cliqueids[i1] ) 607 i2++; 608 if( i2 == endi2 ) 609 break; 610 611 if( cliqueids[i1] == cliqueids[i2] ) 612 return TRUE; 613 } 614 615 return FALSE; 616 } 617 } 618 619 /** returns, whether the edge (node1, node2) is in the graph */ 620 static 621 TCLIQUE_ISEDGE(tcliqueIsedgeClique) 622 { 623 int left; 624 int right; 625 626 assert(tcliquegraph != NULL); 627 assert(0 <= node1 && node1 < tcliquegraph->nnodes); 628 assert(0 <= node2 && node2 < tcliquegraph->nnodes); 629 630 /* check if node2 is contained in adjacency list of node1 (list is ordered by adjacent nodes) */ 631 left = tcliquegraph->adjnodesidxs[node1]; 632 right = tcliquegraph->adjnodesidxs[node1+1]-1; 633 while( left <= right ) 634 { 635 int middle; 636 int node; 637 638 middle = (left+right)/2; 639 node = tcliquegraph->adjnodes[middle]; 640 if( node < node2 ) 641 left = middle+1; 642 else if( node > node2 ) 643 right = middle-1; 644 else 645 return TRUE; 646 } 647 648 /* check if the nodes are member of a common clique */ 649 return nodesHaveCommonClique(tcliquegraph, node1, node2); 650 } 651 652 /** selects all nodes from a given set of nodes which are adjacent to a given node 653 * and returns the number of selected nodes 654 */ 655 static 656 TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique) 657 { 658 int* graphadjnodes; 659 int nadjnodes; 660 int nodeadjindex; 661 int nodeadjend; 662 int i; 663 664 assert(tcliquegraph != NULL); 665 assert(0 <= node && node < tcliquegraph->nnodes); 666 assert(nnodes == 0 || nodes != NULL); 667 assert(adjnodes != NULL); 668 669 nadjnodes = 0; 670 671 /* check for each node in given nodes set, if it is adjacent to the given node or shares a common clique */ 672 graphadjnodes = tcliquegraph->adjnodes; 673 nodeadjindex = tcliquegraph->adjnodesidxs[node]; 674 nodeadjend = tcliquegraph->adjnodesidxs[node+1]; 675 for( i = 0; i < nnodes; i++ ) 676 { 677 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */ 678 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes); 679 assert(i == 0 || nodes[i-1] < nodes[i]); 680 while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[i] ) 681 nodeadjindex++; 682 if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[i] ) 683 { 684 /* current node is adjacent to given node */ 685 adjnodes[nadjnodes] = nodes[i]; 686 nadjnodes++; 687 } 688 else 689 { 690 /* current node is not adjacent to given node: check if they share a common clique */ 691 if( nodesHaveCommonClique(tcliquegraph, node, nodes[i]) ) 692 { 693 adjnodes[nadjnodes] = nodes[i]; 694 nadjnodes++; 695 } 696 } 697 } 698 699 return nadjnodes; 700 } 701 702 /** basic code for new cliques (needed because of error handling) */ 703 static 704 SCIP_RETCODE newsolCliqueAddRow( 705 SCIP* scip, /**< SCIP data structure */ 706 SCIP_SEPA* sepa, /**< the cut separator itself */ 707 SCIP_SEPADATA* sepadata, /**< data of separator */ 708 int ncliquenodes, /**< number of nodes in clique */ 709 int* cliquenodes /**< nodes in clique */ 710 ) 711 { 712 SCIP_VAR** vars; 713 SCIP_ROW* cut; 714 char cutname[SCIP_MAXSTRLEN]; 715 int i; 716 717 vars = sepadata->tcliquegraph->vars; 718 assert(sepadata->tcliquegraph->nnodes > 0); 719 assert(vars != NULL); 720 721 /* create the cut (handle retcode since we do not have a backtrace) */ 722 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "clique%" SCIP_LONGINT_FORMAT "_%d", sepadata->ncalls, sepadata->ncuts); 723 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) ); 724 725 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 726 727 assert(ncliquenodes <= sepadata->tcliquegraph->nnodes); 728 /*SCIPdebugMsg(scip, " -> clique in graph:");*/ 729 for( i = 0; i < ncliquenodes; ++i ) 730 { 731 assert(cliquenodes[i] < sepadata->tcliquegraph->nnodes); 732 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cliquenodes[i]], 1.0) ); 733 /*SCIPdebugMsgPrint(scip, " [%d]<%s>", cliquenodes[i], SCIPvarGetName(vars[cliquenodes[i]]));*/ 734 } 735 /*SCIPdebugMsgPrint(scip, "\n");*/ 736 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 737 738 /* set cut rank: for clique cuts we always set to 1 */ 739 SCIProwChgRank(cut, 1); 740 741 /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/ 742 743 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 744 745 /* release the row */ 746 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 747 748 return SCIP_OKAY; 749 } 750 751 /** generates cuts using a clique found by algorithm for maximum weight clique 752 * and decides whether to stop generating cliques with the algorithm for maximum weight clique 753 */ 754 static 755 TCLIQUE_NEWSOL(tcliqueNewsolClique) 756 { 757 SCIP_SEPADATA* sepadata; 758 TCLIQUE_WEIGHT minweightinc; 759 760 assert(acceptsol != NULL); 761 assert(stopsolving != NULL); 762 763 sepadata = (SCIP_SEPADATA*)tcliquedata; 764 assert(sepadata != NULL); 765 assert(sepadata->scip != NULL); 766 assert(sepadata->sepa != NULL); 767 assert(sepadata->tcliquegraph != NULL); 768 assert(sepadata->ncuts >= 0); 769 770 /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */ 771 *acceptsol = FALSE; 772 *stopsolving = FALSE; 773 774 /* slightly increase the minimal weight for additional cliques */ 775 minweightinc = (cliqueweight - *minweight)/10; 776 minweightinc = MAX(minweightinc, 1); 777 *minweight += minweightinc; 778 779 /* adds cut if weight of the clique is greater than 1 */ 780 if( cliqueweight > sepadata->scaleval ) 781 { 782 SCIP* scip; 783 SCIP_SEPA* sepa; 784 SCIP_Real* varsolvals; 785 SCIP_Real unscaledweight; 786 int i; 787 788 scip = sepadata->scip; 789 sepa = sepadata->sepa; 790 varsolvals = sepadata->varsolvals; 791 assert(varsolvals != NULL); 792 793 /* calculate the weight of the clique in unscaled fractional variable space */ 794 unscaledweight = 0.0; 795 for( i = 0; i < ncliquenodes; i++ ) 796 unscaledweight += varsolvals[cliquenodes[i]]; 797 798 if( SCIPisEfficacious(scip, unscaledweight - 1.0) ) 799 { 800 SCIP_RETCODE retcode; 801 802 /* explicitly handle return code */ 803 retcode = newsolCliqueAddRow(scip, sepa, sepadata, ncliquenodes, cliquenodes); 804 if ( retcode == SCIP_OKAY ) 805 { 806 SCIPdebugMsg(scip, " -> found clique cut (act=%g)\n", unscaledweight); 807 sepadata->ncuts++; 808 809 /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent, 810 * such that only more violated cuts are generated afterwards */ 811 if( sepadata->maxsepacuts >= 0 ) 812 { 813 if( sepadata->ncuts > sepadata->maxsepacuts/2 ) 814 *acceptsol = TRUE; 815 if( sepadata->ncuts >= sepadata->maxsepacuts ) 816 *stopsolving = TRUE; 817 } 818 } 819 else 820 { 821 /* in case an internal SCIP error occurred we stop the algorithm and store the error code for later 822 * evaluation 823 */ 824 sepadata->retcode = retcode; 825 *stopsolving = TRUE; 826 } 827 } 828 } 829 } 830 831 832 /* 833 * main separation method 834 */ 835 836 /** searches and adds clique cuts that separate the given primal solution 837 * 838 * @todo Should the existing cliques in the table be separated before starting the tclique algorithm? 839 * Is this done somewhere else? 840 */ 841 static 842 SCIP_RETCODE separateCuts( 843 SCIP* scip, /**< SCIP data structure */ 844 SCIP_SEPA* sepa, /**< the cut separator itself */ 845 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */ 846 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 847 ) 848 { /*lint --e{715}*/ 849 SCIP_SEPADATA* sepadata; 850 TCLIQUE_GRAPH* tcliquegraph; 851 int* cliquenodes; 852 TCLIQUE_WEIGHT cliqueweight; 853 TCLIQUE_STATUS tcliquestatus; 854 int ncliquenodes; 855 int maxtreenodes; 856 int maxzeroextensions; 857 SCIP_Bool infeasible; 858 859 assert(scip != NULL); 860 assert(*result == SCIP_DIDNOTRUN); 861 862 infeasible = FALSE; 863 /* get clique table */ 864 SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) ); 865 if( infeasible ) 866 return SCIP_OKAY; 867 868 /* get separator data */ 869 sepadata = SCIPsepaGetData(sepa); 870 assert(sepadata != NULL); 871 872 sepadata->sol = sol; 873 sepadata->ncalls = SCIPsepaGetNCalls(sepa); 874 sepadata->cutoff = FALSE; 875 sepadata->ncuts = 0; 876 877 /* if we already detected that no implications between binary variables exist, nothing has to be done */ 878 if( sepadata->tcliquegraph == NULL && sepadata->tcliquegraphloaded ) 879 return SCIP_OKAY; 880 881 *result = SCIP_DIDNOTFIND; 882 883 /* load tclique data structure */ 884 if( !sepadata->tcliquegraphloaded ) 885 { 886 assert(sepadata->tcliquegraph == NULL); 887 888 SCIPdebugMsg(scip, "loading implication and clique graph\n"); 889 SCIP_CALL( loadTcliquegraph(scip, sepadata) ); 890 sepadata->tcliquegraphloaded = TRUE; 891 892 if( sepadata->tcliquegraph == NULL ) 893 { 894 if( SCIPisStopped(scip) ) 895 sepadata->tcliquegraphloaded = FALSE; 896 /* we did not find any variables that are contained in a clique with at least 3 variables in the 897 * implication graph or in the clique table -> nothing has to be done 898 */ 899 else 900 { 901 SCIPdebugMsg(scip, "no 3-cliques found in implication graph\n"); 902 } 903 904 return SCIP_OKAY; 905 } 906 } 907 tcliquegraph = sepadata->tcliquegraph; 908 assert(tcliquegraph != NULL); 909 910 /* store LP-solution in sepadata and update weights in tclique data structure */ 911 SCIP_CALL( SCIPallocBufferArray(scip, &sepadata->varsolvals, tcliquegraph->nnodes) ); 912 SCIP_CALL( SCIPgetSolVals(scip, sol, tcliquegraph->nnodes, tcliquegraph->vars, sepadata->varsolvals) ); 913 updateTcliquegraph(scip, sepadata); 914 915 /* get maximal number of tree nodes and maximal zero-extensions */ 916 maxtreenodes = (sepadata->maxtreenodes == -1 ? INT_MAX : sepadata->maxtreenodes); 917 maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions); 918 919 SCIPdebugMsg(scip, "searching for violated clique cuts\n"); 920 921 sepadata->retcode = SCIP_OKAY; 922 923 /* finds maximum weight clique in tclique */ 924 SCIP_CALL( SCIPallocBufferArray(scip, &cliquenodes, tcliquegraph->nnodes) ); 925 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique, 926 tcliquegraph, tcliqueNewsolClique, (TCLIQUE_DATA*)sepadata, 927 cliquenodes, &ncliquenodes, &cliqueweight, (int)sepadata->scaleval-1, (int)sepadata->scaleval+1, 928 maxtreenodes, sepadata->backtrackfreq, maxzeroextensions, -1, NULL, &tcliquestatus); 929 930 /* in case an internal error occurred during the maximal clique computation, evaluate that one */ 931 SCIP_CALL( sepadata->retcode ); 932 933 SCIPdebugMsg(scip, "finished searching clique cuts: found %d cuts\n", sepadata->ncuts); 934 935 /* frees data structures */ 936 SCIPfreeBufferArray(scip, &cliquenodes); 937 SCIPfreeBufferArray(scip, &sepadata->varsolvals); 938 939 /* adjust result code */ 940 if ( sepadata->cutoff ) 941 *result = SCIP_CUTOFF; 942 else if( sepadata->ncuts > 0 ) 943 *result = SCIP_SEPARATED; 944 945 /* better reset the sol pointer in sepadata to avoid having an invalid pointer */ 946 sepadata->sol = NULL; 947 948 return SCIP_OKAY; 949 } 950 951 952 /* 953 * Callback methods of separator 954 */ 955 956 /** copy method for separator plugins (called when SCIP copies plugins) */ 957 static 958 SCIP_DECL_SEPACOPY(sepaCopyClique) 959 { /*lint --e{715}*/ 960 assert(scip != NULL); 961 assert(sepa != NULL); 962 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 963 964 /* call inclusion method of constraint handler */ 965 SCIP_CALL( SCIPincludeSepaClique(scip) ); 966 967 return SCIP_OKAY; 968 } 969 970 971 /** destructor of separator to free user data (called when SCIP is exiting) */ 972 static 973 SCIP_DECL_SEPAFREE(sepaFreeClique) 974 { /*lint --e{715}*/ 975 SCIP_SEPADATA* sepadata; 976 977 sepadata = SCIPsepaGetData(sepa); 978 assert(sepadata != NULL); 979 assert(sepadata->tcliquegraph == NULL); 980 981 SCIPfreeBlockMemory(scip, &sepadata); 982 SCIPsepaSetData(sepa, NULL); 983 984 return SCIP_OKAY; 985 } 986 987 988 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */ 989 static 990 SCIP_DECL_SEPAEXITSOL(sepaExitsolClique) 991 { /*lint --e{715}*/ 992 SCIP_SEPADATA* sepadata; 993 994 sepadata = SCIPsepaGetData(sepa); 995 assert(sepadata != NULL); 996 997 /* free tclique data */ 998 if( sepadata->tcliquegraph != NULL ) 999 { 1000 SCIP_CALL( tcliquegraphFree(scip, &sepadata->tcliquegraph) ); 1001 } 1002 assert(sepadata->tcliquegraph == NULL); 1003 sepadata->tcliquegraphloaded = FALSE; 1004 1005 return SCIP_OKAY; 1006 } 1007 1008 1009 /** LP solution separation method of separator */ 1010 static 1011 SCIP_DECL_SEPAEXECLP(sepaExeclpClique) 1012 { 1013 /*lint --e{715}*/ 1014 1015 *result = SCIP_DIDNOTRUN; 1016 1017 /* only call separator, if we are not close to terminating */ 1018 if( SCIPisStopped(scip) ) 1019 return SCIP_OKAY; 1020 1021 /* only call separator, if an optimal LP solution is at hand */ 1022 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1023 return SCIP_OKAY; 1024 1025 /* only call separator, if there are fractional variables */ 1026 if( SCIPgetNLPBranchCands(scip) == 0 ) 1027 return SCIP_OKAY; 1028 1029 /* separate cuts on the LP solution */ 1030 SCIP_CALL( separateCuts(scip, sepa, NULL, result) ); 1031 1032 return SCIP_OKAY; 1033 } 1034 1035 1036 /** arbitrary primal solution separation method of separator */ 1037 static 1038 SCIP_DECL_SEPAEXECSOL(sepaExecsolClique) 1039 { 1040 /*lint --e{715}*/ 1041 1042 *result = SCIP_DIDNOTRUN; 1043 1044 /* separate cuts on the given primal solution */ 1045 SCIP_CALL( separateCuts(scip, sepa, sol, result) ); 1046 1047 return SCIP_OKAY; 1048 } 1049 1050 1051 /* 1052 * separator specific interface methods 1053 */ 1054 1055 /** creates the clique separator and includes it in SCIP */ 1056 SCIP_RETCODE SCIPincludeSepaClique( 1057 SCIP* scip /**< SCIP data structure */ 1058 ) 1059 { 1060 SCIP_SEPADATA* sepadata; 1061 SCIP_SEPA* sepa; 1062 1063 /* create clique separator data */ 1064 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 1065 sepadata->tcliquegraph = NULL; 1066 sepadata->scip = scip; 1067 sepadata->sol = NULL; 1068 sepadata->varsolvals = NULL; 1069 sepadata->ncalls = 0; 1070 sepadata->ncuts = 0; 1071 sepadata->tcliquegraphloaded = FALSE; 1072 1073 /* include separator */ 1074 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 1075 SEPA_USESSUBSCIP, SEPA_DELAY, 1076 sepaExeclpClique, sepaExecsolClique, 1077 sepadata) ); 1078 1079 assert(sepa != NULL); 1080 sepadata->sepa = sepa; 1081 1082 /* set non-NULL pointers to callback methods */ 1083 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyClique) ); 1084 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeClique) ); 1085 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolClique) ); 1086 1087 /* add clique separator parameters */ 1088 SCIP_CALL( SCIPaddRealParam(scip, 1089 "separating/clique/scaleval", 1090 "factor for scaling weights", 1091 &sepadata->scaleval, TRUE, DEFAULT_SCALEVAL, 1.0, SCIP_REAL_MAX, NULL, NULL) ); 1092 SCIP_CALL( SCIPaddIntParam(scip, 1093 "separating/clique/maxtreenodes", 1094 "maximal number of nodes in branch and bound tree (-1: no limit)", 1095 &sepadata->maxtreenodes, TRUE, DEFAULT_MAXTREENODES, -1, INT_MAX, NULL, NULL) ); 1096 SCIP_CALL( SCIPaddIntParam(scip, 1097 "separating/clique/backtrackfreq", 1098 "frequency for premature backtracking up to tree level 1 (0: no backtracking)", 1099 &sepadata->backtrackfreq, TRUE, DEFAULT_BACKTRACKFREQ, 0, INT_MAX, NULL, NULL) ); 1100 SCIP_CALL( SCIPaddIntParam(scip, 1101 "separating/clique/maxsepacuts", 1102 "maximal number of clique cuts separated per separation round (-1: no limit)", 1103 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) ); 1104 SCIP_CALL( SCIPaddIntParam(scip, 1105 "separating/clique/maxzeroextensions", 1106 "maximal number of zero-valued variables extending the clique (-1: no limit)", 1107 &sepadata->maxzeroextensions, TRUE, DEFAULT_MAXZEROEXTENSIONS, -1, INT_MAX, NULL, NULL) ); 1108 SCIP_CALL( SCIPaddRealParam(scip, 1109 "separating/clique/cliquetablemem", 1110 "maximal memory size of dense clique table (in kb)", 1111 &sepadata->cliquetablemem, TRUE, DEFAULT_CLIQUETABLEMEM, 0.0, (SCIP_Real)INT_MAX/1024.0, NULL, NULL) ); 1112 SCIP_CALL( SCIPaddRealParam(scip, 1113 "separating/clique/cliquedensity", 1114 "minimal density of cliques to use a dense clique table", 1115 &sepadata->cliquedensity, TRUE, DEFAULT_CLIQUEDENSITY, 0.0, 1.0, NULL, NULL) ); 1116 1117 return SCIP_OKAY; 1118 } 1119