1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright 2002-2023 Zuse Institute Berlin */ 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 symmetry_graph.c 26 * @ingroup PUBLICCOREAPI 27 * @brief methods for dealing with symmetry detection graphs 28 * @author Christopher Hojny 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/symmetry_graph.h" 34 #include "scip/scip.h" 35 #include "scip/misc.h" 36 #include <symmetry/struct_symmetry.h> 37 #include <symmetry/type_symmetry.h> 38 39 40 /** creates and initializes a symmetry detection graph with memory for the given number of nodes and edges 41 * 42 * @note At some point, the graph needs to be freed! 43 */ 44 SCIP_RETCODE SCIPcreateSymgraph( 45 SCIP* scip, /**< SCIP data structure */ 46 SYM_SYMTYPE symtype, /**< type of symmetries encoded in graph */ 47 SYM_GRAPH** graph, /**< pointer to hold symmetry detection graph */ 48 SCIP_VAR** symvars, /**< variables used in symmetry detection */ 49 int nsymvars, /**< number of variables used in symmetry detection */ 50 int nopnodes, /**< number of operator nodes */ 51 int nvalnodes, /**< number of value nodes */ 52 int nconsnodes, /**< number of constraint nodes */ 53 int nedges /**< number of edges */ 54 ) 55 { 56 int nnodes; 57 58 assert(scip != NULL); 59 assert(graph != NULL); 60 assert(symvars != NULL); 61 assert(nopnodes >= 0); 62 assert(nvalnodes >= 0); 63 assert(nconsnodes >= 0); 64 assert(nedges >= 0); 65 66 nnodes = nopnodes + nvalnodes + nconsnodes; 67 68 SCIP_CALL( SCIPallocBlockMemory(scip, graph) ); 69 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->nodetypes, nnodes) ); 70 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->nodeinfopos, nnodes) ); 71 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->ops, nopnodes) ); 72 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->vals, nvalnodes) ); 73 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->conss, nconsnodes) ); 74 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->lhs, nconsnodes) ); 75 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->rhs, nconsnodes) ); 76 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->edgefirst, nedges) ); 77 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->edgesecond, nedges) ); 78 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*graph)->edgevals, nedges) ); 79 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*graph)->isfixedvar, nsymvars) ); 80 81 (*graph)->nnodes = 0; 82 (*graph)->maxnnodes = nnodes; 83 (*graph)->nopnodes = 0; 84 (*graph)->maxnopnodes = nopnodes; 85 (*graph)->nvalnodes = 0; 86 (*graph)->maxnvalnodes = nvalnodes; 87 (*graph)->nconsnodes = 0; 88 (*graph)->maxnconsnodes = nconsnodes; 89 (*graph)->islocked = FALSE; 90 (*graph)->nedges = 0; 91 (*graph)->maxnedges = nedges; 92 (*graph)->symvars = symvars; 93 (*graph)->nsymvars = nsymvars; 94 (*graph)->nvarcolors = -1; 95 (*graph)->uniqueedgetype = FALSE; 96 (*graph)->symtype = symtype; 97 (*graph)->infinity = SCIPinfinity(scip); 98 (*graph)->consnodeperm = NULL; 99 100 /* to avoid reallocation, allocate memory for colors later */ 101 (*graph)->varcolors = NULL; 102 (*graph)->opcolors = NULL; 103 (*graph)->valcolors = NULL; 104 (*graph)->conscolors = NULL; 105 (*graph)->edgecolors = NULL; 106 107 return SCIP_OKAY; 108 } 109 110 /** frees a symmetry detection graph */ 111 SCIP_RETCODE SCIPfreeSymgraph( 112 SCIP* scip, /**< SCIP data structure */ 113 SYM_GRAPH** graph /**< pointer to symmetry detection graph */ 114 ) 115 { 116 assert(scip != NULL); 117 assert(graph != NULL); 118 119 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->edgecolors, (*graph)->nedges); 120 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->conscolors, (*graph)->nconsnodes); 121 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->valcolors, (*graph)->nvalnodes); 122 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->opcolors, (*graph)->nopnodes); 123 switch( (*graph)->symtype ) 124 { 125 case SYM_SYMTYPE_PERM: 126 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->varcolors, (*graph)->nsymvars); 127 break; 128 default: 129 assert((*graph)->symtype == SYM_SYMTYPE_SIGNPERM); 130 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->varcolors, 2 * (*graph)->nsymvars); 131 } /*lint !e788*/ 132 133 SCIPfreeBlockMemoryArrayNull(scip, &(*graph)->consnodeperm, (*graph)->nconsnodes); 134 SCIPfreeBlockMemoryArray(scip, &(*graph)->isfixedvar, (*graph)->nsymvars); 135 SCIPfreeBlockMemoryArray(scip, &(*graph)->edgevals, (*graph)->maxnedges); 136 SCIPfreeBlockMemoryArray(scip, &(*graph)->edgesecond, (*graph)->maxnedges); 137 SCIPfreeBlockMemoryArray(scip, &(*graph)->edgefirst, (*graph)->maxnedges); 138 SCIPfreeBlockMemoryArray(scip, &(*graph)->rhs, (*graph)->maxnconsnodes); 139 SCIPfreeBlockMemoryArray(scip, &(*graph)->lhs, (*graph)->maxnconsnodes); 140 SCIPfreeBlockMemoryArray(scip, &(*graph)->conss, (*graph)->maxnconsnodes); 141 SCIPfreeBlockMemoryArray(scip, &(*graph)->vals, (*graph)->maxnvalnodes); 142 SCIPfreeBlockMemoryArray(scip, &(*graph)->ops, (*graph)->maxnopnodes); 143 SCIPfreeBlockMemoryArray(scip, &(*graph)->nodeinfopos, (*graph)->maxnnodes); 144 SCIPfreeBlockMemoryArray(scip, &(*graph)->nodetypes, (*graph)->maxnnodes); 145 SCIPfreeBlockMemory(scip, graph); 146 147 return SCIP_OKAY; 148 } 149 150 /** copies an existing graph and changes variable nodes according to a permutation */ 151 SCIP_RETCODE SCIPcopySymgraph( 152 SCIP* scip, /**< SCIP data structure */ 153 SYM_GRAPH** graph, /**< pointer to hold copy of symmetry detection graph */ 154 SYM_GRAPH* origgraph, /**< graph to be copied */ 155 int* perm, /**< permutation of variables */ 156 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */ 157 ) 158 { /*lint --e{788}*/ 159 SYM_NODETYPE nodetype; 160 int* nodeinfopos; 161 int nnodes; 162 int first; 163 int second; 164 int nodeidx; 165 int i; 166 167 assert(scip != NULL); 168 assert(graph != NULL); 169 assert(origgraph != NULL); 170 assert(perm != NULL); 171 172 SCIP_CALL( SCIPcreateSymgraph(scip, origgraph->symtype, graph, origgraph->symvars, origgraph->nsymvars, 173 origgraph->nopnodes, origgraph->nvalnodes, origgraph->nconsnodes, origgraph->nedges) ); 174 175 /* copy nodes */ 176 nnodes = origgraph->nnodes; 177 nodeinfopos = origgraph->nodeinfopos; 178 for( i = 0; i < nnodes; ++i ) 179 { 180 nodetype = origgraph->nodetypes[i]; 181 182 switch( nodetype ) 183 { 184 case SYM_NODETYPE_OPERATOR: 185 SCIP_CALL( SCIPaddSymgraphOpnode(scip, *graph, origgraph->ops[nodeinfopos[i]], &nodeidx) ); 186 break; 187 case SYM_NODETYPE_VAL: 188 SCIP_CALL( SCIPaddSymgraphValnode(scip, *graph, origgraph->vals[nodeinfopos[i]], &nodeidx) ); 189 break; 190 default: 191 assert(nodetype == SYM_NODETYPE_CONS); 192 SCIP_CALL( SCIPaddSymgraphConsnode(scip, *graph, origgraph->conss[nodeinfopos[i]], 193 origgraph->lhs[nodeinfopos[i]], origgraph->rhs[nodeinfopos[i]], &nodeidx) ); 194 } 195 assert(0 <= nodeidx && nodeidx < nnodes); 196 } 197 198 /* copy edges */ 199 for( i = 0; i < origgraph->nedges; ++i ) 200 { 201 first = SCIPgetSymgraphEdgeFirst(origgraph, i); 202 second = SCIPgetSymgraphEdgeSecond(origgraph, i); 203 204 /* possibly adapt edges due to permutation of variables */ 205 if( first < 0 ) 206 first = -perm[-first - 1] - 1; 207 if( second < 0 ) 208 second = -perm[-second - 1] - 1; 209 210 SCIP_CALL( SCIPaddSymgraphEdge(scip, *graph, first, second, 211 ! SCIPisInfinity(scip, origgraph->edgevals[i]), origgraph->edgevals[i]) ); 212 } 213 214 SCIP_CALL( SCIPcomputeSymgraphColors(scip, *graph, fixedtype) ); 215 216 return SCIP_OKAY; 217 } 218 219 /** adds a symmetry detection graph for a linear constraint to existing graph 220 * 221 * For permutation symmetries, a constraint node is added that is connected to all 222 * variable nodes in the constraint. Edges are colored according to the variable coefficients. 223 * For signed permutation symmetries, also edges connecting the constraint node and 224 * the negated variable nodes are added, these edges are colored by the negative coefficients. 225 */ 226 SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear( 227 SCIP* scip, /**< SCIP data structure */ 228 SYM_GRAPH* graph, /**< symmetry detection graph */ 229 SCIP_VAR** vars, /**< variable array of linear constraint */ 230 SCIP_Real* vals, /**< coefficients of linear constraint */ 231 int nvars, /**< number of variables in linear constraint */ 232 SCIP_CONS* cons, /**< constraint for which we encode symmetries */ 233 SCIP_Real lhs, /**< left-hand side of constraint */ 234 SCIP_Real rhs, /**< right-hand side of constraint */ 235 SCIP_Bool* success /**< pointer to store whether graph could be built */ 236 ) 237 { 238 int rhsnodeidx; 239 int varnodeidx; 240 int i; 241 242 assert(scip != NULL); 243 assert(graph != NULL); 244 assert(vars != NULL); 245 assert(vals != NULL); 246 assert(nvars >= 0); 247 assert(cons != NULL); 248 assert(success != NULL); 249 assert(! graph->islocked); 250 251 *success = TRUE; 252 253 #ifndef NDEBUG 254 /* check whether variable nodes exist in the graph */ 255 for( i = 0; i < nvars; ++i ) 256 { 257 assert(0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < graph->nsymvars); 258 } 259 #endif 260 261 /* create node corresponding to right-hand side */ 262 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, lhs, rhs, &rhsnodeidx) ); 263 264 /* create edges */ 265 for( i = 0; i < nvars; ++i ) 266 { 267 if( SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_SIGNPERM ) 268 { 269 varnodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, vars[i]); 270 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rhsnodeidx, varnodeidx, TRUE, -vals[i]) ); 271 272 varnodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[i]); 273 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rhsnodeidx, varnodeidx, TRUE, vals[i]) ); 274 } 275 else 276 { 277 assert(SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_PERM); 278 279 varnodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[i]); 280 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rhsnodeidx, varnodeidx, TRUE, vals[i]) ); 281 } 282 } 283 284 return SCIP_OKAY; 285 } 286 287 /** adds nodes and edges corresponding to the aggregation of a variable to a symmetry detection graph 288 * 289 * For permutation symmetries, the root node is connected with all variable nodes in the aggregation. 290 * Edges are colored according to the variable coefficients. 291 * For signed permutation symmetries, also edges connecting the root node and the negated variable 292 * nodes are added, these edges are colored by the negative coefficients. 293 */ 294 SCIP_RETCODE SCIPaddSymgraphVarAggegration( 295 SCIP* scip, /**< SCIP data structure */ 296 SYM_GRAPH* graph, /**< symmetry detection graph */ 297 int rootidx, /**< index of root node of the aggegration */ 298 SCIP_VAR** vars, /**< array of variables in aggregation */ 299 SCIP_Real* vals, /**< coefficients of variables */ 300 int nvars, /**< number of variables in aggregation */ 301 SCIP_Real constant /**< constant of aggregation */ 302 ) 303 { 304 int nodeidx; 305 int j; 306 307 assert(scip != NULL); 308 assert(graph != NULL); 309 assert(rootidx >= 0); 310 assert(vars != NULL); 311 assert(vals != NULL); 312 assert(nvars >= 0); 313 314 #ifndef NDEBUG 315 /* check whether variable nodes exist in the graph */ 316 for( j = 0; j < nvars; ++j ) 317 { 318 assert(0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < graph->nsymvars); 319 } 320 #endif 321 322 /* add edges incident to variables in aggregation */ 323 for( j = 0; j < nvars; ++j ) 324 { 325 if( SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_SIGNPERM ) 326 { 327 nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, vars[j]); 328 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rootidx, nodeidx, TRUE, -vals[j]) ); 329 330 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[j]); 331 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rootidx, nodeidx, TRUE, vals[j]) ); 332 } 333 else 334 { 335 assert(SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_PERM); 336 337 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[j]); 338 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rootidx, nodeidx, TRUE, vals[j]) ); 339 } 340 } 341 342 /* possibly add node for constant */ 343 if( ! SCIPisZero(scip, constant) ) 344 { 345 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) ); 346 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, rootidx, nodeidx, FALSE, 0.0) ); 347 } 348 349 return SCIP_OKAY; 350 } 351 352 /* 353 * methods for adding and accessing nodes 354 */ 355 356 /** ensures that the node-based arrays in symmetry graph are sufficiently long */ 357 static 358 SCIP_RETCODE ensureNodeArraysSize( 359 SCIP* scip, /**< SCIP data structure */ 360 SYM_GRAPH* graph, /**< symmetry detection graph */ 361 int addsize /**< required additional size of node-based arrays */ 362 ) 363 { 364 assert(scip != NULL); 365 assert(graph != NULL); 366 assert(addsize > 0); 367 368 if( graph->nnodes + addsize > graph->maxnnodes ) 369 { 370 int newsize; 371 372 newsize = SCIPcalcMemGrowSize(scip, graph->nnodes + addsize); 373 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->nodetypes, graph->maxnnodes, newsize) ); 374 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->nodeinfopos, graph->maxnnodes, newsize) ); 375 graph->maxnnodes = newsize; 376 } 377 378 return SCIP_OKAY; 379 } 380 381 /** adds an operator node to a symmetry detection graph and returns its node index */ 382 SCIP_RETCODE SCIPaddSymgraphOpnode( 383 SCIP* scip, /**< SCIP data structure */ 384 SYM_GRAPH* graph, /**< symmetry detection graph */ 385 int op, /**< int associated with operator of node */ 386 int* nodeidx /**< pointer to hold index of created node */ 387 ) 388 { 389 assert(scip != NULL); 390 assert(graph != NULL); 391 assert(nodeidx != NULL); 392 393 /* we can only add nodes if symmetry colors have not been computed yet */ 394 if( graph->islocked ) 395 { 396 SCIPerrorMessage("Cannot add nodes to a graph for which colors have already been computed.\n"); 397 return SCIP_ERROR; 398 } 399 400 SCIP_CALL( ensureNodeArraysSize(scip, graph, 1) ); 401 402 if( graph->nopnodes >= graph->maxnopnodes ) 403 { 404 int newsize; 405 406 newsize = SCIPcalcMemGrowSize(scip, graph->nopnodes + 1); 407 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->ops, graph->maxnopnodes, newsize) ); 408 graph->maxnopnodes = newsize; 409 } 410 411 graph->nodetypes[graph->nnodes] = SYM_NODETYPE_OPERATOR; 412 graph->nodeinfopos[graph->nnodes] = graph->nopnodes; 413 graph->ops[graph->nopnodes] = op; 414 415 *nodeidx = graph->nnodes; 416 ++graph->nnodes; 417 ++graph->nopnodes; 418 419 return SCIP_OKAY; 420 } 421 422 /** adds a value node to a symmetry detection graph and returns its node index */ 423 SCIP_RETCODE SCIPaddSymgraphValnode( 424 SCIP* scip, /**< SCIP data structure */ 425 SYM_GRAPH* graph, /**< symmetry detection graph */ 426 SCIP_Real val, /**< value of node */ 427 int* nodeidx /**< pointer to hold index of created node */ 428 ) 429 { 430 assert(scip != NULL); 431 assert(graph != NULL); 432 assert(nodeidx != NULL); 433 434 /* we can only add nodes if symmetry colors have not been computed yet */ 435 if( graph->islocked ) 436 { 437 SCIPerrorMessage("Cannot add nodes to a graph for which colors have already been computed.\n"); 438 return SCIP_ERROR; 439 } 440 441 SCIP_CALL( ensureNodeArraysSize(scip, graph, 1) ); 442 443 if( graph->nvalnodes >= graph->maxnvalnodes ) 444 { 445 int newsize; 446 447 newsize = SCIPcalcMemGrowSize(scip, graph->nvalnodes + 1); 448 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->vals, graph->maxnvalnodes, newsize) ); 449 graph->maxnvalnodes = newsize; 450 } 451 452 graph->nodetypes[graph->nnodes] = SYM_NODETYPE_VAL; 453 graph->nodeinfopos[graph->nnodes] = graph->nvalnodes; 454 graph->vals[graph->nvalnodes] = val; 455 456 *nodeidx = graph->nnodes; 457 ++graph->nnodes; 458 ++graph->nvalnodes; 459 460 return SCIP_OKAY; 461 } 462 463 /** adds a constraint node to a symmetry detection graph and returns its node index */ 464 SCIP_RETCODE SCIPaddSymgraphConsnode( 465 SCIP* scip, /**< SCIP data structure */ 466 SYM_GRAPH* graph, /**< symmetry detection graph */ 467 SCIP_CONS* cons, /**< constraint of node */ 468 SCIP_Real lhs, /**< left-hand side of node */ 469 SCIP_Real rhs, /**< right-hand side of node */ 470 int* nodeidx /**< pointer to hold index of created node */ 471 ) 472 { 473 assert(scip != NULL); 474 assert(graph != NULL); 475 assert(cons != NULL); 476 assert(nodeidx != NULL); 477 478 /* we can only add nodes if symmetry colors have not been computed yet */ 479 if( graph->islocked ) 480 { 481 SCIPerrorMessage("Cannot add nodes to a graph for which colors have already been computed.\n"); 482 return SCIP_ERROR; 483 } 484 485 SCIP_CALL( ensureNodeArraysSize(scip, graph, 1) ); 486 487 if( graph->nconsnodes >= graph->maxnconsnodes ) 488 { 489 int newsize; 490 491 newsize = SCIPcalcMemGrowSize(scip, graph->nconsnodes + 1); 492 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->conss, graph->maxnconsnodes, newsize) ); 493 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->lhs, graph->maxnconsnodes, newsize) ); 494 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->rhs, graph->maxnconsnodes, newsize) ); 495 graph->maxnconsnodes = newsize; 496 } 497 498 graph->nodetypes[graph->nnodes] = SYM_NODETYPE_CONS; 499 graph->nodeinfopos[graph->nnodes] = graph->nconsnodes; 500 graph->conss[graph->nconsnodes] = cons; 501 graph->lhs[graph->nconsnodes] = MAX(lhs, -graph->infinity); 502 graph->rhs[graph->nconsnodes] = MIN(rhs, graph->infinity); 503 504 *nodeidx = graph->nnodes; 505 ++graph->nnodes; 506 ++graph->nconsnodes; 507 508 return SCIP_OKAY; 509 } 510 511 /** returns the (hypothetical) node index of a variable */ 512 int SCIPgetSymgraphVarnodeidx( 513 SCIP* scip, /**< SCIP data structure */ 514 SYM_GRAPH* graph, /**< symmetry detection graph */ 515 SCIP_VAR* var /**< variable */ 516 ) 517 { 518 int nodeidx; 519 520 assert(scip != NULL); 521 assert(graph != NULL); 522 assert(var != NULL); 523 assert(graph->symtype == SYM_SYMTYPE_PERM || graph->symtype == SYM_SYMTYPE_SIGNPERM); 524 525 nodeidx = -SCIPvarGetProbindex(var) - 1; 526 assert(nodeidx != INT_MAX); 527 528 return nodeidx; 529 } 530 531 /** returns the (hypothetical) node index of a negated variable */ 532 int SCIPgetSymgraphNegatedVarnodeidx( 533 SCIP* scip, /**< SCIP data structure */ 534 SYM_GRAPH* graph, /**< symmetry detection graph */ 535 SCIP_VAR* var /**< variable */ 536 ) 537 { 538 int nodeidx; 539 540 assert(scip != NULL); 541 assert(graph != NULL); 542 assert(var != NULL); 543 assert(graph->symtype == SYM_SYMTYPE_SIGNPERM); 544 assert(SCIPgetSymgraphVarnodeidx(scip, graph, var) < 0 ); 545 546 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, var) - graph->nsymvars; 547 assert(nodeidx != INT_MAX); 548 549 return nodeidx; 550 } 551 552 /** updates the lhs of a constraint node */ 553 SCIP_RETCODE SCIPupdateSymgraphLhs( 554 SYM_GRAPH* graph, /**< symmetry detection graph */ 555 int nodeidx, /**< index of constraint node in graph */ 556 SCIP_Real newlhs /**< new left-hand side of node */ 557 ) 558 { 559 assert(graph != NULL); 560 assert(nodeidx >= 0); 561 assert(graph->nodetypes[nodeidx] == SYM_NODETYPE_CONS); 562 563 graph->lhs[graph->nodeinfopos[nodeidx]] = newlhs; 564 565 return SCIP_OKAY; 566 } 567 568 /** updates the rhs of a constraint node */ 569 SCIP_RETCODE SCIPupdateSymgraphRhs( 570 SYM_GRAPH* graph, /**< symmetry detection graph */ 571 int nodeidx, /**< index of constraint node in graph */ 572 SCIP_Real newrhs /**< new reft-hand side of node */ 573 ) 574 { 575 assert(graph != NULL); 576 assert(nodeidx >= 0); 577 assert(graph->nodetypes[nodeidx] == SYM_NODETYPE_CONS); 578 579 graph->rhs[graph->nodeinfopos[nodeidx]] = newrhs; 580 581 return SCIP_OKAY; 582 } 583 584 /** registers a variable node (corresponding to active variable) to be fixed by symmetry */ 585 SCIP_RETCODE SCIPfixSymgraphVarnode( 586 SYM_GRAPH* graph, /**< symmetry detection graph */ 587 SCIP_VAR* var /**< active variable that needs to be fixed */ 588 ) 589 { 590 int varidx; 591 592 assert(graph != NULL); 593 assert(var != NULL); 594 595 varidx = SCIPvarGetProbindex(var); 596 assert(0 <= varidx && varidx < graph->nsymvars); 597 598 graph->isfixedvar[varidx] = TRUE; 599 600 return SCIP_OKAY; 601 } 602 603 /* 604 * methods for adding edges 605 */ 606 607 /** ensures that the edge-based arrays in symmetry graph are sufficiently long */ 608 static 609 SCIP_RETCODE ensureEdgeArraysSize( 610 SCIP* scip, /**< SCIP data structure */ 611 SYM_GRAPH* graph, /**< symmetry detection graph */ 612 int addsize /**< required additional size of edge-based arrays */ 613 ) 614 { 615 assert(scip != NULL); 616 assert(graph != NULL); 617 assert(addsize > 0); 618 619 if( graph->nedges + addsize > graph->maxnedges ) 620 { 621 int newsize; 622 623 newsize = SCIPcalcMemGrowSize(scip, graph->nedges + addsize); 624 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->edgefirst, graph->maxnedges, newsize) ); 625 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->edgesecond, graph->maxnedges, newsize) ); 626 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &graph->edgevals, graph->maxnedges, newsize) ); 627 graph->maxnedges = newsize; 628 } 629 630 return SCIP_OKAY; 631 } 632 633 /** adds an edge to a symmetry detection graph */ 634 SCIP_RETCODE SCIPaddSymgraphEdge( 635 SCIP* scip, /**< SCIP data structure */ 636 SYM_GRAPH* graph, /**< symmetry detection graph */ 637 int first, /**< first node index of edge */ 638 int second, /**< second node index of edge */ 639 SCIP_Bool hasval, /**< whether the edge has a value */ 640 SCIP_Real val /**< value of the edge (is it has a value) */ 641 ) 642 { 643 assert(scip != NULL); 644 assert(graph != NULL); 645 646 /* we can only add edges if symmetry colors have not been computed yet */ 647 if( graph->islocked ) 648 { 649 SCIPerrorMessage("Cannot add edges to a graph for which colors have already been computed.\n"); 650 return SCIP_ERROR; 651 } 652 653 SCIP_CALL( ensureEdgeArraysSize(scip, graph, 1) ); 654 655 graph->edgefirst[graph->nedges] = first; 656 graph->edgesecond[graph->nedges] = second; 657 if( hasval ) 658 graph->edgevals[graph->nedges] = val; 659 else 660 graph->edgevals[graph->nedges] = SCIPinfinity(scip); 661 662 graph->nedges += 1; 663 664 return SCIP_OKAY; 665 } 666 667 /* 668 * methods to compute colors 669 */ 670 671 /** compares two variables for permutation symmetry detection 672 * 673 * Variables are sorted first by their type, then by their objective coefficient, 674 * then by their lower bound, and then by their upper bound. 675 * 676 * result: 677 * < 0: ind1 comes before (is better than) ind2 678 * = 0: both indices have the same value 679 * > 0: ind2 comes after (is worse than) ind2 680 */ 681 static 682 int compareVars( 683 SCIP* scip, /**< SCIP pointer (or NULL for exact comparison) */ 684 SCIP_VAR* var1, /**< first variable for comparison */ 685 SCIP_VAR* var2 /**< second variable for comparison */ 686 ) 687 { 688 assert(var1 != NULL); 689 assert(var2 != NULL); 690 691 if( SCIPvarGetType(var1) < SCIPvarGetType(var2) ) 692 return -1; 693 if( SCIPvarGetType(var1) > SCIPvarGetType(var2) ) 694 return 1; 695 696 /* use SCIP's comparison functions if available */ 697 if( scip == NULL ) 698 { 699 if( SCIPvarGetObj(var1) < SCIPvarGetObj(var2) ) 700 return -1; 701 if( SCIPvarGetObj(var1) > SCIPvarGetObj(var2) ) 702 return 1; 703 704 if( SCIPvarGetLbGlobal(var1) < SCIPvarGetLbGlobal(var2) ) 705 return -1; 706 if( SCIPvarGetLbGlobal(var1) > SCIPvarGetLbGlobal(var2) ) 707 return 1; 708 709 if( SCIPvarGetUbGlobal(var1) < SCIPvarGetUbGlobal(var2) ) 710 return -1; 711 if( SCIPvarGetUbGlobal(var1) > SCIPvarGetUbGlobal(var2) ) 712 return 1; 713 } 714 else 715 { 716 if( SCIPisLT(scip, SCIPvarGetObj(var1), SCIPvarGetObj(var2)) ) 717 return -1; 718 if( SCIPisGT(scip, SCIPvarGetObj(var1), SCIPvarGetObj(var2)) ) 719 return 1; 720 721 if( SCIPisLT(scip, SCIPvarGetLbGlobal(var1), SCIPvarGetLbGlobal(var2)) ) 722 return -1; 723 if( SCIPisGT(scip, SCIPvarGetLbGlobal(var1), SCIPvarGetLbGlobal(var2)) ) 724 return 1; 725 726 if( SCIPisLT(scip, SCIPvarGetUbGlobal(var1), SCIPvarGetUbGlobal(var2)) ) 727 return -1; 728 if( SCIPisGT(scip, SCIPvarGetUbGlobal(var1), SCIPvarGetUbGlobal(var2)) ) 729 return 1; 730 } 731 732 return 0; 733 } 734 735 /** compares two variables for permutation symmetry detection 736 * 737 * Variables are sorted first by whether they are fixed, then by their type, then by 738 * their objective coefficient, then by their lower bound, and then by their upper bound. 739 * 740 * result: 741 * < 0: ind1 comes before (is better than) ind2 742 * = 0: both indices have the same value 743 * > 0: ind2 comes after (is worse than) ind2 744 */ 745 static 746 int compareVarsFixed( 747 SCIP* scip, /**< SCIP pointer (or NULL for exact comparison) */ 748 SCIP_VAR* var1, /**< first variable for comparison */ 749 SCIP_VAR* var2, /**< second variable for comparison */ 750 SCIP_Bool isfixed1, /**< whether var1 needs to be fixed */ 751 SCIP_Bool isfixed2 /**< whether var2 needs to be fixed */ 752 ) 753 { 754 assert(var1 != NULL); 755 assert(var2 != NULL); 756 757 if( (! isfixed1) && isfixed2 ) 758 return -1; 759 if( isfixed1 && (! isfixed2) ) 760 return 1; 761 762 return compareVars(scip, var1, var2); 763 } 764 765 /** sorts nodes of a permutation symmetry detection graph 766 * 767 * Variables are sorted first by whether they are fixed, then by their type, then by 768 * their objective coefficient, then by their lower bound, and then by their upper bound. 769 * 770 * result: 771 * < 0: ind1 comes before (is better than) ind2 772 * = 0: both indices have the same value 773 * > 0: ind2 comes after (is worse than) ind2 774 */ 775 static 776 SCIP_DECL_SORTINDCOMP(SYMsortVarnodesPermsym) 777 { 778 SYM_GRAPH* graph; 779 SCIP_VAR** vars; 780 SCIP_Bool* isfixedvar; 781 782 graph = (SYM_GRAPH*) dataptr; 783 assert(graph != NULL); 784 785 vars = graph->symvars; 786 assert(vars != NULL); 787 788 isfixedvar = graph->isfixedvar; 789 assert(isfixedvar != NULL); 790 791 return compareVarsFixed(NULL, vars[ind1], vars[ind2], isfixedvar[ind1], isfixedvar[ind2]); 792 } 793 794 /** compares two variables for signed permutation symmetry detection 795 * 796 * Variables are sorted first by their type, then by their objective coefficient, 797 * then by their lower bound, and then by their upper bound. 798 * To take signed permutations into account, variable domains are centered at origin 799 * if the domain is finite. 800 * 801 * result: 802 * < 0: ind1 comes before (is better than) ind2 803 * = 0: both indices have the same value 804 * > 0: ind2 comes after (is worse than) ind2 805 */ 806 static 807 int compareVarsSignedPerm( 808 SCIP* scip, /**< SCIP pointer (or NULL for exact comparison) */ 809 SCIP_VAR* var1, /**< first variable for comparison */ 810 SCIP_VAR* var2, /**< second variable for comparison */ 811 SCIP_Bool isneg1, /**< whether var1 needs to be negated */ 812 SCIP_Bool isneg2, /**< whether var2 needs to be negated */ 813 SCIP_Real infinity /**< values as least as large as this are regarded as infinite */ 814 ) 815 { 816 SCIP_Real ub1; 817 SCIP_Real ub2; 818 SCIP_Real lb1; 819 SCIP_Real lb2; 820 SCIP_Real obj1; 821 SCIP_Real obj2; 822 SCIP_Real mid; 823 824 assert(var1 != NULL); 825 assert(var2 != NULL); 826 827 /* use SCIP's comparison functions if available */ 828 if( scip == NULL ) 829 { 830 if( SCIPvarGetType(var1) < SCIPvarGetType(var2) ) 831 return -1; 832 if( SCIPvarGetType(var1) > SCIPvarGetType(var2) ) 833 return 1; 834 } 835 else 836 { 837 if( SCIPvarGetType(var1) < SCIPvarGetType(var2) ) 838 return -1; 839 if( SCIPvarGetType(var1) > SCIPvarGetType(var2) ) 840 return 1; 841 } 842 843 obj1 = isneg1 ? -SCIPvarGetObj(var1) : SCIPvarGetObj(var1); 844 obj2 = isneg2 ? -SCIPvarGetObj(var2) : SCIPvarGetObj(var2); 845 846 /* use SCIP's comparison functions if available */ 847 if( scip == NULL ) 848 { 849 if( obj1 < obj2 ) 850 return -1; 851 if( obj1 > obj2 ) 852 return 1; 853 } 854 else 855 { 856 if( SCIPisLT(scip, obj1, obj2) ) 857 return -1; 858 if( SCIPisGT(scip, obj1, obj2) ) 859 return 1; 860 } 861 862 /* adapt lower and upper bounds if domain is finite */ 863 lb1 = SCIPvarGetLbGlobal(var1); 864 lb2 = SCIPvarGetLbGlobal(var2); 865 ub1 = SCIPvarGetUbGlobal(var1); 866 ub2 = SCIPvarGetUbGlobal(var2); 867 if( ub1 < infinity && -lb1 < infinity ) 868 { 869 mid = (lb1 + ub1) / 2; 870 lb1 -= mid; 871 ub1 -= mid; 872 } 873 if( ub2 < infinity && -lb2 < infinity ) 874 { 875 mid = (lb2 + ub2) / 2; 876 lb2 -= mid; 877 ub2 -= mid; 878 } 879 880 /* for negated variables, flip upper and lower bounds */ 881 if( isneg1 ) 882 { 883 mid = lb1; 884 lb1 = -ub1; 885 ub1 = -mid; 886 } 887 if( isneg2 ) 888 { 889 mid = lb2; 890 lb2 = -ub2; 891 ub2 = -mid; 892 } 893 894 /* use SCIP's comparison functions if available */ 895 if( scip == NULL ) 896 { 897 if( lb1 < lb2 ) 898 return -1; 899 if( lb1 > lb2 ) 900 return 1; 901 902 if( ub1 < ub2 ) 903 return -1; 904 if( ub1 > ub2 ) 905 return 1; 906 } 907 else 908 { 909 if( SCIPisLT(scip, lb1, lb2) ) 910 return -1; 911 if( SCIPisGT(scip, lb1, lb2) ) 912 return 1; 913 914 if( SCIPisLT(scip, ub1, ub2) ) 915 return -1; 916 if( SCIPisGT(scip, ub1, ub2) ) 917 return 1; 918 } 919 920 return 0; 921 } 922 923 /** compares two variables for signed permutation symmetry detection 924 * 925 * Variables are sorted first by whether they are fixed, then by their type, then 926 * by their objective coefficient, then by their lower bound and then by their upper bound. 927 * To take signed permutations into account, variable domains are centered at origin 928 * if the domain is finite. 929 * 930 * result: 931 * < 0: ind1 comes before (is better than) ind2 932 * = 0: both indices have the same value 933 * > 0: ind2 comes after (is worse than) ind2 934 */ 935 static 936 int compareVarsFixedSignedPerm( 937 SCIP* scip, /**< SCIP pointer (or NULL for exact comparison) */ 938 SCIP_VAR* var1, /**< first variable for comparison */ 939 SCIP_VAR* var2, /**< second variable for comparison */ 940 SCIP_Bool isfixed1, /**< whether var1 needs to be fixed */ 941 SCIP_Bool isfixed2, /**< whether var2 needs to be fixed */ 942 SCIP_Bool isneg1, /**< whether var1 needs to be negated */ 943 SCIP_Bool isneg2, /**< whether var2 needs to be negated */ 944 SCIP_Real infinity /**< values as least as large as this are regarded as infinite */ 945 ) 946 { 947 assert(var1 != NULL); 948 assert(var2 != NULL); 949 950 if( (! isfixed1) && isfixed2 ) 951 return -1; 952 if( isfixed1 && (! isfixed2) ) 953 return 1; 954 955 return compareVarsSignedPerm(scip, var1, var2, isneg1, isneg2, infinity); 956 } 957 958 /** sorts nodes of a signed permutation symmetry detection graph 959 * 960 * Variables are sorted first by whether they are fixed, then by their type, then 961 * by their objective coefficient, then by their lower bound and then by their upper bound. 962 * To take signed permutations into account, variable domains are centered at origin 963 * if the domain is finite. 964 * 965 * result: 966 * < 0: ind1 comes before (is better than) ind2 967 * = 0: both indices have the same value 968 * > 0: ind2 comes after (is worse than) ind2 969 */ 970 static 971 SCIP_DECL_SORTINDCOMP(SYMsortVarnodesSignedPermsym) 972 { 973 SYM_GRAPH* graph; 974 SCIP_VAR** vars; 975 SCIP_Bool* isfixedvar; 976 int nsymvars; 977 int locind1; 978 int locind2; 979 SCIP_Bool isneg1 = FALSE; 980 SCIP_Bool isneg2 = FALSE; 981 982 graph = (SYM_GRAPH*) dataptr; 983 assert(graph != NULL); 984 985 nsymvars = graph->nsymvars; 986 vars = graph->symvars; 987 assert(nsymvars > 0); 988 assert(vars != NULL); 989 990 isfixedvar = graph->isfixedvar; 991 assert(isfixedvar != NULL); 992 993 locind1 = ind1; 994 if( locind1 >= nsymvars ) 995 { 996 isneg1 = TRUE; 997 locind1 -= nsymvars; 998 } 999 locind2 = ind2; 1000 if( locind2 >= nsymvars ) 1001 { 1002 isneg2 = TRUE; 1003 locind2 -= nsymvars; 1004 } 1005 1006 return compareVarsFixedSignedPerm(NULL, vars[locind1], vars[locind2], isfixedvar[locind1], isfixedvar[locind2], 1007 isneg1, isneg2, graph->infinity); 1008 } 1009 1010 /** compares two operators 1011 * 1012 * Operators are sorted by their int values. 1013 * 1014 * result: 1015 * < 0: ind1 comes before (is better than) ind2 1016 * = 0: both indices have the same value 1017 * > 0: ind2 comes after (is worse than) ind2 1018 */ 1019 static 1020 int compareOps( 1021 int op1, /**< first operator in comparison */ 1022 int op2 /**< second operator in comparison */ 1023 ) 1024 { 1025 if( op1 < op2 ) 1026 return -1; 1027 else if( op1 > op2 ) 1028 return 1; 1029 1030 return 0; 1031 } 1032 1033 /** sorts operators corresponding to SCIP_EXPRHDLR* 1034 * 1035 * result: 1036 * < 0: ind1 comes before (is better than) ind2 1037 * = 0: both indices have the same value 1038 * > 0: ind2 comes after (is worse than) ind2 1039 */ 1040 static 1041 SCIP_DECL_SORTINDCOMP(SYMsortOpnodes) 1042 { 1043 int* vals; 1044 1045 vals = (int*) dataptr; 1046 1047 return compareOps(vals[ind1], vals[ind2]); 1048 } 1049 1050 /** sorts real values 1051 * 1052 * result: 1053 * < 0: ind1 comes before (is better than) ind2 1054 * = 0: both indices have the same value 1055 * > 0: ind2 comes after (is worse than) ind2 1056 */ 1057 static 1058 SCIP_DECL_SORTINDCOMP(SYMsortReals) 1059 { 1060 SCIP_Real* vals; 1061 1062 vals = (SCIP_Real*) dataptr; 1063 1064 if( vals[ind1] < vals[ind2] ) 1065 return -1; 1066 if( vals[ind1] > vals[ind2] ) 1067 return 1; 1068 1069 return 0; 1070 } 1071 1072 /** compares constraint nodes 1073 * 1074 * Nodes are sorted by their type of constraint, then by the lhs, and then by the rhs. 1075 * 1076 * result: 1077 * < 0: ind1 comes before (is better than) ind2 1078 * = 0: both indices have the same value 1079 * > 0: ind2 comes after (is worse than) ind2 1080 */ 1081 static 1082 int compareConsnodes( 1083 SCIP* scip, /**< SCIP data structure */ 1084 SYM_GRAPH* graph, /**< underlying symmetry detection graph */ 1085 int ind1, /**< index of first constraint node */ 1086 int ind2 /**< index of second constraint node */ 1087 ) 1088 { 1089 SCIP_CONS* cons1; 1090 SCIP_CONS* cons2; 1091 1092 assert(graph != NULL); 1093 assert(0 <= ind1 && ind1 < graph->nconsnodes); 1094 assert(0 <= ind2 && ind2 < graph->nconsnodes); 1095 1096 cons1 = graph->conss[ind1]; 1097 cons2 = graph->conss[ind2]; 1098 1099 if( SCIPconsGetHdlr(cons1) < SCIPconsGetHdlr(cons2) ) 1100 return -1; 1101 if( SCIPconsGetHdlr(cons1) > SCIPconsGetHdlr(cons2) ) 1102 return 1; 1103 1104 /* use SCIP's comparison functions if available */ 1105 if( scip != NULL ) 1106 { 1107 if( SCIPisLT(scip, graph->lhs[ind1], graph->lhs[ind2]) ) 1108 return -1; 1109 if( SCIPisGT(scip, graph->lhs[ind1], graph->lhs[ind2]) ) 1110 return 1; 1111 1112 if( SCIPisLT(scip, graph->rhs[ind1], graph->rhs[ind2]) ) 1113 return -1; 1114 if( SCIPisGT(scip, graph->rhs[ind1], graph->rhs[ind2]) ) 1115 return 1; 1116 } 1117 else 1118 { 1119 if( graph->lhs[ind1] < graph->lhs[ind2] ) 1120 return -1; 1121 if( graph->lhs[ind1] > graph->lhs[ind2] ) 1122 return 1; 1123 1124 if( graph->rhs[ind1] < graph->rhs[ind2] ) 1125 return -1; 1126 if( graph->rhs[ind1] > graph->rhs[ind2] ) 1127 return 1; 1128 } 1129 1130 return 0; 1131 } 1132 1133 /** sorts constraint nodes 1134 * 1135 * Nodes are sorted by their type of constraint, then by the lhs, and then by the rhs. 1136 * 1137 * result: 1138 * < 0: ind1 comes before (is better than) ind2 1139 * = 0: both indices have the same value 1140 * > 0: ind2 comes after (is worse than) ind2 1141 */ 1142 static 1143 SCIP_DECL_SORTINDCOMP(SYMsortConsnodes) 1144 { 1145 return compareConsnodes(NULL, (SYM_GRAPH*) dataptr, ind1, ind2); 1146 } 1147 1148 /** sorts edges 1149 * 1150 * Edges are sorted by their weights. 1151 * 1152 * result: 1153 * < 0: ind1 comes before (is better than) ind2 1154 * = 0: both indices have the same value 1155 * > 0: ind2 comes after (is worse than) ind2 1156 */ 1157 static 1158 SCIP_DECL_SORTINDCOMP(SYMsortEdges) 1159 { 1160 SYM_GRAPH* G; 1161 1162 G = (SYM_GRAPH*) dataptr; 1163 1164 if( G->edgevals[ind1] < G->edgevals[ind2] ) 1165 return -1; 1166 if( G->edgevals[ind1] > G->edgevals[ind2] ) 1167 return 1; 1168 1169 return 0; 1170 } 1171 1172 /** returns whether a node of the symmetry detection graph needs to be fixed */ 1173 static 1174 SCIP_Bool isFixedVar( 1175 SCIP_VAR* var, /**< active problem variable */ 1176 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */ 1177 ) 1178 { 1179 assert(var != NULL); 1180 1181 if ( (fixedtype & SYM_SPEC_INTEGER) && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER ) 1182 return TRUE; 1183 if ( (fixedtype & SYM_SPEC_BINARY) && SCIPvarGetType(var) == SCIP_VARTYPE_BINARY ) 1184 return TRUE; 1185 if ( (fixedtype & SYM_SPEC_REAL) && 1186 (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) ) 1187 return TRUE; 1188 return FALSE; 1189 } 1190 1191 /** computes colors of nodes and edges 1192 * 1193 * Colors are detected by sorting different types of nodes (variables, operators, values, and constraint) and edges. 1194 * If two consecutive nodes of the same type differ (e.g., different variable type), they are assigned a new color. 1195 */ 1196 SCIP_RETCODE SCIPcomputeSymgraphColors( 1197 SCIP* scip, /**< SCIP data structure */ 1198 SYM_GRAPH* graph, /**< symmetry detection graph */ 1199 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */ 1200 ) 1201 { 1202 SCIP_VAR* prevvar; 1203 SCIP_VAR* thisvar; 1204 SCIP_Real prevval; 1205 SCIP_Real thisval; 1206 SCIP_Bool previsneg; 1207 SCIP_Bool thisisneg; 1208 int* perm; 1209 int nusedvars; 1210 int len; 1211 int i; 1212 int color = 0; 1213 1214 assert(scip != NULL); 1215 assert(graph != NULL); 1216 1217 /* terminate early if colors have already been computed */ 1218 if( graph->islocked ) 1219 return SCIP_OKAY; 1220 1221 /* lock graph to be extended */ 1222 graph->islocked = TRUE; 1223 1224 /* possibly fix variables */ 1225 for( i = 0; i < graph->nsymvars; ++i ) 1226 { 1227 if( isFixedVar(graph->symvars[i], fixedtype) ) 1228 graph->isfixedvar[i] = TRUE; 1229 } 1230 1231 /* get number of variables used in symmetry detection graph */ 1232 switch( graph->symtype ) 1233 { 1234 case SYM_SYMTYPE_PERM: 1235 nusedvars = graph->nsymvars; 1236 break; 1237 default: 1238 assert(graph->symtype == SYM_SYMTYPE_SIGNPERM); 1239 nusedvars = 2 * graph->nsymvars; 1240 } /*lint !e788*/ 1241 1242 /* allocate memory for colors */ 1243 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->varcolors, nusedvars) ); 1244 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->opcolors, graph->nopnodes) ); 1245 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->valcolors, graph->nvalnodes) ); 1246 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->conscolors, graph->nconsnodes) ); 1247 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->edgecolors, graph->nedges) ); 1248 1249 /* allocate permutation of arrays, will be initialized by SCIPsort() */ 1250 len = graph->nedges; 1251 if ( graph->nopnodes > len ) 1252 len = graph->nopnodes; 1253 if ( graph->nvalnodes > len ) 1254 len = graph->nvalnodes; 1255 if ( graph->nconsnodes > len ) 1256 len = graph->nconsnodes; 1257 if ( nusedvars > len ) 1258 len = nusedvars; 1259 1260 SCIP_CALL( SCIPallocBufferArray(scip, &perm, len) ); 1261 1262 /* find colors of variable nodes */ 1263 assert(graph->nsymvars > 0); 1264 switch( graph->symtype ) 1265 { 1266 case SYM_SYMTYPE_PERM: 1267 SCIPsort(perm, SYMsortVarnodesPermsym, (void*) graph, nusedvars); 1268 1269 graph->varcolors[perm[0]] = color; 1270 prevvar = graph->symvars[perm[0]]; 1271 1272 for( i = 1; i < nusedvars; ++i ) 1273 { 1274 thisvar = graph->symvars[perm[i]]; 1275 1276 if( graph->isfixedvar[i] || compareVars(scip, prevvar, thisvar) != 0 ) 1277 ++color; 1278 1279 graph->varcolors[perm[i]] = color; 1280 prevvar = thisvar; 1281 } 1282 graph->nvarcolors = color; 1283 break; 1284 default: 1285 assert(graph->symtype == SYM_SYMTYPE_SIGNPERM); 1286 1287 SCIPsort(perm, SYMsortVarnodesSignedPermsym, (void*) graph, nusedvars); 1288 1289 graph->varcolors[perm[0]] = color; 1290 1291 /* store information about first variable */ 1292 if( perm[0] < graph->nsymvars ) 1293 { 1294 previsneg = FALSE; 1295 prevvar = graph->symvars[perm[0]]; 1296 } 1297 else 1298 { 1299 previsneg = TRUE; 1300 prevvar = graph->symvars[perm[0] - graph->nsymvars]; 1301 } 1302 1303 /* compute colors of remaining variables */ 1304 for( i = 1; i < nusedvars; ++i ) 1305 { 1306 if( perm[i] < graph->nsymvars ) 1307 { 1308 thisisneg = FALSE; 1309 thisvar = graph->symvars[perm[i]]; 1310 } 1311 else 1312 { 1313 thisisneg = TRUE; 1314 thisvar = graph->symvars[perm[i] - graph->nsymvars]; 1315 } 1316 1317 if( graph->isfixedvar[i % graph->nsymvars] 1318 || compareVarsSignedPerm(scip, prevvar, thisvar, previsneg, thisisneg, graph->infinity) != 0 ) 1319 ++color; 1320 1321 graph->varcolors[perm[i]] = color; 1322 prevvar = thisvar; 1323 previsneg = thisisneg; 1324 } 1325 graph->nvarcolors = color; 1326 } /*lint !e788*/ 1327 1328 /* find colors of operator nodes */ 1329 if( graph->nopnodes > 0 ) 1330 { 1331 int prevop; 1332 int thisop; 1333 1334 SCIPsort(perm, SYMsortOpnodes, (void*) graph->ops, graph->nopnodes); 1335 1336 graph->opcolors[perm[0]] = ++color; 1337 prevop = graph->ops[perm[0]]; 1338 1339 for( i = 1; i < graph->nopnodes; ++i ) 1340 { 1341 thisop = graph->ops[perm[i]]; 1342 1343 if( compareOps(prevop, thisop) != 0 ) 1344 ++color; 1345 1346 graph->opcolors[perm[i]] = color; 1347 prevop = thisop; 1348 } 1349 } 1350 1351 /* find colors of value nodes */ 1352 if( graph->nvalnodes > 0 ) 1353 { 1354 SCIPsort(perm, SYMsortReals, (void*) graph->vals, graph->nvalnodes); 1355 1356 graph->valcolors[perm[0]] = ++color; 1357 prevval = graph->vals[perm[0]]; 1358 1359 for( i = 1; i < graph->nvalnodes; ++i ) 1360 { 1361 thisval = graph->vals[perm[i]]; 1362 1363 if( ! SCIPisEQ(scip, prevval, thisval) ) 1364 ++color; 1365 1366 graph->valcolors[perm[i]] = color; 1367 prevval = thisval; 1368 } 1369 } 1370 1371 /* find colors of constraint nodes */ 1372 if( graph->nconsnodes > 0 ) 1373 { 1374 SCIPsort(perm, SYMsortConsnodes, (void*) graph, graph->nconsnodes); 1375 1376 graph->conscolors[perm[0]] = ++color; 1377 1378 for( i = 1; i < graph->nconsnodes; ++i ) 1379 { 1380 if( compareConsnodes(scip, graph, perm[i-1], perm[i]) != 0 ) 1381 ++color; 1382 1383 graph->conscolors[perm[i]] = color; 1384 } 1385 } 1386 1387 /* find colors of edges */ 1388 if( graph->nedges > 0 ) 1389 { 1390 SCIPsort(perm, SYMsortEdges, (void*) graph, graph->nedges); 1391 1392 /* check whether edges are colored; due to sorting, only check first edge */ 1393 if( SCIPisInfinity(scip, graph->edgevals[perm[0]]) ) 1394 { 1395 /* all edges are uncolored */ 1396 for( i = 0; i < graph->nedges; ++i ) 1397 graph->edgecolors[perm[i]] = -1; 1398 } 1399 else 1400 { 1401 /* first edge is colored */ 1402 graph->edgecolors[perm[0]] = ++color; 1403 prevval = graph->edgevals[perm[0]]; 1404 1405 for( i = 1; i < graph->nedges; ++i ) 1406 { 1407 thisval = graph->edgevals[perm[i]]; 1408 1409 /* terminate if edges are not colored anymore */ 1410 if( SCIPisInfinity(scip, thisval) ) 1411 break; 1412 1413 if( ! SCIPisEQ(scip, prevval, thisval) ) 1414 ++color; 1415 1416 graph->edgecolors[perm[i]] = color; 1417 prevval = thisval; 1418 } 1419 1420 /* check whether all edges are equivalent */ 1421 if( i == graph->nedges && graph->edgecolors[perm[0]] == graph->edgecolors[perm[i-1]] ) 1422 graph->uniqueedgetype = TRUE; 1423 1424 /* assign uncolored edges color -1 */ 1425 for( ; i < graph->nedges; ++i ) 1426 graph->edgecolors[perm[i]] = -1; 1427 } 1428 } 1429 1430 SCIPfreeBufferArray(scip, &perm); 1431 1432 return SCIP_OKAY; 1433 } 1434 1435 1436 /* general methods */ 1437 1438 /** returns the type of symmetries encoded in graph */ 1439 SYM_SYMTYPE SCIPgetSymgraphSymtype( 1440 SYM_GRAPH* graph /**< symmetry detection graph */ 1441 ) 1442 { 1443 assert(graph != NULL); 1444 1445 return graph->symtype; 1446 } 1447 1448 /** returns the variables in a symmetry detection graph */ 1449 SCIP_VAR** SCIPgetSymgraphVars( 1450 SYM_GRAPH* graph /**< symmetry detection graph */ 1451 ) 1452 { 1453 assert(graph != NULL); 1454 1455 return graph->symvars; 1456 } 1457 1458 /** returns the number of variables in a symmetry detection graph */ 1459 int SCIPgetSymgraphNVars( 1460 SYM_GRAPH* graph /**< symmetry detection graph */ 1461 ) 1462 { 1463 assert(graph != NULL); 1464 1465 return graph->nsymvars; 1466 } 1467 1468 /** returns the number of constraint nodes in a symmetry detection graph */ 1469 int SCIPgetSymgraphNConsnodes( 1470 SYM_GRAPH* graph /**< symmetry detection graph */ 1471 ) 1472 { 1473 assert(graph != NULL); 1474 1475 return graph->nconsnodes; 1476 } 1477 1478 /** returns the number of non-variable nodes in a graph */ 1479 int SCIPgetSymgraphNNodes( 1480 SYM_GRAPH* graph /**< symmetry detection graph */ 1481 ) 1482 { 1483 assert(graph != NULL); 1484 1485 return graph->nnodes; 1486 } 1487 1488 /** returns the number of edges in a graph */ 1489 int SCIPgetSymgraphNEdges( 1490 SYM_GRAPH* graph /**< symmetry detection graph */ 1491 ) 1492 { 1493 assert(graph != NULL); 1494 1495 return graph->nedges; 1496 } 1497 1498 /** return the first node index of an edge */ 1499 int SCIPgetSymgraphEdgeFirst( 1500 SYM_GRAPH* graph, /**< symmetry detection graph */ 1501 int edgeidx /**< index of edge */ 1502 ) 1503 { 1504 assert(graph != NULL); 1505 assert(0 <= edgeidx && edgeidx < graph->nedges); 1506 1507 return graph->edgefirst[edgeidx]; 1508 } 1509 1510 /** return the second node index of an edge */ 1511 int SCIPgetSymgraphEdgeSecond( 1512 SYM_GRAPH* graph, /**< symmetry detection graph */ 1513 int edgeidx /**< index of edge */ 1514 ) 1515 { 1516 assert(graph != NULL); 1517 assert(0 <= edgeidx && edgeidx < graph->nedges); 1518 1519 return graph->edgesecond[edgeidx]; 1520 } 1521 1522 /** returns the color of a variable node */ 1523 int SCIPgetSymgraphVarnodeColor( 1524 SYM_GRAPH* graph, /**< symmetry detection graph */ 1525 int nodeidx /**< index of variable node */ 1526 ) 1527 { 1528 assert(graph != NULL); 1529 assert(graph->islocked); 1530 1531 switch( graph->symtype ) 1532 { 1533 case SYM_SYMTYPE_PERM: 1534 assert(0 <= nodeidx && nodeidx < graph->nsymvars); 1535 break; 1536 default: 1537 assert(graph->symtype == SYM_SYMTYPE_SIGNPERM); 1538 assert(0 <= nodeidx && nodeidx < 2 * graph->nsymvars); 1539 } /*lint !e788*/ 1540 1541 return graph->varcolors[nodeidx]; 1542 } 1543 1544 /** returns the type of a node */ 1545 SYM_NODETYPE SCIPgetSymgraphNodeType( 1546 SYM_GRAPH* graph, /**< symmetry detection graph */ 1547 int nodeidx /**< index of node */ 1548 ) 1549 { 1550 assert(graph != NULL); 1551 assert(nodeidx < graph->nnodes); 1552 1553 if( nodeidx < 0 ) 1554 return SYM_NODETYPE_VAR; 1555 1556 return graph->nodetypes[nodeidx]; 1557 } 1558 1559 /** returns the color of a non-variable node */ 1560 int SCIPgetSymgraphNodeColor( 1561 SYM_GRAPH* graph, /**< symmetry detection graph */ 1562 int nodeidx /**< index of node */ 1563 ) 1564 { /*lint --e{788}*/ 1565 assert(graph != NULL); 1566 assert(0 <= nodeidx && nodeidx < graph->nnodes); 1567 assert(graph->islocked); 1568 1569 switch( graph->nodetypes[nodeidx] ) 1570 { 1571 case SYM_NODETYPE_OPERATOR: 1572 return graph->opcolors[graph->nodeinfopos[nodeidx]]; 1573 case SYM_NODETYPE_VAL: 1574 return graph->valcolors[graph->nodeinfopos[nodeidx]]; 1575 default: 1576 assert(graph->nodetypes[nodeidx] == SYM_NODETYPE_CONS); 1577 } 1578 1579 return graph->conscolors[graph->nodeinfopos[nodeidx]]; 1580 } 1581 1582 /** returns whether an edge is colored */ 1583 SCIP_Bool SCIPisSymgraphEdgeColored( 1584 SYM_GRAPH* graph, /**< symmetry detection graph */ 1585 int edgeidx /**< index of edge */ 1586 ) 1587 { 1588 assert(graph != NULL); 1589 assert(0 <= edgeidx && edgeidx < graph->nedges); 1590 1591 if( ! graph->islocked || graph->edgecolors[edgeidx] == -1 ) 1592 return FALSE; 1593 1594 return TRUE; 1595 } 1596 1597 /** returns color of an edge */ 1598 int SCIPgetSymgraphEdgeColor( 1599 SYM_GRAPH* graph, /**< symmetry detection graph */ 1600 int edgeidx /**< index of edge */ 1601 ) 1602 { 1603 assert(graph != NULL); 1604 assert(0 <= edgeidx && edgeidx < graph->nedges); 1605 assert(SCIPisSymgraphEdgeColored(graph, edgeidx)); 1606 1607 return graph->edgecolors[edgeidx]; 1608 } 1609 1610 /** returns the number of unique variable colors in the graph */ 1611 int SCIPgetSymgraphNVarcolors( 1612 SYM_GRAPH* graph /**< symmetry detection graph */ 1613 ) 1614 { 1615 assert(graph != NULL); 1616 1617 if( graph->nvarcolors < 0 ) 1618 return graph->nsymvars; 1619 1620 return graph->nvarcolors; 1621 } 1622 1623 /** returns whether the graph has a unique edge type */ 1624 SCIP_Bool SCIPhasGraphUniqueEdgetype( 1625 SYM_GRAPH* graph /**< symmetry detection graph */ 1626 ) 1627 { 1628 assert(graph != NULL); 1629 1630 return graph->uniqueedgetype; 1631 } 1632 1633 /** creates consnodeperm array for symmetry detection graph 1634 * 1635 * @note @p colors of symmetry detection graph must have been computed 1636 */ 1637 SCIP_RETCODE SCIPcreateSymgraphConsnodeperm( 1638 SCIP* scip, /**< SCIP data structure */ 1639 SYM_GRAPH* graph /**< symmetry detection graph */ 1640 ) 1641 { 1642 assert(scip != NULL); 1643 assert(graph != NULL); 1644 assert(graph->islocked); 1645 1646 /* either there are no constraint nodes or we have already computed the permutation */ 1647 if( graph->nconsnodes <= 0 || graph->consnodeperm != NULL ) 1648 return SCIP_OKAY; 1649 1650 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->consnodeperm, graph->nconsnodes) ); 1651 SCIPsort(graph->consnodeperm, SYMsortConsnodes, (void*) graph, graph->nconsnodes); 1652 1653 return SCIP_OKAY; 1654 } 1655 1656 /** frees consnodeperm array for symmetry detection graph */ 1657 SCIP_RETCODE SCIPfreeSymgraphConsnodeperm( 1658 SCIP* scip, /**< SCIP data structure */ 1659 SYM_GRAPH* graph /**< symmetry detection graph */ 1660 ) 1661 { 1662 assert(scip != NULL); 1663 assert(graph != NULL); 1664 assert(graph->islocked); 1665 1666 SCIPfreeBlockMemoryArrayNull(scip, &graph->consnodeperm, graph->nconsnodes); 1667 1668 return SCIP_OKAY; 1669 } 1670 1671 /** returns consnodeperm array for symmetry detection graph 1672 * 1673 * @note @p colors of symmetry detection graph must have been computed 1674 */ 1675 int* SCIPgetSymgraphConsnodeperm( 1676 SCIP* scip, /**< SCIP data structure */ 1677 SYM_GRAPH* graph /**< symmetry detection graph */ 1678 ) 1679 { 1680 assert(scip != NULL); 1681 assert(graph != NULL); 1682 assert(graph->islocked); 1683 1684 SCIP_CALL_ABORT( SCIPcreateSymgraphConsnodeperm(scip, graph) ); 1685 1686 return graph->consnodeperm; 1687 } 1688 1689 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant. 1690 * 1691 * For permutation symmetries, active variables as encoded in SCIP are used. For signed permutation symmetries, 1692 * active variables are shifted such that their domain is centered at 0 (if both their upper and lower bounds 1693 * are finite). 1694 * 1695 * @note @p constant needs to be initialized! 1696 */ 1697 SCIP_RETCODE SCIPgetActiveVariables( 1698 SCIP* scip, /**< SCIP data structure */ 1699 SYM_SYMTYPE symtype, /**< type of symmetries for which variables are required */ 1700 SCIP_VAR*** vars, /**< pointer to vars array to get active variables for */ 1701 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */ 1702 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 1703 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 1704 SCIP_Bool transformed /**< transformed constraint? */ 1705 ) 1706 { 1707 SCIP_Real ub; 1708 SCIP_Real lb; 1709 int requiredsize; 1710 int v; 1711 1712 assert(scip != NULL); 1713 assert(vars != NULL); 1714 assert(scalars != NULL); 1715 assert(*vars != NULL); 1716 assert(*scalars != NULL); 1717 assert(nvars != NULL); 1718 assert(constant != NULL); 1719 1720 if( transformed ) 1721 { 1722 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) ); 1723 1724 if( requiredsize > *nvars ) 1725 { 1726 SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) ); 1727 SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) ); 1728 1729 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) ); 1730 assert(requiredsize <= *nvars); 1731 } 1732 } 1733 else 1734 { 1735 for( v = 0; v < *nvars; ++v ) 1736 { 1737 SCIP_CALL( SCIPvarGetOrigvarSum(&(*vars)[v], &(*scalars)[v], constant) ); 1738 } 1739 } 1740 1741 /* possibly post-process active variables */ 1742 if( symtype == SYM_SYMTYPE_SIGNPERM ) 1743 { 1744 /* center variables at origin if their domain is finite */ 1745 for (v = 0; v < *nvars; ++v) 1746 { 1747 ub = SCIPvarGetUbGlobal((*vars)[v]); 1748 lb = SCIPvarGetLbGlobal((*vars)[v]); 1749 1750 if ( SCIPisInfinity(scip, ub) || SCIPisInfinity(scip, -lb) ) 1751 continue; 1752 1753 *constant += (*scalars)[v] * (ub + lb) / 2; 1754 } 1755 } 1756 1757 return SCIP_OKAY; 1758 } 1759 1760 /** frees symmetry information of an expression */ 1761 SCIP_RETCODE SCIPfreeSymDataExpr( 1762 SCIP* scip, /**< SCIP data structure */ 1763 SYM_EXPRDATA** symdata /**< symmetry information of an expression */ 1764 ) 1765 { 1766 assert(scip != NULL); 1767 assert(symdata != NULL); 1768 1769 if( (*symdata)->nconstants > 0 ) 1770 { 1771 SCIPfreeBlockMemoryArrayNull(scip, &(*symdata)->constants, (*symdata)->nconstants); 1772 } 1773 if( (*symdata)->ncoefficients > 0 ) 1774 { 1775 SCIPfreeBlockMemoryArrayNull(scip, &(*symdata)->coefficients, (*symdata)->ncoefficients); 1776 SCIPfreeBlockMemoryArrayNull(scip, &(*symdata)->children, (*symdata)->ncoefficients); 1777 } 1778 SCIPfreeBlockMemory(scip, symdata); 1779 1780 return SCIP_OKAY; 1781 } 1782 1783 /** returns number of coefficients from exprdata */ 1784 int SCIPgetSymExprdataNConstants( 1785 SYM_EXPRDATA* symdata /**< symmetry information of an expression */ 1786 ) 1787 { 1788 assert(symdata != NULL); 1789 1790 return symdata->nconstants; 1791 } 1792 1793 /** returns number of coefficients form exprdata */ 1794 SCIP_Real* SCIPgetSymExprdataConstants( 1795 SYM_EXPRDATA* symdata /**< symmetry information of an expression */ 1796 ) 1797 { 1798 assert(symdata != NULL); 1799 1800 return symdata->constants; 1801 } 1802 1803 /** gets coefficient of expression from parent expression */ 1804 SCIP_RETCODE SCIPgetCoefSymData( 1805 SCIP* scip, /**< SCIP data structure */ 1806 SCIP_EXPR* expr, /**< expression for which coefficient needs to be found */ 1807 SCIP_EXPR* parentexpr, /**< parent of expr */ 1808 SCIP_Real* coef, /**< buffer to store coefficient */ 1809 SCIP_Bool* success /**< whether a coefficient is found */ 1810 ) 1811 { 1812 SYM_EXPRDATA* symdata; 1813 int i; 1814 1815 assert(scip != NULL); 1816 assert(expr != NULL); 1817 assert(parentexpr != NULL); 1818 assert(coef != NULL); 1819 assert(success != NULL); 1820 1821 *success = FALSE; 1822 1823 /* parent does not assign coefficients to its children */ 1824 if( ! SCIPexprhdlrHasGetSymData(SCIPexprGetHdlr(parentexpr)) ) 1825 return SCIP_OKAY; 1826 1827 SCIP_CALL( SCIPgetSymDataExpr(scip, parentexpr, &symdata) ); 1828 1829 /* parent does not assign coefficients to its children */ 1830 if( symdata->ncoefficients < 1 ) 1831 { 1832 SCIP_CALL( SCIPfreeSymDataExpr(scip, &symdata) ); 1833 1834 return SCIP_OKAY; 1835 } 1836 1837 /* search for expr in the children of parentexpr */ 1838 for( i = 0; i < symdata->ncoefficients; ++i ) 1839 { 1840 if( symdata->children[i] == expr ) 1841 { 1842 *coef = symdata->coefficients[i]; 1843 *success = TRUE; 1844 break; 1845 } 1846 } 1847 1848 SCIP_CALL( SCIPfreeSymDataExpr(scip, &symdata) ); 1849 1850 return SCIP_OKAY; 1851 } 1852