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 symmetry_orbital.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for handling symmetries by orbital reduction 28 * @author Jasper van Doornmalen 29 * 30 * Orbital fixing is introduced by@n 31 * F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003. 32 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the 33 * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other 34 * variables in the orbit is fixed to 0 or 1, respectively. This method only works for binary variables. 35 * Margot considers the subgroup that stabilizes the set of one-fixings setwise. We determine a subgroup of this group, 36 * namely the group generated by the given symmetry group component generators, where the generators satisfy the 37 * stabilization condition. 38 * 39 * A generalisation is given in the unified symmetry handling constraint paper, Section 4.3 and 5.1 in [vD,H]:@n 40 * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, 41 * https://doi.org/10.48550/arXiv.2211.01295. 42 * 43 * We assume that the provided symmetries (given by a generating permutation set) are symmetries for the problem at the 44 * root node. It is possible that dual (presolving) reductions break this symmetry. As an example, in cons_components.c, 45 * if the problem contains an independent component (i.e., variables are not connected logically by constraints), then 46 * these individual 'components' can be solved. If an optimal solution is easily retrieved, the variables of this 47 * component are fixed, even if symmetrically equivalent solutions exist. Another example is 'stuffing' for linear 48 * constraints. 49 * 50 * To illustrate this, consider the example \f$\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b, 51 * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the 52 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting 53 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would 54 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different 55 * values). 56 * 57 * We have observed, and assume, that such dual reductions only take place at presolving or in the root node. 58 * So, to avoid this situation, if we detect that a symmetry-breaking reduction is applied at the root node, 59 * we disable orbital fixing for certain generating permutations based on the bounds of the affected global variables, 60 * see identifyOrbitalSymmetriesBroken. 61 * 62 * With the assumption that the symmetries are actual symmetries at the root node, symmetries are broken by the 63 * branching decisions. 64 * For a branch-and-bound tree node \f$\beta\f$ and variable vector \f$x\f$, 65 * let \f$\sigma_\beta(x)\f$ be the permuted and restricted vector \f$x\f$ that enumerates the branching variables, 66 * following the path of the root node to \f$\beta\f$ (cf., Example 11 in [vD,H]). 67 * Consider a component of the symmetry group, given by a set of generating permutations. 68 * Of this set, we select these permutations (not disabled by identifyOrbitalSymmetriesBroken) 69 * for which te variable domains of the branched variables \f$\sigma_\beta(x)\f$ 70 * are smaller or equal to the variable domains of the permuted variable. This defines a group (cf. [vD,H, Lemma 22]). 71 * This group is a subgroup of \f$\delta^\beta\f$ of [vD,H, Section 4.3], meaning that the reductions are valid. 72 * 73 * The reductions are: 74 * 75 * - For each orbit of the group, every variable domains can be shrunk to the intersection of all variable domains in 76 * the orbit. 77 * - The domains of the branching variables are upper bounds to the domains of the variables in its orbits. 78 * 79 * For orbital fixing, it is crucial that the vectors \f$\sigma_\beta(x)\f$ are the branching variables up to node 80 * \f$\beta\f$ in the given order. Since SCIP can change the tree structure during solving (re-writing history), 81 * we store the original branching decisions at the moment they are made. See event_shadowtree.c . 82 */ 83 84 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 85 86 #include "blockmemshell/memory.h" 87 #include "scip/symmetry_orbital.h" 88 #include "scip/pub_cons.h" 89 #include "scip/pub_message.h" 90 #include "scip/pub_var.h" 91 #include "scip/struct_var.h" 92 #include "scip/type_var.h" 93 #include "scip/scip.h" 94 #include "scip/scip_branch.h" 95 #include "scip/scip_conflict.h" 96 #include "scip/scip_cons.h" 97 #include "scip/scip_copy.h" 98 #include "scip/scip_cut.h" 99 #include "scip/scip_general.h" 100 #include "scip/scip_lp.h" 101 #include "scip/scip_mem.h" 102 #include "scip/scip_message.h" 103 #include "scip/scip_numerics.h" 104 #include "scip/scip_param.h" 105 #include "scip/scip_prob.h" 106 #include "scip/scip_probing.h" 107 #include "scip/scip_sol.h" 108 #include "scip/scip_var.h" 109 #include "scip/debug.h" 110 #include "scip/struct_scip.h" 111 #include "scip/struct_mem.h" 112 #include "scip/struct_tree.h" 113 #include "scip/symmetry.h" 114 #include "scip/event_shadowtree.h" 115 #include <ctype.h> 116 #include <string.h> 117 #include <memory.h> 118 119 120 /* event handler properties */ 121 #define EVENTHDLR_SYMMETRY_NAME "symmetry_orbital" 122 #define EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction" 123 124 125 /* 126 * Data structures 127 */ 128 129 130 /** data for orbital reduction component propagator */ 131 struct OrbitalReductionComponentData 132 { 133 SCIP_NODE* lastnode; /**< last node processed by orbital reduction component */ 134 SCIP_Real* globalvarlbs; /**< global variable lower bounds until before branching starts */ 135 SCIP_Real* globalvarubs; /**< global variable upper bounds until before branching starts */ 136 int** perms; /**< the permutations for orbital reduction */ 137 int nperms; /**< the number of permutations in perms */ 138 SCIP_VAR** permvars; /**< array consisting of the variables of this component */ 139 int npermvars; /**< number of vars in this component */ 140 SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */ 141 142 SCIP_Bool symmetrybrokencomputed; /**< whether the symmetry broken information is computed already */ 143 int* symbrokenvarids; /**< variables to be stabilized because the symmetry is globally broken */ 144 int nsymbrokenvarids; /**< symbrokenvarids array length, is 0 iff symbrokenvarids is NULL */ 145 146 SCIP_Bool treewarninggiven; /**< whether a warning is given for missing nodes in shadowtree */ 147 }; 148 typedef struct OrbitalReductionComponentData ORCDATA; 149 150 151 /** data for orbital reduction propagator */ 152 struct SCIP_OrbitalReductionData 153 { 154 SCIP_EVENTHDLR* shadowtreeeventhdlr;/**< eventhandler for the shadow tree data structure */ 155 SCIP_EVENTHDLR* globalfixeventhdlr; /**< event handler for handling global variable bound reductions */ 156 157 ORCDATA** componentdatas; /**< array of pointers to individual components for orbital reduction */ 158 int ncomponents; /**< number of orbital reduction datas in array */ 159 int maxncomponents; /**< allocated orbital reduction datas array size */ 160 int nred; /**< total number of reductions */ 161 int ncutoff; /**< total number of cutoffs */ 162 }; 163 164 165 /* 166 * Local methods 167 */ 168 169 170 /** identifies the orbits at which symmetry is broken according to the global bounds 171 * 172 * An example of a symmetry-breaking constraint is cons_components. 173 */ 174 static 175 SCIP_RETCODE identifyOrbitalSymmetriesBroken( 176 SCIP* scip, /**< pointer to SCIP data structure */ 177 ORCDATA* orcdata /**< pointer to data for orbital reduction data */ 178 ) 179 { 180 SCIP_DISJOINTSET* orbitset; 181 int i; 182 int j; 183 int p; 184 int* perm; 185 int* varorbitids; 186 int* varorbitidssort; 187 int orbitbegin; 188 int orbitend; 189 int orbitid; 190 int maxnsymbrokenvarids; 191 SCIP_Real orbitglb; 192 SCIP_Real orbitgub; 193 SCIP_Bool orbitsymbroken; 194 195 assert( scip != NULL ); 196 assert( orcdata != NULL ); 197 assert( !orcdata->symmetrybrokencomputed ); 198 orcdata->symbrokenvarids = NULL; 199 orcdata->nsymbrokenvarids = 0; 200 maxnsymbrokenvarids = 0; 201 202 /* determine all orbits */ 203 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) ); 204 for (p = 0; p < orcdata->nperms; ++p) 205 { 206 perm = orcdata->perms[p]; 207 assert( perm != NULL ); 208 209 for (i = 0; i < orcdata->npermvars; ++i) 210 { 211 j = perm[i]; 212 if ( i != j ) 213 SCIPdisjointsetUnion(orbitset, i, j, FALSE); 214 } 215 } 216 217 #ifndef NDEBUG 218 /* no arithmetic is performed on these bounds, so we can compare floats by their value exactly */ 219 for (i = 0; i < orcdata->npermvars; ++i) 220 { 221 assert( SCIPvarGetLbGlobal(orcdata->permvars[i]) == orcdata->globalvarlbs[i] ); /*lint !e777*/ 222 assert( SCIPvarGetUbGlobal(orcdata->permvars[i]) == orcdata->globalvarubs[i] ); /*lint !e777*/ 223 } 224 #endif 225 226 /* sort all orbits */ 227 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) ); 228 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) ); 229 for (i = 0; i < orcdata->npermvars; ++i) 230 varorbitids[i] = SCIPdisjointsetFind(orbitset, i); 231 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars); 232 233 /* iterate over all orbits and get the maximal orbit lower bound and minimal orbit upper bound */ 234 for (orbitbegin = 0; orbitbegin < orcdata->npermvars; orbitbegin = orbitend) 235 { 236 /* get id of the orbit */ 237 orbitid = varorbitids[varorbitidssort[orbitbegin]]; 238 239 /* the orbit must have the same bounds */ 240 orbitsymbroken = FALSE; 241 j = varorbitids[orbitbegin]; 242 orbitglb = orcdata->globalvarlbs[j]; 243 orbitgub = orcdata->globalvarubs[j]; 244 for (i = orbitbegin + 1; i < orcdata->npermvars; ++i) 245 { 246 j = varorbitidssort[i]; 247 248 /* stop if j is not the element in the orbit, then it is part of the next orbit */ 249 if ( varorbitids[j] != orbitid ) 250 break; 251 252 if ( !orbitsymbroken ) 253 { 254 if ( !SCIPEQ(scip, orbitglb, orcdata->globalvarlbs[j]) || !SCIPEQ(scip, orbitgub, orcdata->globalvarubs[j]) ) 255 { 256 orbitsymbroken = TRUE; 257 break; 258 } 259 } 260 } 261 /* the loop above has terminated, so i is either orcdata->npermvars or varorbitidssort[i] is in the next orbit, 262 * and orbitglb and orbitgub are the maximal global lower bound and minimal global upper bound in orbit orbitid */ 263 orbitend = i; 264 265 /* symmetry is broken within this orbit if the intersection of the global variable domains are empty */ 266 if ( orbitsymbroken ) 267 { 268 /* add all variable ids in the orbit to the symbrokenvarids array: resize if needed */ 269 if ( orcdata->nsymbrokenvarids + orbitend - orbitbegin > maxnsymbrokenvarids ) 270 { 271 int newsize; 272 273 newsize = SCIPcalcMemGrowSize(scip, orcdata->nsymbrokenvarids + orbitend - orbitbegin); 274 assert( newsize >= 0 ); 275 276 if ( orcdata->nsymbrokenvarids == 0 ) 277 { 278 assert( orcdata->symbrokenvarids == NULL ); 279 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->symbrokenvarids, newsize) ); 280 } 281 else 282 { 283 assert( orcdata->symbrokenvarids != NULL ); 284 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orcdata->symbrokenvarids, 285 maxnsymbrokenvarids, newsize) ); 286 } 287 288 maxnsymbrokenvarids = newsize; 289 } 290 291 /* add all variable ids in the orbit to the symbrokenvarids array: add */ 292 for (i = orbitbegin; i < orbitend; ++i) 293 { 294 j = varorbitidssort[i]; 295 assert( varorbitids[j] == orbitid ); 296 assert( orcdata->nsymbrokenvarids < maxnsymbrokenvarids ); 297 orcdata->symbrokenvarids[orcdata->nsymbrokenvarids++] = j; 298 } 299 } 300 } 301 302 /* shrink the allocated array size to the actually needed size */ 303 assert( orcdata->nsymbrokenvarids <= maxnsymbrokenvarids ); 304 if ( orcdata->nsymbrokenvarids > 0 && orcdata->nsymbrokenvarids < maxnsymbrokenvarids ) 305 { 306 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orcdata->symbrokenvarids, 307 maxnsymbrokenvarids, orcdata->nsymbrokenvarids) ); 308 } 309 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) ); 310 311 /* mark that this method is executed for the component */ 312 orcdata->symmetrybrokencomputed = TRUE; 313 314 /* output information */ 315 if ( orcdata->nsymbrokenvarids > 0 ) 316 { 317 SCIPwarningMessage(scip, 318 "Orbital fixing symmetry for %p broken before symmetry. Requires fixing %d/%d affected variables.\n", 319 (void*) orcdata, orcdata->nsymbrokenvarids, orcdata->npermvars); 320 } 321 322 SCIPfreeBufferArray(scip, &varorbitidssort); 323 SCIPfreeBufferArray(scip, &varorbitids); 324 SCIPfreeDisjointset(scip, &orbitset); 325 326 return SCIP_OKAY; 327 } 328 329 330 /** populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions 331 * 332 * The symmetry subgroup considered is generated by all permutations where for all branching variables \f$x$ 333 * with permuted variable \f$y$ for all possible variable assignments we have \f$x \leq y$. 334 * We restrict ourselves to testing this only for the group generators. 335 */ 336 static 337 SCIP_RETCODE orbitalReductionGetSymmetryStabilizerSubgroup( 338 SCIP* scip, /**< pointer to SCIP data structure */ 339 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */ 340 int** chosenperms, /**< pointer to permutations that are chosen */ 341 int* nchosenperms, /**< pointer to store the number of chosen permutations */ 342 SCIP_Real* varlbs, /**< array of orcdata->permvars variable LBs. If NULL, use local bounds */ 343 SCIP_Real* varubs, /**< array of orcdata->permvars variable UBs. If NULL, use local bounds */ 344 int* branchedvarindices, /**< array of given branching decisions, in branching order */ 345 SCIP_Bool* inbranchedvarindices, /**< array stating whether variable with index in orcdata->permvars is 346 * contained in the branching decisions. */ 347 int nbranchedvarindices /**< number of branching decisions */ 348 ) 349 { 350 int i; 351 int p; 352 int* perm; 353 int varid; 354 int varidimage; 355 356 assert( scip != NULL ); 357 assert( orcdata != NULL ); 358 assert( chosenperms != NULL ); 359 assert( nchosenperms != NULL ); 360 assert( (varlbs == NULL) == (varubs == NULL) ); 361 assert( branchedvarindices != NULL ); 362 assert( inbranchedvarindices != NULL ); 363 assert( nbranchedvarindices >= 0 ); 364 assert( orcdata->symmetrybrokencomputed ); 365 assert( (orcdata->nsymbrokenvarids == 0) == (orcdata->symbrokenvarids == NULL) ); 366 367 *nchosenperms = 0; 368 369 for (p = 0; p < orcdata->nperms; ++p) 370 { 371 perm = orcdata->perms[p]; 372 373 /* make sure that the symmetry broken orbit variable indices are met with equality */ 374 for (i = 0; i < orcdata->nsymbrokenvarids; ++i) 375 { 376 varid = orcdata->symbrokenvarids[i]; 377 assert( varid >= 0 ); 378 assert( varid < orcdata->npermvars ); 379 assert( orcdata->permvars[varid] != NULL ); 380 varidimage = perm[varid]; 381 assert( varidimage >= 0 ); 382 assert( varidimage < orcdata->npermvars ); 383 assert( orcdata->permvars[varidimage] != NULL ); 384 385 /* branching variable is not affected by this permutation */ 386 if ( varidimage == varid ) 387 continue; 388 389 /* the variables on which symmetry is broken must be permuted to entries with the same fixed value 390 * 391 * Because we check a whole orbit of the group and perm is part of it, it suffices to compare the upper bound 392 * of varid with the lower bound of varidimage. Namely, for all indices i, \f$lb_i \leq ub_i\f$, so we get 393 * a series of equalities yielding that all expressions must be the same: 394 * \f$ub_i = lb_j <= ub_j = lb_{\cdots} <= \cdots = lb_j < ub_j \f$ 395 */ 396 if ( ! SCIPEQ(scip, 397 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]), 398 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) ) 399 ) 400 break; 401 } 402 /* if the above loop is broken, this permutation does not qualify for the stabilizer */ 403 if ( i < orcdata->nsymbrokenvarids ) 404 continue; 405 406 /* iterate over each branched variable and check */ 407 for (i = 0; i < nbranchedvarindices; ++i) 408 { 409 varid = branchedvarindices[i]; 410 assert( varid >= 0 ); 411 assert( varid < orcdata->npermvars ); 412 assert( orcdata->permvars[varid] != NULL ); 413 varidimage = perm[varid]; 414 assert( varidimage >= 0 ); 415 assert( varidimage < orcdata->npermvars ); 416 assert( orcdata->permvars[varidimage] != NULL ); 417 418 /* branching variable is not affected by this permutation */ 419 if ( varidimage == varid ) 420 continue; 421 422 if ( SCIPGT(scip, 423 varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]), 424 varlbs ? varlbs[varidimage] : SCIPvarGetLbLocal(orcdata->permvars[varidimage]) ) 425 ) 426 break; 427 } 428 /* if the above loop is broken, this permutation does not qualify for the stabilizer */ 429 if ( i < nbranchedvarindices ) 430 continue; 431 432 /* permutation qualifies for the stabilizer. Add permutation */ 433 chosenperms[(*nchosenperms)++] = perm; 434 } 435 436 return SCIP_OKAY; 437 } 438 439 /** using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid 440 * 441 * If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright. 442 */ 443 static 444 int bisectSortedArrayFindFirstGEQ( 445 int* ids, /**< int array with entries */ 446 int* idssort, /**< array of indices of ids that sort ids */ 447 int frameleft, /**< search in idssort for index range [frameleft, frameright) */ 448 int frameright, /**< search in idssort for index range [frameleft, frameright) */ 449 int findid /**< entry value to find */ 450 ) 451 { 452 int center; 453 int id; 454 455 #ifndef NDEBUG 456 int origframeleft; 457 int origframeright; 458 origframeleft = frameleft; 459 origframeright = frameright; 460 #endif 461 462 assert( ids != NULL ); 463 assert( idssort != NULL ); 464 assert( frameleft >= 0 ); 465 assert( frameright >= frameleft ); 466 467 /* empty frame case */ 468 if ( frameright == frameleft ) 469 return frameright; 470 471 while (frameright - frameleft >= 2) 472 { 473 /* split [frameleft, frameright) in [frameleft, center) and [center, frameright) */ 474 center = frameleft + ((frameright - frameleft) / 2); 475 assert( center > frameleft ); 476 assert( center < frameright ); 477 id = idssort[center]; 478 if ( ids[id] < findid ) 479 { 480 /* first instance greater or equal to findid is in [center, frameright) */ 481 frameleft = center; 482 } 483 else 484 { 485 /* first instance greater or equal to findid is in [frameleft, center) */ 486 frameright = center; 487 } 488 } 489 490 assert( frameright - frameleft == 1 ); 491 id = idssort[frameleft]; 492 if ( ids[id] < findid ) 493 ++frameleft; 494 495 assert( frameleft >= origframeleft ); 496 assert( frameright <= origframeright ); 497 assert( frameleft >= origframeright || ids[idssort[frameleft]] >= findid ); 498 assert( frameleft - 1 < origframeleft || ids[idssort[frameleft - 1]] < findid ); 499 return frameleft; 500 } 501 502 503 /** applies the orbital reduction steps for precomputed orbits 504 * 505 * Either use the local variable bounds, or variable bounds determined by the @param varlbs and @param varubs arrays. 506 * @pre @param varubs is NULL if and only if @param varlbs is NULL. 507 */ 508 static 509 SCIP_RETCODE applyOrbitalReductionPart( 510 SCIP* scip, /**< pointer to SCIP data structure */ 511 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */ 512 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */ 513 int* nred, /**< pointer to store the number of determined domain reductions */ 514 int* varorbitids, /**< array specifying the orbit IDs for variables in array orcdata->vars */ 515 int* varorbitidssort, /**< an index array that sorts the varorbitids array */ 516 SCIP_Real* varlbs, /**< array of lower bounds for variable array orcdata->vars to compute with 517 * or NULL, if local bounds are used */ 518 SCIP_Real* varubs /**< array of upper bounds for variable array orcdata->vars to compute with 519 * or NULL, if local bounds are used. */ 520 ) 521 { 522 int i; 523 int varid; 524 int orbitid; 525 int orbitbegin; 526 int orbitend; 527 SCIP_Real orbitlb; 528 SCIP_Real orbitub; 529 SCIP_Real lb; 530 SCIP_Real ub; 531 532 assert( scip != NULL ); 533 assert( orcdata != NULL ); 534 assert( infeasible != NULL ); 535 assert( nred != NULL ); 536 assert( varorbitids != NULL ); 537 assert( varorbitidssort != NULL ); 538 assert( ( varlbs == NULL ) == ( varubs == NULL ) ); 539 540 /* infeasible and nred are defined by the function that calls this function, 541 * and this function only gets called if no infeasibility is found so far. 542 */ 543 assert( !*infeasible ); 544 assert( *nred >= 0 ); 545 546 for (orbitbegin = 0; orbitbegin < orcdata->npermvars; orbitbegin = orbitend) 547 { 548 /* get id of the orbit, and scan how large the orbit is */ 549 orbitid = varorbitids[varorbitidssort[orbitbegin]]; 550 for (orbitend = orbitbegin + 1; orbitend < orcdata->npermvars; ++orbitend) 551 { 552 if ( varorbitids[varorbitidssort[orbitend]] != orbitid ) 553 break; 554 } 555 556 /* orbits consisting of only one element cannot yield reductions */ 557 if ( orbitend - orbitbegin <= 1 ) 558 continue; 559 560 /* get upper and lower bounds in orbit */ 561 orbitlb = -INFINITY; 562 orbitub = INFINITY; 563 for (i = orbitbegin; i < orbitend; ++i) 564 { 565 varid = varorbitidssort[i]; 566 assert( varid >= 0 ); 567 assert( varid < orcdata->npermvars ); 568 assert( orcdata->permvars[varid] != NULL ); 569 570 lb = varlbs ? varlbs[varid] : SCIPvarGetLbLocal(orcdata->permvars[varid]); 571 if ( SCIPGT(scip, lb, orbitlb) ) 572 orbitlb = lb; 573 ub = varubs ? varubs[varid] : SCIPvarGetUbLocal(orcdata->permvars[varid]); 574 if ( SCIPLT(scip, ub, orbitub) ) 575 orbitub = ub; 576 } 577 578 /* if bounds are incompatible, infeasibility is detected */ 579 if ( SCIPGT(scip, orbitlb, orbitub) ) 580 { 581 *infeasible = TRUE; 582 return SCIP_OKAY; 583 } 584 assert( SCIPLE(scip, orbitlb, orbitub) ); 585 586 /* update variable bounds to be in this range */ 587 for (i = orbitbegin; i < orbitend; ++i) 588 { 589 varid = varorbitidssort[i]; 590 assert( varid >= 0 ); 591 assert( varid < orcdata->npermvars ); 592 593 if ( varlbs != NULL ) 594 { 595 assert( SCIPLE(scip, varlbs[varid], orbitlb) ); 596 varlbs[varid] = orbitlb; 597 } 598 if ( !SCIPisInfinity(scip, -orbitlb) && 599 SCIPLT(scip, SCIPvarGetLbLocal(orcdata->permvars[varid]), orbitlb) ) 600 { 601 SCIP_Bool tightened; 602 SCIP_CALL( SCIPtightenVarLb(scip, orcdata->permvars[varid], orbitlb, TRUE, infeasible, &tightened) ); 603 604 /* propagator detected infeasibility in this node */ 605 if ( *infeasible ) 606 return SCIP_OKAY; 607 assert( tightened ); 608 *nred += 1; 609 } 610 611 if ( varubs != NULL ) 612 { 613 assert( SCIPGE(scip, varubs[varid], orbitub) ); 614 varubs[varid] = orbitub; 615 } 616 if ( !SCIPisInfinity(scip, orbitub) && 617 SCIPGT(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), orbitub) ) 618 { 619 SCIP_Bool tightened; 620 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], orbitub, TRUE, infeasible, &tightened) ); 621 622 /* propagator detected infeasibility in this node */ 623 if ( *infeasible ) 624 return SCIP_OKAY; 625 assert( tightened ); 626 *nred += 1; 627 } 628 } 629 } 630 assert( !*infeasible ); 631 return SCIP_OKAY; 632 } 633 634 635 /** orbital reduction, the orbital branching part */ 636 static 637 SCIP_RETCODE applyOrbitalBranchingPropagations( 638 SCIP* scip, /**< pointer to SCIP data structure */ 639 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */ 640 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */ 641 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */ 642 int* nred /**< pointer to store the number of determined domain reductions */ 643 ) 644 { 645 SCIP_NODE* focusnode; 646 SCIP_NODE* parentnode; 647 SCIP_SHADOWNODE* shadowfocusnode; 648 SCIP_SHADOWNODE* tmpshadownode; 649 SCIP_SHADOWNODE** rootedshadowpath; 650 int pathlength; 651 int depth; 652 int branchstep; 653 int i; 654 SCIP_Real* varlbs; 655 SCIP_Real* varubs; 656 SCIP_SHADOWBOUNDUPDATE* update; 657 int* branchedvarindices; 658 SCIP_Bool* inbranchedvarindices; 659 int nbranchedvarindices; 660 int varid; 661 SCIP_SHADOWBOUNDUPDATE* branchingdecision; 662 int branchingdecisionvarid; 663 int** chosenperms; 664 int* perm; 665 int nchosenperms; 666 int p; 667 int* varorbitids; 668 int* varorbitidssort; 669 int idx; 670 int orbitbegin; 671 int orbitend; 672 SCIP_DISJOINTSET* orbitset; 673 int orbitsetcomponentid; 674 675 assert( scip != NULL ); 676 assert( orcdata != NULL ); 677 assert( shadowtree != NULL ); 678 assert( infeasible != NULL ); 679 assert( nred != NULL ); 680 681 /* infeasible and nred are defined by the function that calls this function, 682 * and this function only gets called if no infeasibility is found so far. 683 */ 684 assert( !*infeasible ); 685 assert( *nred >= 0 ); 686 687 focusnode = SCIPgetFocusNode(scip); 688 assert( focusnode == SCIPgetCurrentNode(scip) ); 689 assert( focusnode != NULL ); 690 691 /* do nothing if this method has already been called for this node */ 692 if ( orcdata->lastnode == focusnode ) 693 return SCIP_OKAY; 694 695 orcdata->lastnode = focusnode; 696 parentnode = SCIPnodeGetParent(focusnode); 697 698 /* the root node has not been generated by branching decisions */ 699 if ( parentnode == NULL ) 700 return SCIP_OKAY; 701 702 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode); 703 704 /* do not apply orbital reduction if focusnode does not exist in the shadowtree */ 705 if ( shadowfocusnode == NULL ) 706 { 707 if ( !orcdata->treewarninggiven ) 708 { 709 SCIPwarningMessage(scip, "Attempting orbital reduction on nodes not existing in the symmetry shadowtree" 710 " (and suppressing future warnings for this component)\n"); 711 orcdata->treewarninggiven = TRUE; 712 } 713 return SCIP_OKAY; 714 } 715 716 /* get the rooted path */ 717 /* @todo add depth field to shadow tree node to improve efficiency */ 718 pathlength = 0; 719 tmpshadownode = shadowfocusnode; 720 do 721 { 722 tmpshadownode = tmpshadownode->parent; 723 ++pathlength; 724 } 725 while ( tmpshadownode != NULL ); 726 727 SCIP_CALL( SCIPallocBufferArray(scip, &rootedshadowpath, pathlength) ); 728 i = pathlength; 729 tmpshadownode = shadowfocusnode; 730 while ( i > 0 ) 731 { 732 rootedshadowpath[--i] = tmpshadownode; 733 assert( tmpshadownode != NULL ); 734 tmpshadownode = tmpshadownode->parent; 735 } 736 assert( tmpshadownode == NULL ); 737 assert( i == 0 ); 738 739 /* replay bound reductions and propagations made until just before the focusnode */ 740 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */ 741 742 SCIP_CALL( SCIPallocBufferArray(scip, &varlbs, orcdata->npermvars) ); 743 SCIP_CALL( SCIPallocBufferArray(scip, &varubs, orcdata->npermvars) ); 744 SCIP_CALL( SCIPallocBufferArray(scip, &branchedvarindices, orcdata->npermvars) ); 745 SCIP_CALL( SCIPallocCleanBufferArray(scip, &inbranchedvarindices, orcdata->npermvars) ); 746 747 /* start with the bounds found after computing the symmetry group */ 748 for (i = 0; i < orcdata->npermvars; ++i) 749 varlbs[i] = orcdata->globalvarlbs[i]; 750 for (i = 0; i < orcdata->npermvars; ++i) 751 varubs[i] = orcdata->globalvarubs[i]; 752 753 nbranchedvarindices = 0; 754 for (depth = 0; depth < pathlength - 1; ++depth) 755 { 756 tmpshadownode = rootedshadowpath[depth]; 757 758 /* receive propagations */ 759 for (i = 0; i < tmpshadownode->npropagations; ++i) 760 { 761 update = &(tmpshadownode->propagations[i]); 762 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var); 763 assert( varid < orcdata->npermvars || varid == INT_MAX ); 764 assert( varid >= 0 ); 765 if ( varid < orcdata->npermvars ) 766 { 767 assert( SCIPLE(scip, varlbs[varid], varubs[varid]) ); 768 switch (update->boundchgtype) 769 { 770 case SCIP_BOUNDTYPE_LOWER: 771 assert( SCIPGE(scip, update->newbound, varlbs[varid]) ); 772 varlbs[varid] = update->newbound; 773 break; 774 case SCIP_BOUNDTYPE_UPPER: 775 assert( SCIPLE(scip, update->newbound, varubs[varid]) ); 776 varubs[varid] = update->newbound; 777 break; 778 default: 779 assert( FALSE ); 780 } 781 assert( SCIPLE(scip, varlbs[varid], varubs[varid]) ); 782 } 783 } 784 785 /* receive variable indices of branched variables */ 786 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i) 787 { 788 update = &(tmpshadownode->branchingdecisions[i]); 789 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var); 790 assert( varid < orcdata->npermvars || varid == INT_MAX ); 791 assert( varid >= 0 ); 792 if ( varid < orcdata->npermvars ) 793 { 794 if ( inbranchedvarindices[varid] ) 795 continue; 796 branchedvarindices[nbranchedvarindices++] = varid; 797 inbranchedvarindices[varid] = TRUE; 798 } 799 } 800 } 801 802 /* determine symmetry group at this point, apply branched variable, apply orbital branching for this 803 * 804 * The branching variables are applied one-after-the-other. 805 * So, the group before branching is determined, orbital branching to the branching variable, then the branching 806 * variable is applied, and possibly repeated for other branching variables. 807 */ 808 SCIP_CALL( SCIPallocBufferArray(scip, &chosenperms, orcdata->nperms) ); 809 for (branchstep = 0; branchstep < shadowfocusnode->nbranchingdecisions; ++branchstep) 810 { 811 branchingdecision = &(shadowfocusnode->branchingdecisions[branchstep]); 812 branchingdecisionvarid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) branchingdecision->var); 813 assert( branchingdecisionvarid < orcdata->npermvars || branchingdecisionvarid == INT_MAX ); 814 assert( branchingdecisionvarid >= 0 ); 815 816 /* branching decision will not have an effect on this */ 817 if ( branchingdecisionvarid >= orcdata->npermvars ) 818 continue; 819 assert( branchingdecisionvarid >= 0 && branchingdecisionvarid < orcdata->npermvars ); 820 assert( branchingdecision->boundchgtype == SCIP_BOUNDTYPE_LOWER ? 821 SCIPLE(scip, varlbs[branchingdecisionvarid], branchingdecision->newbound) : 822 SCIPGE(scip, varubs[branchingdecisionvarid], branchingdecision->newbound) ); 823 assert( SCIPLE(scip, varlbs[branchingdecisionvarid], varubs[branchingdecisionvarid]) ); 824 825 /* get the generating set of permutations of a subgroup of a stabilizing symmetry subgroup. 826 * 827 * Note: All information about branching decisions is kept in varlbs, varubs, and the branchedvarindices. 828 */ 829 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms, 830 varlbs, varubs, branchedvarindices, inbranchedvarindices, nbranchedvarindices) ); 831 832 /* compute orbit containing branching var */ 833 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) ); 834 835 /* put elements mapping to each other in same orbit */ 836 /* @todo a potential performance hazard; quadratic time */ 837 for (p = 0; p < nchosenperms; ++p) 838 { 839 perm = chosenperms[p]; 840 for (i = 0; i < orcdata->npermvars; ++i) 841 { 842 if ( i != perm[i] ) 843 SCIPdisjointsetUnion(orbitset, i, perm[i], FALSE); 844 } 845 } 846 847 /* 1. ensure that the bounds are tightest possible just before the branching step (orbital reduction step) 848 * 849 * If complete propagation was applied in the previous node, 850 * then all variables in the same orbit have the same bounds just before branching, 851 * so the bounds of the branching variable should be the tightest in its orbit by now. 852 * It is possible that that is not the case. In that case, we do it here. 853 */ 854 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) ); 855 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) ); 856 for (i = 0; i < orcdata->npermvars; ++i) 857 varorbitids[i] = SCIPdisjointsetFind(orbitset, i); 858 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars); 859 860 /* apply orbital reduction to these orbits */ 861 SCIP_CALL( applyOrbitalReductionPart(scip, orcdata, infeasible, nred, varorbitids, 862 varorbitidssort, varlbs, varubs) ); 863 if ( *infeasible ) 864 goto FREE; 865 assert( !*infeasible ); 866 867 /* 2. apply branching step to varlbs or varubs array 868 * 869 * Due to the steps above, it is possible that the branching step is redundant or infeasible. 870 */ 871 assert( SCIPLE(scip, varlbs[branchingdecisionvarid], varubs[branchingdecisionvarid]) ); 872 switch (branchingdecision->boundchgtype) 873 { 874 case SCIP_BOUNDTYPE_LOWER: 875 /* incompatible upper bound */ 876 if ( SCIPGT(scip, branchingdecision->newbound, varubs[branchingdecisionvarid]) ) 877 { 878 *infeasible = TRUE; 879 goto FREE; 880 } 881 882 assert( SCIPLE(scip, varlbs[branchingdecisionvarid], branchingdecision->newbound) ); 883 varlbs[branchingdecisionvarid] = branchingdecision->newbound; 884 break; 885 case SCIP_BOUNDTYPE_UPPER: 886 /* incompatible lower bound */ 887 if ( SCIPLT(scip, branchingdecision->newbound, varlbs[branchingdecisionvarid]) ) 888 { 889 *infeasible = TRUE; 890 goto FREE; 891 } 892 893 assert( SCIPGE(scip, varubs[branchingdecisionvarid], branchingdecision->newbound) ); 894 varubs[branchingdecisionvarid] = branchingdecision->newbound; 895 break; 896 default: 897 assert( FALSE ); 898 } 899 900 /* 3. propagate that branching variable is >= the variables in its orbit 901 * 902 * Also apply the updates to the variable arrays 903 */ 904 905 /* get the orbit of the branching variable */ 906 orbitsetcomponentid = SCIPdisjointsetFind(orbitset, branchingdecisionvarid); 907 908 /* find the orbit in the sorted array of orbits. npermvars can be huge, so use bisection. */ 909 orbitbegin = bisectSortedArrayFindFirstGEQ(varorbitids, varorbitidssort, 0, orcdata->npermvars, 910 orbitsetcomponentid); 911 assert( orbitbegin >= 0 && orbitbegin < orcdata->npermvars ); 912 assert( varorbitids[varorbitidssort[orbitbegin]] == orbitsetcomponentid ); 913 assert( orbitbegin == 0 || varorbitids[varorbitidssort[orbitbegin - 1]] < orbitsetcomponentid ); 914 915 orbitend = bisectSortedArrayFindFirstGEQ(varorbitids, varorbitidssort, orbitbegin + 1, orcdata->npermvars, 916 orbitsetcomponentid + 1); 917 assert( orbitend > 0 && orbitend <= orcdata->npermvars && orbitend > orbitbegin ); 918 assert( orbitend == orcdata->npermvars || varorbitids[varorbitidssort[orbitend]] > orbitsetcomponentid ); 919 assert( varorbitids[varorbitidssort[orbitend - 1]] == orbitsetcomponentid ); 920 921 /* propagate that branching variable is >= the variables in its orbit */ 922 for (idx = orbitbegin; idx < orbitend; ++idx) 923 { 924 varid = varorbitidssort[idx]; 925 assert( varorbitids[varid] == orbitsetcomponentid ); 926 927 /* ignore current branching variable */ 928 if ( varid == branchingdecisionvarid ) 929 continue; 930 931 /* is variable varid in the orbit? */ 932 if ( SCIPdisjointsetFind(orbitset, varid) != orbitsetcomponentid ) 933 continue; 934 935 /* all variables in the same orbit have the same bounds just before branching, 936 * due to orbital reduction. If that was not the case, these steps are applied just before applying 937 * the branching step above. After the branching step, the branching variable bounds are most restricted. 938 */ 939 assert( SCIPisInfinity(scip, -varlbs[branchingdecisionvarid]) 940 || SCIPGE(scip, varlbs[branchingdecisionvarid], varlbs[varid]) ); 941 assert( SCIPisInfinity(scip, varubs[branchingdecisionvarid]) 942 || SCIPLE(scip, varubs[branchingdecisionvarid], varubs[varid]) ); 943 /* bound changes already made could only have tightened the variable domains we are thinking about */ 944 assert( SCIPGE(scip, SCIPvarGetLbLocal(orcdata->permvars[varid]), varlbs[varid]) ); 945 assert( SCIPLE(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[varid]) ); 946 947 /* for branching variable x and variable y in its orbit, propagate x >= y. */ 948 /* modify UB of y-variables */ 949 assert( SCIPGE(scip, varubs[varid], varubs[branchingdecisionvarid]) ); 950 varubs[varid] = varubs[branchingdecisionvarid]; 951 if ( SCIPGT(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[branchingdecisionvarid]) ) 952 { 953 SCIP_Bool tightened; 954 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], varubs[branchingdecisionvarid], TRUE, 955 infeasible, &tightened) ); 956 957 /* propagator detected infeasibility in this node. */ 958 if ( *infeasible ) 959 goto FREE; 960 assert( tightened ); 961 *nred += 1; 962 } 963 964 /* because variable domains are initially the same, the LB of the x-variables does not need to be modified. */ 965 assert( SCIPLE(scip, varlbs[varid], varlbs[branchingdecisionvarid]) ); 966 } 967 968 FREE: 969 SCIPfreeBufferArray(scip, &varorbitidssort); 970 SCIPfreeBufferArray(scip, &varorbitids); 971 SCIPfreeDisjointset(scip, &orbitset); 972 973 if ( *infeasible ) 974 break; 975 976 /* for the next branched variable at this node, if it's not already added, 977 * mark the branching variable of this iteration as a branching variable. */ 978 if ( !inbranchedvarindices[branchingdecisionvarid] ) 979 { 980 assert( nbranchedvarindices < orcdata->npermvars ); 981 branchedvarindices[nbranchedvarindices++] = branchingdecisionvarid; 982 inbranchedvarindices[branchingdecisionvarid] = TRUE; 983 } 984 } 985 SCIPfreeBufferArray(scip, &chosenperms); 986 987 /* clean inbranchedvarindices array */ 988 for (i = 0; i < nbranchedvarindices; ++i) 989 { 990 varid = branchedvarindices[i]; 991 assert( varid >= 0 ); 992 assert( varid < orcdata->npermvars ); 993 assert( inbranchedvarindices[varid] ); 994 inbranchedvarindices[varid] = FALSE; 995 } 996 #ifndef NDEBUG 997 for (i = 0; i < orcdata->npermvars; ++i) 998 { 999 assert( inbranchedvarindices[i] == FALSE ); 1000 } 1001 #endif 1002 1003 /* free everything */ 1004 SCIPfreeCleanBufferArray(scip, &inbranchedvarindices); 1005 SCIPfreeBufferArray(scip, &branchedvarindices); 1006 SCIPfreeBufferArray(scip, &varubs); 1007 SCIPfreeBufferArray(scip, &varlbs); 1008 SCIPfreeBufferArray(scip, &rootedshadowpath); 1009 1010 return SCIP_OKAY; 1011 } 1012 1013 /** orbital reduction, the orbital reduction part */ 1014 static 1015 SCIP_RETCODE applyOrbitalReductionPropagations( 1016 SCIP* scip, /**< pointer to SCIP data structure */ 1017 ORCDATA* orcdata, /**< pointer to data for orbital reduction data */ 1018 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */ 1019 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected */ 1020 int* nred /**< pointer to store the number of determined domain reductions */ 1021 ) 1022 { 1023 SCIP_NODE* focusnode; 1024 SCIP_SHADOWNODE* shadowfocusnode; 1025 SCIP_SHADOWNODE* tmpshadownode; 1026 int i; 1027 SCIP_SHADOWBOUNDUPDATE* update; 1028 int* branchedvarindices; 1029 SCIP_Bool* inbranchedvarindices; 1030 int nbranchedvarindices; 1031 int varid; 1032 int** chosenperms; 1033 int* perm; 1034 int nchosenperms; 1035 int p; 1036 SCIP_DISJOINTSET* orbitset; 1037 int* varorbitids; 1038 int* varorbitidssort; 1039 1040 assert( scip != NULL ); 1041 assert( orcdata != NULL ); 1042 assert( shadowtree != NULL ); 1043 assert( infeasible != NULL ); 1044 assert( nred != NULL ); 1045 1046 /* infeasible and nred are defined by the function that calls this function, 1047 * and this function only gets called if no infeasibility is found so far. 1048 */ 1049 assert( !*infeasible ); 1050 assert( *nred >= 0 ); 1051 1052 focusnode = SCIPgetFocusNode(scip); 1053 assert( focusnode == SCIPgetCurrentNode(scip) ); 1054 assert( focusnode != NULL ); 1055 1056 shadowfocusnode = SCIPshadowTreeGetShadowNode(shadowtree, focusnode); 1057 assert( shadowfocusnode != NULL ); 1058 1059 /* get the branching variables until present, so including the branchings of the focusnode */ 1060 assert( orcdata->npermvars > 0 ); /* if it's 0, then we do not have to do anything at all */ 1061 1062 SCIP_CALL( SCIPallocBufferArray(scip, &branchedvarindices, orcdata->npermvars) ); 1063 SCIP_CALL( SCIPallocCleanBufferArray(scip, &inbranchedvarindices, orcdata->npermvars) ); 1064 1065 nbranchedvarindices = 0; 1066 tmpshadownode = shadowfocusnode; 1067 while ( tmpshadownode != NULL ) 1068 { 1069 /* receive variable indices of branched variables */ 1070 for (i = 0; i < tmpshadownode->nbranchingdecisions; ++i) 1071 { 1072 update = &(tmpshadownode->branchingdecisions[i]); 1073 varid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) update->var); 1074 assert( varid < orcdata->npermvars || varid == INT_MAX ); 1075 assert( varid >= 0 ); 1076 if ( varid < orcdata->npermvars ) 1077 { 1078 if ( inbranchedvarindices[varid] ) 1079 continue; 1080 branchedvarindices[nbranchedvarindices++] = varid; 1081 inbranchedvarindices[varid] = TRUE; 1082 } 1083 } 1084 tmpshadownode = tmpshadownode->parent; 1085 } 1086 1087 /* 1. compute the orbit of the branching variable of the stabilized symmetry subgroup at this point. */ 1088 /* 1.1. identify the permutations of the symmetry group that are permitted */ 1089 SCIP_CALL( SCIPallocBufferArray(scip, &chosenperms, orcdata->nperms) ); 1090 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms, 1091 NULL, NULL, branchedvarindices, inbranchedvarindices, nbranchedvarindices) ); 1092 assert( nchosenperms >= 0 ); 1093 1094 /* no reductions can be yielded by orbital reduction if the group is trivial */ 1095 if ( nchosenperms == 0 ) 1096 goto FREE; 1097 1098 /* 1.2. compute orbits of this subgroup */ 1099 SCIP_CALL( SCIPcreateDisjointset(scip, &orbitset, orcdata->npermvars) ); 1100 1101 /* put elements mapping to each other in same orbit */ 1102 /* @todo this is O(nchosenperms * npermvars), which is a potential performance bottleneck. 1103 Alternative: precompute support per permutation at initialization, and iterate over these.*/ 1104 for (p = 0; p < nchosenperms; ++p) 1105 { 1106 perm = chosenperms[p]; 1107 for (i = 0; i < orcdata->npermvars; ++i) 1108 { 1109 if ( i != perm[i] ) 1110 SCIPdisjointsetUnion(orbitset, i, perm[i], FALSE); 1111 } 1112 } 1113 1114 /* 2. for each orbit, take the intersection of the domains */ 1115 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitids, orcdata->npermvars) ); 1116 SCIP_CALL( SCIPallocBufferArray(scip, &varorbitidssort, orcdata->npermvars) ); 1117 for (i = 0; i < orcdata->npermvars; ++i) 1118 varorbitids[i] = SCIPdisjointsetFind(orbitset, i); 1119 SCIPsort(varorbitidssort, SCIPsortArgsortInt, varorbitids, orcdata->npermvars); 1120 1121 /* apply orbital reduction to these orbits */ 1122 SCIP_CALL( applyOrbitalReductionPart(scip, orcdata, infeasible, nred, varorbitids, varorbitidssort, NULL, NULL) ); 1123 1124 SCIPfreeBufferArray(scip, &varorbitidssort); 1125 SCIPfreeBufferArray(scip, &varorbitids); 1126 SCIPfreeDisjointset(scip, &orbitset); 1127 FREE: 1128 SCIPfreeBufferArray(scip, &chosenperms); 1129 1130 /* clean inbranchedvarindices array */ 1131 for (i = 0; i < nbranchedvarindices; ++i) 1132 { 1133 varid = branchedvarindices[i]; 1134 assert( varid >= 0 ); 1135 assert( varid < orcdata->npermvars ); 1136 assert( inbranchedvarindices[varid] ); 1137 inbranchedvarindices[varid] = FALSE; 1138 } 1139 #ifndef NDEBUG 1140 for (i = 0; i < orcdata->npermvars; ++i) 1141 { 1142 assert( inbranchedvarindices[i] == FALSE ); 1143 } 1144 #endif 1145 1146 SCIPfreeCleanBufferArray(scip, &inbranchedvarindices); 1147 SCIPfreeBufferArray(scip, &branchedvarindices); 1148 1149 return SCIP_OKAY; 1150 } 1151 1152 1153 /** applies orbital reduction on a symmetry group component using a two step mechanism 1154 * 1155 * 1. At the parent of our focus node (which is the current node, because we're not probing), 1156 * compute the symmetry group just before branching. Then, for our branching variable x with variable y in its 1157 * orbit, we mimic adding the constraint x >= y by variable bound propagations in this node. 1158 * 1159 * In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields 1160 * 1. In the 1-branch: 1 = x >= y is a tautology (since y is in {0, 1}). Nothing happens. 1161 * 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching. 1162 * REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178. 1163 * 1164 * (This only needs to be done once per node.) 1165 * 1166 * 2. At the focus node itself, compute the symmetry group. 1167 * The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group 1168 * as described in the function orbitalReductionGetSymmetryStabilizerSubgroup. 1169 * For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable 1170 * domains in the orbit. 1171 * 1172 * This generalizes orbital fixing in the binary case. 1173 * REF: Margot 2002, Margot 2003, Orbital Branching, Ostrowski's PhD thesis. 1174 */ 1175 static 1176 SCIP_RETCODE orbitalReductionPropagateComponent( 1177 SCIP* scip, /**< SCIP data structure */ 1178 ORCDATA* orcdata, /**< orbital reduction component data */ 1179 SCIP_SHADOWTREE* shadowtree, /**< pointer to shadow tree */ 1180 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */ 1181 int* nred /**< pointer to store the number of domain reductions */ 1182 ) 1183 { 1184 assert( scip != NULL ); 1185 assert( orcdata != NULL ); 1186 assert( shadowtree != NULL ); 1187 assert( infeasible != NULL ); 1188 assert( nred != NULL ); 1189 1190 /* infeasible and nred are defined by the function that calls this function, 1191 * and this function only gets called if no infeasibility is found so far. 1192 */ 1193 assert( !*infeasible ); 1194 assert( *nred >= 0 ); 1195 1196 /* orbital reduction is only propagated when branching has started */ 1197 assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetNNodes(scip) > 1 ); 1198 1199 /* if this is the first call, identify the orbits for which symmetry is broken */ 1200 if ( !orcdata->symmetrybrokencomputed ) 1201 { 1202 SCIP_CALL( identifyOrbitalSymmetriesBroken(scip, orcdata) ); 1203 } 1204 assert( orcdata->symmetrybrokencomputed ); 1205 assert( orcdata->nsymbrokenvarids <= orcdata->npermvars ); 1206 1207 /* If symmetry is broken for all orbits, stop! */ 1208 if ( orcdata->nsymbrokenvarids == orcdata->npermvars ) 1209 return SCIP_OKAY; 1210 1211 /* step 1 */ 1212 SCIP_CALL( applyOrbitalBranchingPropagations(scip, orcdata, shadowtree, infeasible, nred) ); 1213 if ( *infeasible ) 1214 return SCIP_OKAY; 1215 1216 /* step 2 */ 1217 SCIP_CALL( applyOrbitalReductionPropagations(scip, orcdata, shadowtree, infeasible, nred) ); 1218 if ( *infeasible ) 1219 return SCIP_OKAY; 1220 1221 return SCIP_OKAY; 1222 } 1223 1224 1225 /** adds component */ 1226 static 1227 SCIP_RETCODE addComponent( 1228 SCIP* scip, /**< SCIP data structure */ 1229 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */ 1230 SCIP_VAR** permvars, /**< variable array of the permutation */ 1231 int npermvars, /**< number of variables in that array */ 1232 int** perms, /**< permutations in the component */ 1233 int nperms, /**< number of permutations in the component */ 1234 SCIP_Bool* success /**< to store whether the component is successfully added */ 1235 ) 1236 { 1237 ORCDATA* orcdata; 1238 int i; 1239 int j; 1240 int p; 1241 int* origperm; 1242 int* newperm; 1243 int newidx; 1244 int newpermidx; 1245 1246 assert( scip != NULL ); 1247 assert( orbireddata != NULL ); 1248 assert( permvars != NULL ); 1249 assert( npermvars > 0 ); 1250 assert( perms != NULL ); 1251 assert( nperms > 0 ); 1252 assert( success != NULL ); 1253 1254 *success = TRUE; 1255 SCIP_CALL( SCIPallocBlockMemory(scip, &orcdata) ); 1256 1257 /* correct indices by removing fixed points */ 1258 1259 /* determine the number of vars that are moved by the component, assign to orcdata->npermvars */ 1260 orcdata->npermvars = 0; 1261 for (i = 0; i < npermvars; ++i) 1262 { 1263 /* is index i moved by any of the permutations in the component? */ 1264 for (p = 0; p < nperms; ++p) 1265 { 1266 if ( perms[p][i] != i ) 1267 { 1268 ++orcdata->npermvars; 1269 break; 1270 } 1271 } 1272 } 1273 1274 /* do not support the setting where the component is empty */ 1275 if ( orcdata->npermvars <= 0 ) 1276 { 1277 SCIPfreeBlockMemory(scip, &orcdata); 1278 *success = FALSE; 1279 return SCIP_OKAY; 1280 } 1281 1282 /* require that the shadowtree is active */ 1283 SCIP_CALL( SCIPactivateShadowTree(scip, orbireddata->shadowtreeeventhdlr) ); 1284 1285 /* create index-corrected permvars array and the inverse */ 1286 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->permvars, orcdata->npermvars) ); 1287 SCIP_CALL( SCIPhashmapCreate(&orcdata->permvarmap, SCIPblkmem(scip), orcdata->npermvars) ); 1288 1289 j = 0; 1290 for (i = 0; i < npermvars; ++i) 1291 { 1292 /* permvars array must be unique */ 1293 assert( SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]) == INT_MAX ); 1294 1295 /* is index i moved by any of the permutations in the component? */ 1296 for (p = 0; p < nperms; ++p) 1297 { 1298 if ( perms[p][i] != i ) 1299 { 1300 /* var is moved by component; add, disable multiaggregation and capture */ 1301 SCIP_CALL( SCIPcaptureVar(scip, permvars[i]) ); 1302 orcdata->permvars[j] = permvars[i]; 1303 SCIP_CALL( SCIPhashmapInsertInt(orcdata->permvarmap, (void*) permvars[i], j) ); 1304 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, permvars[i]) ); 1305 ++j; 1306 break; 1307 } 1308 } 1309 } 1310 assert( j == orcdata->npermvars ); 1311 1312 /* allocate permutations */ 1313 orcdata->nperms = nperms; 1314 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms, nperms) ); 1315 for (p = 0; p < nperms; ++p) 1316 { 1317 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->perms[p], orcdata->npermvars) ); 1318 origperm = perms[p]; 1319 newperm = orcdata->perms[p]; 1320 1321 for (i = 0; i < npermvars; ++i) 1322 { 1323 newidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[i]); 1324 if ( newidx >= orcdata->npermvars ) 1325 continue; 1326 assert( newidx >= 0 ); 1327 assert( newidx < orcdata->npermvars ); 1328 assert( orcdata->permvars[newidx] == permvars[i] ); 1329 newpermidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) permvars[origperm[i]]); 1330 assert( newpermidx >= 0 ); 1331 assert( newidx < orcdata->npermvars ); /* this is in the orbit of any permutation, so cannot be INT_MAX */ 1332 assert( orcdata->permvars[newpermidx] == permvars[origperm[i]] ); 1333 1334 newperm[newidx] = newpermidx; 1335 } 1336 } 1337 1338 /* global variable bounds */ 1339 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->globalvarlbs, orcdata->npermvars) ); 1340 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orcdata->globalvarubs, orcdata->npermvars) ); 1341 for (i = 0; i < orcdata->npermvars; ++i) 1342 { 1343 orcdata->globalvarlbs[i] = SCIPvarGetLbGlobal(orcdata->permvars[i]); 1344 orcdata->globalvarubs[i] = SCIPvarGetUbGlobal(orcdata->permvars[i]); 1345 } 1346 1347 /* catch global variable bound change event */ 1348 for (i = 0; i < orcdata->npermvars; ++i) 1349 { 1350 SCIP_CALL( SCIPcatchVarEvent(scip, orcdata->permvars[i], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED, 1351 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) orcdata, NULL) ); 1352 } 1353 1354 /* lastnode field */ 1355 orcdata->lastnode = NULL; 1356 1357 /* symmetry computed field */ 1358 orcdata->symmetrybrokencomputed = FALSE; 1359 orcdata->symbrokenvarids = NULL; 1360 orcdata->nsymbrokenvarids = -1; 1361 1362 /* resize component array if needed */ 1363 assert( orbireddata->ncomponents >= 0 ); 1364 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) ); 1365 assert( orbireddata->ncomponents <= orbireddata->maxncomponents ); 1366 if ( orbireddata->ncomponents == orbireddata->maxncomponents ) 1367 { 1368 int newsize; 1369 1370 newsize = SCIPcalcMemGrowSize(scip, orbireddata->ncomponents + 1); 1371 assert( newsize >= 0 ); 1372 1373 if ( orbireddata->ncomponents == 0 ) 1374 { 1375 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbireddata->componentdatas, newsize) ); 1376 } 1377 else 1378 { 1379 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->componentdatas, 1380 orbireddata->ncomponents, newsize) ); 1381 } 1382 1383 orbireddata->maxncomponents = newsize; 1384 } 1385 1386 /* tree warning indicator */ 1387 orcdata->treewarninggiven = FALSE; 1388 1389 /* add component */ 1390 assert( orbireddata->ncomponents < orbireddata->maxncomponents ); 1391 orbireddata->componentdatas[orbireddata->ncomponents++] = orcdata; 1392 1393 return SCIP_OKAY; 1394 } 1395 1396 1397 /** frees component */ 1398 static 1399 SCIP_RETCODE freeComponent( 1400 SCIP* scip, /**< SCIP data structure */ 1401 SCIP_ORBITALREDDATA* orbireddata, /**< pointer to the orbital reduction data */ 1402 ORCDATA** orcdata /**< pointer to component data */ 1403 ) 1404 { 1405 int i; 1406 int p; 1407 1408 assert( scip != NULL ); 1409 assert( orbireddata != NULL ); 1410 assert( orcdata != NULL ); 1411 assert( *orcdata != NULL ); 1412 assert( (*orcdata)->globalvarlbs != NULL ); 1413 assert( (*orcdata)->globalvarubs != NULL ); 1414 assert( (*orcdata)->nperms > 0 ); 1415 assert( (*orcdata)->npermvars > 0 ); 1416 assert( (*orcdata)->perms != NULL ); 1417 assert( (*orcdata)->permvarmap != NULL ); 1418 assert( (*orcdata)->permvars != NULL ); 1419 assert( (*orcdata)->npermvars > 0 ); 1420 1421 assert( SCIPisTransformed(scip) ); 1422 1423 /* free symmetry broken information if it has been computed */ 1424 if ( (*orcdata)->symmetrybrokencomputed ) 1425 { 1426 assert( ((*orcdata)->nsymbrokenvarids == 0) == ((*orcdata)->symbrokenvarids == NULL) ); 1427 SCIPfreeBlockMemoryArrayNull(scip, &(*orcdata)->symbrokenvarids, (*orcdata)->nsymbrokenvarids); 1428 } 1429 1430 /* free global variable bound change event */ 1431 if ( SCIPgetStage(scip) != SCIP_STAGE_FREE ) 1432 { 1433 /* events at the freeing stage may not be dropped, because they are already getting dropped */ 1434 for (i = (*orcdata)->npermvars - 1; i >= 0; --i) 1435 { 1436 SCIP_CALL( SCIPdropVarEvent(scip, (*orcdata)->permvars[i], 1437 SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED, 1438 orbireddata->globalfixeventhdlr, (SCIP_EVENTDATA*) (*orcdata), -1) ); 1439 } 1440 } 1441 1442 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarubs, (*orcdata)->npermvars); 1443 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->globalvarlbs, (*orcdata)->npermvars); 1444 1445 for (p = (*orcdata)->nperms -1; p >= 0; --p) 1446 { 1447 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms[p], (*orcdata)->npermvars); 1448 } 1449 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->perms, (*orcdata)->nperms); 1450 1451 /* release variables */ 1452 for (i = 0; i < (*orcdata)->npermvars; ++i) 1453 { 1454 assert( (*orcdata)->permvars[i] != NULL ); 1455 SCIP_CALL( SCIPreleaseVar(scip, &(*orcdata)->permvars[i]) ); 1456 } 1457 1458 SCIPhashmapFree(&(*orcdata)->permvarmap); 1459 SCIPfreeBlockMemoryArray(scip, &(*orcdata)->permvars, (*orcdata)->npermvars); 1460 1461 SCIPfreeBlockMemory(scip, orcdata); 1462 1463 return SCIP_OKAY; 1464 } 1465 1466 1467 /* 1468 * Event handler callback methods 1469 */ 1470 1471 /** maintains global variable bound reductions found during presolving or at the root node */ 1472 static 1473 SCIP_DECL_EVENTEXEC(eventExecGlobalBoundChange) 1474 { 1475 ORCDATA* orcdata; 1476 SCIP_VAR* var; 1477 int varidx; 1478 1479 assert( eventhdlr != NULL ); 1480 assert( eventdata != NULL ); 1481 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_SYMMETRY_NAME) == 0 ); 1482 assert( event != NULL ); 1483 1484 orcdata = (ORCDATA*) eventdata; 1485 assert( orcdata != NULL ); 1486 1487 /* only update the global bounds if the propagator has not been called yet */ 1488 if ( orcdata->symmetrybrokencomputed ) 1489 { 1490 /* identifyOrbitalSymmetriesBroken is only called when we're propagating, which is only done for during solving */ 1491 assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetNNodes(scip) > 1 ); 1492 return SCIP_OKAY; 1493 } 1494 1495 var = SCIPeventGetVar(event); 1496 assert( var != NULL ); 1497 assert( SCIPvarIsTransformed(var) ); 1498 1499 assert( orcdata->permvarmap != NULL ); 1500 varidx = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) var); 1501 1502 switch ( SCIPeventGetType(event) ) 1503 { 1504 case SCIP_EVENTTYPE_GUBCHANGED: 1505 /* can assert with equality, because no arithmetic must be applied after inheriting the value of oldbound */ 1506 assert( orcdata->globalvarubs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */ 1507 orcdata->globalvarubs[varidx] = SCIPeventGetNewbound(event); 1508 break; 1509 case SCIP_EVENTTYPE_GLBCHANGED: 1510 assert( orcdata->globalvarlbs[varidx] == SCIPeventGetOldbound(event) ); /*lint !e777 */ 1511 orcdata->globalvarlbs[varidx] = SCIPeventGetNewbound(event); 1512 break; 1513 default: 1514 SCIPABORT(); 1515 return SCIP_ERROR; 1516 } 1517 1518 return SCIP_OKAY; 1519 } 1520 1521 1522 /* 1523 * Interface methods 1524 */ 1525 1526 1527 /** prints orbital reduction data */ 1528 SCIP_RETCODE SCIPorbitalReductionGetStatistics( 1529 SCIP* scip, /**< SCIP data structure */ 1530 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */ 1531 int* nred, /**< pointer to store the total number of reductions applied */ 1532 int* ncutoff /**< pointer to store the total number of cutoffs applied */ 1533 ) 1534 { 1535 assert( scip != NULL ); 1536 assert( orbireddata != NULL ); 1537 1538 *nred = orbireddata->nred; 1539 *ncutoff = orbireddata->ncutoff; 1540 1541 return SCIP_OKAY; 1542 } 1543 1544 /** prints orbital reduction data */ 1545 SCIP_RETCODE SCIPorbitalReductionPrintStatistics( 1546 SCIP* scip, /**< SCIP data structure */ 1547 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */ 1548 ) 1549 { 1550 int i; 1551 1552 assert( scip != NULL ); 1553 assert( orbireddata != NULL ); 1554 1555 if ( orbireddata->ncomponents == 0 ) 1556 { 1557 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " orbital reduction: no components\n"); 1558 return SCIP_OKAY; 1559 } 1560 1561 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 1562 " orbital reduction: %4d components of sizes ", orbireddata->ncomponents); 1563 for (i = 0; i < orbireddata->ncomponents; ++i) 1564 { 1565 if ( i > 0 ) 1566 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", "); 1567 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", orbireddata->componentdatas[i]->nperms); 1568 } 1569 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "\n"); 1570 1571 return SCIP_OKAY; 1572 } 1573 1574 1575 /** propagates orbital reduction */ 1576 SCIP_RETCODE SCIPorbitalReductionPropagate( 1577 SCIP* scip, /**< SCIP data structure */ 1578 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */ 1579 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is found */ 1580 int* nred, /**< pointer to store the number of domain reductions */ 1581 SCIP_Bool* didrun /**< a global pointer maintaining if any symmetry propagator has run 1582 * only set this to TRUE when a reduction is found, never set to FALSE */ 1583 ) 1584 { 1585 ORCDATA* orcdata; 1586 SCIP_SHADOWTREE* shadowtree; 1587 int c; 1588 1589 assert( scip != NULL ); 1590 assert( orbireddata != NULL ); 1591 assert( infeasible != NULL ); 1592 assert( nred != NULL ); 1593 assert( didrun != NULL ); 1594 1595 *infeasible = FALSE; 1596 *nred = 0; 1597 1598 /* no components, no orbital reduction */ 1599 assert( orbireddata->ncomponents >= 0 ); 1600 if ( orbireddata->ncomponents == 0 ) 1601 return SCIP_OKAY; 1602 1603 /* do nothing if we are in a probing node */ 1604 if ( SCIPinProbing(scip) ) 1605 return SCIP_OKAY; 1606 1607 /* do not run again in repropagation, since the path to the root might have changed */ 1608 if ( SCIPinRepropagation(scip) ) 1609 return SCIP_OKAY; 1610 1611 assert( orbireddata->shadowtreeeventhdlr != NULL ); 1612 shadowtree = SCIPgetShadowTree(orbireddata->shadowtreeeventhdlr); 1613 assert( shadowtree != NULL ); 1614 1615 for (c = 0; c < orbireddata->ncomponents; ++c) 1616 { 1617 orcdata = orbireddata->componentdatas[c]; 1618 assert( orcdata != NULL ); 1619 assert( orcdata->nperms > 0 ); 1620 SCIP_CALL( orbitalReductionPropagateComponent(scip, orcdata, shadowtree, infeasible, nred) ); 1621 1622 /* a symmetry propagator has ran, so set didrun to TRUE */ 1623 *didrun = TRUE; 1624 1625 if ( *infeasible ) 1626 break; 1627 } 1628 1629 orbireddata->nred += *nred; 1630 if ( *infeasible ) 1631 ++orbireddata->ncutoff; 1632 1633 return SCIP_OKAY; 1634 } 1635 1636 1637 /** adds component for orbital reduction */ 1638 SCIP_RETCODE SCIPorbitalReductionAddComponent( 1639 SCIP* scip, /**< SCIP data structure */ 1640 SCIP_ORBITALREDDATA* orbireddata, /**< orbital reduction data structure */ 1641 SCIP_VAR** permvars, /**< variable array of the permutation */ 1642 int npermvars, /**< number of variables in that array */ 1643 int** perms, /**< permutations in the component */ 1644 int nperms, /**< number of permutations in the component */ 1645 SCIP_Bool* success /**< to store whether the component is successfully added */ 1646 ) 1647 { 1648 assert( scip != NULL ); 1649 assert( orbireddata != NULL ); 1650 assert( permvars != NULL ); 1651 assert( npermvars > 0 ); 1652 assert( perms != NULL ); 1653 assert( nperms > 0 ); 1654 assert( success != NULL ); 1655 1656 /* dynamic symmetry reductions cannot be performed on original problem */ 1657 assert( SCIPisTransformed(scip) ); 1658 1659 SCIP_CALL( addComponent(scip, orbireddata, permvars, npermvars, perms, nperms, success) ); 1660 1661 return SCIP_OKAY; 1662 } 1663 1664 1665 /** resets orbital reduction data structure (clears all components) */ 1666 SCIP_RETCODE SCIPorbitalReductionReset( 1667 SCIP* scip, /**< SCIP data structure */ 1668 SCIP_ORBITALREDDATA* orbireddata /**< orbital reduction data structure */ 1669 ) 1670 { 1671 assert( scip != NULL ); 1672 assert( orbireddata != NULL ); 1673 assert( orbireddata->ncomponents >= 0 ); 1674 assert( (orbireddata->ncomponents == 0) == (orbireddata->componentdatas == NULL) ); 1675 assert( orbireddata->ncomponents <= orbireddata->maxncomponents ); 1676 assert( orbireddata->shadowtreeeventhdlr != NULL ); 1677 1678 while ( orbireddata->ncomponents > 0 ) 1679 { 1680 SCIP_CALL( freeComponent(scip, orbireddata, &(orbireddata->componentdatas[--orbireddata->ncomponents])) ); 1681 } 1682 1683 assert( orbireddata->ncomponents == 0 ); 1684 SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->componentdatas, orbireddata->maxncomponents); 1685 orbireddata->componentdatas = NULL; 1686 orbireddata->maxncomponents = 0; 1687 1688 return SCIP_OKAY; 1689 } 1690 1691 1692 /** frees orbital reduction data */ 1693 SCIP_RETCODE SCIPorbitalReductionFree( 1694 SCIP* scip, /**< SCIP data structure */ 1695 SCIP_ORBITALREDDATA** orbireddata /**< orbital reduction data structure */ 1696 ) 1697 { 1698 assert( scip != NULL ); 1699 assert( orbireddata != NULL ); 1700 assert( *orbireddata != NULL ); 1701 1702 SCIP_CALL( SCIPorbitalReductionReset(scip, *orbireddata) ); 1703 1704 SCIPfreeBlockMemory(scip, orbireddata); 1705 return SCIP_OKAY; 1706 } 1707 1708 1709 /** initializes structures needed for orbital reduction 1710 * 1711 * This is only done exactly once. 1712 */ 1713 SCIP_RETCODE SCIPincludeOrbitalReduction( 1714 SCIP* scip, /**< SCIP data structure */ 1715 SCIP_ORBITALREDDATA** orbireddata, /**< pointer to orbital reduction data structure to populate */ 1716 SCIP_EVENTHDLR* shadowtreeeventhdlr /**< pointer to the shadow tree eventhdlr */ 1717 ) 1718 { 1719 assert( scip != NULL ); 1720 assert( orbireddata != NULL ); 1721 assert( shadowtreeeventhdlr != NULL ); 1722 1723 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, 1724 FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1725 1726 SCIP_CALL( SCIPallocBlockMemory(scip, orbireddata) ); 1727 1728 (*orbireddata)->componentdatas = NULL; 1729 (*orbireddata)->ncomponents = 0; 1730 (*orbireddata)->maxncomponents = 0; 1731 (*orbireddata)->shadowtreeeventhdlr = shadowtreeeventhdlr; 1732 (*orbireddata)->nred = 0; 1733 (*orbireddata)->ncutoff = 0; 1734 1735 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(*orbireddata)->globalfixeventhdlr, 1736 EVENTHDLR_SYMMETRY_NAME, EVENTHDLR_SYMMETRY_DESC, eventExecGlobalBoundChange, 1737 (SCIP_EVENTHDLRDATA*) (*orbireddata)) ); 1738 1739 return SCIP_OKAY; 1740 } 1741