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_orbitopal.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for handling orbitopal symmetries
28   	 * @author Jasper van Doornmalen
29   	 *
30   	 * This implements orbitopal reducion, which generalizes full orbitope propagation to work for non-binary variable
31   	 * domains, and is dynamified. See cons_orbitope.c for the variant for binary variables, both the static and partially
32   	 * dynamic variant.
33   	 * Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables
34   	 * branched on from the root node to the focus node.
35   	 *
36   	 * See Section 4.2, Example 12 and Section 5.1 in [vD,H]:@n
37   	 * J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023,
38   	 * https://doi.org/10.48550/arXiv.2211.01295.
39   	 *
40   	 * Orbitopal reduction can be used to handle symmetries of the following type.
41   	 * If the variables can be arranged in a matrix and the symmetries correspond to all column permutations of this matrix,
42   	 * then these symmetries are called orbitopal.
43   	 * Symmetry is completely handled by enforcing that the columns are lexicographically decreasing.
44   	 * If a reduction on a variable is applied, and if this variable is high up in the variable matrix, then this has a
45   	 * relatively large impact on the lexicographic ordering. Moreover, the ordering of the columns also matter.
46   	 * Dynamification allows for choosing a custom ordering of a subset of rows and a permutation of the columns.
47   	 * For every node, we maintain the ordered subset of rows and the column order.
48   	 * The root node assumes no rows and an arbitrary column order (we choose the identity).
49   	 * If towards a new node it is branched on a variable, that appears in a row which is not included in the subset of
50   	 * rows for the current node, then the row set of the new children is the ordered row set of the current node, appended
51   	 * by this new row.
52   	 * For the column order, if at the current node columns are symmetrically equivalent, then these can be permuted for
53   	 * the sake of symmetry handling. In the implementation, we only swap the column containing the branching variable
54   	 * with a symmetrically equivalent column elsewhere. We use one of the following heuristics:
55   	 *
56   	 * - None: Keep the column-order as-is.
57   	 * - First: Permute such that the column containing the branching variable is in the symmetrically equivalent column
58   	 *   with minimal index.
59   	 * - Last: The same, but to the symmetrically equivalent column with maximal index.
60   	 * - Centre: The same, but to the symmetrically equivalent column closest to to the middlemost column among all columns.
61   	 * - Median: The same, but to the median of all symmetrically equivalent columns. (This is the default)
62   	 *
63   	 * Since the dynamic row and column ordering rule for a branch-and-bound tree node depends on the decisions made up to
64   	 * that branch-and-bound tree node, we compute and store the row and column order for the branch-and-bound tree children
65   	 * at the moment of branching. This is done by the eventhandler in this file.
66   	 * Instead of storing those, we could have chosen to reconstruct this row and column ordering to save memory.
67   	 * However, we cannot reliably reconstruct this order from the branch-and-bound tree itself,
68   	 * because the row and column ordering depends on symmetrical equivalence of columns in the orbitope matrix,
69   	 * and because SCIP can change the tree structure during solving that may re-write historic variable bound changes
70   	 * (for instance when global variable bound changes are found, or when the root node is moved down the tree to become
71   	 * the new effective root node).
72   	 * We are not concerned about storing the row and column ordering, since we only store the mutations with its parent.
73   	 * These are usually at most one column swap and usually at most one additional row.
74   	 *
75   	 * @todo Exploiting packing-partitioning structures
76   	 * @todo for packing-partitioning rows, use the FIRST column swap heuristic.
77   	 */
78   	
79   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
80   	
81   	#include "blockmemshell/memory.h"
82   	#include "scip/symmetry_orbitopal.h"
83   	#include "scip/pub_cons.h"
84   	#include "scip/pub_message.h"
85   	#include "scip/pub_var.h"
86   	#include "scip/struct_var.h"
87   	#include "scip/type_var.h"
88   	#include "scip/scip.h"
89   	#include "scip/scip_branch.h"
90   	#include "scip/scip_conflict.h"
91   	#include "scip/scip_cons.h"
92   	#include "scip/scip_copy.h"
93   	#include "scip/scip_cut.h"
94   	#include "scip/scip_general.h"
95   	#include "scip/scip_lp.h"
96   	#include "scip/scip_mem.h"
97   	#include "scip/scip_message.h"
98   	#include "scip/scip_numerics.h"
99   	#include "scip/scip_param.h"
100  	#include "scip/scip_prob.h"
101  	#include "scip/scip_probing.h"
102  	#include "scip/scip_sol.h"
103  	#include "scip/scip_var.h"
104  	#include "scip/struct_scip.h"
105  	#include "scip/struct_mem.h"
106  	#include "scip/struct_tree.h"
107  	#include "scip/symmetry.h"
108  	#include "scip/debug.h"
109  	#include <string.h>
110  	#include <symmetry/type_symmetry.h>
111  	
112  	
113  	/* symmetry handler properties */
114  	#define SYMHDLR_NAME           "orbitopalreduction"
115  	
116  	/* orbitopal symmetry handler properties */
117  	#define EVENTHDLR_NAME         "symmetry_orbitopal_eventhdlr"
118  	#define EVENTHDLR_DESC         "event handler for maintaining the branch-and-bound tree"
119  	#define DEFAULT_COLUMNORDERING SCIP_COLUMNORDERING_MEDIAN /**< the column ordering variant */
120  	
121  	/*
122  	 * Data structures
123  	 */
124  	
125  	/** orbitopal symmetry handling data for a single orbitope */
126  	struct OrbitopeData
127  	{
128  	   SCIP_VAR**            vars;               /**< orbitope variable array representing orbitope matrix row-wise */
129  	   int                   nrows;              /**< number of rows */
130  	   int                   ncols;              /**< number of columns */
131  	   int                   nbranchrows;        /**< number of rows containing variables potentially used for branching */
132  	   SCIP_HASHMAP*         rowindexmap;        /**< map of variables to row index in orbitope matrix */
133  	   SCIP_HASHMAP*         colindexmap;        /**< map of variables to column index in orbitope matrix */
134  	#ifndef NDEBUG
135  	   SCIP_Longint          lastnodenumber;     /**< the last node number where the row and column order is computed */
136  	   int                   dbghash;            /**< a hash for the column order in the last iteration */
137  	#endif
138  	   SCIP_HASHTABLE*       nodeinfos;          /**< symmetry handling information per branch-and-bound tree node */
139  	   SCIP_COLUMNORDERING   columnordering;     /**< policy for the column ordering */
140  	   SCIP_ROWORDERING      rowordering;        /**< policy for the row ordering */
141  	};
142  	typedef struct OrbitopeData ORBITOPEDATA; /**< orbitopal symmetry handling data for a single orbitope */
143  	
144  	/** wrapper for all orbitopes in orbitopal symmetry handling data */
145  	struct SCIP_OrbitopalReductionData
146  	{
147  	   SCIP_COLUMNORDERING   defaultcolumnordering; /**< default policy for the column ordering */
148  	   SCIP_EVENTHDLR*       eventhdlr;          /**< pointer to the event handler for managing the branching tree */
149  	   ORBITOPEDATA**        orbitopes;          /**< array of pointers to orbitope data structs */
150  	   int                   norbitopes;         /**< number of orbitope data structs in array */
151  	   int                   maxnorbitopes;      /**< allocated orbitopes array size */
152  	   SCIP_CONSHDLR*        conshdlr_nonlinear; /**< nonlinear constraint handler,
153  	                                              * is used to determine if a variable is a branching variable */
154  	   SCIP_Bool             conshdlr_nonlinear_checked; /**< nonlinear constraint handler is already added? */
155  	   int                   nred;               /**< total number of reductions */
156  	   int                   ncutoff;            /**< total number of cutoffs */
157  	};
158  	
159  	/*
160  	 * Local methods
161  	 */
162  	
163  	/** gets whether a variable type is a branchrow-type */
164  	static
165  	SCIP_Bool vartypeIsBranchRowType(
166  	   SCIP*                 scip,               /**< SCIP data structure */
167  	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< pointer to the dynamic orbitopal reduction data */
168  	   SCIP_VARTYPE          vartype             /**< var type */
169  	)
170  	{
171  	   assert( scip != NULL );
172  	   assert( orbireddata != NULL );
173  	   assert( orbireddata->conshdlr_nonlinear_checked );
174  	
175  	   switch (vartype)
176  	   {
177  	   case SCIP_VARTYPE_BINARY:
178  	   case SCIP_VARTYPE_INTEGER:
179  	      return TRUE;
180  	   case SCIP_VARTYPE_CONTINUOUS:
181  	   case SCIP_VARTYPE_IMPLINT:
182  	      /* potential branching variables if nonlinear constraints exist */
183  	      assert( orbireddata->conshdlr_nonlinear_checked );
184  	      return orbireddata->conshdlr_nonlinear == NULL ? FALSE :
185  	         SCIPconshdlrGetNActiveConss(orbireddata->conshdlr_nonlinear) > 0;
186  	   default:
187  	      SCIPerrorMessage("unknown vartype\n");
188  	      SCIPABORT();
189  	      /* resolve compiler warning: no asserts in optimized mode */
190  	      return FALSE;
191  	   }
192  	}
193  	
194  	
195  	/** container for column index permutations */
196  	struct ColSwap
197  	{
198  	   int                   from;               /**< from which column ID */
199  	   int                   to;                 /**< to which column ID */
200  	};
201  	typedef struct ColSwap COLSWAP;
202  	
203  	/** information stored for branch-and-bound nodes */
204  	struct BnbNodeInfo
205  	{
206  	   SCIP_Longint          nodenumber;         /**< node number of the branch-and-bound tree node */
207  	   COLSWAP*              colswaps;           /**< list containing column swaps by node branching decisions */
208  	   int                   ncolswaps;          /**< number of elements in colswaps. ncolswaps == 0 <=> colswaps == NULL */
209  	   int*                  rows;               /**< list of new variable rows by node branching decisions */
210  	   int                   nrows;              /**< number of new variable rows added. nrows == 0 <=> rows == NULL */
211  	};
212  	typedef struct BnbNodeInfo BNBNODEINFO;
213  	
214  	/** hash key for virtual branch and bound nodeinfo struct */
215  	static
216  	SCIP_DECL_HASHGETKEY(hashGetKeyBnbnodeinfo)
217  	{  /*lint --e{715}*/
218  	   return elem;
219  	}
220  	
221  	/** returns TRUE iff the indices of both node numbers are equal */
222  	static
223  	SCIP_DECL_HASHKEYEQ(hashKeyEqBnbnodeinfo)
224  	{  /*lint --e{715}*/
225  	   BNBNODEINFO* nodeinfo1 = (BNBNODEINFO*) key1;
226  	   BNBNODEINFO* nodeinfo2 = (BNBNODEINFO*) key2;
227  	   return nodeinfo1->nodenumber == nodeinfo2->nodenumber;
228  	}
229  	
230  	/** returns the hash value of the key */
231  	static
232  	SCIP_DECL_HASHKEYVAL(hashKeyValBnbnodeinfo)
233  	{  /*lint --e{715}*/
234  	   BNBNODEINFO* nodeinfo = (BNBNODEINFO*) key;
235  	   return (unsigned int) nodeinfo->nodenumber;
236  	}
237  	
238  	
239  	/** tests if two columns are symmetrically equivalent
240  	 *
241  	 * We test if the columns with index col1 and col2 have elementwise the same bounds.
242  	 * If all symmetry-compatible reductions are applied, then it suffices to check only as many rows as are selected
243  	 * for orbitopal reduction. However, to be resilient to reductions that are not symmetry-compatible,
244  	 * we test all variables in the columns.
245  	 */
246  	static
247  	SCIP_Bool testColumnsAreSymmetricallyEquivalent(
248  	   SCIP*                 scip,               /**< SCIP data structure */
249  	   ORBITOPEDATA*         orbidata,           /**< orbitope information */
250  	   int                   col1,               /**< first column to compare */
251  	   int                   col2                /**< second column to compare */
252  	   )
253  	{
254  	   int i;
255  	   SCIP_VAR* var1;
256  	   SCIP_VAR* var2;
257  	
258  	   assert( scip != NULL );
259  	   assert( orbidata != NULL );
260  	   assert( col1 >= 0 );
261  	   assert( col1 < orbidata->ncols );
262  	   assert( col2 >= 0 );
263  	   assert( col2 < orbidata->ncols );
264  	
265  	   /* @todo test only for the selected rows (see function description) */
266  	   for (i = 0; i < orbidata->nrows; ++i)
267  	   {
268  	      var1 = orbidata->vars[i * orbidata->ncols + col1];
269  	      var2 = orbidata->vars[i * orbidata->ncols + col2];
270  	
271  	      /* if variable bounds differ: columns c and origcolid are not the same */
272  	      if (
273  	         (! SCIPEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetLbLocal(var2)))
274  	         ||
275  	         (! SCIPEQ(scip, SCIPvarGetUbLocal(var1), SCIPvarGetUbLocal(var2)))
276  	      )
277  	         return FALSE;
278  	   }
279  	
280  	   /* loop terminated, so columns are equal */
281  	   return TRUE;
282  	}
283  	
284  	/** updates the column order with a bound change
285  	 *
286  	 *  When it is branched on a variable in a column, update the column order for the children of the focusnode.
287  	 *  Symmetrically equivalent columns, that is the columns where the variables have elementwise the same domain,
288  	 *  at the focusnode at the moment of branching can be permuted.
289  	 *  In this function, we select such a permutation, based on the column containing the branching variable(s).
290  	 *  In all cases, we swap the column containing the branching variable with a symmetrically equivalent column,
291  	 *  and the @param columnordering specifies if we prefer it to be the leftmost, rightmost, centermost symmetrically
292  	 *  equivalent column, or the median column among the symmetrically equivalent columns.
293  	 *
294  	 *  The column ordering is determined and stored at the moment of branching.
295  	 */
296  	static
297  	SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn(
298  	   SCIP*                 scip,               /**< SCIP data structure */
299  	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
300  	   int*                  colorder,           /**< array to populate with column order, of size colorder */
301  	   int*                  colorderinv,        /**< inverse array of the column order, of size colorder */
302  	   SCIP_VAR*             var,                /**< variable that we branch on */
303  	   COLSWAP*              thiscolswap         /**< the colswap to populate */
304  	   )
305  	{
306  	   int origcolid;
307  	   int swaporigcolid;
308  	   int c;
309  	   int ncols;
310  	   int* origequalcolids;
311  	   int norigequalcolids;
312  	   int middlecolumn = 0;
313  	   int positionorigcolidincolorder;
314  	   int positionswaporigcolidincolorder;
315  	
316  	#ifndef NDEBUG
317  	   SCIP_VAR* var1;
318  	   SCIP_VAR* var2;
319  	   int i;
320  	   int nrows;
321  	#endif
322  	
323  	   assert( scip != NULL );
324  	   assert( orbidata != NULL );
325  	   assert( colorder != NULL );
326  	   assert( colorderinv != NULL );
327  	   assert( var != NULL );
328  	   assert( thiscolswap != NULL );
329  	   assert( orbidata->ncols > 0 );
330  	   assert( orbidata->nrows > 0 );
331  	
332  	   ncols = orbidata->ncols;
333  	   assert( ncols > 0 );
334  	#ifndef NDEBUG
335  	   nrows = orbidata->nrows > 0;
336  	   assert( nrows > 0 );
337  	#endif
338  	
339  	   /* do not apply a column swap if no column permutations are applied */
340  	   if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
341  	   {
342  	      thiscolswap->from = 0;
343  	      thiscolswap->to = 0;
344  	      return SCIP_OKAY;
345  	   }
346  	
347  	   /* only variables from the orbitope matrix are of interest */
348  	   origcolid = SCIPhashmapGetImageInt(orbidata->colindexmap, (void*) var);
349  	   if ( origcolid == INT_MAX )
350  	   {
351  	      thiscolswap->from = 0;
352  	      thiscolswap->to = 0;
353  	      return SCIP_OKAY;
354  	   }
355  	   assert( origcolid >= 0 );
356  	   assert( origcolid < ncols );
357  	
358  	   /* policy: swap with identical column that is closest to the center in relabeled order */
359  	   /* @todo other policies: If the variable is in a ppc-row, then select the minimal/second to minimal to branch on */
360  	   swaporigcolid = origcolid;
361  	
362  	   switch (orbidata->columnordering)
363  	   {
364  	   case SCIP_COLUMNORDERING_CENTRE:
365  	      /* CENTRE uses the same code as FIRST and LAST, but requires that middlecolumn = ncols / 2 is set */
366  	      middlecolumn = ncols / 2;
367  	      /*lint -fallthrough*/
368  	   case SCIP_COLUMNORDERING_FIRST:
369  	   case SCIP_COLUMNORDERING_LAST:
370  	      /* for each column, test column ordering condition, then if the column is identical to the var-column */
371  	      for (c = 0; c < ncols; ++c)
372  	      {
373  	         /* origcolid is not interesting */
374  	         if ( c == origcolid )
375  	            continue;
376  	
377  	         /* test if c is a better choice than swaporigcolid,
378  	          * otherwise continue to next iteration through CONDITIONFAIL
379  	          */
380  	         switch (orbidata->columnordering)
381  	         {
382  	            case SCIP_COLUMNORDERING_FIRST:
383  	               /* only swap with c if c is earlier in column order than swaporigcolid */
384  	               if ( colorderinv[c] >= colorderinv[swaporigcolid] )
385  	                  goto CONDITIONFAIL;
386  	               break;
387  	            case SCIP_COLUMNORDERING_LAST:
388  	               /* only swap with c if c is later in column order than swaporigcolid */
389  	               if ( colorderinv[c] <= colorderinv[swaporigcolid] )
390  	                  goto CONDITIONFAIL;
391  	               break;
392  	            case SCIP_COLUMNORDERING_CENTRE:
393  	               /* if the column is not more central than swaporigcolid, ignore */
394  	               if ( ABS(colorderinv[c] - middlecolumn) >=
395  	                     ABS(colorderinv[swaporigcolid] - middlecolumn) )
396  	                  goto CONDITIONFAIL;
397  	               break;
398  	            default:
399  	               return SCIP_ERROR;
400  	         }
401  	
402  	         /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */
403  	         if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) )
404  	            continue;
405  	
406  	         /* the variable domain reductions in c and origcolid are the same */
407  	         swaporigcolid = c;
408  	
409  	      CONDITIONFAIL:
410  	         ;  /* no-op for going to the next iteration */
411  	      }
412  	
413  	      /* end switch */
414  	      break;
415  	
416  	   case SCIP_COLUMNORDERING_MEDIAN:
417  	      /* collect columns identical to the var-column, then select column satisfying ordering condition */
418  	      norigequalcolids = 0;
419  	      SCIP_CALL( SCIPallocBufferArray(scip, &origequalcolids, ncols) );
420  	
421  	      /* collect equal columns */
422  	#ifdef SCIP_MORE_DEBUG
423  	      SCIPdebugMessage("Detect columns identical to original column %d: ", origcolid);
424  	#endif
425  	      for (c = 0; c < ncols; ++c)
426  	      {
427  	         /* column origcolid is always equal to itself */
428  	         if ( c == origcolid )
429  	         {
430  	            origequalcolids[norigequalcolids++] = c;
431  	#ifdef SCIP_MORE_DEBUG
432  	            SCIPdebugPrintf("%d ", c);
433  	#endif
434  	            assert( norigequalcolids <= ncols );
435  	            continue;
436  	         }
437  	
438  	         /* test: are c and origcolid the same columns w.r.t. the variable domain restrictions? */
439  	         if ( !testColumnsAreSymmetricallyEquivalent(scip, orbidata, c, origcolid) )
440  	            continue;
441  	
442  	         /* the variable domain reductions in c and origcolid are the same */
443  	         origequalcolids[norigequalcolids++] = c;
444  	#ifdef SCIP_MORE_DEBUG
445  	         SCIPdebugPrintf("%d ", c);
446  	#endif
447  	         assert( norigequalcolids <= ncols );
448  	      }
449  	#ifdef SCIP_MORE_DEBUG
450  	      SCIPdebugPrintf("\n");
451  	#endif
452  	
453  	      /* we should have found origcolid, at least */
454  	      assert( norigequalcolids >= 1 );
455  	
456  	      /* from origequalcolids, select the column satisfying the column ordering policy */
457  	
458  	      /* get median column; since colorder maps origcolids to our ordering,
459  	       * we need to use colorderinv as the argument. */
460  	      /* @todo computing the median is O(n) by repeated median-of-medians (CLRS, Ch9), but let's just sort things */
461  	      SCIPsortInd(origequalcolids, SCIPsortArgsortInt, colorderinv, norigequalcolids);
462  	      /* get the median, that is swaporigcolid */
463  	      swaporigcolid = origequalcolids[norigequalcolids / 2];
464  	
465  	      SCIPfreeBufferArray(scip, &origequalcolids);
466  	
467  	      /* end switch */
468  	      break;
469  	
470  	   case SCIP_COLUMNORDERING_NONE:
471  	      /* already handled earlier in this function */
472  	   default:
473  	      /* unknown column ordering variant */
474  	      return SCIP_ERROR;
475  	   }
476  	
477  	   thiscolswap->from = swaporigcolid;
478  	   thiscolswap->to = origcolid;
479  	
480  	   /* if we do not replace origcolid */
481  	   if ( swaporigcolid == origcolid )
482  	      return SCIP_OKAY;
483  	
484  	#ifndef NDEBUG
485  	   /* swapped columns should be equivalent */
486  	   for (i = 0; i < nrows; ++i)
487  	   {
488  	      var1 = orbidata->vars[i * ncols + swaporigcolid];
489  	      var2 = orbidata->vars[i * ncols + origcolid];
490  	      assert( SCIPEQ(scip, SCIPvarGetLbLocal(var1), SCIPvarGetLbLocal(var2)) );
491  	      assert( SCIPEQ(scip, SCIPvarGetUbLocal(var1), SCIPvarGetUbLocal(var2)) );
492  	   }
493  	#endif
494  	
495  	   /* now swap the permuted column indices of swaporigcolid and origcolid */
496  	
497  	   /* at which column is origcolid? */
498  	   positionorigcolidincolorder = colorderinv[origcolid];
499  	   assert( positionorigcolidincolorder >= 0 );
500  	   assert( positionorigcolidincolorder < ncols );
501  	   assert( colorder[positionorigcolidincolorder] == origcolid );
502  	
503  	   /* at which column is swaporigcolid? */
504  	   positionswaporigcolidincolorder = colorderinv[swaporigcolid];
505  	   assert( positionswaporigcolidincolorder >= 0 );
506  	   assert( positionswaporigcolidincolorder < ncols );
507  	   assert( colorder[positionswaporigcolidincolorder] == swaporigcolid );
508  	
509  	   SCIPdebugMessage("Orbitope %p: Swapping column %d (at position %d) with column %d (at position %d)\n",
510  	      (void*) orbidata, origcolid, positionorigcolidincolorder, swaporigcolid, positionswaporigcolidincolorder);
511  	
512  	   /* swap them, also keep track of the inverses */
513  	   colorder[positionswaporigcolidincolorder] = origcolid;
514  	   colorder[positionorigcolidincolorder] = swaporigcolid;
515  	   colorderinv[origcolid] = positionswaporigcolidincolorder;
516  	   colorderinv[swaporigcolid] = positionorigcolidincolorder;
517  	
518  	   return SCIP_OKAY;
519  	}
520  	
521  	
522  	/** yields entry at index in array, or returns entry if array is NULL */
523  	static
524  	int getArrayEntryOrIndex(
525  	   int*                  arr,                /**< array */
526  	   int                   idx                 /**< index */
527  	)
528  	{
529  	   assert( idx >= 0 );
530  	   if ( arr == NULL )
531  	      return idx;
532  	   return arr[idx];
533  	}
534  	
535  	/** frees the row order */
536  	static
537  	void freeRowOrder(
538  	   SCIP*                 scip,               /**< SCIP data structure */
539  	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
540  	   int**                 roworder            /**< roworder array that is initialized with the roworder in the dynamic
541  	                                               *  case, and NULL in the static case */
542  	)
543  	{
544  	   assert( scip != NULL );
545  	   assert( orbidata != NULL );
546  	   assert( roworder != NULL );
547  	
548  	   if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
549  	   {
550  	      assert( *roworder == NULL );
551  	      return;
552  	   }
553  	
554  	   assert( *roworder != NULL );
555  	   assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
556  	   SCIPfreeBlockMemoryArray(scip, roworder, orbidata->nrows);
557  	
558  	   return;
559  	}
560  	
561  	/** gets the row order at the node
562  	 *
563  	 *  this is NULL (i.e., the identity map) in the static (none) setting.
564  	 *  this is an array of size orbidata->nrows in the dynamic (branching) setting.
565  	 *
566  	 *  The row order is given in the order of the variables that is branched on.
567  	 *  @todo combine with variant of cons_orbitope.c
568  	 */
569  	static
570  	SCIP_RETCODE getRowOrder(
571  	   SCIP*                 scip,               /**< SCIP data structure */
572  	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
573  	   SCIP_NODE*            node,               /**< node for which the row order should be detected */
574  	   int**                 roworder,           /**< array to populate with row order */
575  	   int*                  nselrows            /**< pointer to populate with the number of rows part of the row order */
576  	   )
577  	{
578  	   int i;
579  	   int j;
580  	   BNBNODEINFO* ancestornodeinfo;
581  	   BNBNODEINFO tmpnodeinfo;  /* used for lookups in hash table */
582  	
583  	   assert( orbidata != NULL );
584  	   assert( orbidata->nrows > 0 );
585  	   assert( orbidata->ncols > 0 );
586  	   assert( node != NULL );
587  	   assert( roworder != NULL );
588  	   assert( nselrows != NULL );
589  	
590  	   if ( orbidata->rowordering == SCIP_ROWORDERING_NONE )
591  	   {
592  	      *roworder = NULL;
593  	      *nselrows = orbidata->nrows;
594  	      return SCIP_OKAY;
595  	   }
596  	
597  	   assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
598  	
599  	   /* allocate number of rows */
600  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, roworder, orbidata->nrows) );
601  	
602  	   *nselrows = 0;
603  	
604  	   /* get the present row order up to this node (excluding the node itself) */
605  	   node = SCIPnodeGetParent(node);
606  	   while (node != NULL)
607  	   {
608  	      /* retrieve the nodeinfo of this ancestor node */
609  	      tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
610  	      ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
611  	      if ( ancestornodeinfo != NULL )
612  	      {
613  	         assert( ancestornodeinfo->nrows >= 0 );
614  	         for (i = ancestornodeinfo->nrows - 1; i >= 0; --i)
615  	         {
616  	            (*roworder)[(*nselrows)++] = ancestornodeinfo->rows[i];
617  	#ifndef NDEBUG
618  	            {
619  	               /* check if this row is not featured earlier */
620  	               for (j = 0; j < (*nselrows) - 1; ++j)
621  	               {
622  	                  assert( ancestornodeinfo->rows[i] != (*roworder)[j] );
623  	               }
624  	            }
625  	#endif
626  	         }
627  	      }
628  	
629  	      node = SCIPnodeGetParent(node);
630  	   }
631  	
632  	   /* row order is in reverse order now, so reverse the array */
633  	   for (i = 0; i < (*nselrows) / 2; ++i)
634  	   {
635  	      /* swap entry i with nselrows - 1 - i */
636  	      j = (*roworder)[i];
637  	      (*roworder)[i] = (*roworder)[(*nselrows) - 1 - i];
638  	      (*roworder)[(*nselrows) - 1 - i] = j;
639  	   }
640  	
641  	   return SCIP_OKAY;
642  	}
643  	
644  	
645  	/** gets rooted path up to node and populates column ordering array */
646  	static
647  	SCIP_RETCODE populateRootedPathColumnOrder(
648  	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
649  	   SCIP_NODE*            node,               /**< node considered */
650  	   SCIP_NODE**           rootedpath,         /**< array to populate with the rooted path, must be sufficiently long */
651  	   int*                  colorder,           /**< array to populate with the column order, must be nvars long */
652  	   int*                  colorderinv         /**< array to populate with the inverse column order, must be nvars long */
653  	   )
654  	{
655  	   int i;
656  	   int j;
657  	   int depth;
658  	   BNBNODEINFO* ancestornodeinfo;
659  	   BNBNODEINFO tmpnodeinfo;
660  	   COLSWAP* thiscolswap;
661  	
662  	   assert( orbidata != NULL );
663  	   assert( node != NULL );
664  	   assert( rootedpath != NULL );
665  	   assert( colorder != NULL );
666  	   assert( colorderinv != NULL );
667  	
668  	   depth = SCIPnodeGetDepth(node);
669  	   i = depth;
670  	   while ( node != NULL )
671  	   {
672  	      assert( SCIPnodeGetDepth(node) == i );
673  	      rootedpath[i--] = node;
674  	      node = SCIPnodeGetParent(node);
675  	   }
676  	   assert( i == -1 );
677  	
678  	   for (i = 0; i <= depth; ++i)
679  	   {
680  	      node = rootedpath[i];
681  	
682  	      assert( SCIPnodeGetDepth(node) == i );
683  	
684  	      /* get the node info of that node */
685  	      tmpnodeinfo.nodenumber = SCIPnodeGetNumber(node);
686  	      ancestornodeinfo = (BNBNODEINFO*) SCIPhashtableRetrieve(orbidata->nodeinfos, (void*) &tmpnodeinfo);
687  	
688  	      /* skip nodes that do not imply any row or column swaps */
689  	      if ( ancestornodeinfo == NULL )
690  	         continue;
691  	
692  	      /* ncolswaps == 0 iff colswaps == NULL */
693  	      assert( (ancestornodeinfo->ncolswaps == 0) != (ancestornodeinfo->colswaps != NULL) );
694  	
695  	      for (j = 0; j < ancestornodeinfo->ncolswaps; ++j)
696  	      {
697  	         int positionfromincolorder;
698  	         int positiontoincolorder;
699  	
700  	         thiscolswap = &ancestornodeinfo->colswaps[j];
701  	         assert( thiscolswap->from != thiscolswap->to );  /* there are no trivial swaps in the list */
702  	         assert( thiscolswap->from >= 0 && thiscolswap->from < orbidata->ncols );
703  	         assert( thiscolswap->to >= 0 && thiscolswap->to < orbidata->ncols );
704  	
705  	         /* at which column is origcolid? */
706  	         positionfromincolorder = colorderinv[thiscolswap->from];
707  	         assert( positionfromincolorder >= 0 );
708  	         assert( positionfromincolorder < orbidata->ncols );
709  	         assert( colorder[positionfromincolorder] == thiscolswap->from );
710  	
711  	         /* at which column is swaporigcolid? */
712  	         positiontoincolorder = colorderinv[thiscolswap->to];
713  	         assert( positiontoincolorder >= 0 );
714  	         assert( positiontoincolorder < orbidata->ncols );
715  	         assert( colorder[positiontoincolorder] == thiscolswap->to );
716  	
717  	         /* swap them, also keep track of the inverses */
718  	         colorder[positiontoincolorder] = thiscolswap->from;
719  	         colorder[positionfromincolorder] = thiscolswap->to;
720  	         colorderinv[thiscolswap->from] = positiontoincolorder;
721  	         colorderinv[thiscolswap->to] = positionfromincolorder;
722  	      }
723  	   }
724  	
725  	   return SCIP_OKAY;
726  	}
727  	
728  	/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
729  	static
730  	SCIP_DECL_EVENTEXEC(eventExecNodeBranched)
731  	{
732  	   ORBITOPEDATA* orbidata;
733  	   SCIP_NODE* node;
734  	   SCIP_NODE* eventnode;
735  	   SCIP_NODE** children;
736  	   SCIP_NODE* childnode;
737  	   SCIP_DOMCHG* domchg;
738  	   SCIP_BOUNDCHG* boundchg;
739  	   SCIP_VAR* var;
740  	   SCIP_VAR** branchvars;
741  	   int maxnbranchvars;
742  	   int nbranchvars;
743  	   int nboundchgs;
744  	   int nchildren;
745  	   int i;
746  	   int j;
747  	   int c;
748  	   int rowid;
749  	   BNBNODEINFO* newnodeinfo;
750  	   SCIP_NODE** rootedpath;
751  	
752  	   assert( eventdata != NULL );
753  	   assert( !SCIPinProbing(scip) );
754  	
755  	   eventnode = SCIPeventGetNode(event);
756  	   assert( SCIPgetFocusNode(scip) == eventnode );
757  	
758  	   orbidata = (ORBITOPEDATA*) eventdata;
759  	   assert( orbidata != NULL );
760  	   assert( orbidata->nrows > 0 );
761  	   assert( orbidata->ncols > 0 );
762  	   assert( orbidata->vars != NULL );
763  	   assert( orbidata->colindexmap != NULL );
764  	   assert( orbidata->rowindexmap != NULL );
765  	
766  	   SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
767  	
768  	   /* arrays used within the loop */
769  	   maxnbranchvars = 1;  /* it's a good guess that there's one branching variable, because that's likely the number */
770  	   SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, maxnbranchvars) );
771  	   SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, SCIPnodeGetDepth(eventnode)) );
772  	
773  	   /* get all variables branched upon (check all branches) */
774  	   nbranchvars = 0;
775  	   for (c = 0; c < nchildren; ++c)
776  	   {
777  	      childnode = children[c];
778  	      domchg = SCIPnodeGetDomchg(childnode);
779  	
780  	      /* loop through all bound changes */
781  	      nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
782  	      for (i = 0; i < nboundchgs; ++i)
783  	      {
784  	         /* get bound change info */
785  	         boundchg = SCIPdomchgGetBoundchg(domchg, i);
786  	         assert( boundchg != NULL );
787  	
788  	         /* branching decisions have to be in the beginning of the bound change array */
789  	         if ( SCIPboundchgGetBoundchgtype(boundchg) != SCIP_BOUNDCHGTYPE_BRANCHING )
790  	            break;
791  	
792  	         /* get corresponding branching variable */
793  	         var = SCIPboundchgGetVar(boundchg);
794  	
795  	         /* only variables from the orbitope matrix are of interest */
796  	         if ( ! SCIPhashmapExists(orbidata->rowindexmap, (void*) var) )
797  	            continue;
798  	
799  	         /* skip variables that are already stored */
800  	         if ( nbranchvars > 0 )
801  	         {
802  	            for (j = 0; j < nbranchvars; ++j)
803  	            {
804  	               if ( branchvars[j] == var )
805  	                  break;
806  	            }
807  	            /* if the loop above is stopped with `break`, `j < nbranchvars` is not satisfied.
808  	               * then, go to the next iteration
809  	               */
810  	            if ( j < nbranchvars )
811  	               continue;
812  	         }
813  	
814  	         /* the variable is not already in the array, so store it */
815  	         if ( nbranchvars >= maxnbranchvars )
816  	         {
817  	            assert( nbranchvars == maxnbranchvars );
818  	            assert( maxnbranchvars > 0 );
819  	            maxnbranchvars = SCIPcalcMemGrowSize(scip, maxnbranchvars + 1);
820  	            SCIP_CALL( SCIPreallocBufferArray(scip, &branchvars, maxnbranchvars) );
821  	         }
822  	         assert( nbranchvars < maxnbranchvars );
823  	         branchvars[nbranchvars++] = var;
824  	      }
825  	   }
826  	
827  	   /* skip orbitopes whose variable matrices do not contain any branching variable */
828  	   if ( nbranchvars <= 0 )
829  	      goto FREE;
830  	
831  	   SCIP_CALL( SCIPallocBlockMemory(scip, &newnodeinfo) );
832  	   newnodeinfo->nodenumber = SCIPnodeGetNumber(eventnode);
833  	   newnodeinfo->colswaps = NULL;
834  	   newnodeinfo->ncolswaps = 0;
835  	   newnodeinfo->rows = NULL;
836  	   newnodeinfo->nrows = 0;
837  	
838  	   /* store data about row ordering */
839  	   if ( orbidata->rowordering != SCIP_ROWORDERING_NONE )
840  	   {
841  	      int* roworder;
842  	      int nselrows;
843  	
844  	      assert( orbidata->nrows > 0 );
845  	      assert( orbidata->rowordering == SCIP_ROWORDERING_BRANCHING );
846  	
847  	      /* get the present row order up to this node */
848  	      SCIP_CALL( getRowOrder(scip, orbidata, eventnode, &roworder, &nselrows) );
849  	      assert( roworder != NULL );
850  	
851  	      /* extend the row fixings with the steps from this node */
852  	      for (i = 0; i < nbranchvars; ++i)
853  	      {
854  	         var = branchvars[i];
855  	
856  	         assert( SCIPhashmapExists(orbidata->rowindexmap, (void*) var) ); /* otherwise was not added to branchvars */
857  	         rowid = SCIPhashmapGetImageInt(orbidata->rowindexmap, (void*) var);
858  	         assert( rowid >= 0 );
859  	         assert( rowid < orbidata->nrows );
860  	
861  	         /* avoid adding row to row order twice */
862  	         if ( nselrows > 0 )
863  	         {
864  	            for (j = 0; j < nselrows; ++j)
865  	            {
866  	               if ( rowid == roworder[j] )
867  	                  break;
868  	            }
869  	            if ( j < nselrows )  /* if the loop is interrupted */
870  	               continue;
871  	         }
872  	
873  	         /* if we end up here, the row index does not appear for any ancestor or the present row order */
874  	
875  	         /* append rowid to present roworder */
876  	         roworder[nselrows++] = rowid;
877  	
878  	         /* mark that this row index is the new one in the node */
879  	         if ( newnodeinfo->rows == NULL )
880  	         {
881  	            assert( newnodeinfo->nrows == 0 );
882  	            SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->rows, newnodeinfo->nrows + 1) );
883  	         }
884  	         else
885  	         {
886  	            /* reallocate with linear increments, because we expect 1 branching variable most of the time */
887  	            SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &newnodeinfo->rows,
888  	               newnodeinfo->nrows, newnodeinfo->nrows + 1) );
889  	         }
890  	         newnodeinfo->rows[newnodeinfo->nrows++] = rowid;
891  	      }
892  	
893  	      freeRowOrder(scip, orbidata, &roworder);
894  	   }
895  	
896  	   /* store data about column ordering */
897  	   if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE )
898  	   {
899  	      int* colorder;
900  	      int* colorderinv;
901  	      COLSWAP* thiscolswap;
902  	      COLSWAP tmpcolswap;
903  	
904  	      assert( orbidata->ncols > 0 );
905  	      SCIP_CALL( SCIPallocBufferArray(scip, &colorder, orbidata->ncols) );
906  	      SCIP_CALL( SCIPallocBufferArray(scip, &colorderinv, orbidata->ncols) );
907  	
908  	      /* populate colorder with standard ordering */
909  	      for (i = 0; i < orbidata->ncols; ++i)
910  	         colorder[i] = i;
911  	
912  	      /* introduce inverse column ordering */
913  	      for (i = 0; i < orbidata->ncols; ++i)
914  	         colorderinv[i] = i;
915  	
916  	      /* get the rooted path
917  	      *
918  	      * We want to iterate through the bound changes in the order of the rooted path to this node.
919  	      */
920  	      node = SCIPnodeGetParent(eventnode);
921  	      if ( node != NULL )
922  	      {
923  	         SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, colorder, colorderinv) );
924  	      }
925  	
926  	      /* get the swap for this node */
927  	      for (i = 0; i < nbranchvars; ++i)
928  	      {
929  	         SCIP_CALL( updateColumnOrderWhenBranchingOnColumn(scip, orbidata, colorder,
930  	            colorderinv, branchvars[i], &tmpcolswap) );
931  	
932  	         /* skip trivial swaps of columns */
933  	         if ( tmpcolswap.from == tmpcolswap.to )
934  	            continue;
935  	
936  	         /* mark that this row index is the new one in the node */
937  	         if ( newnodeinfo->rows == NULL )
938  	         {
939  	            assert( newnodeinfo->nrows == 0 );
940  	            SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps + 1) );
941  	         }
942  	         else
943  	         {
944  	            /* reallocate with linear increments, because we expect 1 branching variable most of the time */
945  	            SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &newnodeinfo->colswaps, newnodeinfo->ncolswaps,
946  	               newnodeinfo->ncolswaps + 1) );
947  	         }
948  	         thiscolswap = &(newnodeinfo->colswaps[newnodeinfo->ncolswaps++]);
949  	         thiscolswap->from = tmpcolswap.from;
950  	         thiscolswap->to = tmpcolswap.to;
951  	      }
952  	
953  	      SCIPfreeBufferArray(scip, &colorder);
954  	      SCIPfreeBufferArray(scip, &colorderinv);
955  	   }
956  	
957  	   /* store updates of row/column order or free memory if no change applied */
958  	   if ( newnodeinfo->nrows > 0 || newnodeinfo->ncolswaps > 0 )
959  	   {
960  	      SCIP_CALL( SCIPhashtableSafeInsert(orbidata->nodeinfos, newnodeinfo) );
961  	   }
962  	   else
963  	   {
964  	      SCIPfreeBlockMemory(scip, &newnodeinfo);
965  	   }
966  	
967  	FREE:
968  	   SCIPfreeBufferArray(scip, &rootedpath);
969  	   SCIPfreeBufferArray(scip, &branchvars);
970  	
971  	   return SCIP_OKAY;
972  	} /*lint !e715*/
973  	
974  	
975  	/** at branching decisions, maintains the column swap and potential new rows in the orbitope */
976  	static
977  	SCIP_DECL_EVENTEXEC(eventExec)
978  	{
979  	   switch (SCIPeventGetType(event))
980  	   {
981  	   case SCIP_EVENTTYPE_NODEBRANCHED:
982  	      return eventExecNodeBranched(scip, eventhdlr, event, eventdata);
983  	   default:
984  	      SCIPerrorMessage("Eventhandler " EVENTHDLR_NAME " is called with an unsupported eventtype.\n");
985  	      return SCIP_ERROR;
986  	   }
987  	}
988  	
989  	
990  	/** returns whether a row contains potential branching variables */
991  	static
992  	SCIP_Bool rowIsBranchRow(
993  	   SCIP*                 scip,               /**< SCIP data structure */
994  	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< pointer to the dynamic orbitopal reduction data */
995  	   ORBITOPEDATA*         orbidata,           /**< symmetry handling data for orbitopal structure */
996  	   int                   rowid               /**< row id for which to check */
997  	   )
998  	{
999  	   SCIP_VAR* var;
1000 	#ifndef NDEBUG
1001 	   int c;
1002 	#endif
1003 	
1004 	   assert( scip != NULL );
1005 	   assert( orbireddata != NULL );
1006 	   assert( orbidata != NULL );
1007 	   assert( orbidata->nrows > 0 );
1008 	   assert( orbidata->ncols > 0 );
1009 	   assert( rowid >= 0 );
1010 	   assert( rowid < orbidata->nrows );
1011 	   assert( orbidata->vars != NULL );
1012 	   assert( orbidata->vars[rowid * orbidata->ncols] );  /* variable in first column must be set */
1013 	
1014 	   /* get the first variable from the row */
1015 	   var = orbidata->vars[rowid * orbidata->ncols];
1016 	
1017 	   /* debugging: the variable types in a row should all be the same */
1018 	#ifndef NDEBUG
1019 	   for (c = 1; c < orbidata->ncols; ++c)
1020 	   {
1021 	      /* the actual vartypes can be different,
1022 	       * for example when an INTEGER vartype turns into BINARY due to bound changes
1023 	       */
1024 	      assert( vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var)) ==
1025 	         vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(orbidata->vars[rowid * orbidata->ncols + c])) );
1026 	   }
1027 	#endif
1028 	
1029 	   return vartypeIsBranchRowType(scip, orbireddata, SCIPvarGetType(var));
1030 	}
1031 	
1032 	
1033 	/** frees orbitope data */
1034 	static
1035 	SCIP_RETCODE freeOrbitope(
1036 	   SCIP*                 scip,               /**< SCIP data structure */
1037 	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< pointer to the dynamic orbitopal reduction data */
1038 	   ORBITOPEDATA**        orbidata            /**< pointer to orbitope data */
1039 	   )
1040 	{
1041 	   BNBNODEINFO* nodeinfo;
1042 	   int i;
1043 	   int nentries;
1044 	   int nelem;
1045 	
1046 	   assert( scip != NULL );
1047 	   assert( orbireddata != NULL );
1048 	   assert( orbidata != NULL );
1049 	   assert( *orbidata != NULL );
1050 	   assert( (*orbidata)->vars != NULL );
1051 	   assert( (*orbidata)->nrows > 0 );
1052 	   assert( (*orbidata)->ncols > 0 );
1053 	   assert( (*orbidata)->nrows * (*orbidata)->ncols > 0 );
1054 	   assert( SCIPisTransformed(scip) );
1055 	
1056 	   /* free data if orbitopal reduction is dynamic */
1057 	   if ( (*orbidata)->columnordering != SCIP_COLUMNORDERING_NONE || (*orbidata)->rowordering != SCIP_ROWORDERING_NONE )
1058 	   {
1059 	      /* drop event */
1060 	      SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr,
1061 	            (SCIP_EVENTDATA*) *orbidata, -1 ) );
1062 	
1063 	      /* free nodeinfos */
1064 	      nentries = SCIPhashtableGetNEntries((*orbidata)->nodeinfos);
1065 	      for (i = 0; i < nentries; ++i)
1066 	      {
1067 	         /* @todo in principle, can deal with memory sparsity by first getting all nodeinfos,
1068 	          * then sorting by address and free them in descending order
1069 	          */
1070 	         nodeinfo = (BNBNODEINFO*) (SCIPhashtableGetEntry((*orbidata)->nodeinfos, i));
1071 	         if ( nodeinfo == NULL )
1072 	            continue;
1073 	
1074 	         assert( nodeinfo != NULL );
1075 	         assert( nodeinfo->nrows > 0 || nodeinfo->ncolswaps > 0 );
1076 	
1077 	         assert( (nodeinfo->ncolswaps == 0) != (nodeinfo->colswaps != NULL) );
1078 	         SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->colswaps), nodeinfo->ncolswaps);
1079 	
1080 	         assert( (nodeinfo->nrows == 0) != (nodeinfo->rows != NULL) );
1081 	         SCIPfreeBlockMemoryArrayNull(scip, &(nodeinfo->rows), nodeinfo->nrows);
1082 	
1083 	         SCIPfreeBlockMemory(scip, &nodeinfo);
1084 	      }
1085 	      SCIPhashtableFree(&((*orbidata)->nodeinfos));
1086 	   }
1087 	
1088 	   /* free index lookup hashsets */
1089 	   SCIPhashmapFree(&((*orbidata)->colindexmap));
1090 	   SCIPhashmapFree(&((*orbidata)->rowindexmap));
1091 	
1092 	   /* free and release vars */
1093 	   nelem = (*orbidata)->nrows * (*orbidata)->ncols;
1094 	   assert( nelem > 0 );
1095 	   for (i = 0; i < nelem; ++i)
1096 	   {
1097 	      SCIP_CALL( SCIPreleaseVar(scip, &(*orbidata)->vars[i]) );
1098 	   }
1099 	   SCIPfreeBlockMemoryArray(scip, &((*orbidata)->vars), (*orbidata)->nrows * (*orbidata)->ncols); /*lint !e647*/
1100 	
1101 	   SCIPfreeBlockMemory(scip, orbidata);
1102 	
1103 	   return SCIP_OKAY;
1104 	}
1105 	
1106 	
1107 	/** adds an orbitope to the orbitopal reduction data */
1108 	static
1109 	SCIP_RETCODE addOrbitope(
1110 	   SCIP*                 scip,               /**< SCIP data structure */
1111 	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< pointer to the dynamic orbitopal reduction data */
1112 	   SCIP_ROWORDERING      rowordering,        /**< specifies how rows of orbitope are ordered */
1113 	   SCIP_COLUMNORDERING   colordering,        /**< specifies how columnss of orbitope are ordered */
1114 	   SCIP_VAR**            vars,               /**< variables array, must have size nrows * ncols */
1115 	   int                   nrows,              /**< number of rows in orbitope */
1116 	   int                   ncols,              /**< number of columns in orbitope */
1117 	   SCIP_Bool*            success             /**< to store whether the component is successfully added */
1118 	   )
1119 	{
1120 	   ORBITOPEDATA* orbidata;
1121 	   SCIP_VAR* var;
1122 	   int i;
1123 	   int rowid;
1124 	   int colid;
1125 	   int nelem;
1126 	
1127 	   assert( scip != NULL );
1128 	   assert( orbireddata != NULL );
1129 	   assert( orbireddata->eventhdlr != NULL );
1130 	   assert( vars != NULL );
1131 	   assert( nrows >= 0 );
1132 	   assert( ncols >= 0 );
1133 	
1134 	   nelem = nrows * ncols;
1135 	   assert( nelem >= 0 );
1136 	
1137 	   /* prevent trivial case with empty orbitope */
1138 	   if ( nelem == 0 )
1139 	   {
1140 	      *success = FALSE;
1141 	      return SCIP_OKAY;
1142 	   }
1143 	
1144 	   *success = TRUE;
1145 	
1146 	   SCIP_CALL( SCIPallocBlockMemory(scip, &orbidata) );
1147 	
1148 	   orbidata->nrows = nrows;
1149 	   orbidata->ncols = ncols;
1150 	   orbidata->columnordering = colordering;
1151 	   orbidata->rowordering = rowordering;
1152 	
1153 	#ifndef NDEBUG
1154 	   orbidata->lastnodenumber = -1;
1155 	   orbidata->dbghash = 0;
1156 	#endif
1157 	
1158 	   /* variable array enumerates the orbitope matrix row-wise */
1159 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbidata->vars, nelem) );
1160 	
1161 	   /* create row and column index lookup maps */
1162 	   SCIP_CALL( SCIPhashmapCreate(&orbidata->rowindexmap, SCIPblkmem(scip), nrows) );
1163 	   SCIP_CALL( SCIPhashmapCreate(&orbidata->colindexmap, SCIPblkmem(scip), ncols) );
1164 	
1165 	   SCIPdebugMessage("Orbitope variables for (%dx%d) orbitope with orbidata %p\n", nrows, ncols, (void*) orbidata);
1166 	
1167 	   /* populate variable array defining orbitope matrix for orbitope data */
1168 	   for (i = 0, rowid = 0, colid = 0; i < nelem; ++i, ++colid)
1169 	   {
1170 	      if ( colid == ncols )
1171 	      {
1172 	         colid = 0;
1173 	         ++rowid;
1174 	      }
1175 	      assert( nrows > 0 );
1176 	      assert( ncols > 0 );
1177 	      assert( rowid == i / ncols );
1178 	      assert( colid == i % ncols );
1179 	
1180 	      var = vars[i];
1181 	      assert( var != NULL );
1182 	      assert( SCIPvarIsTransformed(var) );
1183 	
1184 	      SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
1185 	      SCIP_CALL( SCIPcaptureVar(scip, var) );
1186 	
1187 	      orbidata->vars[i] = var;
1188 	
1189 	      /* variables cannot be repeated in the variable matrix */
1190 	      assert( ! SCIPhashmapExists(orbidata->rowindexmap, var) );
1191 	      SCIP_CALL( SCIPhashmapInsertInt(orbidata->rowindexmap, var, rowid) );
1192 	
1193 	      assert( ! SCIPhashmapExists(orbidata->colindexmap, var) );
1194 	      SCIP_CALL( SCIPhashmapInsertInt(orbidata->colindexmap, var, colid) );
1195 	
1196 	      SCIPdebugMessage("%4d %4d -> %s\n", rowid, colid, var->name);
1197 	   }
1198 	
1199 	   /* count number of branchable rows in orbitope */
1200 	   orbidata->nbranchrows = 0;
1201 	   /* @todo at getRowData: If nselrows == nbranchrows, append the non-branch rows (like before) */
1202 	   for (i = 0; i < nrows; ++i)
1203 	   {
1204 	      if ( rowIsBranchRow(scip, orbireddata, orbidata, i) )
1205 	         ++orbidata->nbranchrows;
1206 	   }
1207 	
1208 	   /* cannot add orbitope when already branching */
1209 	   assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING ? SCIPgetNNodes(scip) == 0 : TRUE );
1210 	
1211 	   /* possibly create data needed for dynamic orbitopal reduction */
1212 	   if ( orbidata->columnordering != SCIP_COLUMNORDERING_NONE || orbidata->rowordering != SCIP_ROWORDERING_NONE )
1213 	   {
1214 	      /* add the event to store the row and column updates of nodes in the branch-and-bound tree */
1215 	      SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED, orbireddata->eventhdlr,
1216 	            (SCIP_EVENTDATA*) orbidata, NULL) );
1217 	
1218 	      /* nodeinfos: every node that implies a column swap is represented
1219 	       *
1220 	       * Assuming at most one branching on every variable implying a column swap, initial hashtable size nelem.
1221 	       * In case that there are many more rows than columns, we do not expect too many column swaps.
1222 	       */
1223 	      SCIP_CALL( SCIPhashtableCreate(&orbidata->nodeinfos, scip->mem->probmem, MIN(16 * ncols + 64, nelem),
1224 	            hashGetKeyBnbnodeinfo, hashKeyEqBnbnodeinfo, hashKeyValBnbnodeinfo, NULL) );
1225 	   }
1226 	
1227 	   /* resize orbitope array if needed */
1228 	   assert( orbireddata->norbitopes >= 0 );
1229 	   assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
1230 	   assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
1231 	   if ( orbireddata->norbitopes == orbireddata->maxnorbitopes )
1232 	   {
1233 	      int newsize;
1234 	
1235 	      newsize = SCIPcalcMemGrowSize(scip, orbireddata->norbitopes + 1);
1236 	      assert( newsize >= 0 );
1237 	
1238 	      if ( orbireddata->norbitopes == 0 )
1239 	      {
1240 	         SCIP_CALL( SCIPallocBlockMemoryArray(scip, &orbireddata->orbitopes, newsize) );
1241 	      }
1242 	      else
1243 	      {
1244 	         SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &orbireddata->orbitopes, orbireddata->norbitopes, newsize) );
1245 	      }
1246 	
1247 	      orbireddata->maxnorbitopes = newsize;
1248 	   }
1249 	   assert( orbireddata->orbitopes != NULL );
1250 	   assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1251 	
1252 	   /* add orbitope to orbitopal reduction data */
1253 	   assert( orbireddata->norbitopes < orbireddata->maxnorbitopes );
1254 	   orbireddata->orbitopes[orbireddata->norbitopes++] = orbidata;
1255 	
1256 	   SCIPdebugMsg(scip, "Added orbitope for orbitopal reduction of size %d by %d\n", nrows, ncols);
1257 	
1258 	   return SCIP_OKAY;
1259 	}
1260 	
1261 	
1262 	/** frees the column order */
1263 	static
1264 	void freeColumnOrder(
1265 	   SCIP*                 scip,               /**< SCIP data structure */
1266 	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
1267 	   int**                 colorder,           /**< colorder array that is initialized with the colorder in the dynamic
1268 	                                               *  case, of size ncols, and NULL in the static case */
1269 	   int**                 colorderinv         /**< array with the inverse column order, of size ncols */
1270 	)
1271 	{
1272 	   assert( scip != NULL );
1273 	   assert( orbidata != NULL );
1274 	   assert( colorder != NULL );
1275 	   assert( colorderinv != NULL );
1276 	
1277 	   if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1278 	   {
1279 	      assert( *colorder == NULL );
1280 	      assert( *colorderinv == NULL );
1281 	      return;
1282 	   }
1283 	   assert( *colorder != NULL );
1284 	   assert( *colorderinv != NULL );
1285 	
1286 	   SCIPfreeBlockMemoryArray(scip, colorder, orbidata->ncols);
1287 	   SCIPfreeBlockMemoryArray(scip, colorderinv, orbidata->ncols);
1288 	}
1289 	
1290 	
1291 	/** gets the column order at the node
1292 	 *
1293 	 *  The column order is (deterministically) dynamically decided based on the policy for column ordering.
1294 	 */
1295 	static
1296 	SCIP_RETCODE getColumnOrder(
1297 	   SCIP*                 scip,               /**< SCIP data structure */
1298 	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
1299 	   SCIP_NODE*            eventnode,          /**< node where this should be determined at */
1300 	   int*                  roworder,           /**< array with the row order, of size nselrows */
1301 	   int                   nselrows,           /**< number of rows (required to be positive) */
1302 	   int**                 colorder,           /**< array to populate with column order, of size ncols */
1303 	   int**                 colorderinv         /**< array to populate with inverse column order, of size ncols */
1304 	   )
1305 	{
1306 	   SCIP_NODE* node;
1307 	   SCIP_NODE** rootedpath;
1308 	   int i;
1309 	   int depth;
1310 	   int ncols;
1311 	
1312 	   assert( scip != NULL );
1313 	   assert( orbidata != NULL );
1314 	   assert( eventnode != NULL );
1315 	   assert( roworder != NULL );
1316 	   assert( nselrows > 0 );
1317 	   assert( colorder != NULL );
1318 	   assert( colorderinv != NULL );
1319 	
1320 	   if ( orbidata->columnordering == SCIP_COLUMNORDERING_NONE )
1321 	   {
1322 	      *colorder = NULL;
1323 	      *colorderinv = NULL;
1324 	      return SCIP_OKAY;
1325 	   }
1326 	   ncols = orbidata->ncols;
1327 	   assert( ncols > 0 );
1328 	
1329 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorder, ncols) );
1330 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, colorderinv, ncols) );
1331 	
1332 	   /* populate colorder with standard ordering */
1333 	   for (i = 0; i < ncols; ++i)
1334 	      (*colorder)[i] = i;
1335 	
1336 	   /* introduce inverse column ordering */
1337 	   for (i = 0; i < ncols; ++i)
1338 	      (*colorderinv)[i] = i;
1339 	
1340 	   /* get the rooted path
1341 	    *
1342 	    * We want to iterate through the bound changes in the order of the rooted path to this node.
1343 	    */
1344 	   node = SCIPnodeGetParent(eventnode);
1345 	   if ( node != NULL )
1346 	   {
1347 	      depth = SCIPnodeGetDepth(node);
1348 	      SCIP_CALL( SCIPallocBufferArray(scip, &rootedpath, depth + 1) );
1349 	      SCIP_CALL( populateRootedPathColumnOrder(orbidata, node, rootedpath, *colorder, *colorderinv) );
1350 	      SCIPfreeBufferArray(scip, &rootedpath);
1351 	   }
1352 	
1353 	   return SCIP_OKAY;
1354 	}
1355 	
1356 	
1357 	#ifndef NDEBUG
1358 	/** checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering */
1359 	static
1360 	void assertIsOrbitopeMatrix(
1361 	   SCIP*                 scip,               /**< SCIP data structure */
1362 	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
1363 	   int*                  roworder,           /**< array with the row order */
1364 	   int*                  colorder,           /**< array with the column order */
1365 	   SCIP_Real*            matrix,             /**< a matrix */
1366 	   int                   nrows,              /**< number of rows of matrix */
1367 	   int                   ncols,              /**< number of cols of matrix */
1368 	   int*                  infinitesimal,      /**< array specifying where the infinitesimals are at */
1369 	   SCIP_Bool             addinfinitesimals   /**< whether infinitesimals are added (TRUE) or subtracted (FALSE) */
1370 	   )
1371 	{
1372 	   int rowid;
1373 	   int colid;
1374 	   int idx;
1375 	   int origrowid;
1376 	   int origcolid;
1377 	   int origidx;
1378 	   SCIP_VAR* var;
1379 	
1380 	   assert( scip != NULL );
1381 	   assert( matrix != NULL );
1382 	   assert( orbidata != NULL );
1383 	   assert( orbidata->vars != NULL );
1384 	   assert( nrows >= 0 );
1385 	   assert( nrows <= orbidata->nrows );
1386 	   assert( ncols >= 0 );
1387 	   assert( ncols <= orbidata->ncols );
1388 	   assert( infinitesimal != NULL );
1389 	
1390 	   /* respect variable bounds */
1391 	   for (rowid = 0; rowid < nrows; ++rowid)
1392 	   {
1393 	      origrowid = getArrayEntryOrIndex(roworder, rowid);
1394 	      for (colid = 0; colid < ncols; ++colid)
1395 	      {
1396 	         origcolid = getArrayEntryOrIndex(colorder, colid);
1397 	         idx = rowid * ncols + colid;
1398 	         origidx = origrowid * ncols + origcolid;
1399 	         var = orbidata->vars[origidx];
1400 	         assert( SCIPGE(scip, matrix[idx], SCIPvarGetLbLocal(var)) );
1401 	         assert( SCIPLE(scip, matrix[idx], SCIPvarGetUbLocal(var)) );
1402 	      }
1403 	   }
1404 	
1405 	   /* is orbitope */
1406 	   for (colid = 0; colid < ncols - 1; ++colid)
1407 	   {
1408 	      /* compare column colid with colid + 1 */
1409 	      for (rowid = 0; rowid < nrows; ++rowid)
1410 	      {
1411 	         /* entry is >= entry to the right */
1412 	         assert( SCIPGE(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1413 	
1414 	         if ( SCIPGT(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) )
1415 	         {
1416 	            /* critical row */
1417 	            break;
1418 	         }
1419 	         else
1420 	         {
1421 	            /* check for infinitesimal values
1422 	             * If infinitesimals are added (lexminface case), then if the left column has a +epsilon,
1423 	             * it does not matter whether the right column has +epsilon or not, then the left column is >,
1424 	             * due to the axioms x + epsilon > x + epsilon and x + epsilon > x.
1425 	             * Analogously, x > x - epsilon and x - epsilon > x - epsilon.
1426 	             */
1427 	            assert( SCIPEQ(scip, matrix[rowid * ncols + colid], matrix[rowid * ncols + colid + 1]) );
1428 	            if ( addinfinitesimals
1429 	               ? (infinitesimal[colid] == rowid) /* left has +epsilon term */
1430 	               : (infinitesimal[colid + 1] == rowid) /* right has -epsilon term */
1431 	            )
1432 	            {
1433 	               /* critical row */
1434 	               break;
1435 	            }
1436 	         }
1437 	      }
1438 	   }
1439 	}
1440 	#endif
1441 	
1442 	#ifndef NDEBUG
1443 	/** to test if arrays are the same, generates some hash for an array of integers */
1444 	static
1445 	int debugGetArrayHash(
1446 	   int*                  array,              /** array */
1447 	   int                   len                 /** array length */
1448 	   )
1449 	{
1450 	   int i;
1451 	   unsigned int hash = 0;
1452 	
1453 	   assert( array != NULL );
1454 	   assert( len >= 0 );
1455 	
1456 	   for (i = 0; i < len; i++)
1457 	   {
1458 	      hash ^= (unsigned int) (array[i]);
1459 	      hash = (hash << 1) ^ (hash >> 1);
1460 	   }
1461 	
1462 	   return (int) hash;
1463 	}
1464 	#endif
1465 	
1466 	#ifdef SCIP_MORE_DEBUG
1467 	/** prints nrows × ncols matrix of floats with 2 decimals */
1468 	static
1469 	void debugPrintMatrix(
1470 	   SCIP_Real*            matrix,             /** matrix, encoded as array enumerating the elements row-wise */
1471 	   int                   nrows,              /** number of rows */
1472 	   int                   ncols               /** number of rows */
1473 	   )
1474 	{
1475 	   int row;
1476 	   int col;
1477 	
1478 	   assert( matrix != NULL );
1479 	   assert( nrows >= 0 );
1480 	   assert( ncols >= 0 );
1481 	
1482 	   for (row = 0; row < nrows; ++row)
1483 	   {
1484 	      SCIPdebugPrintf("[");
1485 	      for (col = 0; col < ncols; ++col)
1486 	      {
1487 	         SCIPdebugPrintf(" %+10.2f", matrix[row * ncols + col]);
1488 	      }
1489 	      SCIPdebugPrintf(" ]\n");
1490 	   }
1491 	}
1492 	#endif
1493 	
1494 	
1495 	/** gets the column order at the node */
1496 	static
1497 	SCIP_RETCODE propagateStaticOrbitope(
1498 	   SCIP*                 scip,               /**< SCIP data structure */
1499 	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
1500 	   int*                  roworder,           /**< array with the row order (or NULL if identity function is used) */
1501 	   int                   nselrows,           /**< number of selected rows */
1502 	   int*                  colorder,           /**< array with the column order (or NULL if identity function is used) */
1503 	   SCIP_Bool*            infeasible,         /**< pointer to store whether the problem is infeasible */
1504 	   int*                  nfixedvars          /**< pointer to counter of number of variable domain reductions */
1505 	   )
1506 	{
1507 	   /* @todo also make "nselcols" to allow for colorders smaller than orbidata->ncols */
1508 	   SCIP_Real* lexminface = NULL;
1509 	   int* lexminepsrow = NULL;
1510 	   SCIP_Real* lexmaxface = NULL;
1511 	   int* lexmaxepsrow = NULL;
1512 	   int nelem;
1513 	   int rowid;
1514 	   int colid;
1515 	   int ncols;
1516 	   int origrowid;
1517 	   int origcolid;
1518 	   int origidx;
1519 	   int i;
1520 	   int lastunfixed;
1521 	   SCIP_Real lb;
1522 	   SCIP_Real ub;
1523 	   SCIP_Bool iseq;
1524 	   SCIP_Bool success;
1525 	   SCIP_VAR* var;
1526 	   SCIP_VAR* othervar;
1527 	
1528 	   assert( scip != NULL );
1529 	   assert( orbidata != NULL );
1530 	   assert( orbidata->vars != NULL );
1531 	   assert( nselrows >= 0 );
1532 	   assert( infeasible != NULL );
1533 	   assert( nfixedvars != NULL );
1534 	
1535 	   *infeasible = FALSE;
1536 	
1537 	   assert( orbidata->nrows > 0 );
1538 	   assert( orbidata->nrows >= nselrows );
1539 	   ncols = orbidata->ncols;
1540 	   assert( ncols > 1 );
1541 	
1542 	   /* nothing to propagate without any rows */
1543 	   if ( nselrows <= 0 )
1544 	      return SCIP_OKAY;
1545 	
1546 	#ifdef SCIP_MORE_DEBUG
1547 	   /* print matrix for debugging purposes */
1548 	   {
1549 	      int k;
1550 	      int r;
1551 	      SCIP_VAR* thisvar;
1552 	      SCIPdebugMessage("Start propagating static orbitope: \n");
1553 	      SCIPdebugPrintf(">");
1554 	      for (k = 0; k < ncols; ++k)
1555 	      {
1556 	         SCIPdebugPrintf("%12d ", colorder[k]);
1557 	      }
1558 	      SCIPdebugPrintf("< (IDs)\n");
1559 	
1560 	      for (r = 0; r < nselrows; ++r)
1561 	      {
1562 	         SCIPdebugPrintf("[");
1563 	         for (k = 0; k < ncols; ++k)
1564 	         {
1565 	            thisvar = orbidata->vars[roworder[r] * ncols + colorder[k]];
1566 	            SCIPdebugPrintf("%4s %+1.2f,%+1.2f ", SCIPvarGetName(thisvar),
1567 	               SCIPvarGetLbLocal(thisvar), SCIPvarGetUbLocal(thisvar));
1568 	         }
1569 	         SCIPdebugPrintf("] (row %d)\n", roworder[r]);
1570 	      }
1571 	   }
1572 	#endif
1573 	
1574 	   nelem = nselrows * ncols;
1575 	
1576 	   /* compute lexmin face */
1577 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexminface, nelem) );
1578 	
1579 	   /* array to store for each column at which row we add an infinitesimal value, initially at none (-1) */
1580 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexminepsrow, ncols) );
1581 	   for (colid = 0; colid < ncols; ++colid)
1582 	      lexminepsrow[colid] = -1;
1583 	
1584 	   /* last column takes the minimally possible values. */
1585 	   colid = ncols - 1;
1586 	   origcolid = getArrayEntryOrIndex(colorder, colid);
1587 	   for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1588 	   {
1589 	      origrowid = getArrayEntryOrIndex(roworder, rowid);
1590 	      origidx = origrowid * ncols + origcolid;
1591 	      var = orbidata->vars[origidx];
1592 	
1593 	      assert( i == rowid * ncols + colid );
1594 	      assert( var != NULL );
1595 	
1596 	      lexminface[i] = SCIPvarGetLbLocal(var);
1597 	   }
1598 	   /* all previous columns: One-column replacement algorithm */
1599 	   for (colid = ncols - 2; colid >= 0; --colid)
1600 	   {
1601 	      /* "rowid" of the last unfixed entry whose domain allows for larger values than the current chosen.
1602 	       * If there is none, -1. */
1603 	      lastunfixed = -1;
1604 	      /* whether column "colid" is the same as column "colid + 1" up (but excluding) to "rowid" */
1605 	      iseq = TRUE;
1606 	
1607 	      origcolid = getArrayEntryOrIndex(colorder, colid);
1608 	      for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1609 	      {
1610 	         origrowid = getArrayEntryOrIndex(roworder, rowid);
1611 	         origidx = origrowid * ncols + origcolid;
1612 	         assert( i == rowid * ncols + colid );
1613 	
1614 	         /* the entry one to the right is not the first column */
1615 	         assert( (i + 1) % ncols > 0 );
1616 	
1617 	         var = orbidata->vars[origidx];
1618 	         assert( var != NULL );
1619 	
1620 	         if ( iseq )
1621 	         {
1622 	            /* equality holds up to this row
1623 	             * Compare to the entry value on the column immediately right.
1624 	             * The value we choose on the left must be at least this.
1625 	             * 2 Options:
1626 	             * Option 1: The upper bound is smaller. Then we're in an infeasible situation. Resolve as described below.
1627 	             * Option 2: The upper bound is greater or equal.
1628 	             */
1629 	            ub = SCIPvarGetUbLocal(var);
1630 	
1631 	            /* compare to the value in the column right of it */
1632 	            if ( SCIPLT(scip, ub, lexminface[i + 1]) ||
1633 	               ( lexminepsrow[colid + 1] == rowid && SCIPEQ(scip, ub, lexminface[i + 1]) ) )
1634 	            {
1635 	               /* value of this column can only be strictly smaller than the value in the column to its right
1636 	                * This may not be possible.
1637 	                * Try to repair: Go back to the last row with "room" left, and make the value minimally larger.
1638 	                */
1639 	               if ( lastunfixed >= 0 )
1640 	               {
1641 	                  /* repair: return to the last row with "room", and increase the lexmin-value at that row. */
1642 	                  assert( SCIPEQ(scip, lexminface[lastunfixed * ncols + colid],
1643 	                     lexminface[lastunfixed * ncols + colid + 1]) );
1644 	                  othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1645 	                  switch (SCIPvarGetType(othervar))
1646 	                  {
1647 	                  case SCIP_VARTYPE_BINARY:
1648 	                  case SCIP_VARTYPE_IMPLINT:
1649 	                  case SCIP_VARTYPE_INTEGER:
1650 	                     /* discrete type with unit steps: Add one to the bound. */
1651 	                     /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1652 	                     assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) );
1653 	                     lexminface[lastunfixed * ncols + colid] += 1.0;
1654 	                     assert( SCIPisIntegral(scip, lexminface[lastunfixed * ncols + colid]) );
1655 	                     assert( SCIPLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1656 	                     break;
1657 	                  case SCIP_VARTYPE_CONTINUOUS:
1658 	                     /* continuous type, so add an infinitesimal value to the bound */
1659 	                     assert( SCIPLE(scip, lexminface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1660 	                     assert( lexminepsrow[colid] == -1 );
1661 	                     lexminepsrow[colid] = lastunfixed;
1662 	                     break;
1663 	                  default:
1664 	                     return SCIP_ERROR;
1665 	                  }
1666 	                  /* now row "lastunfixed" is greater. Restart from here. */
1667 	                  iseq = FALSE;
1668 	                  rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1669 	                  i = rowid * ncols + colid;
1670 	                  continue;
1671 	               }
1672 	               else
1673 	               {
1674 	                  /* cannot repair. It is infeasible. */
1675 	                  *infeasible = TRUE;
1676 	                  SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), min\n", colid, origcolid);
1677 	                  goto FREE;
1678 	               }
1679 	            }
1680 	            else
1681 	            {
1682 	               assert( SCIPGE(scip, ub, lexminface[i + 1]) );
1683 	               lb = SCIPvarGetLbLocal(var);
1684 	               assert( SCIPLE(scip, lb, ub) );
1685 	               lexminface[i] = MAX(lexminface[i + 1], lb);
1686 	               assert( SCIPGE(scip, lexminface[i], lexminface[i + 1]) );
1687 	
1688 	               /* are we still equal? */
1689 	               if ( SCIPGT(scip, lexminface[i], lexminface[i + 1]) )
1690 	                  iseq = FALSE;
1691 	               else if ( lexminepsrow[colid + 1] == rowid )
1692 	               {
1693 	                  assert( SCIPEQ(scip, lexminface[i], lexminface[i + 1]) );
1694 	                  assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1695 	                     == SCIP_VARTYPE_CONTINUOUS );
1696 	                  assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS );
1697 	                  /* right column (colid+1) has value x + epsilon, left column (colid) has value x, now
1698 	                   * must also become  x + epsilon in order to be larger or equal
1699 	                   * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1700 	                   */
1701 	                  iseq = FALSE;
1702 	                  assert( lexminepsrow[colid] == -1 );
1703 	                  lexminepsrow[colid] = rowid;
1704 	               }
1705 	
1706 	               /* is there room left to increase this variable further? */
1707 	               switch (SCIPvarGetType(var))
1708 	               {
1709 	               case SCIP_VARTYPE_BINARY:
1710 	               case SCIP_VARTYPE_IMPLINT:
1711 	               case SCIP_VARTYPE_INTEGER:
1712 	                  /* discrete type with unit steps: Add one to the bound. */
1713 	                  /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1714 	                  /* @todo in principle, this can be made more tight using the hole-lists... */
1715 	                  assert( SCIPisIntegral(scip, lexminface[i]) );
1716 	                  if ( SCIPLE(scip, lexminface[i] + 1.0, ub) )
1717 	                     lastunfixed = rowid;
1718 	                  break;
1719 	               case SCIP_VARTYPE_CONTINUOUS:
1720 	                  /* continuous type: if we can add an infinitesimal value to the current lexminface[i] value,
1721 	                   * mark row as 'lastunfixed'
1722 	                   */
1723 	                  if ( SCIPLT(scip, lexminface[i], ub) )
1724 	                     lastunfixed = rowid;
1725 	                  break;
1726 	               default:
1727 	                  return SCIP_ERROR;
1728 	               }
1729 	            }
1730 	         }
1731 	         else
1732 	         {
1733 	            /* there had been a row before which breaks the equality-condition, choose minimally possible value */
1734 	            lexminface[i] = SCIPvarGetLbLocal(var);
1735 	         }
1736 	      }
1737 	   }
1738 	
1739 	#ifndef NDEBUG
1740 	   /* sanity checks */
1741 	   assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexminface, nselrows, ncols, lexminepsrow, TRUE);
1742 	#endif
1743 	
1744 	   /* compute lexmax face */
1745 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxface, nelem) );
1746 	
1747 	   /* array to store for each column at which row we subtract an infinitesimal value, initially at none (-1) */
1748 	   SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxepsrow, ncols) );
1749 	   for (colid = 0; colid < ncols; ++colid)
1750 	      lexmaxepsrow[colid] = -1;
1751 	
1752 	   /* first column, fill all unfixed entries with maximally possible values */
1753 	   colid = 0;
1754 	   origcolid = getArrayEntryOrIndex(colorder, colid);
1755 	   for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1756 	   {
1757 	      origrowid = getArrayEntryOrIndex(roworder, rowid);
1758 	      origidx = origrowid * ncols + origcolid;
1759 	      var = orbidata->vars[origidx];
1760 	
1761 	      assert( i == rowid * ncols + colid );
1762 	      assert( var != NULL );
1763 	
1764 	      lexmaxface[i] = SCIPvarGetUbLocal(var);
1765 	   }
1766 	   /* all next columns: One-column replacement algorithm */
1767 	   for (colid = 1; colid < ncols; ++colid)
1768 	   {
1769 	      /* "rowid" of the last unfixed entry whose domain allows for smaller values than the current chosen.
1770 	       * If there is none, -1. */
1771 	      lastunfixed = -1;
1772 	      /* whether column "colid" is the same as column "colid - 1" up (but excluding) to "rowid" */
1773 	      iseq = TRUE;
1774 	
1775 	      origcolid = getArrayEntryOrIndex(colorder, colid);
1776 	      for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1777 	      {
1778 	         origrowid = getArrayEntryOrIndex(roworder, rowid);
1779 	         origidx = origrowid * ncols + origcolid;
1780 	         assert( i == rowid * ncols + colid );
1781 	
1782 	         /* the entry one to the left is not the last column, i.e., this column cannot be the first column */
1783 	         assert( i % ncols > 0 );
1784 	
1785 	         var = orbidata->vars[origidx];
1786 	         assert( var != NULL );
1787 	
1788 	         if ( iseq )
1789 	         {
1790 	            /* equality holds up to this row
1791 	             * Compare to the entry value on the column immediately left.
1792 	             * The value we choose on the right must be at most this.
1793 	             * 2 Options:
1794 	             * Option 1: The lower bound is larger. Then we're in an infeasible situation. Resolve as described below.
1795 	             * Option 2: The lower bound is smaller or equal.
1796 	             */
1797 	            lb = SCIPvarGetLbLocal(var);
1798 	
1799 	            /* compare to the value in the column left of it */
1800 	            if ( SCIPGT(scip, lb, lexmaxface[i - 1]) ||
1801 	               ( lexmaxepsrow[colid - 1] == rowid && SCIPEQ(scip, lb, lexmaxface[i - 1]) ) )
1802 	            {
1803 	               /* value of this column can only be strictly larger than the value in the column to its left
1804 	                * This may not be possible.
1805 	                * Try to repair: Go back to the last row with "room" left, and make the value minimally smaller.
1806 	                */
1807 	               if ( lastunfixed >= 0 )
1808 	               {
1809 	                  /* repair: return to the last row with "room", and decrease the lexmax-value at that row. */
1810 	                  assert( SCIPEQ(scip, lexmaxface[lastunfixed * ncols + colid],
1811 	                     lexmaxface[lastunfixed * ncols + colid - 1]) );
1812 	                  othervar = orbidata->vars[getArrayEntryOrIndex(roworder, lastunfixed) * ncols + origcolid];
1813 	                  switch (SCIPvarGetType(othervar))
1814 	                  {
1815 	                  case SCIP_VARTYPE_BINARY:
1816 	                  case SCIP_VARTYPE_IMPLINT:
1817 	                  case SCIP_VARTYPE_INTEGER:
1818 	                     /* discrete type with unit steps: Remove one from the lexmax-value. */
1819 	                     /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1820 	                     assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) );
1821 	                     lexmaxface[lastunfixed * ncols + colid] -= 1.0;
1822 	                     assert( SCIPisIntegral(scip, lexmaxface[lastunfixed * ncols + colid]) );
1823 	                     assert( SCIPGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1824 	                     assert( SCIPLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1825 	                     break;
1826 	                  case SCIP_VARTYPE_CONTINUOUS:
1827 	                     /* continuous type, so subtract an infinitesimal value to the bound */
1828 	                     assert( SCIPGE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetLbLocal(othervar)) );
1829 	                     assert( SCIPLE(scip, lexmaxface[lastunfixed * ncols + colid], SCIPvarGetUbLocal(othervar)) );
1830 	                     assert( lexmaxepsrow[colid] == -1 );
1831 	                     lexmaxepsrow[colid] = lastunfixed;
1832 	                     break;
1833 	                  default:
1834 	                     return SCIP_ERROR;
1835 	                  }
1836 	                  /* now row "lastunfixed" is greater. Restart from here. */
1837 	                  iseq = FALSE;
1838 	                  rowid = lastunfixed; /* the next iteration considers "lastunfixed + 1" */
1839 	                  i = rowid * ncols + colid;
1840 	                  continue;
1841 	               }
1842 	               else
1843 	               {
1844 	                  /* cannot repair. It is infeasible. */
1845 	                  *infeasible = TRUE;
1846 	                  SCIPdebugMessage("Cannot repair infeasibility for column %d (original: %d), max\n", colid, origcolid);
1847 	                  goto FREE;
1848 	               }
1849 	            }
1850 	            else
1851 	            {
1852 	               assert( SCIPLE(scip, lb, lexmaxface[i - 1]) );
1853 	               ub = SCIPvarGetUbLocal(var);
1854 	               assert( SCIPLE(scip, lb, ub) );
1855 	               lexmaxface[i] = MIN(lexmaxface[i - 1], ub);
1856 	               assert( SCIPGE(scip, lexmaxface[i - 1], lexmaxface[i]) );
1857 	
1858 	               /* are we still equal? */
1859 	               if ( SCIPGT(scip, lexmaxface[i - 1], lexmaxface[i]) )
1860 	                  iseq = FALSE;
1861 	               else if ( lexmaxepsrow[colid - 1] == rowid )
1862 	               {
1863 	                  assert( SCIPEQ(scip, lexmaxface[i - 1], lexmaxface[i]) );
1864 	                  assert( SCIPvarGetType(orbidata->vars[getArrayEntryOrIndex(roworder, rowid) * ncols + origcolid])
1865 	                     == SCIP_VARTYPE_CONTINUOUS );
1866 	                  assert( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS );
1867 	                  /* left column (colid-1) has value x - epsilon, right column (colid) has value x, now
1868 	                   * must also become  x - epsilon in order to be larger or equal
1869 	                   * by axioms, we can squeeze infinitesimals between one other; epsilon > epsilon.
1870 	                   */
1871 	                  iseq = FALSE;
1872 	                  assert( lexmaxepsrow[colid] == -1 );
1873 	                  lexmaxepsrow[colid] = rowid;
1874 	               }
1875 	
1876 	               /* is there room left to decrease this variable further? */
1877 	               switch (SCIPvarGetType(var))
1878 	               {
1879 	               case SCIP_VARTYPE_BINARY:
1880 	               case SCIP_VARTYPE_IMPLINT:
1881 	               case SCIP_VARTYPE_INTEGER:
1882 	                  /* discrete type with unit steps: Remove one from the lexmax-value. */
1883 	                  /* @todo @question Are variable bounds for SCIP_VARTYPE_IMPLINT always integral? */
1884 	                  /* @todo in principle, this can be made more tight using the hole-lists... */
1885 	                  assert( SCIPisIntegral(scip, lexmaxface[i]) );
1886 	                  if ( SCIPGE(scip, lexmaxface[i] - 1.0, lb) )
1887 	                     lastunfixed = rowid;
1888 	                  break;
1889 	               case SCIP_VARTYPE_CONTINUOUS:
1890 	                  /* continuous type: if we can subtract an infinitesimal value to the current lexmaxface[i] value,
1891 	                   * mark row as 'lastunfixed'
1892 	                   */
1893 	                  if ( SCIPGT(scip, lexmaxface[i], lb) )
1894 	                     lastunfixed = rowid;
1895 	                  break;
1896 	               default:
1897 	                  return SCIP_ERROR;
1898 	               }
1899 	            }
1900 	         }
1901 	         else
1902 	         {
1903 	            /* there had been a row before which breaks the equality-condition, choose maximally possible value */
1904 	            lexmaxface[i] = SCIPvarGetUbLocal(var);
1905 	         }
1906 	      }
1907 	   }
1908 	
1909 	#ifndef NDEBUG
1910 	   /* sanity checks */
1911 	   assertIsOrbitopeMatrix(scip, orbidata, roworder, colorder, lexmaxface, nselrows, ncols, lexmaxepsrow, FALSE);
1912 	#endif
1913 	
1914 	#ifdef SCIP_MORE_DEBUG
1915 	   /* show lexmin and lexmax face */
1916 	   SCIPdebugMessage("Lex min face\n");
1917 	   debugPrintMatrix(lexminface, nselrows, ncols);
1918 	   SCIPdebugMessage("Lex max face\n");
1919 	   debugPrintMatrix(lexmaxface, nselrows, ncols);
1920 	#endif
1921 	
1922 	   /* compare the two column-wise and apply domain reductions */
1923 	   for (colid = 0; colid < ncols; ++colid)
1924 	   {
1925 	      for (rowid = 0, i = colid; rowid < nselrows; ++rowid, i += ncols)
1926 	      {
1927 	         assert( i == rowid * ncols + colid );
1928 	
1929 	         /* get var */
1930 	         origrowid = getArrayEntryOrIndex(roworder, rowid);
1931 	         origcolid = getArrayEntryOrIndex(colorder, colid);
1932 	         origidx = origrowid * ncols + origcolid;
1933 	         var = orbidata->vars[origidx];
1934 	
1935 	         if ( SCIPEQ(scip, lexminface[i], lexmaxface[i]) )
1936 	         {
1937 	            /* tighten LB and UB to same value (i.e. fixing) */
1938 	            SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1939 	            if ( success )
1940 	            {
1941 	               SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1942 	               *nfixedvars += 1;
1943 	            }
1944 	            else
1945 	            {
1946 	               SCIPdebugMessage("Fixing variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1947 	                 lexminface[i]);
1948 	            }
1949 	            if ( *infeasible )
1950 	            {
1951 	               SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1952 	                  var->name, rowid, colid, lexminface[i]);
1953 	               goto FREE;
1954 	            }
1955 	
1956 	            SCIP_CALL( SCIPtightenVarUb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1957 	            if ( success )
1958 	            {
1959 	               SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid, lexminface[i]);
1960 	               *nfixedvars += 1;
1961 	            }
1962 	            else
1963 	            {
1964 	               SCIPdebugMessage("Fixing variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name, rowid, colid,
1965 	                 lexminface[i]);
1966 	            }
1967 	            if ( *infeasible )
1968 	            {
1969 	               SCIPdebugMessage("Detected infeasibility fixing variable %12s (%3d,%3d) to %5.2f\n",
1970 	                  var->name, rowid, colid, lexminface[i]);
1971 	               goto FREE;
1972 	            }
1973 	         }
1974 	         else
1975 	         {
1976 	            /* This is the row index where the min- and max-face have a different value for this column entry.
1977 	             * Update the lower bound and upper bound */
1978 	
1979 	            /* lower bound, based on lexminface */
1980 	            SCIP_CALL( SCIPtightenVarLb(scip, var, lexminface[i], FALSE, infeasible, &success) );
1981 	            if ( success )
1982 	            {
1983 	               SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
1984 	                  lexminface[i]);
1985 	               *nfixedvars += 1;
1986 	            }
1987 	            else
1988 	            {
1989 	               SCIPdebugMessage("Restricting variable LB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
1990 	                 rowid, colid, lexminface[i]);
1991 	            }
1992 	            if ( *infeasible )
1993 	            {
1994 	               SCIPdebugMessage("Detected infeasibility restricting variable LB %12s (%3d,%3d) to %5.2f\n",
1995 	                  var->name, rowid, colid, lexminface[i]);
1996 	               goto FREE;
1997 	            }
1998 	
1999 	            /* upper bound, based on lexmaxface */
2000 	            SCIP_CALL( SCIPtightenVarUb(scip, var, lexmaxface[i], FALSE, infeasible, &success) );
2001 	            if ( success )
2002 	            {
2003 	               SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f\n", var->name, rowid, colid,
2004 	                  lexmaxface[i]);
2005 	               *nfixedvars += 1;
2006 	            }
2007 	            else
2008 	            {
2009 	               SCIPdebugMessage("Restricting variable UB %12s (%3d,%3d) to %5.2f (no success)\n", var->name,
2010 	                 rowid, colid, lexmaxface[i]);
2011 	            }
2012 	            if ( *infeasible )
2013 	            {
2014 	               SCIPdebugMessage("Detected infeasibility restricting variable UB %12s (%3d,%3d) to %5.2f\n",
2015 	                  var->name, rowid, colid, lexmaxface[i]);
2016 	               goto FREE;
2017 	            }
2018 	            break;
2019 	         }
2020 	      }
2021 	   }
2022 	
2023 	FREE:
2024 	   SCIPfreeBufferArrayNull(scip, &lexmaxepsrow);
2025 	   SCIPfreeBufferArrayNull(scip, &lexmaxface);
2026 	   SCIPfreeBufferArrayNull(scip, &lexminepsrow);
2027 	   SCIPfreeBufferArrayNull(scip, &lexminface);
2028 	
2029 	   return SCIP_OKAY;
2030 	}
2031 	
2032 	
2033 	/** propagation method for a single orbitope matrix */
2034 	static
2035 	SCIP_RETCODE propagateOrbitope(
2036 	   SCIP*                 scip,               /**< SCIP data structure */
2037 	   ORBITOPEDATA*         orbidata,           /**< orbitope data */
2038 	   SCIP_Bool*            infeasible,         /**< pointer to store whether the problem is infeasible */
2039 	   int*                  nfixedvars          /**< pointer to store the number of found domain reductions */
2040 	   )
2041 	{
2042 	   SCIP_NODE* focusnode;
2043 	   int* roworder;
2044 	   int nselrows;
2045 	   int* colorder;
2046 	   int* colorderinv;
2047 	
2048 	   assert( scip != NULL );
2049 	   assert( orbidata != NULL );
2050 	   assert( infeasible != NULL );
2051 	   assert( nfixedvars != NULL );
2052 	
2053 	   *nfixedvars = 0;
2054 	   *infeasible = FALSE;
2055 	
2056 	   assert( orbidata->ncols > 0 );
2057 	   assert( orbidata->nrows > 0 );
2058 	
2059 	   focusnode = SCIPgetFocusNode(scip);
2060 	   assert( focusnode != NULL );
2061 	
2062 	   /* get row order */
2063 	   SCIP_CALL( getRowOrder(scip, orbidata, focusnode, &roworder, &nselrows) );
2064 	   assert( nselrows >= 0 );
2065 	   assert( nselrows <= orbidata->nrows );
2066 	   if ( nselrows == 0 )
2067 	      goto FREEROWS;
2068 	
2069 	   /* get column order */
2070 	   SCIP_CALL( getColumnOrder(scip, orbidata, focusnode, roworder, nselrows, &colorder, &colorderinv) );
2071 	
2072 	#ifndef NDEBUG
2073 	   /* DEBUG: if propagation is repeated in the same node, the same column order and row order is needed */
2074 	   /* @todo: performance: move roworder and colorder to orbidata, then re-use */
2075 	   {
2076 	      int colhash = (colorder == NULL) ? 1 : debugGetArrayHash(colorder, orbidata->ncols);
2077 	      int rowhash = (roworder == NULL) ? 0 : debugGetArrayHash(roworder, nselrows);
2078 	      int hash = colhash ^ rowhash;
2079 	
2080 	#ifdef SCIP_DEBUG
2081 	      SCIPdebugPrintf("Col hash %32d; Row hash %32d; Hash %32d\n", colhash, rowhash, hash);
2082 	      {
2083 	         SCIP_NODE* tmpnode;
2084 	         tmpnode = SCIPgetFocusNode(scip);
2085 	         while ( tmpnode != NULL )
2086 	         {
2087 	            int nbranchings, nconsprop, nprop;
2088 	            SCIPnodeGetDomchg(tmpnode);
2089 	            SCIPnodeGetNDomchg(tmpnode, &nbranchings, &nconsprop, &nprop);
2090 	            SCIPdebugPrintf("  node %lld: (%d, %d, %d) \n", tmpnode->number, nbranchings, nconsprop, nprop);
2091 	            tmpnode = SCIPnodeGetParent(tmpnode);
2092 	         }
2093 	      }
2094 	#endif
2095 	
2096 	      assert( SCIPgetCurrentNode(scip) == SCIPgetFocusNode(scip) );  /* no probing */
2097 	      if ( orbidata->lastnodenumber == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
2098 	      {
2099 	         assert( orbidata->dbghash == hash );
2100 	      }
2101 	      orbidata->dbghash = hash;
2102 	   }
2103 	   orbidata->lastnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
2104 	#endif
2105 	
2106 	   SCIP_CALL( propagateStaticOrbitope(scip, orbidata, roworder, nselrows, colorder, infeasible, nfixedvars) );
2107 	
2108 	   freeColumnOrder(scip, orbidata, &colorder, &colorderinv);
2109 	FREEROWS:
2110 	   freeRowOrder(scip, orbidata, &roworder);
2111 	
2112 	#ifdef SCIP_MORE_DEBUG
2113 	   SCIPdebugPrintf("\n\n");
2114 	#endif
2115 	
2116 	   return SCIP_OKAY;
2117 	}
2118 	
2119 	
2120 	/*
2121 	 * Interface methods
2122 	 */
2123 	
2124 	
2125 	/** gets the number of reductions */
2126 	SCIP_RETCODE SCIPorbitopalReductionGetStatistics(
2127 	   SCIP*                 scip,               /**< SCIP data structure */
2128 	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< orbitopal reduction data structure */
2129 	   int*                  nred,               /**< total number of reductions applied */
2130 	   int*                  ncutoff             /**< total number of cutoffs applied */
2131 	   )
2132 	{
2133 	   assert( scip != NULL );
2134 	   assert( orbireddata != NULL );
2135 	   assert( nred != NULL );
2136 	
2137 	   *nred = orbireddata->nred;
2138 	   *ncutoff = orbireddata->ncutoff;
2139 	
2140 	   return SCIP_OKAY;
2141 	}
2142 	
2143 	
2144 	/** prints orbitopal reduction data */
2145 	SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(
2146 	   SCIP*                 scip,               /**< SCIP data structure */
2147 	   SCIP_ORBITOPALREDDATA* orbireddata        /**< orbitopal reduction data structure */
2148 	   )
2149 	{
2150 	   int i;
2151 	
2152 	   assert( scip != NULL );
2153 	   assert( orbireddata != NULL );
2154 	
2155 	   if ( orbireddata->norbitopes == 0 )
2156 	   {
2157 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "   orbitopal reduction:       no components\n");
2158 	      return SCIP_OKAY;
2159 	   }
2160 	
2161 	   SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
2162 	      "   orbitopal reduction:     %4d components: ", orbireddata->norbitopes);
2163 	   for (i = 0; i < orbireddata->norbitopes; ++i)
2164 	   {
2165 	      if ( i > 0 )
2166 	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", ");
2167 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
2168 	         "%dx%d", orbireddata->orbitopes[i]->nrows, orbireddata->orbitopes[i]->ncols);
2169 	   }
2170 	   SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "\n");
2171 	
2172 	   return SCIP_OKAY;
2173 	}
2174 	
2175 	
2176 	/** propagates orbitopal reduction */
2177 	SCIP_RETCODE SCIPorbitopalReductionPropagate(
2178 	   SCIP*                 scip,               /**< SCIP data structure */
2179 	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< orbitopal reduction data structure */
2180 	   SCIP_Bool*            infeasible,         /**< pointer to store whether infeasibility is found */
2181 	   int*                  nred,               /**< pointer to store the number of domain reductions */
2182 	   SCIP_Bool*            didrun              /**< a global pointer maintaining if any symmetry propagator has run
2183 	                                              *   only set this to TRUE when a reduction is found, never set to FALSE */
2184 	   )
2185 	{
2186 	   ORBITOPEDATA* orbidata;
2187 	   int c;
2188 	   int thisfixedvars;
2189 	
2190 	   assert( scip != NULL );
2191 	   assert( orbireddata != NULL );
2192 	   assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2193 	   assert( infeasible != NULL );
2194 	   assert( nred != NULL );
2195 	
2196 	   *infeasible = FALSE;
2197 	   *nred = 0;
2198 	
2199 	   /* @todo Can the following be removed? */
2200 	   /* @todo shouldn't this be SCIPallowWeakDualReds, since we do not regard the objective */
2201 	   if ( ! SCIPallowStrongDualReds(scip) )
2202 	      return SCIP_OKAY;
2203 	
2204 	   /* cannot do anything during probing
2205 	    * @todo can find deductions for the probing node, maybe?
2206 	    */
2207 	   if ( SCIPinProbing(scip) )
2208 	      return SCIP_OKAY;
2209 	
2210 	   /* propagate all orbitopes */
2211 	   for (c = 0; c < orbireddata->norbitopes; ++c)
2212 	   {
2213 	      orbidata = orbireddata->orbitopes[c];
2214 	      assert( orbidata != NULL );
2215 	
2216 	      SCIP_CALL( propagateOrbitope(scip, orbidata, infeasible, &thisfixedvars) );
2217 	      SCIPdebugMessage("Found %d reductions during orbitopal reduction for orbitope %d\n", thisfixedvars, c);
2218 	      *nred += thisfixedvars;
2219 	
2220 	      /* a symmetry propagator has ran, so set didrun to TRUE */
2221 	      *didrun = TRUE;
2222 	
2223 	      /* stop if we find infeasibility in one of the methods */
2224 	      if ( *infeasible )
2225 	      {
2226 	         SCIPdebugMessage("Detected infeasibility during orbitopal reduction for orbitope %d\n", c);
2227 	         break;
2228 	      }
2229 	   }
2230 	
2231 	   orbireddata->nred += *nred;
2232 	   if ( *infeasible )
2233 	      ++orbireddata->ncutoff;
2234 	
2235 	   return SCIP_OKAY;
2236 	}
2237 	
2238 	/** adds orbitopal component to orbitopal symmetry handler */
2239 	SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(
2240 	   SCIP*                 scip,               /**< SCIP data structure */
2241 	   SCIP_ORBITOPALREDDATA* orbireddata,       /**< orbitopal reduction data structure */
2242 	   SCIP_ROWORDERING      rowordering,        /**< specifies how rows of orbitope are ordered */
2243 	   SCIP_COLUMNORDERING   colordering,        /**< specifies how columnss of orbitope are ordered */
2244 	   SCIP_VAR**            vars,               /**< matrix of variables on which the symmetry acts */
2245 	   int                   nrows,              /**< number of rows */
2246 	   int                   ncols,              /**< number of columns */
2247 	   SCIP_Bool*            success             /**< to store whether the component is successfully added */
2248 	   )
2249 	{
2250 	   assert( scip != NULL );
2251 	   assert( orbireddata != NULL );
2252 	   assert( vars != NULL );
2253 	   assert( nrows > 0 );
2254 	   assert( ncols > 0 );
2255 	
2256 	   /* dynamic symmetry reductions cannot be performed on original problem */
2257 	   assert( SCIPisTransformed(scip) );
2258 	
2259 	   /* if this is the first time adding an orbitope, check if the nonlinear conshlr exists */
2260 	   if ( !orbireddata->conshdlr_nonlinear_checked )
2261 	   {
2262 	      orbireddata->conshdlr_nonlinear = SCIPfindConshdlr(scip, "nonlinear");
2263 	      orbireddata->conshdlr_nonlinear_checked = TRUE;
2264 	   }
2265 	
2266 	   /* create orbitope data */
2267 	   SCIP_CALL( addOrbitope(scip, orbireddata, rowordering, colordering, vars, nrows, ncols, success) );
2268 	
2269 	   return SCIP_OKAY;
2270 	}
2271 	
2272 	
2273 	/** resets orbitopal reduction data structure (clears all orbitopes) */
2274 	SCIP_RETCODE SCIPorbitopalReductionReset(
2275 	   SCIP*                 scip,               /**< SCIP data structure */
2276 	   SCIP_ORBITOPALREDDATA* orbireddata        /**< pointer to orbitopal reduction structure to populate */
2277 	   )
2278 	{
2279 	   assert( scip != NULL );
2280 	   assert( orbireddata != NULL );
2281 	   assert( orbireddata->norbitopes >= 0 );
2282 	   assert( (orbireddata->norbitopes == 0) == (orbireddata->orbitopes == NULL) );
2283 	   assert( orbireddata->norbitopes <= orbireddata->maxnorbitopes );
2284 	   assert( orbireddata->eventhdlr != NULL );
2285 	
2286 	   /* free orbitopes that are added */
2287 	   while (orbireddata->norbitopes > 0)
2288 	   {
2289 	      SCIP_CALL( freeOrbitope(scip, orbireddata, &(orbireddata->orbitopes[--orbireddata->norbitopes])) );
2290 	   }
2291 	   assert( orbireddata->norbitopes == 0 );
2292 	   SCIPfreeBlockMemoryArrayNull(scip, &orbireddata->orbitopes, orbireddata->maxnorbitopes);
2293 	   orbireddata->orbitopes = NULL;
2294 	   orbireddata->maxnorbitopes = 0;
2295 	
2296 	   return SCIP_OKAY;
2297 	}
2298 	
2299 	
2300 	/** frees orbitopal reduction data */
2301 	SCIP_RETCODE SCIPorbitopalReductionFree(
2302 	   SCIP*                 scip,               /**< SCIP data structure */
2303 	   SCIP_ORBITOPALREDDATA** orbireddata       /**< pointer to orbitopal reduction structure to populate */
2304 	   )
2305 	{
2306 	   assert( scip != NULL );
2307 	   assert( orbireddata != NULL );
2308 	   assert( *orbireddata != NULL );
2309 	
2310 	   SCIP_CALL( SCIPorbitopalReductionReset(scip, *orbireddata) );
2311 	
2312 	   SCIPfreeBlockMemory(scip, orbireddata);
2313 	   return SCIP_OKAY;
2314 	}
2315 	
2316 	
2317 	/** initializes structures needed for orbitopal reduction
2318 	 *
2319 	 *  This is only done exactly once.
2320 	 */
2321 	SCIP_RETCODE SCIPincludeOrbitopalReduction(
2322 	   SCIP*                 scip,               /**< SCIP data structure */
2323 	   SCIP_ORBITOPALREDDATA** orbireddata       /**< pointer to orbitopal reduction structure to populate */
2324 	   )
2325 	{
2326 	   SCIP_EVENTHDLR* eventhdlr;
2327 	
2328 	   assert( scip != NULL );
2329 	   assert( orbireddata != NULL );
2330 	
2331 	   SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitopalReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
2332 	      FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2333 	
2334 	   /* create orbitope handler data */
2335 	   SCIP_CALL( SCIPallocBlockMemory(scip, orbireddata) );
2336 	
2337 	   /* default column ordering param */
2338 	   SCIP_CALL( SCIPaddIntParam(scip, "propagating/symmetry/" SYMHDLR_NAME "/columnordering",
2339 	         "The column ordering variant, respects enum SCIP_ColumnOrdering.",
2340 	         (int*) &(*orbireddata)->defaultcolumnordering, TRUE, DEFAULT_COLUMNORDERING, 0, 4,
2341 	         NULL, NULL) ); /*lint !e641*/
2342 	
2343 	   /* initialize event handler. */
2344 	   assert( SCIPfindEventhdlr(scip, EVENTHDLR_NAME) == NULL );
2345 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExec, NULL) );
2346 	   assert( eventhdlr != NULL );
2347 	   (*orbireddata)->eventhdlr = eventhdlr;
2348 	
2349 	   /* orbitopes array */
2350 	   (*orbireddata)->orbitopes = NULL;
2351 	   (*orbireddata)->norbitopes = 0;
2352 	   (*orbireddata)->maxnorbitopes = 0;
2353 	
2354 	   /* conshdlr nonlinear */
2355 	   (*orbireddata)->conshdlr_nonlinear = NULL;
2356 	   (*orbireddata)->conshdlr_nonlinear_checked = FALSE;
2357 	
2358 	   /* counter of total number of reductions and cutoffs */
2359 	   (*orbireddata)->nred = 0;
2360 	   (*orbireddata)->ncutoff = 0;
2361 	
2362 	   return SCIP_OKAY;
2363 	}
2364 	
2365 	
2366 	/** returns the default column ordering */
2367 	SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(
2368 	   SCIP_ORBITOPALREDDATA* orbireddata        /**< pointer to orbitopal reduction structure to populate */
2369 	   )
2370 	{
2371 	   assert( orbireddata != NULL );
2372 	
2373 	   return orbireddata->defaultcolumnordering;
2374 	}
2375