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