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