SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
compute_symmetry_nauty.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 2002-2022 Zuse Institute Berlin */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file compute_symmetry_nauty.c
26 * @brief interface for symmetry computations to nauty/traces
27 * @author Marc Pfetsch
28 */
29
30/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32#include "compute_symmetry.h"
33
34/* the following determines whether nauty or traces is used: */
35#define NAUTY
36
37/* include nauty/traces */
38/* turn off warning (just for including nauty/traces) */
39#pragma GCC diagnostic ignored "-Wunused-variable"
40#pragma GCC diagnostic ignored "-Wredundant-decls"
41#pragma GCC diagnostic ignored "-Wpedantic"
42
43#ifdef NAUTY
44#include "nauty/nauty.h"
45#include "nauty/nausparse.h"
46#else
47#include "nauty/traces.h"
48#endif
49
50#pragma GCC diagnostic warning "-Wunused-variable"
51#pragma GCC diagnostic warning "-Wredundant-decls"
52#pragma GCC diagnostic warning "-Wpedantic"
53
54#include "scip/expr_var.h"
55#include "scip/expr_sum.h"
56#include "scip/expr_pow.h"
57#include "scip/expr.h"
58#include "scip/cons_nonlinear.h"
59#include "scip/cons_linear.h"
60#include "scip/scip_mem.h"
61
62
63/** struct for nauty callback */
65{
66 SCIP* scip; /**< SCIP pointer */
67 int npermvars; /**< number of variables for permutations */
68 int nperms; /**< number of permutations */
69 int** perms; /**< permutation generators as (nperms x npermvars) matrix */
70 int nmaxperms; /**< maximal number of permutations */
71 int maxgenerators; /**< maximal number of generators to be constructed (= 0 if unlimited) */
72};
73
74/* static data for nauty callback */
75static struct NAUTY_Data data_;
76
77
78/* ------------------- map for operator types ------------------- */
79
80/** gets the key of the given element */
81static
83{ /*lint --e{715}*/
84 return elem;
85}
86
87/** returns TRUE iff both keys are equal
88 *
89 * Compare the types of two operators according to their name, level and, in case of power, exponent.
90 */
91static
93{
96
97 k1 = (SYM_OPTYPE*) key1;
98 k2 = (SYM_OPTYPE*) key2;
99
100 /* first check operator name */
101 if ( SCIPexprGetHdlr(k1->expr) != SCIPexprGetHdlr(k2->expr) )
102 return FALSE;
103
104 /* for pow expressions, also check exponent (TODO should that happen for signpow as well?) */
105 if ( SCIPisExprPower((SCIP*) userptr, k1->expr )
106 && SCIPgetExponentExprPow(k1->expr) != SCIPgetExponentExprPow(k2->expr) ) /*lint !e777*/
107 return FALSE;
108
109 /* if still undecided, take level */
110 if ( k1->level != k2->level )
111 return FALSE;
112
113 return TRUE;
114}
115
116/** returns the hash value of the key */
117static
119{ /*lint --e{715}*/
120 SYM_OPTYPE* k;
121 SCIP_Real exponent;
122 uint64_t result;
123
124 k = (SYM_OPTYPE*) key;
125
126 if ( SCIPisExprPower((SCIP*) userptr, k->expr) )
127 exponent = SCIPgetExponentExprPow(k->expr);
128 else
129 exponent = 1.0;
130
132
133 return result;
134}
135
136/* ------------------- map for constant types ------------------- */
137
138/** gets the key of the given element */
139static
141{ /*lint --e{715}*/
142 return elem;
143}
144
145/** returns TRUE iff both keys are equal
146 *
147 * Compare two constants according to their values.
148 */
149static
151{ /*lint --e{715}*/
154
155 k1 = (SYM_CONSTTYPE*) key1;
156 k2 = (SYM_CONSTTYPE*) key2;
157
158 return (SCIP_Bool)(k1->value == k2->value); /*lint !e777*/
159}
160
161/** returns the hash value of the key */
162static
164{ /*lint --e{715}*/
166
167 k = (SYM_CONSTTYPE*) key;
168
169 return SCIPrealHashCode(k->value);
170}
171
172/* ------------------- map for constraint side types ------------------- */
173
174/** gets the key of the given element */
175static
177{ /*lint --e{715}*/
178 return elem;
179}
180
181/** returns TRUE iff both keys are equal
182 *
183 * Compare two constraint sides according to lhs and rhs.
184 */
185static
187{ /*lint --e{715}*/
190
191 k1 = (SYM_RHSTYPE*) key1;
192 k2 = (SYM_RHSTYPE*) key2;
193
194 if ( k1->lhs != k2->lhs ) /*lint !e777*/
195 return FALSE;
196
197 return (SCIP_Bool)(k1->rhs == k2->rhs); /*lint !e777*/
198}
199
200/** returns the hash value of the key */
201static
203{ /*lint --e{715}*/
204 SYM_RHSTYPE* k;
205
206 k = (SYM_RHSTYPE*) key;
207
208 return SCIPhashTwo(SCIPrealHashCode(k->lhs), SCIPrealHashCode(k->rhs));
209}
210
211
212/* ------------------- hook functions ------------------- */
213
214#ifdef NAUTY
215
216/** callback function for nauty */ /*lint -e{715}*/
217static
219 int count, /**< ID of this generator */
220 int* p, /**< generator (permutation) that nauty found */
221 int* orbits, /**< orbits generated by the group found so far */
222 int numorbits, /**< number of orbits */
223 int stabvertex, /**< stabilizing node */
224 int n /**< number of nodes in the graph */
225 )
226{ /* lint --e{715} */
227 SCIP_Bool isidentity = TRUE;
228 int* pp;
229 int j;
230
231 assert( p != NULL );
232
233 /* make sure we do not generate more than maxgenerators many permutations */
235 {
236 /* request a kill from nauty */
238 return;
239 }
240
241 /* check for identity */
242 for (j = 0; j < data_.npermvars && isidentity; ++j)
243 {
244 /* convert index of variable-level 0-nodes to variable indices */
245 if ( p[j] != j )
247 }
248
249 /* ignore trivial generators, i.e. generators that only permute the constraints */
250 if ( isidentity )
251 return;
252
253 /* check whether we should allocate space for perms */
254 if ( data_.nmaxperms <= 0 )
255 {
256 if ( data_.maxgenerators == 0 )
257 data_.nmaxperms = 100; /* seems to cover many cases */
258 else
260
262 return;
263 }
264 else if ( data_.nperms >= data_.nmaxperms ) /* check whether we need to resize */
265 {
266 int newsize;
267
270 assert( data_.maxgenerators == 0 );
271
273 return;
274
276 }
277
279 return;
281}
282
283#else
284
285/** callback function for traces */
286static
287void traceshook(
288 int count, /**< number of generator */
289 int* p, /**< generator that traces found */
290 int n /**< number of nodes in the graph */
291 )
292{
293 SCIP_Bool isidentity = TRUE;
294 int* pp;
295 int j;
296
297 assert( p != NULL );
298
299 /* make sure we do not generate more than maxgenerators many permutations */
301 {
302 /* request a kill from traces */
304 return;
305 }
306
307 /* check for identity */
308 for (j = 0; j < data_.npermvars && isidentity; ++j)
309 {
310 /* convert index of variable-level 0-nodes to variable indices */
311 if ( p[j] != j )
313 }
314
315 /* ignore trivial generators, i.e. generators that only permute the constraints */
316 if ( isidentity )
317 return;
318
319 /* check whether we should allocate space for perms */
320 if ( data_.nmaxperms <= 0 )
321 {
322 if ( data_.maxgenerators == 0 )
323 data_.nmaxperms = 100; /* seems to cover many cases */
324 else
326
328 return;
329 }
330 else if ( data_.nperms >= data_.nmaxperms ) /* check whether we need to resize */
331 {
332 int newsize;
333
336 assert( data_.maxgenerators == 0 );
337
339 return;
340
342 }
343
345 return;
347}
348
349#endif
350
351
352/* ------------------- other functions ------------------- */
353
354/** determine number of nodes and edges */
355static
357 SCIP* scip, /**< SCIP instance */
358 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
359 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
360 int* nnodes, /**< pointer to store the total number of nodes in graph */
361 int* nedges, /**< pointer to store the total number of edges in graph */
362 int* nlinearnodes, /**< pointer to store the number of internal nodes for linear constraints */
363 int* nnonlinearnodes, /**< pointer to store the number of internal nodes for nonlinear constraints */
364 int* nlinearedges, /**< pointer to store the number of edges for linear constraints */
365 int* nnonlinearedges, /**< pointer to store the number of edges for nonlinear constraints */
366 int** degrees, /**< pointer to store the degrees of the nodes */
367 int* maxdegrees, /**< pointer to store the maximal size of the degree array */
368 SCIP_Bool* success /**< pointer to store whether the construction was successful */
369 )
370{
371 SCIP_CONSHDLR* conshdlr;
372 SCIP_Bool groupByConstraints;
373 int* internodes = NULL;
374 int nmaxinternodes;
375 int oldcolor = -1;
376#ifndef NDEBUG
377 SCIP_Real oldcoef = SCIP_INVALID;
378#endif
379 int firstcolornodenumber = -1;
380 int nconss;
381 int j;
382
383 assert( scip != NULL );
384 assert( matrixdata != NULL );
385 assert( nnodes != NULL );
386 assert( nedges != NULL );
391 assert( degrees != NULL );
392 assert( maxdegrees != NULL );
393 assert( success != NULL );
394
395 *success = TRUE;
396
397 /* count nodes for variables */
398 *nnodes = matrixdata->npermvars;
399
400 /* count nodes for rhs of constraints */
401 *nnodes += matrixdata->nrhscoef;
402
403 /* allocate memory for degrees (will grow dynamically) */
404 *degrees = NULL;
405 *maxdegrees = 0;
407 for (j = 0; j < *nnodes; ++j)
408 (*degrees)[j] = 0;
409
410 /* initialize counters */
411 *nedges = 0;
412 *nlinearnodes = 0;
413 *nnonlinearnodes = 0;
414 *nlinearedges = 0;
415 *nnonlinearedges = 0;
416
417 /* Determine grouping depending on the number of rhs vs. variables; see fillGraphByLinearConss(). */
418 if ( matrixdata->nrhscoef < matrixdata->npermvars )
420 else
422
423 /* determine size of intermediate nodes */
424 if ( groupByConstraints )
425 nmaxinternodes = matrixdata->nrhscoef;
426 else
427 nmaxinternodes = matrixdata->npermvars;
428
430 for (j = 0; j < nmaxinternodes; ++j)
431 internodes[j] = -1;
432
433 /* loop through all matrix coefficients */
434 for (j = 0; j < matrixdata->nmatcoef; ++j)
435 {
436 int varrhsidx;
437 int rhsnode;
438 int varnode;
439 int color;
440 int idx;
441
442 idx = matrixdata->matidx[j];
443 assert( 0 <= idx && idx < matrixdata->nmatcoef );
444
445 /* find color corresponding to matrix coefficient */
446 color = matrixdata->matcoefcolors[idx];
447 assert( 0 <= color && color < matrixdata->nuniquemat );
448
449 assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
450 assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
451
452 rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
453 varnode = matrixdata->matvaridx[idx];
455 assert( rhsnode < *nnodes );
456 assert( varnode < *nnodes );
457
458 if ( matrixdata->nuniquemat == 1 )
459 {
460 /* We do not need intermediate nodes if we have only one coefficient class; just add edges. */
461 ++(*degrees)[varnode];
462 ++(*degrees)[rhsnode];
463 ++(*nlinearedges);
464 }
465 else
466 {
467 SCIP_Bool newinternode = FALSE;
468 int internode;
469
470 /* if new group of coefficients has been reached */
471 if ( color != oldcolor )
472 {
473 assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
474 oldcolor = color;
476#ifndef NDEBUG
477 oldcoef = matrixdata->matcoef[idx];
478#endif
479 }
480 else
481 assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
482
483 if ( groupByConstraints )
484 varrhsidx = matrixdata->matrhsidx[idx];
485 else
486 varrhsidx = matrixdata->matvaridx[idx];
488
490 {
491 internodes[varrhsidx] = (*nnodes)++;
492 ++(*nlinearnodes);
493
494 /* ensure memory for degrees */
496 (*degrees)[internodes[varrhsidx]] = 0;
498 }
500 assert( internode >= matrixdata->npermvars + matrixdata->nrhscoef );
502
503 /* determine whether graph would be too large for nauty/traces (can only handle int) */
504 if ( *nnodes >= INT_MAX/2 )
505 {
506 *success = FALSE;
507 break;
508 }
509
510 if ( groupByConstraints )
511 {
512 if ( newinternode )
513 {
514 ++(*degrees)[rhsnode];
515 ++(*degrees)[internode];
516 ++(*nlinearedges);
517 }
518 ++(*degrees)[varnode];
519 ++(*degrees)[internode];
520 ++(*nlinearedges);
521 }
522 else
523 {
524 if ( newinternode )
525 {
526 ++(*degrees)[varnode];
527 ++(*degrees)[internode];
528 ++(*nlinearedges);
529 }
530 ++(*degrees)[rhsnode];
531 ++(*degrees)[internode];
532 ++(*nlinearedges);
533 }
534 }
535 }
537
538 /* now treat nonlinear constraints */
539 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
540 nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
541 if ( nconss > 0 )
542 {
543 SCIP_CONS** conss;
545 SCIP_VAR** vars = NULL;
546 SCIP_Real* vals = NULL;
547 int* visitednodes;
548 int* ischildofsum;
549 int maxvisitednodes;
550 int maxischildofsum;
551 int numvisitednodes = 0;
552 int numischildofsum = 0;
553 int varssize;
554 int i;
555
556 conss = SCIPconshdlrGetConss(conshdlr);
557
558 /* prepare iterator */
560
561 /* prepare stacks */
562 maxvisitednodes = exprdata->nuniqueoperators + exprdata->nuniqueconstants + exprdata->nuniquecoefs;
566
567 /* get number of variables */
568 varssize = SCIPgetNVars(scip);
569
570 /* iterate over all expressions and add the corresponding nodes to the graph */
571 for (i = 0; i < nconss; ++i)
572 {
574 SCIP_EXPR* expr;
575 int currentlevel = 0;
576
578
581
582 for (expr = SCIPexpriterGetCurrent(it); ! SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
583 {
584 /* upon entering an expression, check its type and add nodes and edges if neccessary */
585 switch ( SCIPexpriterGetStageDFS(it) )
586 {
588 {
589 int node = -1;
590 int parentnode = -1;
591 SCIP_Bool isVarExpr = FALSE;
592
593 /* for variable expressions, get the corresponding node that is already in the graph */
594 if ( SCIPisExprVar(scip, expr) )
595 {
596 SCIP_VAR* var;
597
598 var = SCIPgetVarExprVar(expr);
599 isVarExpr = TRUE;
600
601 /* Check whether the variable is active; if not, then replace the inactive variable by its aggregation
602 * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
603 * expression.
604 */
605 if ( SCIPvarIsActive(var) )
606 {
607 node = SCIPvarGetProbindex(var);
608 assert( node < *nnodes );
609 }
610 else
611 {
612 SCIP_Real constant = 0.0;
613 int nvars;
614 int requiredsize;
615 int k;
616
617 if ( vars == NULL )
618 {
620 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals, varssize) );
621 }
622 assert( vars != NULL && vals != NULL );
623
624 vars[0] = var;
625 vals[0] = 1.0;
626 nvars = 1;
627
628 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &nvars, varssize, &constant, &requiredsize, TRUE) );
629 assert( requiredsize <= varssize );
630
631 assert( numvisitednodes > 0 );
634
635 /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
636 for (k = 0; k < nvars; ++k)
637 {
638 int internode;
639
640 assert( vars[k] != NULL );
641 assert( vals[k] != 0.0 );
642
643 /* add node */
644 internode = (*nnodes)++;
645 ++(nnonlinearnodes);
646
647 /* ensure size of degrees */
649 (*degrees)[internode] = 0;
650
651 ++(*degrees)[internode];
652 ++(*degrees)[parentnode];
653 ++(*nnonlinearedges);
654
655 /* connect the intermediate node to its corresponding variable node */
656 node = SCIPvarGetProbindex(vars[k]);
657 assert( node < *nnodes );
658
659 ++(*degrees)[internode];
660 ++(*degrees)[node];
661 ++(*nnonlinearedges);
662 }
663
664 /* add the node for the constant */
665 if ( constant != 0.0 )
666 {
667 /* add node */
668 node = (*nnodes)++;
669 ++(*nnonlinearnodes);
670
671 /* ensure size of degrees */
673 (*degrees)[node] = 0;
674
675 ++(*degrees)[node];
676 ++(*degrees)[parentnode];
677 ++(*nnonlinearedges);
678 }
679
680 /* add a filler node since it will be removed in the next iteration anyway */
683
686 ++currentlevel;
687
688 break;
689 }
690 }
691 /* for all other expressions, no nodes or edges have to be created */
692 else
693 {
694 /* do nothing here */
695 }
696
697 /* if this is the root expression, add the constraint side node (will be parent of expression node) */
699 {
700 /* add the constraint side node */
701 parentnode = (*nnodes)++;
702 ++(*nnonlinearnodes);
703
704 /* ensure size of degrees */
706 (*degrees)[parentnode] = 0;
707 }
708 /* otherwise, get the parentnode stored in visitednodes */
709 else
710 {
713 }
714
715 /* in all cases apart from variable expressions, the new node is added with the corresponding color */
716 if ( ! isVarExpr )
717 {
718 node = (*nnodes)++;
719 ++(*nnonlinearnodes);
720
721 /* ensure size of degrees */
723 (*degrees)[node] = 0;
724 }
725
726 /* store the new node so that it can be used as parentnode later */
729
730 assert( node != -1 );
733
734 /* connect the current node with its parent */
735 assert( parentnode != -1 );
736 ++(*degrees)[node];
737 ++(*degrees)[parentnode];
738 ++(*nnonlinearedges);
739
740 /* for sum expression, also add intermediate nodes for the coefficients */
741 if ( SCIPisExprSum(scip, expr) )
742 {
743 SCIP_Real constval;
744 int internode;
745
746 /* iterate over children from last to first, such that visitednodes array is in correct order */
747 for (j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
748 {
749 /* add the intermediate node with the corresponding color */
750 internode = (*nnodes)++;
751 ++(*nnonlinearnodes);
752
755
758
759 /* ensure size of degrees */
761 (*degrees)[internode] = 0;
762
763 ++(*degrees)[internode];
764 ++(*degrees)[node];
765 ++(*nnonlinearedges);
766 }
767
768 /* add node for the constant term of the sum expression */
770 if ( constval != 0.0 )
771 {
772 /* add the node with a new color */
773 internode = (*nnodes)++;
774 ++(*nnonlinearnodes);
775
776 /* ensure size of degrees */
778 (*degrees)[internode] = 0;
779
780 ++(*degrees)[internode];
781 ++(*degrees)[node];
782 ++(*nnonlinearedges);
783 }
784 }
785
786 ++currentlevel;
787 break;
788 }
789 /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
791 {
794 currentlevel--;
795
796 /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
797 * used for the coefficients of summands
798 */
800 {
803 }
804
805 break;
806 }
807
808 default:
809 SCIPABORT(); /* we should never be called in this stage */
810 break;
811 }
812 }
813
814 assert( currentlevel == 0 );
815 assert( numvisitednodes == 0 );
816 assert( numischildofsum == 0 );
817 }
818 SCIPfreeBlockMemoryArrayNull(scip, &vals, varssize);
820
824 }
825
826 *nedges = *nlinearedges + *nnonlinearedges;
827 assert( *nnodes == matrixdata->npermvars + matrixdata->nrhscoef + *nlinearnodes + *nnonlinearnodes );
828
829 SCIPdebugMsg(scip, "#nodes for variables: %d\n", matrixdata->npermvars);
830 SCIPdebugMsg(scip, "#nodes for rhs: %d\n", matrixdata->nrhscoef);
831 SCIPdebugMsg(scip, "#intermediate nodes for linear constraints: %d\n", *nlinearnodes);
832 SCIPdebugMsg(scip, "#intermediate nodes for nonlinear constraints: %d\n", *nnonlinearnodes);
833 SCIPdebugMsg(scip, "#edges for linear constraints: %d\n", *nlinearedges);
834 SCIPdebugMsg(scip, "#edges for nonlinear constraints: %d\n", *nnonlinearedges);
835
836 return SCIP_OKAY;
837}
838
839
840/** Construct linear and nonlinear part of colored graph for symmetry computations
841 *
842 * Construct linear graph:
843 * - Each variable gets a different node.
844 * - Each constraint gets a different node.
845 * - Each matrix coefficient gets a different node that is connected to the two nodes
846 * corresponding to the respective constraint and variable.
847 * - Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.
848 *
849 * Construct nonlinear graph:
850 * - Each node of the expression trees gets a different node.
851 * - Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
852 * - Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
853 *
854 * @note: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs
855 * and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different
856 * formulations of the same constraints would not be detected as equivalent, e.g. for
857 * 0 <= x1 + x2 <= 1
858 * 0 <= x3 + x4
859 * x3 + x4 <= 1
860 * there would be no symmetry between (x1,x2) and (x3,x4) detected.
861 *
862 * Each different constraint (sides), sum-expression coefficient, constant and operator type gets a
863 * different color that is attached to the corresponding entries.
864 */
865static
867 SCIP* scip, /**< SCIP instance */
868 sparsegraph* SG, /**< graph to be constructed */
869 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
870 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
871 int nnodes, /**< total number of nodes in graph */
872 int nedges, /**< total number of edges in graph */
873 int nlinearnodes, /**< number of intermediate nodes for linear constraints */
874 int nnonlinearnodes, /**< number of intermediate nodes for nonlinear constraints */
875 int nlinearedges, /**< number of intermediate edges for linear constraints */
876 int nnonlinearedges, /**< number of intermediate edges for nonlinear constraints */
877 int* degrees, /**< array with the degrees of the nodes */
878 int* colors, /**< array with colors of nodes on output */
879 int* nusedcolors /**< pointer to store number of used colors in the graph so far */
880 )
881{
890 SCIP_CONSHDLR* conshdlr;
891 SCIP_CONS** conss;
893 SCIP_Bool* ischildofsum;
894 SCIP_VAR** vars = NULL;
895 SCIP_Real* vals = NULL;
896 SCIP_Bool groupByConstraints;
897 int* internodes = NULL;
898 int* pos = NULL;
899 int* visitednodes;
900 int maxischildofsum;
901 int maxvisitednodes;
902 int numvisitednodes = 0;
903 int numischildofsum = 0;
904 int nconss;
905 int nuniqueops = 0;
906 int nuniqueconsts = 0;
907 int nuniquecoefs = 0;
908 int nuniquerhs = 0;
909 int oparraysize;
910 int constarraysize;
911 int coefarraysize;
912 int rhsarraysize;
913 int nmaxinternodes;
914 int oldcolor = -1;
915 int cnt;
916 int varssize;
917#ifndef NDEBUG
918 SCIP_Real oldcoef = SCIP_INVALID;
919#endif
920 int firstcolornodenumber = -1;
921 int n = 0;
922 int m = 0;
923 int i;
924 int j;
925
926 assert( scip != NULL );
927 assert( SG != NULL );
928 assert( matrixdata != NULL );
929 assert( exprdata != NULL );
930 assert( degrees != NULL );
931 assert( colors != NULL );
932 assert( nusedcolors != NULL );
933
934 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for linear part.\n");
935
936 /* fill in array with colors for variables */
937 for (j = 0; j < matrixdata->npermvars; ++j)
938 {
939 assert( 0 <= matrixdata->permvarcolors[j] && matrixdata->permvarcolors[j] < matrixdata->nuniquevars );
940 colors[n++] = matrixdata->permvarcolors[j];
941 }
942 *nusedcolors = matrixdata->nuniquevars;
943
944 /* fill in array with colors for rhs */
945 for (i = 0; i < matrixdata->nrhscoef; ++i)
946 {
947 assert( 0 <= matrixdata->rhscoefcolors[i] && matrixdata->rhscoefcolors[i] < matrixdata->nuniquerhs );
948 colors[n++] = *nusedcolors + matrixdata->rhscoefcolors[i];
949 }
950 *nusedcolors += matrixdata->nuniquerhs;
951
953
954 /* fill in positions in graph */
955 cnt = 0;
956 for (i = 0; i < nnodes; ++i)
957 {
958 SG->d[i] = degrees[i]; /* degree of node i */
959 SG->v[i] = (size_t) (unsigned) cnt; /* position of edges for node i */
960 pos[i] = cnt; /* also store position */
961 cnt += degrees[i];
962 }
963
964 /* Grouping of nodes depends on the number of nodes in the bipartite graph class. If there are more variables than
965 * constraints, we group by constraints. That is, given several variable nodes which are incident to one constraint
966 * node by the same color, we join these variable nodes to the constraint node by only one intermediate node.
967 */
968 if ( matrixdata->nrhscoef < matrixdata->npermvars )
970 else
972
973 /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
974 if ( groupByConstraints )
975 nmaxinternodes = matrixdata->nrhscoef;
976 else
977 nmaxinternodes = matrixdata->npermvars;
978
980 for (j = 0; j < nmaxinternodes; ++j)
981 internodes[j] = -1;
982
983 /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
984 * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
985 * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
986 * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
987 for (j = 0; j < matrixdata->nmatcoef; ++j)
988 {
989 int idx;
990 int color;
991 int rhsnode;
992 int varnode;
993 int varrhsidx;
994
995 idx = matrixdata->matidx[j];
996 assert( 0 <= idx && idx < matrixdata->nmatcoef );
997
998 /* find color corresponding to matrix coefficient */
999 color = matrixdata->matcoefcolors[idx];
1000 assert( 0 <= color && color < matrixdata->nuniquemat );
1001
1002 assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
1003 assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
1004
1005 rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
1006 varnode = matrixdata->matvaridx[idx];
1007 assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
1008 assert( rhsnode < nnodes );
1009 assert( varnode < nnodes );
1010
1011 /* if we have only one color, we do not need intermediate nodes */
1012 if ( matrixdata->nuniquemat == 1 )
1013 {
1014 SG->e[pos[varnode]++] = rhsnode;
1015 SG->e[pos[rhsnode]++] = varnode;
1016 assert( varnode == nnodes - 1 || pos[varnode] <= (int) SG->v[varnode+1] );
1017 assert( rhsnode == nnodes - 1 || pos[rhsnode] <= (int) SG->v[rhsnode+1] );
1018 ++m;
1019 }
1020 else
1021 {
1022 SCIP_Bool newinternode = FALSE;
1023 int internode;
1024
1025 /* if new group of coefficients has been reached */
1026 if ( color != oldcolor )
1027 {
1028 assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
1029 oldcolor = color;
1031#ifndef NDEBUG
1032 oldcoef = matrixdata->matcoef[idx];
1033#endif
1034 }
1035 else
1036 assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
1037
1038 if ( groupByConstraints )
1039 varrhsidx = matrixdata->matrhsidx[idx];
1040 else
1041 varrhsidx = matrixdata->matvaridx[idx];
1043
1045 {
1046 colors[n] = *nusedcolors + color;
1047 internodes[varrhsidx] = n++;
1049 }
1051 assert( internode >= matrixdata->npermvars + matrixdata->nrhscoef );
1053 assert( internode < nnodes );
1054
1055 if ( groupByConstraints )
1056 {
1057 if ( newinternode )
1058 {
1059 SG->e[pos[rhsnode]++] = internode;
1060 SG->e[pos[internode]++] = rhsnode;
1061 ++m;
1062 }
1063 SG->e[pos[varnode]++] = internode;
1064 SG->e[pos[internode]++] = varnode;
1065 ++m;
1066 }
1067 else
1068 {
1069 if ( newinternode )
1070 {
1071 SG->e[pos[varnode]++] = internode;
1072 SG->e[pos[internode]++] = varnode;
1073 ++m;
1074 }
1075 SG->e[pos[rhsnode]++] = internode;
1076 SG->e[pos[internode]++] = rhsnode;
1077 ++m;
1078 }
1079
1080 assert( varnode == nnodes - 1 || pos[varnode] <= (int) SG->v[varnode+1] );
1081 assert( internode == nnodes - 1 || pos[internode] <= (int) SG->v[internode+1] );
1082 }
1083 }
1084 assert( n == matrixdata->npermvars + matrixdata->nrhscoef + nlinearnodes );
1085 assert( m == nlinearedges );
1086
1088
1089 *nusedcolors += matrixdata->nuniquemat;
1090
1091 /* ------------------------------------------------------------------------ */
1092 /* treat nonlinear constraints */
1093 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
1094 nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
1095 if ( nconss == 0 )
1096 {
1098 return SCIP_OKAY;
1099 }
1100
1101 conss = SCIPconshdlrGetConss(conshdlr);
1102 rhsarraysize = nconss;
1103
1104 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for non-linear part.\n");
1105
1106 /* create maps for optypes, constants, sum coefficients and rhs to indices */
1107 oparraysize = exprdata->nuniqueoperators;
1108 constarraysize = exprdata->nuniqueconstants;
1109 coefarraysize = exprdata->nuniquecoefs;
1110
1119
1120 assert( optypemap != NULL );
1121 assert( consttypemap != NULL );
1122 assert( sumcoefmap != NULL );
1123 assert( rhstypemap != NULL );
1124
1125 /* allocate space for mappings from optypes, constants, sum coefficients and rhs to colors */
1130
1132
1137
1138 /* get number of variables */
1139 varssize = SCIPgetNVars(scip);
1140
1141 /* iterate over all expressions and add the corresponding nodes to the graph */
1142 for (i = 0; i < nconss; ++i)
1143 {
1145 SCIP_EXPR* expr;
1146 int currentlevel = 0;
1147
1149
1152
1153 for (expr = SCIPexpriterGetCurrent(it); ! SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
1154 {
1155 /* upon entering an expression, check its type and add nodes and edges if neccessary */
1156 switch ( SCIPexpriterGetStageDFS(it) )
1157 {
1159 {
1160 int node = -1;
1161 int parentnode = -1;
1162 int color = -1;
1163
1164 /* for variable expressions, get the corresponding node that is already in the graph */
1165 if ( SCIPisExprVar(scip, expr) )
1166 {
1167 SCIP_VAR* var;
1168
1169 var = SCIPgetVarExprVar(expr);
1170
1171 /* Check whether the variable is active; if not, then replace the inactive variable by its aggregation
1172 * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
1173 * expression.
1174 */
1175 if ( SCIPvarIsActive(var) )
1176 {
1177 node = SCIPvarGetProbindex(var);
1178 assert( node < nnodes );
1179 }
1180 else
1181 {
1182 SCIP_Real constant = 0.0;
1183 int nvars;
1184 int requiredsize;
1185 int k;
1186
1187 if ( vars == NULL )
1188 {
1190 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals, varssize) );
1191 }
1192 assert( vars != NULL && vals != NULL );
1193
1194 vars[0] = var;
1195 vals[0] = 1.0;
1196 nvars = 1;
1197
1198 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &nvars, varssize, &constant, &requiredsize, TRUE) );
1200
1201 assert( numvisitednodes > 0 );
1204
1205 /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
1206 for (k = 0; k < nvars; ++k)
1207 {
1209 int internode;
1210
1211 assert( vars[k] != NULL );
1212 assert( vals[k] != 0.0 );
1213 assert( nuniquecoefs < coefarraysize );
1214
1215 ct = &sumcoefarray[nuniquecoefs];
1216 ct->value = vals[k];
1217
1218 if ( ! SCIPhashtableExists(sumcoefmap, (void *) ct) )
1219 {
1221 ct->color = (*nusedcolors)++;
1222 color = ct->color;
1223 nuniquecoefs++;
1224 }
1225 else
1226 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
1227
1228 /* add the intermediate node with the corresponding color */
1229 colors[n] = color;
1230 internode = n++;
1231
1232 assert( internode < nnodes );
1233
1234 SG->e[pos[parentnode]++] = internode;
1235 SG->e[pos[internode]++] = parentnode;
1236 ++m;
1237 assert( parentnode == nnodes - 1 || pos[parentnode] <= (int) SG->v[parentnode+1] );
1238 assert( internode == nnodes - 1 || pos[internode] <= (int) SG->v[internode+1] );
1239 assert( m <= nedges );
1240
1241 /* connect the intermediate node to its corresponding variable node */
1242 node = SCIPvarGetProbindex(vars[k]);
1243 assert( node < nnodes );
1244
1245 SG->e[pos[node]++] = internode;
1246 SG->e[pos[internode]++] = node;
1247 ++m;
1248 assert( node == nnodes - 1 || pos[node] <= (int) SG->v[node+1] );
1249 assert( internode == nnodes - 1 || pos[internode] <= (int) SG->v[internode+1] );
1250 assert( m <= nedges );
1251 }
1252
1253 /* add the node for the constant */
1254 if ( constant != 0.0 )
1255 {
1257
1258 /* check whether we have to resize */
1261
1263 ct->value = constant;
1264
1265 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1266 {
1268 ct->color = (*nusedcolors)++;
1269 color = ct->color;
1270 nuniqueconsts++;
1271 }
1272 else
1273 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1274
1275 /* add the node with a new color */
1276 colors[n] = color;
1277 node = n++;
1278
1279 assert( node < nnodes );
1280
1281 SG->e[pos[node]++] = parentnode;
1282 SG->e[pos[parentnode]++] = node;
1283 ++m;
1284 assert( parentnode == nnodes - 1 || pos[parentnode] <= (int) SG->v[parentnode+1] );
1285 assert( node == nnodes - 1 || pos[node] <= (int) SG->v[node+1] );
1286 assert( m <= nedges );
1287 }
1288
1289 /* add a filler node since it will be removed in the next iteration anyway */
1292
1295 ++currentlevel;
1296
1297 break;
1298 }
1299 }
1300 /* for constant expressions, get the color of its type (value) or assign a new one */
1301 else if ( SCIPisExprValue(scip, expr) )
1302 {
1304
1306
1308 ct->value = SCIPgetValueExprValue(expr);
1309
1310 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1311 {
1313 ct->color = (*nusedcolors)++;
1314 color = ct->color;
1315 nuniqueconsts++;
1316 }
1317 else
1318 {
1319 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1320 }
1321 }
1322 /* for all other expressions, get the color of its operator type or assign a new one */
1323 else
1324 {
1325 SYM_OPTYPE* ot;
1326
1328
1330
1331 ot->expr = expr;
1332 ot->level = currentlevel;
1333
1334 if ( ! SCIPhashtableExists(optypemap, (void *) ot) )
1335 {
1337 ot->color = (*nusedcolors)++;
1338 color = ot->color;
1339 nuniqueops++;
1340 }
1341 else
1342 color = ((SYM_OPTYPE*) SCIPhashtableRetrieve(optypemap, (void *) ot))->color;
1343 }
1344
1345 /* if this is the root expression, add the constraint side node (will be parent of expression node) */
1347 {
1348 /* add the node corresponding to the constraint */
1349 SYM_RHSTYPE* rt;
1350 int parentcolor;
1351
1352 assert( nuniquerhs < rhsarraysize );
1353
1354 rt = &uniquerhsarray[nuniquerhs];
1355 rt->lhs = SCIPgetLhsNonlinear(conss[i]);
1356 rt->rhs = SCIPgetRhsNonlinear(conss[i]);
1357
1358 if ( ! SCIPhashtableExists(rhstypemap, (void *) rt) )
1359 {
1361 rt->color = (*nusedcolors)++;
1362 parentcolor = rt->color;
1363 nuniquerhs++;
1364 }
1365 else
1367
1368 /* add the constraint side node with the corresponding color */
1369 parentnode = n++;
1370 colors[parentnode] = parentcolor;
1372 }
1373 /* otherwise, get the parentnode stored in visitednodes */
1374 else
1375 {
1378 }
1379
1380 /* in all cases apart from variable expressions, the new node is added with the corresponding color */
1381 if ( color != -1 )
1382 {
1383 node = n++;
1384 colors[node] = color;
1385 assert( node < nnodes );
1386 assert( n <= nnodes );
1387 }
1388
1389 /* store the new node so that it can be used as parentnode later */
1392
1393 assert( node != -1 );
1394 visitednodes[numvisitednodes++] = node;
1396
1397 /* connect the current node with its parent */
1398 assert( parentnode != -1 );
1399
1400 SG->e[pos[node]++] = parentnode;
1401 SG->e[pos[parentnode]++] = node;
1402 ++m;
1403 assert( parentnode == nnodes - 1 || pos[parentnode] <= (int) SG->v[parentnode+1] );
1404 assert( node == nnodes - 1 || pos[node] <= (int) SG->v[node+1] );
1405 assert( m <= nedges );
1406
1407 /* for sum expression, also add intermediate nodes for the coefficients */
1408 if ( SCIPisExprSum(scip, expr) )
1409 {
1410 SCIP_Real* coefs;
1411 SCIP_Real constval;
1412 int internode;
1413
1414 coefs = SCIPgetCoefsExprSum(expr);
1415
1416 /* iterate over children from last to first, such that visitednodes array is in correct order */
1417 for (j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
1418 {
1420
1421 assert( nuniquecoefs < coefarraysize );
1422
1423 ct = &sumcoefarray[nuniquecoefs];
1424 ct->value = coefs[j];
1425
1426 if ( ! SCIPhashtableExists(sumcoefmap, (void *) ct) )
1427 {
1429 ct->color = (*nusedcolors)++;
1430 color = ct->color;
1431 nuniquecoefs++;
1432 }
1433 else
1434 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
1435
1436 /* add the intermediate node with the corresponding color */
1437 internode = n++;
1438 colors[internode] = color;
1439
1442
1445
1446 assert( internode < nnodes );
1447
1448 SG->e[pos[node]++] = internode;
1449 SG->e[pos[internode]++] = node;
1450 ++m;
1451 assert( internode == nnodes - 1 || pos[internode] <= (int) SG->v[internode+1] );
1452 assert( node == nnodes - 1 || pos[node] <= (int) SG->v[node+1] );
1453 assert( m <= nedges );
1454 }
1455
1456 /* add node for the constant term of the sum expression */
1458 if ( constval != 0.0 )
1459 {
1461
1462 /* check whether we have to resize */
1465
1467 ct->value = constval;
1468
1469 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1470 {
1472 ct->color = (*nusedcolors)++;
1473 color = ct->color;
1474 nuniqueconsts++;
1475 }
1476 else
1477 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1478
1479 /* add the node with a new color */
1480 internode = n++;
1481 colors[internode] = color;
1482
1483 assert( node < nnodes );
1484
1485 SG->e[pos[node]++] = internode;
1486 SG->e[pos[internode]++] = node;
1487 ++m;
1488 assert( internode == nnodes - 1 || pos[internode] <= (int) SG->v[internode+1] );
1489 assert( node == nnodes - 1 || pos[node] <= (int) SG->v[node+1] );
1490 assert( m <= nedges );
1491 }
1492 }
1493
1494 ++currentlevel;
1495 break;
1496 }
1497 /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
1499 {
1502 currentlevel--;
1503
1504 /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
1505 * used for the coefficients of summands
1506 */
1508 {
1511 }
1512
1513 break;
1514 }
1515
1516 default:
1517 SCIPABORT(); /* we should never be called in this stage */
1518 break;
1519 }
1520 }
1521
1522 assert( currentlevel == 0 );
1523 assert( numvisitednodes == 0 );
1524 assert( numischildofsum == 0 );
1525 }
1526 assert( n == nnodes );
1527 assert( m == nedges );
1528 assert( n == matrixdata->npermvars + matrixdata->nrhscoef + nlinearnodes + nnonlinearnodes );
1530
1531#ifndef NDEBUG
1532 for (i = 0; i < nnodes - 1; ++i)
1533 assert( pos[i] == (int) SG->v[i+1] );
1534#endif
1535
1536 /* free everything */
1537 SCIPfreeBlockMemoryArrayNull(scip, &vals, varssize);
1539
1552
1553 return SCIP_OKAY;
1554}
1555
1556/** return whether symmetry can be computed */
1558{
1559 return TRUE;
1560}
1561
1562/** static variable for holding the name of name */
1563#ifdef NAUTY
1564static const char nautyname[] = "Nauty "NAUTYVERSION;
1565#else
1566static const char nautyname[] = "Traces "NAUTYVERSION;
1567#endif
1568
1569/** return name of external program used to compute generators */
1570const char* SYMsymmetryGetName(void)
1571{
1572 return nautyname;
1573}
1574
1575/** return description of external program used to compute generators */
1576const char* SYMsymmetryGetDesc(void)
1577{
1578#ifdef NAUTY
1579 return "Computing Graph Automorphism Groups by Brendan D. McKay (https://users.cecs.anu.edu.au/~bdm/nauty/)";
1580#else
1581 return "Computing Graph Automorphism Groups by Adolfo Piperno (https://pallini.di.uniroma1.it/)";
1582#endif
1583}
1584
1585/** return name of additional external program used for computing symmetries */
1586const char* SYMsymmetryGetAddName(void)
1587{
1588 return NULL;
1589}
1590
1591/** return description of additional external program used to compute symmetries */
1592const char* SYMsymmetryGetAddDesc(void)
1593{
1594 return NULL;
1595}
1596
1597/** compute generators of symmetry group */
1599 SCIP* scip, /**< SCIP pointer */
1600 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1601 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
1602 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
1603 int* nperms, /**< pointer to store number of permutations */
1604 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1605 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1606 SCIP_Real* log10groupsize, /**< pointer to store size of group */
1607 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
1608 )
1609{
1610 SCIP_Real oldtime;
1611 SCIP_Bool success = FALSE;
1612 int* degrees;
1613 int* colors;
1614 int maxdegrees;
1615 int nnodes;
1616 int nedges;
1617 int nlinearnodes;
1618 int nnonlinearnodes;
1619 int nlinearedges;
1620 int nnonlinearedges;
1621 int nusedcolors;
1622 int v;
1623
1624 /* nauty data structures */
1626 int* lab;
1627 int* ptn;
1628 int* orbits;
1629
1630#ifdef NAUTY
1632 statsblk stats;
1633#else
1635 TracesStats stats;
1636#endif
1637
1638 assert( scip != NULL );
1639 assert( matrixdata != NULL );
1640 assert( exprdata != NULL );
1641 assert( nperms != NULL );
1642 assert( nmaxperms != NULL );
1643 assert( perms != NULL );
1644 assert( log10groupsize != NULL );
1645 assert( maxgenerators >= 0 );
1646 assert( symcodetime != NULL );
1647
1648 /* init */
1649 *nperms = 0;
1650 *nmaxperms = 0;
1651 *perms = NULL;
1652 *log10groupsize = 0;
1653 *symcodetime = 0.0;
1654
1655 /* init options */
1656#ifdef NAUTY
1657 /* init callback functions for nauty (accumulate the group generators found by nauty) */
1658 options.writeautoms = FALSE;
1659 options.userautomproc = nautyhook;
1660 options.defaultptn = FALSE; /* use color classes */
1661#else
1662 /* init callback functions for traces (accumulate the group generators found by traces) */
1663 options.writeautoms = FALSE;
1664 options.userautomproc = traceshook;
1665 options.defaultptn = FALSE; /* use color classes */
1666#endif
1667
1668 /* determine number of nodes and edges */
1671 &degrees, &maxdegrees, &success) );
1672
1673 if ( ! success )
1674 {
1675 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Stopped symmetry computation: Symmetry graph would become too large.\n");
1676 return SCIP_OKAY;
1677 }
1678
1679 /* allocate temporary array for colors */
1681
1682 /* init graph */
1683 SG_INIT(SG);
1684
1685 SG_ALLOC(SG, (unsigned) nnodes, (unsigned) 2 * nedges, "malloc"); /*lint !e647*/
1686
1687 SG.nv = nnodes; /* number of nodes */
1688 SG.nde = (size_t) (unsigned) (2 * nedges); /* number of directed edges */
1689
1690 /* add the nodes for linear and nonlinear constraints to the graph */
1693 degrees, colors, &nusedcolors) );
1694
1696
1697 /* memory allocation for nauty/traces */
1701
1702 /* fill in array with colors for variables */
1703 for (v = 0; v < nnodes; ++v)
1704 lab[v] = v;
1705
1706 /* sort nodes according to colors */
1707 SCIPsortIntInt(colors, lab, nnodes);
1708
1709 /* set up ptn marking new colors */
1710 for (v = 0; v < nnodes; ++v)
1711 {
1712 if ( v < nnodes-1 && colors[v] == colors[v+1] )
1713 ptn[v] = 1; /* color class does not end */
1714 else
1715 ptn[v] = 0; /* color class ends */
1716 }
1717
1718 SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
1719
1720 data_.scip = scip;
1721 data_.npermvars = matrixdata->npermvars;
1722 data_.nperms = 0;
1723 data_.nmaxperms = 0;
1725 data_.perms = NULL;
1726
1727 /* call nauty/traces */
1729#ifdef NAUTY
1730 sparsenauty(&SG, lab, ptn, orbits, &options, &stats, NULL);
1731#else
1732 Traces(&SG, lab, ptn, orbits, &options, &stats, NULL);
1733#endif
1735
1736 SCIPfreeBufferArray(scip, &orbits);
1739
1740 SCIPfreeBufferArray(scip, &colors);
1741
1742 SG_FREE(SG);
1743
1744 /* prepare return values */
1745 if ( data_.nperms > 0 )
1746 {
1747 *perms = data_.perms;
1748 *nperms = data_.nperms;
1750 }
1751 else
1752 {
1753 assert( data_.perms == NULL );
1754 assert( data_.nmaxperms == 0 );
1755 }
1756
1757 /* determine log10 of symmetry group size */
1758 *log10groupsize = (SCIP_Real) stats.grpsize2;
1759
1760 return SCIP_OKAY;
1761}
interface for symmetry computations
const char * SYMsymmetryGetName(void)
static const char nautyname[]
static SCIP_RETCODE determineGraphSize(SCIP *scip, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nnodes, int *nedges, int *nlinearnodes, int *nnonlinearnodes, int *nlinearedges, int *nnonlinearedges, int **degrees, int *maxdegrees, SCIP_Bool *success)
static SCIP_RETCODE fillGraphByConss(SCIP *scip, sparsegraph *SG, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int nnodes, int nedges, int nlinearnodes, int nnonlinearnodes, int nlinearedges, int nnonlinearedges, int *degrees, int *colors, int *nusedcolors)
static void nautyhook(int count, int *p, int *orbits, int numorbits, int stabvertex, int n)
const char * SYMsymmetryGetAddName(void)
static struct NAUTY_Data data_
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
const char * SYMsymmetryGetDesc(void)
const char * SYMsymmetryGetAddDesc(void)
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_INVALID
Definition def.h:206
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define SCIP_CALL(x)
Definition def.h:388
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
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
SCIP_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition misc.c:2296
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2609
#define SCIPhashTwo(a, b)
Definition pub_misc.h:519
#define SCIPhashThree(a, b, c)
Definition pub_misc.h:521
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition misc.c:2246
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition misc.c:2558
static INLINE uint32_t SCIPrealHashCode(double x)
Definition pub_misc.h:544
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition misc.c:2497
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4595
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4552
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition expr.c:532
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition expr_pow.c:3351
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition expriter.c:968
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1443
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition expr_sum.c:1166
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1432
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition expriter.c:682
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition expriter.c:663
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1421
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition scip_expr.c:2296
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:739
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition expr_value.c:294
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1465
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition expriter.c:857
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition expr_sum.c:1181
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition expr_var.c:416
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition scip_expr.c:2310
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:695
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition expriter.c:500
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3824
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition scip_mem.h:107
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#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 SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition scip_var.c:1738
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17570
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for memory management
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
#define SCIP_EXPRITER_LEAVEEXPR
Definition type_expr.h:679
#define SCIP_EXPRITER_ENTEREXPR
Definition type_expr.h:676
@ SCIP_VERBLEVEL_MINIMAL
#define SCIP_DECL_HASHKEYEQ(x)
Definition type_misc.h:194
#define SCIP_DECL_HASHGETKEY(x)
Definition type_misc.h:191
#define SCIP_DECL_HASHKEYVAL(x)
Definition type_misc.h:197
enum SCIP_Retcode SCIP_RETCODE