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