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