Scippy

SCIP

Solving Constraint Integer Programs

build_sassy_graph.cpp
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 build_sassy_graph.cpp
26 * @brief methods to build sassy graph for symmetry detection
27 * @author Christopher Hojny
28 */
29
30/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32#include "build_sassy_graph.h"
33#include "scip/expr_var.h"
34#include "scip/expr_sum.h"
35#include "scip/expr_pow.h"
36#include "scip/expr.h"
37#include "scip/cons_nonlinear.h"
38#include "scip/cons_linear.h"
39#include "scip/scip_mem.h"
40#include "scip/symmetry_graph.h"
41
42
43/* ------------------- auxiliary functions ------------------- */
44
45/** returns whether an edge is considered in grouping process */
46static
48 SYM_GRAPH* graph, /**< symmetry detection graph */
49 int edgeidx, /**< index of edge to be checked */
50 SCIP_Bool groupbycons /**< whether edges are grouped by constraints */
51 )
52{
53 int first;
54 int second;
55
56 assert(graph != NULL);
57
58 first = SCIPgetSymgraphEdgeFirst(graph, edgeidx);
59 second = SCIPgetSymgraphEdgeSecond(graph, edgeidx);
60
61 /* uncolored edges are not grouped */
62 if ( ! SCIPisSymgraphEdgeColored(graph, edgeidx) )
63 return FALSE;
64
65 /* two variable nodes are connected */
66 if ( first < 0 && second < 0 )
67 return FALSE;
68
69 if ( ! groupbycons )
70 {
71 /* grouping by variables requires one variable node */
72 if ( first < 0 || second < 0 )
73 return TRUE;
74 }
75 else
76 {
77 /* check whether there is exactly one constraint node in edge */
78 if ( first >= 0 && second >= 0 )
79 {
80 if ( (SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS
81 && SCIPgetSymgraphNodeType(graph, second) != SYM_NODETYPE_CONS)
83 && SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS) )
84 return TRUE;
85 }
86 else if ( first >= 0 )
87 {
88 if ( SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS )
89 return TRUE;
90 }
91 else
92 {
93 if ( SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS )
94 return TRUE;
95 }
96 }
97
98 return FALSE;
99}
100
101/** adds grouped edges all of which have one common endpoint to a graph
102 *
103 * The grouping mechanism works by sorting the edges according to their color. If two
104 * edges have the same color, they share the same intermediate node, which is connected
105 * to the common node and the other endpoints of equivalent edges.
106 */
107static
109 SCIP* scip, /**< SCIP pointer */
110 sassy::static_graph* G, /**< graph which gets extended */
111 SCIP_Bool determinesize, /**< whether only the effect of grouping on the graph shall be checked */
112 int* internodeid, /**< (initialized) pointer to store the ID of the next intermediate node */
113 int** degrees, /**< pointer to array of degrees for nodes in G */
114 int* maxdegrees, /**< (initialized) pointer to maximum number of entries degrees can hold */
115 int* nnodes, /**< (initialized) pointer to store the number of */
116 int* nedges, /**< (initialized) pointer to store the number of */
117 int commonnodeidx, /**< index of common node in G */
118 int* neighbors, /**< neighbors of common node */
119 int* colors, /**< colors of edges to neighbors */
120 int nneighbors, /**< number of neighbors */
121 int* naddednodes, /**< pointer to store number of nodes added to G */
122 int* naddededges /**< pointer to store number of edges added to G */
123 )
124{
125 int curcolor;
126 int curstart;
127 int e;
128 int f;
129
130 assert( G != NULL || determinesize );
131 assert( internodeid != NULL );
132 assert( *internodeid >= 0 );
133 assert( degrees != NULL );
134 assert( maxdegrees != NULL );
135 assert( *maxdegrees > 0 );
136 assert( nnodes != NULL );
137 assert( nedges != NULL );
138 assert( neighbors != NULL );
139 assert( colors != NULL );
140 assert( naddednodes != NULL );
141 assert( naddededges != NULL );
142 assert( commonnodeidx <= *internodeid );
143
144 *naddednodes = 0;
145 *naddededges = 0;
146
147 /* sort edges according to color */
148 SCIPsortIntInt(colors, neighbors, nneighbors);
149
150 /* iterate over groups of identical edges and group them, ignoring the last group */
151 curcolor = colors[0];
152 curstart = 0;
153 for (e = 1; e < nneighbors; ++e)
154 {
155 /* if a new group started, add edges for previous group */
156 if ( colors[e] != curcolor )
157 {
158 if ( determinesize )
159 {
160 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
161 (*degrees)[*internodeid] = 1;
162 ++(*degrees)[commonnodeidx];
163
164 for (f = curstart; f < e; ++f)
165 {
166 assert( neighbors[f] <= *internodeid );
167 ++(*degrees)[*internodeid];
168 ++(*degrees)[neighbors[f]];
169 }
170 }
171 else
172 {
173 (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
174 G->add_edge((unsigned) commonnodeidx, (unsigned) *internodeid);
175
176 for (f = curstart; f < e; ++f)
177 (*G).add_edge((unsigned) neighbors[f], (unsigned) *internodeid);
178 }
179 *naddednodes += 1;
180 *naddededges += e - curstart + 1;
181 ++(*internodeid);
182
183 curcolor = colors[e];
184 curstart = e;
185 }
186 }
187
188 /* add edges of last group */
189 if ( determinesize )
190 {
191 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
192
193 (*degrees)[*internodeid] = 1;
194 ++(*degrees)[commonnodeidx];
195
196 for (f = curstart; f < nneighbors; ++f)
197 {
198 assert( neighbors[f] <= *internodeid );
199 ++(*degrees)[*internodeid];
200 ++(*degrees)[neighbors[f]];
201 }
202 }
203 else
204 {
205 (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
206 G->add_edge((unsigned) commonnodeidx, (unsigned) *internodeid);
207
208 for (f = curstart; f < nneighbors; ++f)
209 G->add_edge((unsigned) neighbors[f], (unsigned) *internodeid);
210 }
211 *naddednodes += 1;
212 *naddededges += nneighbors - curstart + 1;
213 ++(*internodeid);
214
215 return SCIP_OKAY;
216}
217
218/** either creates a graph or determines its size */
219static
221 SCIP* scip, /**< SCIP instance */
222 SYM_GRAPH* graph, /**< symmetry detection graph */
223 SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
224 sassy::static_graph* G, /**< graph to be constructed */
225 int* nnodes, /**< pointer to store the total number of nodes in graph */
226 int* nedges, /**< pointer to store the total number of edges in graph */
227 int** degrees, /**< pointer to store the degrees of the nodes */
228 int* maxdegrees, /**< pointer to store the maximal size of the degree array */
229 SCIP_Bool* success /**< pointer to store whether the construction was successful */
230 )
231{
232 SYM_SYMTYPE symtype;
233 SYM_NODETYPE comparetype;
234 SCIP_Bool groupByConstraints;
235 int* groupfirsts = NULL;
236 int* groupseconds = NULL;
237 int* groupcolors = NULL;
238 int ngroupedges = 0;
239 int nvarnodestoadd;
240 int internodeid;
241 int nsymvars;
242 int nsymedges;
243 int first;
244 int second;
245 int color;
246 int e;
247 int j;
248
249 assert( scip != NULL );
250 assert( graph != NULL );
251 assert( G != NULL || determinesize );
252 assert( nnodes != NULL );
253 assert( nedges != NULL );
254 assert( degrees != NULL );
255 assert( maxdegrees != NULL );
256 assert( success != NULL );
257
258 *success = TRUE;
259
260 /* collect basic information from symmetry detection graph */
261 nsymvars = SCIPgetSymgraphNVars(graph);
262 symtype = SCIPgetSymgraphSymtype(graph);
263 switch ( symtype )
264 {
265 case SYM_SYMTYPE_PERM:
266 nvarnodestoadd = nsymvars;
267 break;
268 default:
269 assert( symtype == SYM_SYMTYPE_SIGNPERM );
270 nvarnodestoadd = 2 * nsymvars;
271 }
272
273 /* possibly find number of nodes in sassy graph */
274 if ( determinesize )
275 {
276 /* initialize counters */
277 *nnodes = SCIPgetSymgraphNNodes(graph) + nvarnodestoadd;
278 *nedges = 0;
279
280 /* possibly allocate memory for degrees (will grow dynamically) */
281 *degrees = NULL;
282 *maxdegrees = 0;
283 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 100) );
284 for (j = 0; j < *nnodes; ++j)
285 (*degrees)[j] = 0;
286 }
287 else
288 {
289 assert( G != NULL );
290
291 /* add nodes for variables */
292 for (j = 0; j < nvarnodestoadd; ++j)
293 (void) G->add_vertex(SCIPgetSymgraphVarnodeColor(graph, j), (*degrees)[j]);
294
295 /* add nodes for remaining nodes of graph */
296 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
297 (void) G->add_vertex(SCIPgetSymgraphNodeColor(graph, j), (*degrees)[nvarnodestoadd + j]);
298 }
299
300 /* determine grouping depending on the number of rhs vs. variables */
302 groupByConstraints = TRUE;
303 else
304 groupByConstraints = FALSE;
305
306 /* allocate arrays to collect edges to be grouped */
307 nsymedges = SCIPgetSymgraphNEdges(graph);
308 SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
309 SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
310 SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
311
312 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
313 internodeid = SCIPgetSymgraphNNodes(graph) + nvarnodestoadd;
314 for (e = 0; e < SCIPgetSymgraphNEdges(graph); ++e)
315 {
316 first = SCIPgetSymgraphEdgeFirst(graph, e);
317 second = SCIPgetSymgraphEdgeSecond(graph, e);
318
319 /* get the first and second node in edge (corrected by variable shift) */
320 if ( first < 0 )
321 first = -first - 1;
322 else
323 first += nvarnodestoadd;
324 if ( second < 0 )
325 second = -second - 1;
326 else
327 second += nvarnodestoadd;
328 assert(first >= 0);
329 assert(second >= 0);
330
331 /* check whether edge is used for grouping */
332 if ( ! SCIPhasGraphUniqueEdgetype(graph) && isEdgeGroupable(graph, e, groupByConstraints) )
333 {
334 /* store edge, first becomes the cons or var node */
335 comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
336
337 if ( SCIPgetSymgraphNodeType(graph, SCIPgetSymgraphEdgeFirst(graph, e)) == comparetype )
338 {
339 groupfirsts[ngroupedges] = first;
340 groupseconds[ngroupedges] = second;
341 }
342 else
343 {
344 groupfirsts[ngroupedges] = second;
345 groupseconds[ngroupedges] = first;
346 }
347 groupcolors[ngroupedges++] = SCIPgetSymgraphEdgeColor(graph, e);
348 }
349 else
350 {
351 /* immediately add edge or increase degrees */
352 assert(0 <= first && first < *nnodes);
353 assert(0 <= second && second < *nnodes);
354
355 /* possibly split edge if it is colored */
356 if ( ! SCIPhasGraphUniqueEdgetype(graph) && SCIPisSymgraphEdgeColored(graph, e) )
357 {
358 if ( determinesize )
359 {
360 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, internodeid + 1) );
361
362 ++(*degrees)[first];
363 ++(*degrees)[second];
364 (*degrees)[internodeid] = 2;
365 ++(*nnodes);
366 *nedges += 2;
367 ++internodeid;
368 }
369 else
370 {
371 assert( internodeid < *nnodes );
372 assert( G != NULL );
373
374 color = SCIPgetSymgraphEdgeColor(graph, e);
375 (void) G->add_vertex(color, (*degrees)[internodeid]);
376
377 G->add_edge((unsigned) first, (unsigned) internodeid);
378 G->add_edge((unsigned) second, (unsigned) internodeid++);
379 }
380 }
381 else
382 {
383 if ( determinesize )
384 {
385 ++(*degrees)[first];
386 ++(*degrees)[second];
387 ++(*nedges);
388 }
389 else
390 {
391 assert( G != NULL );
392 if ( first < second )
393 G->add_edge((unsigned) first, (unsigned) second);
394 else
395 G->add_edge((unsigned) second, (unsigned) first);
396 }
397 }
398 }
399 }
400
401 /* possibly add groupable edges */
402 if ( ngroupedges > 0 )
403 {
404 int firstidx = 0;
405 int firstnodeidx;
406 int naddednodes;
407 int naddededges;
408
409 /* sort edges according to their first nodes */
410 SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
411 firstnodeidx = groupfirsts[0];
412
413 for (j = 1; j < ngroupedges; ++j)
414 {
415 /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
416 if ( groupfirsts[j] != firstnodeidx )
417 {
418 SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
419 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
420 &naddednodes, &naddededges) );
421
422 firstidx = j;
423 firstnodeidx = groupfirsts[j];
424
425 if ( determinesize )
426 {
427 *nnodes += naddednodes;
428 *nedges += naddededges;
429 }
430 }
431 }
432
433 /* process the last group */
434 SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
435 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
436 &naddednodes, &naddededges) );
437
438 if ( determinesize )
439 {
440 *nnodes += naddednodes;
441 *nedges += naddededges;
442 }
443 }
444
445 SCIPfreeBufferArray(scip, &groupcolors);
446 SCIPfreeBufferArray(scip, &groupseconds);
447 SCIPfreeBufferArray(scip, &groupfirsts);
448
449 /* for signed permutation, also add edges connecting a variable and its negation */
450 switch ( SCIPgetSymgraphSymtype(graph) )
451 {
453 if ( determinesize )
454 {
455 for (j = 0; j < nvarnodestoadd; ++j)
456 ++(*degrees)[j];
457 *nedges += nsymvars;
458 }
459 else
460 {
461 assert( G != NULL );
462 for (j = 0; j < nsymvars; ++j)
463 G->add_edge((unsigned) j, (unsigned) (j + nsymvars));
464 }
465 break;
466 default:
467 assert( SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_PERM );
468 }
469
470 if ( determinesize )
471 {
472 SCIPdebugMsg(scip, "#nodes: %d\n", *nnodes);
473 SCIPdebugMsg(scip, "#nodes for variables: %d\n", nvarnodestoadd);
474 SCIPdebugMsg(scip, "#nodes for rhs: %d\n", SCIPgetSymgraphNConsnodes(graph));
475 SCIPdebugMsg(scip, "#edges: %d\n", *nedges);
476 }
477
478 return SCIP_OKAY;
479}
480
481/** either creates a graph for checking symmetries or determines its size
482 *
483 * The input are two graphs and the graph to be constructed consists of copies
484 * of the two input graphs, in which non-variable nodes are colored according
485 * to the colors used in symmetry detection. Each variable gets a unique color.
486 */
487static
489 SCIP* scip, /**< SCIP instance */
490 SYM_GRAPH* graph1, /**< first symmetry detection graph */
491 SYM_GRAPH* graph2, /**< second symmetry detection graph */
492 SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
493 sassy::static_graph* G, /**< graph to be constructed */
494 int* nnodes, /**< pointer to store the total number of nodes in graph */
495 int* nedges, /**< pointer to store the total number of edges in graph */
496 int** degrees, /**< pointer to store the degrees of the nodes */
497 int* maxdegrees, /**< pointer to store the maximal size of the degree array */
498 int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 (or NULL) */
499 SCIP_Bool* success /**< pointer to store whether the graph could be built */
500 )
501{
502 SYM_SYMTYPE symtype;
503 SYM_NODETYPE comparetype;
504 SCIP_Bool groupByConstraints;
505 SYM_GRAPH* graph;
506 int* nvarused1 = NULL;
507 int* nvarused2 = NULL;
508 int* varlabel = NULL;
509 int* groupfirsts = NULL;
510 int* groupseconds = NULL;
511 int* groupcolors = NULL;
512 int ngroupedges = 0;
513 int nusedvars = 0;
514 int nodeshift;
515 int curnnodes;
516 int nvarnodestoadd;
517 int internodeid;
518 int nsymvars;
519 int nsymedges;
520 int first;
521 int second;
522 int color;
523 int e;
524 int i;
525 int j;
526
527 assert( scip != NULL );
528 assert( graph1 != NULL );
529 assert( graph2 != NULL );
530 assert( G != NULL || determinesize );
531 assert( nnodes != NULL );
532 assert( nedges != NULL );
533 assert( degrees != NULL );
534 assert( maxdegrees != NULL );
535 assert( success != NULL );
536
537 *success = FALSE;
538
539 /* graphs cannot be symmetric */
540 if ( SCIPgetSymgraphNEdges(graph1) != SCIPgetSymgraphNEdges(graph2)
541 || SCIPgetSymgraphNVars(graph1) != SCIPgetSymgraphNVars(graph2) )
542 return SCIP_OKAY;
543
544 /* collect basic information from symmetry detection graph */
545 nsymvars = SCIPgetSymgraphNVars(graph1);
546 nsymedges = SCIPgetSymgraphNEdges(graph1);
547 symtype = SCIPgetSymgraphSymtype(graph1);
548 switch ( symtype )
549 {
550 case SYM_SYMTYPE_PERM:
551 nvarnodestoadd = nsymvars;
552 break;
553 default:
554 assert( symtype == SYM_SYMTYPE_SIGNPERM );
555 nvarnodestoadd = 2 * nsymvars;
556 }
557
558 /* find the variables that are contained in an edge */
559 SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused1, nvarnodestoadd) );
560 SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused2, nvarnodestoadd) );
561 SCIP_CALL( SCIPallocBufferArray(scip, &varlabel, nvarnodestoadd) );
562
563 for (e = 0; e < nsymedges; ++e)
564 {
565 first = SCIPgetSymgraphEdgeFirst(graph1, e);
566 second = SCIPgetSymgraphEdgeSecond(graph1, e);
567 if ( first < 0 )
568 nvarused1[-first - 1] += 1;
569 if ( second < 0 )
570 nvarused1[-second - 1] += 1;
571
572 first = SCIPgetSymgraphEdgeFirst(graph2, e);
573 second = SCIPgetSymgraphEdgeSecond(graph2, e);
574 if ( first < 0 )
575 nvarused2[-first - 1] += 1;
576 if ( second < 0 )
577 nvarused2[-second - 1] += 1;
578 }
579
580 for (j = 0; j < nvarnodestoadd; ++j)
581 {
582 /* graphs cannot be identical */
583 if ( nvarused1[j] != nvarused2[j] )
584 {
585 SCIPfreeBufferArray(scip, &varlabel);
586 SCIPfreeBufferArray(scip, &nvarused2);
587 SCIPfreeBufferArray(scip, &nvarused1);
588
589 return SCIP_OKAY;
590 }
591
592 /* relabel variables by restricting to variables used in constraint (or their negation) */
593 if ( nvarused1[j] > 0 || nvarused1[j % SCIPgetSymgraphNVars(graph1)] > 0 )
594 varlabel[j] = nusedvars++;
595 else
596 varlabel[j] = -1;
597 }
598
599 /* possibly find number of nodes in sassy graph and allocate memory for dynamic array */
600 if ( determinesize )
601 {
602 *degrees = NULL;
603 *maxdegrees = 0;
604 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees,
605 SCIPgetSymgraphNNodes(graph1) + SCIPgetSymgraphNNodes(graph2) + 2 * nusedvars + 100) );
606
607 *nnodes = 0;
608 *nedges = 0;
609 }
610
611 /* determine grouping depending on the number of rhs vs. variables */
612 if ( SCIPgetSymgraphNConsnodes(graph1) < SCIPgetSymgraphNVars(graph1) )
613 groupByConstraints = TRUE;
614 else
615 groupByConstraints = FALSE;
616
617 /* allocate arrays to collect edges to be grouped */
618 SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
619 SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
620 SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
621
622 /* collect information or generate graphs, we shift the node indices of the second graph when adding them to G */
623 nodeshift = 0;
624 for (i = 0; i < 2; ++i)
625 {
626 curnnodes = 0;
627 graph = i == 0 ? graph1 : graph2;
628 ngroupedges = 0;
629
630 /* possibly add nodes for variables and remaining nodes, each variable gets a unique color */
631 if ( determinesize )
632 {
633 /* add nodes for variables */
634 for (j = 0; j < nvarnodestoadd; ++j)
635 {
636 if ( varlabel[j] >= 0 )
637 {
638 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
639 (*degrees)[nodeshift + varlabel[j]] = 0;
640 ++(*nnodes);
641 ++curnnodes;
642 }
643 }
644
645 /* add nodes for remaining nodes of graph */
646 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
647 {
648 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
649 (*degrees)[nodeshift + nusedvars + j] = 0;
650 ++(*nnodes);
651 ++curnnodes;
652 }
653 }
654 else
655 {
656 assert( G != NULL );
657
658 /* add nodes for variables, each variable gets a unique color */
659 for (j = 0; j < nvarnodestoadd; ++j)
660 {
661 if ( varlabel[j] >= 0 )
662 {
663 (void) G->add_vertex(j, (*degrees)[nodeshift + varlabel[j]]);
664 ++curnnodes;
665 }
666 }
667
668 /* add nodes for remaining nodes of graph, ensure that colors do not conflict with variable colors */
669 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
670 {
671 (void) G->add_vertex(nusedvars + SCIPgetSymgraphNodeColor(graph, j),
672 (*degrees)[nodeshift + nusedvars + j]);
673 ++curnnodes;
674 }
675 }
676
677 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
678 internodeid = nodeshift + curnnodes;
679 for (e = 0; e < nsymedges; ++e)
680 {
681 first = SCIPgetSymgraphEdgeFirst(graph, e);
682 second = SCIPgetSymgraphEdgeSecond(graph, e);
683
684 /* get the first and second node in edge (corrected by variable shift) */
685 if ( first < 0 )
686 first = varlabel[-first - 1];
687 else
688 first = nusedvars + first;
689 if ( second < 0 )
690 second = varlabel[-second - 1];
691 else
692 second = nusedvars + second;
693
694 /* check whether edge is used for grouping */
695 if ( ! SCIPhasGraphUniqueEdgetype(graph) && isEdgeGroupable(graph, e, groupByConstraints) )
696 {
697 /* store edge, first becomes the cons or var node */
698 comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
699
700 if ( SCIPgetSymgraphNodeType(graph, SCIPgetSymgraphEdgeFirst(graph, e)) == comparetype )
701 {
702 groupfirsts[ngroupedges] = nodeshift + first;
703 groupseconds[ngroupedges] = nodeshift + second;
704 }
705 else
706 {
707 groupfirsts[ngroupedges] = nodeshift + second;
708 groupseconds[ngroupedges] = nodeshift + first;
709 }
710 groupcolors[ngroupedges++] = nusedvars + SCIPgetSymgraphEdgeColor(graph, e);
711 }
712 else
713 {
714 /* immediately add edge or increase degrees */
715 assert(0 <= first && first < *nnodes);
716 assert(0 <= second && second < *nnodes);
717
718 /* possibly split edge if it is colored */
719 if ( ! SCIPhasGraphUniqueEdgetype(graph) && SCIPisSymgraphEdgeColored(graph, e) )
720 {
721 if ( determinesize )
722 {
723 SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, internodeid + 1) );
724
725 ++(*degrees)[nodeshift + first];
726 ++(*degrees)[nodeshift + second];
727 (*degrees)[internodeid] = 2;
728 ++(*nnodes);
729 *nedges += 2;
730 }
731 else
732 {
733 assert( internodeid < *nnodes );
734 assert( G != NULL );
735
736 color = SCIPgetSymgraphEdgeColor(graph, e);
737 (void) G->add_vertex(nusedvars + color, (*degrees)[internodeid]);
738 G->add_edge((unsigned) (nodeshift + first), (unsigned) internodeid);
739 G->add_edge((unsigned) (nodeshift + second), (unsigned) internodeid);
740 }
741 ++internodeid;
742 ++curnnodes;
743 }
744 else
745 {
746 if ( determinesize )
747 {
748 ++(*degrees)[nodeshift + first];
749 ++(*degrees)[nodeshift + second];
750 ++(*nedges);
751 }
752 else
753 {
754 assert( G != NULL );
755
756 if ( first < second )
757 G->add_edge((unsigned) (nodeshift + first), (unsigned) (nodeshift + second));
758 else
759 G->add_edge((unsigned) (nodeshift + second), (unsigned) (nodeshift + first));
760 }
761 }
762 }
763 }
764
765 /* possibly add groupable edges */
766 if ( ngroupedges > 0 )
767 {
768 int firstidx = 0;
769 int firstnodeidx;
770 int naddednodes;
771 int naddededges;
772
773 /* sort edges according to their first nodes */
774 SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
775 firstnodeidx = groupfirsts[0];
776
777 for (j = 1; j < ngroupedges; ++j)
778 {
779 /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
780 if ( groupfirsts[j] != firstnodeidx )
781 {
782 SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
783 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
784 &naddednodes, &naddededges) );
785
786 firstidx = j;
787 firstnodeidx = groupfirsts[j];
788
789 if ( determinesize )
790 {
791 *nnodes += naddednodes;
792 *nedges += naddededges;
793 }
794 curnnodes += naddednodes;
795 }
796 }
797
798 /* process the last group */
799 SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
800 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
801 &naddednodes, &naddededges) );
802
803 if ( determinesize )
804 {
805 *nnodes += naddednodes;
806 *nedges += naddededges;
807 }
808 curnnodes += naddednodes;
809 }
810
811 /* for signed permutation, also add edges connecting a variable and its negation */
813 {
814 if ( determinesize )
815 {
816 for (j = 0; j < nusedvars; ++j)
817 ++(*degrees)[nodeshift + j];
818 (*nedges) += nusedvars / 2;
819 }
820 else
821 {
822 assert( G != NULL );
823
824 for (j = 0; j < nusedvars/2; ++j)
825 G->add_edge((unsigned) (nodeshift + j), (unsigned) (nodeshift + j + nusedvars / 2));
826 }
827 }
828 nodeshift = curnnodes;
829
830 if ( i == 0 && nnodesfromG1 != NULL )
831 *nnodesfromG1 = curnnodes;
832 }
833
834 SCIPfreeBufferArray(scip, &groupcolors);
835 SCIPfreeBufferArray(scip, &groupseconds);
836 SCIPfreeBufferArray(scip, &groupfirsts);
837
838 SCIPfreeBufferArray(scip, &varlabel);
839 SCIPfreeBufferArray(scip, &nvarused2);
840 SCIPfreeBufferArray(scip, &nvarused1);
841
842 *success = TRUE;
843
844 return SCIP_OKAY;
845}
846
847
848/** compute generators of symmetry group */
850 SCIP* scip, /**< SCIP pointer */
851 sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
852 SYM_GRAPH* graph, /**< symmetry detection graph */
853 SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
854 )
855{
856 int* degrees;
857 int maxdegrees;
858 int nnodes;
859 int nedges;
860
861 assert( scip != NULL );
862 assert( sassygraph != NULL );
863 assert( graph != NULL );
864
865 *success = FALSE;
866
867 /* determine number of nodes and edges */
868 SCIP_CALL( createOrDetermineSizeGraph(scip, graph, TRUE, NULL, &nnodes, &nedges, &degrees, &maxdegrees, success) );
869
870 if ( ! *success )
871 {
873 "Stopped symmetry computation: Symmetry graph would become too large.\n");
874 return SCIP_OKAY;
875 }
876
877 /* init graph */
878 (*sassygraph).initialize_graph((unsigned) nnodes, (unsigned) nedges);
879
880 /* add the nodes for linear and nonlinear constraints to the graph */
881 SCIP_CALL( createOrDetermineSizeGraph(scip, graph, FALSE, sassygraph,
882 &nnodes, &nedges, &degrees, &maxdegrees, success) );
883
884 SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
885
886 SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
887
888 return SCIP_OKAY;
889}
890
891/** returns whether two given graphs are identical */
893 SCIP* scip, /**< SCIP pointer */
894 sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
895 SYM_GRAPH* G1, /**< first graph */
896 SYM_GRAPH* G2, /**< second graph */
897 int* nnodes, /**< pointer to store number of nodes in sassy graph */
898 int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 */
899 SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
900 )
901{
902 int* degrees = NULL;
903 int maxdegrees = 0;
904 int nedges;
905
906 assert( scip != NULL );
907 assert( sassygraph != NULL );
908 assert( G1 != NULL );
909 assert( G2 != NULL );
910 assert( nnodes != NULL );
911 assert( nnodesfromG1 != NULL );
912 assert( success != NULL );
913
914 *success = FALSE;
915 *nnodes = 0;
916 *nnodesfromG1 = 0;
917
918 /* some simple checks */
919 if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
920 || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
921 return SCIP_OKAY;
922
923 /* determine number of nodes and edges */
925 nnodes, &nedges, &degrees, &maxdegrees, nnodesfromG1, success) );
926
927 if ( ! *success )
928 {
929 assert( degrees == NULL );
930 assert( maxdegrees == 0 );
931 return SCIP_OKAY;
932 }
933 if ( *nnodes % 2 != 0 )
934 {
935 assert( degrees != NULL );
936 assert( maxdegrees > 0 );
937
938 SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
939 return SCIP_OKAY;
940 }
941
942 /* init graph */
943 (*sassygraph).initialize_graph((unsigned) *nnodes, (unsigned) nedges);
944
945 /* add the nodes for linear and nonlinear constraints to the graph */
947 nnodes, &nedges, &degrees, &maxdegrees, NULL, success) );
948 assert( *success );
949
950 SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
951
952 return SCIP_OKAY;
953}
static SCIP_Bool isEdgeGroupable(SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
static SCIP_RETCODE createOrDetermineSizeGraphCheck(SCIP *scip, SYM_GRAPH *graph1, SYM_GRAPH *graph2, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int *nnodesfromG1, SCIP_Bool *success)
static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges(SCIP *scip, sassy::static_graph *G, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
static SCIP_RETCODE createOrDetermineSizeGraph(SCIP *scip, SYM_GRAPH *graph, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, SCIP_Bool *success)
methods to build sassy graph for symmetry detection
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_CALL(x)
Definition: def.h:374
private functions to work with algebraic expressions
power and signed power expression handlers
sum expression handler
variable expression handler
#define nnodes
Definition: gastrans.c:74
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
public methods for memory management
methods for dealing with symmetry detection graphs
@ SCIP_VERBLEVEL_MINIMAL
Definition: type_message.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
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_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61