SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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"
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 {
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 */
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 {
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 {
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 */
357static
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);
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);
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
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 */
608static
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 */
681static
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
722 return -1;
724 return 1;
725
727 return -1;
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 */
745static
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 */
775static
776SCIP_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 */
806static
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 */
935static
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 */
970static
971SCIP_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 */
1019static
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 */
1040static
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 */
1057static
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 */
1081static
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 */
1142static
1143SCIP_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 */
1157static
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 */
1173static
1174SCIP_Bool isFixedVar(
1175 SCIP_VAR* var, /**< active problem variable */
1176 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */
1177 )
1178{
1179 assert(var != NULL);
1180
1181 if ( (fixedtype & SYM_SPEC_INTEGER) && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER )
1182 return TRUE;
1183 if ( (fixedtype & SYM_SPEC_BINARY) && SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
1184 return TRUE;
1185 if ( (fixedtype & SYM_SPEC_REAL) &&
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:
1239 nusedvars = 2 * graph->nsymvars;
1240 } /*lint !e788*/
1241
1242 /* allocate memory for colors */
1243 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &graph->varcolors, nusedvars) );
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:
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 {
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
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
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}
#define NULL
Definition def.h:267
#define MIN(x, y)
Definition def.h:243
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_CALL(x)
Definition def.h:374
#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:1792
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3877
#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
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)
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:1737
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition var.c:12774
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition misc.c:5538
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
static const SCIP_Real scalars[]
Definition lp.c:5743
internal miscellaneous methods
#define SCIPerrorMessage
Definition pub_message.h:64
SCIP callable library.
SCIP_EXPR ** children
SCIP_Real * coefficients
SCIP_Real * constants
int * nodeinfopos
SCIP_Real infinity
SYM_NODETYPE * nodetypes
SCIP_Real * edgevals
int * consnodeperm
SCIP_VAR ** symvars
SCIP_Bool * isfixedvar
SCIP_Real * vals
SCIP_Real * rhs
SCIP_Bool islocked
SCIP_Bool uniqueedgetype
SCIP_Real * lhs
SCIP_CONS ** conss
SYM_SYMTYPE symtype
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)
methods for dealing with symmetry detection graphs
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:180
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
type definitions for symmetry computations
enum SYM_Symtype SYM_SYMTYPE
#define SYM_SPEC_BINARY
#define SYM_SPEC_INTEGER
enum SYM_Nodetype SYM_NODETYPE
@ SYM_NODETYPE_CONS
@ SYM_NODETYPE_VAR
@ SYM_NODETYPE_OPERATOR
@ SYM_NODETYPE_VAL
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM
uint32_t SYM_SPEC
#define SYM_SPEC_REAL
@ 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