Scippy

SCIP

Solving Constraint Integer Programs

symmetry_graph.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 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_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"
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  */
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 */
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 */
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  {
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  */
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  {
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  */
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  {
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
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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
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 */
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
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
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
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
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
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
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
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
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
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) &&
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  */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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  */
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 */
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  */
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 
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  */
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 */
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 */
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 */
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 */
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 }
static SCIP_DECL_SORTINDCOMP(SYMsortVarnodesPermsym)
SCIP_RETCODE SCIPgetCoefSymData(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *parentexpr, SCIP_Real *coef, SCIP_Bool *success)
static int compareVarsFixed(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isfixed1, SCIP_Bool isfixed2)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
static int compareVarsFixedSignedPerm(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isfixed1, SCIP_Bool isfixed2, SCIP_Bool isneg1, SCIP_Bool isneg2, SCIP_Real infinity)
int * edgecolors
SCIP_RETCODE SCIPfreeSymgraph(SCIP *scip, SYM_GRAPH **graph)
int * varcolors
SCIP_Bool * isfixedvar
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
#define infinity
Definition: gastrans.c:80
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_Real * vals
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
static int compareOps(int op1, int op2)
SCIP_RETCODE SCIPcomputeSymgraphColors(SCIP *scip, SYM_GRAPH *graph, SYM_SPEC fixedtype)
int SCIPgetSymgraphVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
#define FALSE
Definition: def.h:94
int * edgesecond
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static int compareVars(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
SCIP_RETCODE SCIPupdateSymgraphRhs(SYM_GRAPH *graph, int nodeidx, SCIP_Real newrhs)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
SCIP_Bool islocked
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
int * nodeinfopos
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Real * rhs
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPaddSymgraphVarAggregation(SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
SCIP_RETCODE SCIPcreateSymgraph(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH **graph, SCIP_VAR **symvars, int nsymvars, int nopnodes, int nvalnodes, int nconsnodes, int nedges)
SCIP_VAR ** SCIPgetSymgraphVars(SYM_GRAPH *graph)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
#define SYM_SPEC_BINARY
Definition: type_symmetry.h:44
SCIP_CONS ** conss
SCIP_Real * SCIPgetSymExprdataConstants(SYM_EXPRDATA *symdata)
methods for dealing with symmetry detection graphs
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SYM_SPEC_INTEGER
Definition: type_symmetry.h:43
SCIP_RETCODE SCIPcreateSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
static int compareConsnodes(SCIP *scip, SYM_GRAPH *graph, int ind1, int ind2)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
SYM_NODETYPE * nodetypes
SCIP_Real infinity
SCIP_Bool SCIPexprhdlrHasGetSymData(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:685
SCIP_VAR ** symvars
internal miscellaneous methods
SCIP_EXPR ** children
structs for symmetry computations
SCIP_RETCODE SCIPupdateSymgraphLhs(SYM_GRAPH *graph, int nodeidx, SCIP_Real newlhs)
SCIP_Real * edgevals
#define SCIP_CALL(x)
Definition: def.h:380
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
SCIP_RETCODE SCIPcopySymgraph(SCIP *scip, SYM_GRAPH **graph, SYM_GRAPH *origgraph, int *perm, SYM_SPEC fixedtype)
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1737
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
SCIP_Real * lhs
int SCIPgetSymgraphNegatedVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
SCIP_Bool uniqueedgetype
static SCIP_RETCODE ensureEdgeArraysSize(SCIP *scip, SYM_GRAPH *graph, int addsize)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_RETCODE SCIPfreeSymDataExpr(SCIP *scip, SYM_EXPRDATA **symdata)
#define SCIP_Bool
Definition: def.h:91
static SCIP_RETCODE ensureNodeArraysSize(SCIP *scip, SYM_GRAPH *graph, int addsize)
uint32_t SYM_SPEC
Definition: type_symmetry.h:47
int * opcolors
int * valcolors
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
#define MIN(x, y)
Definition: def.h:243
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
SCIP_RETCODE SCIPgetSymDataExpr(SCIP *scip, SCIP_EXPR *expr, SYM_EXPRDATA **symdata)
Definition: scip_expr.c:1792
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3877
SCIP_RETCODE SCIPaddSymgraphOpnode(SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12775
int * consnodeperm
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
SCIP_Real * coefficients
#define MAX(x, y)
Definition: def.h:239
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5538
type definitions for symmetry computations
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static int compareVarsSignedPerm(SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isneg1, SCIP_Bool isneg2, SCIP_Real infinity)
static const SCIP_Real scalars[]
Definition: lp.c:5743
SCIP_RETCODE SCIPfixSymgraphVarnode(SYM_GRAPH *graph, SCIP_VAR *var)
#define SYM_SPEC_REAL
Definition: type_symmetry.h:45
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
SCIP_RETCODE SCIPaddSymgraphConsnode(SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPfreeSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPaddSymgraphValnode(SCIP *scip, SYM_GRAPH *graph, SCIP_Real val, int *nodeidx)
#define SCIP_Real
Definition: def.h:173
SCIP_Real * constants
int SCIPgetSymExprdataNConstants(SYM_EXPRDATA *symdata)
static SCIP_Bool isFixedVar(SCIP_VAR *var, SYM_SPEC fixedtype)
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
SYM_SYMTYPE symtype
int * SCIPgetSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPaddSymgraphEdge(SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int * edgefirst
#define nnodes
Definition: gastrans.c:74
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPgetSymgraphNVarcolors(SYM_GRAPH *graph)
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
enum SYM_Nodetype SYM_NODETYPE
Definition: type_symmetry.h:74
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int * conscolors
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
SCIP callable library.
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128