SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
compute_symmetry_sassy.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 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_sassy.c
26 * @brief interface for symmetry computations to sassy as a preprocessor to bliss
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/* include bliss */
35#include <bliss/defs.hh>
36#include <bliss/graph.hh>
37
38/* include sassy */
39#ifdef __GNUC__
40#pragma GCC diagnostic ignored "-Wshadow"
41#pragma GCC diagnostic ignored "-Wunused-variable"
42#pragma GCC diagnostic ignored "-Wsign-compare"
43#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
44#endif
45
46#ifdef _MSC_VER
47# pragma warning(push)
48# pragma warning(disable: 4189) // local variable is initialized but not referenced
49# pragma warning(disable: 4267) // conversion of size_t to int (at sassy/preprocessor.h:2897)
50# pragma warning(disable: 4388) // compare signed and unsigned expression
51# pragma warning(disable: 4456) // shadowed variable
52# pragma warning(disable: 4430) // missing type specifier
53#endif
54
55/* the actual include */
56#include <sassy/preprocessor.h>
57
58#ifdef __GNUC__
59#pragma GCC diagnostic warning "-Wunused-but-set-variable"
60#pragma GCC diagnostic warning "-Wsign-compare"
61#pragma GCC diagnostic warning "-Wunused-variable"
62#pragma GCC diagnostic warning "-Wshadow"
63#endif
64
65#ifdef _MSC_VER
66# pragma warning(pop)
67#endif
68
69#include <sassy/tools/bliss_converter.h>
70
71#include "scip/expr_var.h"
72#include "scip/expr_sum.h"
73#include "scip/expr_pow.h"
74#include "scip/expr.h"
75#include "scip/cons_nonlinear.h"
76#include "scip/cons_linear.h"
77#include "scip/scip_mem.h"
78
79
80/** struct for symmetry callback */
82{
83 SCIP* scip; /**< SCIP pointer */
84 int npermvars; /**< number of variables for permutations */
85 int nperms; /**< number of permutations */
86 int** perms; /**< permutation generators as (nperms x npermvars) matrix */
87 int nmaxperms; /**< maximal number of permutations */
88 int maxgenerators; /**< maximal number of generators to be constructed (= 0 if unlimited) */
89};
90
91
92/* ------------------- map for operator types ------------------- */
93
94/** gets the key of the given element */
95static
97{ /*lint --e{715}*/
98 return elem;
99}
100
101/** returns TRUE iff both keys are equal
102 *
103 * Compare the types of two operators according to their name, level and, in case of power, exponent.
104 */
105static
107{
108 SYM_OPTYPE* k1;
109 SYM_OPTYPE* k2;
110
111 k1 = (SYM_OPTYPE*) key1;
112 k2 = (SYM_OPTYPE*) key2;
113
114 /* first check operator name */
115 if ( SCIPexprGetHdlr(k1->expr) != SCIPexprGetHdlr(k2->expr) )
116 return FALSE;
117
118 /* for pow expressions, also check exponent (TODO should that happen for signpow as well?) */
119 if ( SCIPisExprPower((SCIP*) userptr, k1->expr )
120 && SCIPgetExponentExprPow(k1->expr) != SCIPgetExponentExprPow(k2->expr) ) /*lint !e777*/
121 return FALSE;
122
123 /* if still undecided, take level */
124 if ( k1->level != k2->level )
125 return FALSE;
126
127 return TRUE;
128}
129
130/** returns the hash value of the key */
131static
133{ /*lint --e{715}*/
134 SYM_OPTYPE* k;
135 SCIP_Real exponent;
136 uint64_t result;
137
138 k = (SYM_OPTYPE*) key;
139
140 if ( SCIPisExprPower((SCIP*) userptr, k->expr) )
141 exponent = SCIPgetExponentExprPow(k->expr);
142 else
143 exponent = 1.0;
144
145 result = SCIPhashThree(SCIPrealHashCode(exponent), k->level,
146 SCIPhashKeyValString(NULL, static_cast<void*>(const_cast<char*>(SCIPexprhdlrGetName(SCIPexprGetHdlr(k->expr))))));
147
148 return result;
149}
150
151/* ------------------- map for constant types ------------------- */
152
153/** gets the key of the given element */
154static
156{ /*lint --e{715}*/
157 return elem;
158}
159
160/** returns TRUE iff both keys are equal
161 *
162 * Compare two constants according to their values.
163 */
164static
166{
169
170 k1 = (SYM_CONSTTYPE*) key1;
171 k2 = (SYM_CONSTTYPE*) key2;
172
173 return (SCIP_Bool)(k1->value == k2->value); /*lint !e777*/
174}
175
176/** returns the hash value of the key */
177static
179{ /*lint --e{715}*/
181
182 k = (SYM_CONSTTYPE*) key;
183
184 return SCIPrealHashCode(k->value);
185}
186
187/* ------------------- map for constraint side types ------------------- */
188
189/** gets the key of the given element */
190static
192{ /*lint --e{715}*/
193 return elem;
194}
195
196/** returns TRUE iff both keys are equal
197 *
198 * Compare two constraint sides according to lhs and rhs.
199 */
200static
202{
205
206 k1 = (SYM_RHSTYPE*) key1;
207 k2 = (SYM_RHSTYPE*) key2;
208
209 if ( k1->lhs != k2->lhs ) /*lint !e777*/
210 return FALSE;
211
212 return (SCIP_Bool)(k1->rhs == k2->rhs); /*lint !e777*/
213}
214
215/** returns the hash value of the key */
216static
218{ /*lint --e{715}*/
219 SYM_RHSTYPE* k;
220
221 k = (SYM_RHSTYPE*) key;
222
223 return SCIPhashTwo(SCIPrealHashCode(k->lhs), SCIPrealHashCode(k->rhs));
224}
225
226
227/* ------------------- hook functions ------------------- */
228
229/** callback function for sassy */ /*lint -e{715}*/
230static
232 void* user_param, /**< parameter supplied at call to sassy */
233 int n, /**< dimension of permutations */
234 const int* aut, /**< permutation */
235 int nsupp, /**< support size */
236 const int* suppa /**< support list */
237 )
238{
239 assert( aut != NULL );
240 assert( user_param != NULL );
241
242 SYMMETRY_Data* data = static_cast<SYMMETRY_Data*>(user_param);
243 assert( data->scip != NULL );
244 assert( data->npermvars < (int) n );
245 assert( data->maxgenerators >= 0 );
246
247 /* make sure we do not generate more that maxgenerators many permutations */
248 if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
249 return;
250
251 /* copy first part of automorphism */
252 bool isIdentity = true;
253 int* p = 0;
254 if ( SCIPallocBlockMemoryArray(data->scip, &p, data->npermvars) != SCIP_OKAY )
255 return;
256
257 for (int j = 0; j < data->npermvars; ++j)
258 {
259 /* convert index of variable-level 0-nodes to variable indices */
260 p[j] = (int) aut[j];
261 if ( p[j] != j )
262 isIdentity = false;
263 }
264
265 /* ignore trivial generators, i.e. generators that only permute the constraints */
266 if ( isIdentity )
267 {
269 return;
270 }
271
272 /* check whether we should allocate space for perms */
273 if ( data->nmaxperms <= 0 )
274 {
275 if ( data->maxgenerators == 0 )
276 data->nmaxperms = 100; /* seems to cover many cases */
277 else
278 data->nmaxperms = data->maxgenerators;
279
280 if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
281 return;
282 }
283 else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
284 {
285 int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
286 assert( newsize >= data->nperms );
287 assert( data->maxgenerators == 0 );
288
289 if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
290 return;
291
292 data->nmaxperms = newsize;
293 }
294
295 data->perms[data->nperms++] = p;
296}
297
298
299/* ------------------- other functions ------------------- */
300
301/** determine number of nodes and edges */
302static
304 SCIP* scip, /**< SCIP instance */
305 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
306 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
307 int* nnodes, /**< pointer to store the total number of nodes in graph */
308 int* nedges, /**< pointer to store the total number of edges in graph */
309 int* nlinearnodes, /**< pointer to store the number of internal nodes for linear constraints */
310 int* nnonlinearnodes, /**< pointer to store the number of internal nodes for nonlinear constraints */
311 int* nlinearedges, /**< pointer to store the number of edges for linear constraints */
312 int* nnonlinearedges, /**< pointer to store the number of edges for nonlinear constraints */
313 int** degrees, /**< pointer to store the degrees of the nodes */
314 int* maxdegrees, /**< pointer to store the maximal size of the degree array */
315 SCIP_Bool* success /**< pointer to store whether the construction was successful */
316 )
317{
318 SCIP_CONSHDLR* conshdlr;
319 SCIP_Bool groupByConstraints;
320 int* internodes = NULL;
321 int nmaxinternodes;
322 int oldcolor = -1;
323#ifndef NDEBUG
324 SCIP_Real oldcoef = SCIP_INVALID;
325#endif
326 int firstcolornodenumber = -1;
327 int nconss;
328 int j;
329
330 assert( scip != NULL );
331 assert( matrixdata != NULL );
332 assert( exprdata != NULL );
333 assert( nnodes != NULL );
334 assert( nedges != NULL );
339 assert( degrees != NULL );
340 assert( maxdegrees != NULL );
341 assert( success != NULL );
342
343 *success = TRUE;
344
345 /* count nodes for variables */
346 *nnodes = matrixdata->npermvars;
347
348 /* count nodes for rhs of constraints */
349 *nnodes += matrixdata->nrhscoef;
350
351 /* allocate memory for degrees (will grow dynamically) */
352 *degrees = NULL;
353 *maxdegrees = 0;
355 for (j = 0; j < *nnodes; ++j)
356 (*degrees)[j] = 0;
357
358 /* initialize counters */
359 *nedges = 0;
360 *nlinearnodes = 0;
361 *nnonlinearnodes = 0;
362 *nlinearedges = 0;
363 *nnonlinearedges = 0;
364
365 /* Determine grouping depending on the number of rhs vs. variables; see fillGraphByLinearConss(). */
366 if ( matrixdata->nrhscoef < matrixdata->npermvars )
368 else
370
371 /* determine size of intermediate nodes */
372 if ( groupByConstraints )
373 nmaxinternodes = matrixdata->nrhscoef;
374 else
375 nmaxinternodes = matrixdata->npermvars;
376
378 for (j = 0; j < nmaxinternodes; ++j)
379 internodes[j] = -1;
380
381 /* loop through all matrix coefficients */
382 for (j = 0; j < matrixdata->nmatcoef; ++j)
383 {
384 int varrhsidx;
385 int rhsnode;
386 int varnode;
387 int color;
388 int idx;
389
390 idx = matrixdata->matidx[j];
391 assert( 0 <= idx && idx < matrixdata->nmatcoef );
392
393 /* find color corresponding to matrix coefficient */
394 color = matrixdata->matcoefcolors[idx];
395 assert( 0 <= color && color < matrixdata->nuniquemat );
396
397 assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
398 assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
399
400 rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
401 varnode = matrixdata->matvaridx[idx];
402 assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
403 assert( rhsnode < *nnodes );
404 assert( varnode < *nnodes );
405
406 if ( matrixdata->nuniquemat == 1 )
407 {
408 /* We do not need intermediate nodes if we have only one coefficient class; just add edges. */
409 ++(*degrees)[varnode];
410 ++(*degrees)[rhsnode];
411 ++(*nlinearedges);
412 }
413 else
414 {
415 SCIP_Bool newinternode = FALSE;
416 int internode;
417
418 /* if new group of coefficients has been reached */
419 if ( color != oldcolor )
420 {
421 assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
422 oldcolor = color;
424#ifndef NDEBUG
425 oldcoef = matrixdata->matcoef[idx];
426#endif
427 }
428 else
429 assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
430
431 if ( groupByConstraints )
432 varrhsidx = matrixdata->matrhsidx[idx];
433 else
434 varrhsidx = matrixdata->matvaridx[idx];
436
438 {
439 internodes[varrhsidx] = (*nnodes)++;
440 ++(*nlinearnodes);
441
442 /* ensure memory for degrees */
444 (*degrees)[internodes[varrhsidx]] = 0;
446 }
448 assert( internode >= matrixdata->npermvars + matrixdata->nrhscoef );
450
451 /* determine whether graph would be too large */
452 if ( *nnodes >= INT_MAX/2 )
453 {
454 *success = FALSE;
455 break;
456 }
457
458 if ( groupByConstraints )
459 {
460 if ( newinternode )
461 {
462 ++(*degrees)[rhsnode];
463 ++(*degrees)[internode];
464 ++(*nlinearedges);
465 }
466 ++(*degrees)[varnode];
467 ++(*degrees)[internode];
468 ++(*nlinearedges);
469 }
470 else
471 {
472 if ( newinternode )
473 {
474 ++(*degrees)[varnode];
475 ++(*degrees)[internode];
476 ++(*nlinearedges);
477 }
478 ++(*degrees)[rhsnode];
479 ++(*degrees)[internode];
480 ++(*nlinearedges);
481 }
482 }
483 }
485
486 /* now treat nonlinear constraints */
487 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
488 nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
489 if ( nconss > 0 && *success )
490 {
491 SCIP_CONS** conss;
493 SCIP_VAR** vars = NULL;
494 SCIP_Real* vals = NULL;
495 int* visitednodes = NULL;
496 int* ischildofsum = NULL;
497 int maxvisitednodes;
498 int maxischildofsum;
499 int numvisitednodes = 0;
500 int numischildofsum = 0;
501 int varssize;
502 int i;
503
504 conss = SCIPconshdlrGetConss(conshdlr);
505
506 /* prepare iterator */
508
509 /* prepare stacks */
510 maxvisitednodes = exprdata->nuniqueoperators + exprdata->nuniqueconstants + exprdata->nuniquecoefs;
514
515 /* get number of variables */
516 varssize = SCIPgetNVars(scip);
517
518 /* iterate over all expressions and add the corresponding nodes to the graph */
519 for (i = 0; i < nconss; ++i)
520 {
522 SCIP_EXPR* expr;
523#ifndef NDEBUG
524 int currentlevel = 0;
525#endif
526
528
531
532 for (expr = SCIPexpriterGetCurrent(it); ! SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
533 {
534 /* upon entering an expression, check its type and add nodes and edges if neccessary */
535 switch ( SCIPexpriterGetStageDFS(it) )
536 {
538 {
539 int node = -1;
540 int parentnode = -1;
541 SCIP_Bool isVarExpr = FALSE;
542
543 /* for variable expressions, get the corresponding node that is already in the graph */
544 if ( SCIPisExprVar(scip, expr) )
545 {
546 SCIP_VAR* var;
547
548 var = SCIPgetVarExprVar(expr);
549 isVarExpr = TRUE;
550
551 /* Check whether the variable is active; if not, then replace the inactive variable by its aggregation
552 * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
553 * expression.
554 */
555 if ( SCIPvarIsActive(var) )
556 {
557 node = SCIPvarGetProbindex(var);
558 assert( node < *nnodes );
559 }
560 else
561 {
562 SCIP_Real constant = 0.0;
563 int nvars;
564 int requiredsize;
565 int k;
566
567 if ( vars == NULL )
568 {
570 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals, varssize) );
571 }
572 assert( vars != NULL && vals != NULL );
573
574 vars[0] = var;
575 vals[0] = 1.0;
576 nvars = 1;
577
578 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &nvars, varssize, &constant, &requiredsize, TRUE) );
579 assert( requiredsize <= varssize );
580
581 assert( numvisitednodes > 0 );
584
585 /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
586 for (k = 0; k < nvars; ++k)
587 {
588 int internode;
589
590 assert( vars[k] != NULL );
591 assert( vals[k] != 0.0 );
592
593 /* add node */
594 internode = (*nnodes)++;
595 ++(*nnonlinearnodes);
596
597 /* ensure size of degrees */
599 (*degrees)[internode] = 0;
600
601 ++(*degrees)[internode];
602 ++(*degrees)[parentnode];
603 ++(*nnonlinearedges);
604
605 /* connect the intermediate node to its corresponding variable node */
606 node = SCIPvarGetProbindex(vars[k]);
607 assert( node < *nnodes );
608
609 ++(*degrees)[internode];
610 ++(*degrees)[node];
611 ++(*nnonlinearedges);
612 }
613
614 /* add the node for the constant */
615 if ( constant != 0.0 )
616 {
617 /* add node */
618 node = (*nnodes)++;
619 ++(*nnonlinearnodes);
620
621 /* ensure size of degrees */
623 (*degrees)[node] = 0;
624
625 ++(*degrees)[node];
626 ++(*degrees)[parentnode];
627 ++(*nnonlinearedges);
628 }
629
630 /* add a filler node since it will be removed in the next iteration anyway */
633
636#ifndef NDEBUG
637 ++currentlevel;
638#endif
639
640 break;
641 }
642 }
643 /* for all other expressions, no nodes or edges have to be created */
644 else
645 {
646 /* do nothing here */
647 }
648
649 /* if this is the root expression, add the constraint side node (will be parent of expression node) */
651 {
652 /* add the constraint side node */
653 parentnode = (*nnodes)++;
654 ++(*nnonlinearnodes);
655
656 /* ensure size of degrees */
658 (*degrees)[parentnode] = 0;
659 }
660 /* otherwise, get the parentnode stored in visitednodes */
661 else
662 {
665 }
666
667 /* in all cases apart from variable expressions, the new node is added with the corresponding color */
668 if ( ! isVarExpr )
669 {
670 node = (*nnodes)++;
671 ++(*nnonlinearnodes);
672
673 /* ensure size of degrees */
675 (*degrees)[node] = 0;
676 }
677
678 /* store the new node so that it can be used as parentnode later */
681
682 assert( node != -1 );
685
686 /* connect the current node with its parent */
687 assert( parentnode != -1 );
688 ++(*degrees)[node];
689 ++(*degrees)[parentnode];
690 ++(*nnonlinearedges);
691
692 /* for sum expression, also add intermediate nodes for the coefficients */
693 if ( SCIPisExprSum(scip, expr) )
694 {
695 SCIP_Real constval;
696 int internode;
697
698 /* iterate over children from last to first, such that visitednodes array is in correct order */
699 for (j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
700 {
701 /* add the intermediate node with the corresponding color */
702 internode = (*nnodes)++;
703 ++(*nnonlinearnodes);
704
707
710
711 /* ensure size of degrees */
713 (*degrees)[internode] = 0;
714
715 ++(*degrees)[internode];
716 ++(*degrees)[node];
717 ++(*nnonlinearedges);
718 }
719
720 /* add node for the constant term of the sum expression */
722 if ( constval != 0.0 )
723 {
724 /* add the node with a new color */
725 internode = (*nnodes)++;
726 ++(*nnonlinearnodes);
727
728 /* ensure size of degrees */
730 (*degrees)[internode] = 0;
731
732 ++(*degrees)[internode];
733 ++(*degrees)[node];
734 ++(*nnonlinearedges);
735 }
736 }
737
738#ifndef NDEBUG
739 ++currentlevel;
740#endif
741 break;
742 }
743 /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
745 {
748#ifndef NDEBUG
749 currentlevel--;
750#endif
751
752 /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
753 * used for the coefficients of summands
754 */
756 {
759 }
760
761 break;
762 }
763
764 default:
765 SCIPABORT(); /* we should never be called in this stage */
766 break;
767 }
768 }
769
770 assert( currentlevel == 0 );
771 assert( numvisitednodes == 0 );
772 assert( numischildofsum == 0 );
773 }
774 SCIPfreeBlockMemoryArrayNull(scip, &vals, varssize);
776
780 }
781
782 *nedges = *nlinearedges + *nnonlinearedges;
783 assert( *nnodes == matrixdata->npermvars + matrixdata->nrhscoef + *nlinearnodes + *nnonlinearnodes );
784
785 SCIPdebugMsg(scip, "#nodes for variables: %d\n", matrixdata->npermvars);
786 SCIPdebugMsg(scip, "#nodes for rhs: %d\n", matrixdata->nrhscoef);
787 SCIPdebugMsg(scip, "#intermediate nodes for linear constraints: %d\n", *nlinearnodes);
788 SCIPdebugMsg(scip, "#intermediate nodes for nonlinear constraints: %d\n", *nnonlinearnodes);
789 SCIPdebugMsg(scip, "#edges for linear constraints: %d\n", *nlinearedges);
790 SCIPdebugMsg(scip, "#edges for nonlinear constraints: %d\n", *nnonlinearedges);
791
792 return SCIP_OKAY;
793}
794
795
796/** Construct linear and nonlinear part of colored graph for symmetry computations
797 *
798 * Construct linear graph:
799 * - Each variable gets a different node.
800 * - Each constraint gets a different node.
801 * - Each matrix coefficient gets a different node that is connected to the two nodes
802 * corresponding to the respective constraint and variable.
803 * - Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.
804 *
805 * Construct nonlinear graph:
806 * - Each node of the expression trees gets a different node.
807 * - Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
808 * - Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
809 *
810 * @note: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs
811 * and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different
812 * formulations of the same constraints would not be detected as equivalent, e.g. for
813 * 0 <= x1 + x2 <= 1
814 * 0 <= x3 + x4
815 * x3 + x4 <= 1
816 * there would be no symmetry between (x1,x2) and (x3,x4) detected.
817 *
818 * Each different constraint (sides), sum-expression coefficient, constant and operator type gets a
819 * different color that is attached to the corresponding entries.
820 */
821static
823 SCIP* scip, /**< SCIP instance */
824 sassy::static_graph* G, /**< graph to be constructed */
825 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
826 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
827 int nnodes, /**< total number of nodes in graph */
828 int nedges, /**< total number of edges in graph */
829 int nlinearnodes, /**< number of intermediate nodes for linear constraints */
830 int nnonlinearnodes, /**< number of intermediate nodes for nonlinear constraints */
831 int nlinearedges, /**< number of intermediate edges for linear constraints */
832 int nnonlinearedges, /**< number of intermediate edges for nonlinear constraints */
833 int* degrees, /**< array with the degrees of the nodes */
834 int* nusedcolors /**< pointer to store number of used colors in the graph so far */
835 )
836{
845 SCIP_CONSHDLR* conshdlr;
846 SCIP_CONS** conss;
848 SCIP_Bool* ischildofsum = NULL;
849 SCIP_VAR** vars = NULL;
850 SCIP_Real* vals = NULL;
851 SCIP_Bool groupByConstraints;
852 int* internodes = NULL;
853 int* visitednodes = NULL;
854 int maxischildofsum;
855 int maxvisitednodes;
856 int numvisitednodes = 0;
857 int numischildofsum = 0;
858 int nconss;
859 int nuniqueops = 0;
860 int nuniqueconsts = 0;
861 int nuniquecoefs = 0;
862 int nuniquerhs = 0;
863 int oparraysize;
864 int constarraysize;
865 int coefarraysize;
866 int rhsarraysize;
867 int nmaxinternodes;
868 int oldcolor = -1;
869 int varssize;
870#ifndef NDEBUG
871 SCIP_Real oldcoef = SCIP_INVALID;
872 int m = 0;
873#endif
874 int firstcolornodenumber = -1;
875 int n = 0;
876 int i;
877 int j;
878
879 assert( scip != NULL );
880 assert( G != NULL );
881 assert( matrixdata != NULL );
882 assert( exprdata != NULL );
883 assert( degrees != NULL );
884 assert( nusedcolors != NULL );
885
886 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for linear part.\n");
887
888 /* fill in array with colors for variables */
889 for (j = 0; j < matrixdata->npermvars; ++j)
890 {
891 assert( 0 <= matrixdata->permvarcolors[j] && matrixdata->permvarcolors[j] < matrixdata->nuniquevars );
892 (void) G->add_vertex(matrixdata->permvarcolors[j], degrees[n]);
893 ++n;
894 }
895 *nusedcolors = matrixdata->nuniquevars;
896
897 /* fill in array with colors for rhs */
898 for (i = 0; i < matrixdata->nrhscoef; ++i)
899 {
900 assert( 0 <= matrixdata->rhscoefcolors[i] && matrixdata->rhscoefcolors[i] < matrixdata->nuniquerhs );
901 (void) G->add_vertex(*nusedcolors + matrixdata->rhscoefcolors[i], degrees[n]);
902 ++n;
903 }
904 *nusedcolors += matrixdata->nuniquerhs;
905
906 /* Grouping of nodes depends on the number of nodes in the bipartite graph class. If there are more variables than
907 * constraints, we group by constraints. That is, given several variable nodes which are incident to one constraint
908 * node by the same color, we join these variable nodes to the constraint node by only one intermediate node.
909 */
910 if ( matrixdata->nrhscoef < matrixdata->npermvars )
912 else
914
915 /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
916 if ( groupByConstraints )
917 nmaxinternodes = matrixdata->nrhscoef;
918 else
919 nmaxinternodes = matrixdata->npermvars;
920
922 for (j = 0; j < nmaxinternodes; ++j)
923 internodes[j] = -1;
924
925 /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
926 * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
927 * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
928 * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
929 for (j = 0; j < matrixdata->nmatcoef; ++j)
930 {
931 int idx;
932 int color;
933 int rhsnode;
934 int varnode;
935 int varrhsidx;
936
937 idx = matrixdata->matidx[j];
938 assert( 0 <= idx && idx < matrixdata->nmatcoef );
939
940 /* find color corresponding to matrix coefficient */
941 color = matrixdata->matcoefcolors[idx];
942 assert( 0 <= color && color < matrixdata->nuniquemat );
943
944 assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
945 assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
946
947 rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
948 varnode = matrixdata->matvaridx[idx];
949 assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
950 assert( rhsnode < nnodes );
951 assert( varnode < nnodes );
952
953 /* if we have only one color, we do not need intermediate nodes */
954 if ( matrixdata->nuniquemat == 1 )
955 {
956 if ( rhsnode < varnode )
957 G->add_edge((unsigned) rhsnode, (unsigned) varnode);
958 else
959 G->add_edge((unsigned) varnode, (unsigned) rhsnode);
960#ifndef NDEBUG
961 ++m;
962#endif
963 }
964 else
965 {
966 SCIP_Bool newinternode = FALSE;
967 int internode;
968
969 /* if new group of coefficients has been reached */
970 if ( color != oldcolor )
971 {
972 assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
973 oldcolor = color;
975#ifndef NDEBUG
976 oldcoef = matrixdata->matcoef[idx];
977#endif
978 }
979 else
980 assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
981
982 if ( groupByConstraints )
983 varrhsidx = matrixdata->matrhsidx[idx];
984 else
985 varrhsidx = matrixdata->matvaridx[idx];
987
989 {
990 (void) G->add_vertex(*nusedcolors + color, degrees[n]);
991 internodes[varrhsidx] = n++;
993 }
995 assert( internode >= matrixdata->npermvars + matrixdata->nrhscoef );
998
999 if ( groupByConstraints )
1000 {
1001 if ( newinternode )
1002 {
1003 G->add_edge((unsigned) rhsnode, (unsigned) internode);
1004#ifndef NDEBUG
1005 ++m;
1006#endif
1007 }
1008 G->add_edge((unsigned) varnode, (unsigned) internode);
1009#ifndef NDEBUG
1010 ++m;
1011#endif
1012 }
1013 else
1014 {
1015 if ( newinternode )
1016 {
1017 G->add_edge((unsigned) varnode, (unsigned) internode);
1018#ifndef NDEBUG
1019 ++m;
1020#endif
1021 }
1022 G->add_edge((unsigned) rhsnode, (unsigned) internode);
1023#ifndef NDEBUG
1024 ++m;
1025#endif
1026 }
1027 }
1028 }
1029 assert( n == matrixdata->npermvars + matrixdata->nrhscoef + nlinearnodes );
1030 assert( m == nlinearedges );
1031
1033
1034 *nusedcolors += matrixdata->nuniquemat;
1035
1036 /* ------------------------------------------------------------------------ */
1037 /* treat nonlinear constraints */
1038 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
1039 nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
1040 if ( nconss == 0 )
1041 {
1042 return SCIP_OKAY;
1043 }
1044
1045 conss = SCIPconshdlrGetConss(conshdlr);
1046 rhsarraysize = nconss;
1047
1048 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for non-linear part.\n");
1049
1050 /* create maps for optypes, constants, sum coefficients and rhs to indices */
1051 oparraysize = exprdata->nuniqueoperators;
1052 constarraysize = exprdata->nuniqueconstants;
1053 coefarraysize = exprdata->nuniquecoefs;
1054
1063
1064 assert( optypemap != NULL );
1065 assert( consttypemap != NULL );
1066 assert( sumcoefmap != NULL );
1067 assert( rhstypemap != NULL );
1068
1069 /* allocate space for mappings from optypes, constants, sum coefficients and rhs to colors */
1074
1076
1081
1082 /* get number of variables */
1083 varssize = SCIPgetNVars(scip);
1084
1085 /* iterate over all expressions and add the corresponding nodes to the graph */
1086 for (i = 0; i < nconss; ++i)
1087 {
1089 SCIP_EXPR* expr;
1090 int currentlevel = 0;
1091
1093
1096
1097 for (expr = SCIPexpriterGetCurrent(it); ! SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
1098 {
1099 /* upon entering an expression, check its type and add nodes and edges if neccessary */
1100 switch ( SCIPexpriterGetStageDFS(it) )
1101 {
1103 {
1104 int node = -1;
1105 int parentnode = -1;
1106 int color = -1;
1107
1108 /* for variable expressions, get the corresponding node that is already in the graph */
1109 if ( SCIPisExprVar(scip, expr) )
1110 {
1111 SCIP_VAR* var;
1112
1113 var = SCIPgetVarExprVar(expr);
1114
1115 /* Check whether the variable is active; if not, then replace the inactive variable by its aggregation
1116 * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
1117 * expression.
1118 */
1119 if ( SCIPvarIsActive(var) )
1120 {
1121 node = SCIPvarGetProbindex(var);
1122 assert( node < nnodes );
1123 }
1124 else
1125 {
1126 SCIP_Real constant = 0.0;
1127 int nvars;
1128 int requiredsize;
1129 int k;
1130
1131 if ( vars == NULL )
1132 {
1134 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vals, varssize) );
1135 }
1136 assert( vars != NULL && vals != NULL );
1137
1138 vars[0] = var;
1139 vals[0] = 1.0;
1140 nvars = 1;
1141
1142 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &nvars, varssize, &constant, &requiredsize, TRUE) );
1143 assert( requiredsize <= varssize );
1144
1145 assert( numvisitednodes > 0 );
1146
1149
1150 /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
1151 for (k = 0; k < nvars; ++k)
1152 {
1154 int internode;
1155
1156 assert( vars[k] != NULL );
1157 assert( vals[k] != 0.0 );
1158 assert( nuniquecoefs < coefarraysize );
1159
1160 ct = &sumcoefarray[nuniquecoefs];
1161 ct->value = vals[k];
1162
1163 if ( ! SCIPhashtableExists(sumcoefmap, (void *) ct) )
1164 {
1166 ct->color = (*nusedcolors)++;
1167 color = ct->color;
1168 nuniquecoefs++;
1169 }
1170 else
1171 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
1172
1173 /* add the intermediate node with the corresponding color */
1174 (void) G->add_vertex(color, degrees[n]);
1175 internode = n++;
1176
1177 assert( internode < nnodes );
1178
1179 G->add_edge((unsigned) parentnode, (unsigned) internode);
1180#ifndef NDEBUG
1181 ++m;
1182#endif
1183 assert( m <= nedges );
1184
1185 /* connect the intermediate node to its corresponding variable node */
1186 node = SCIPvarGetProbindex(vars[k]);
1187 assert( node < nnodes );
1188
1189 G->add_edge((unsigned) node, (unsigned) internode);
1190#ifndef NDEBUG
1191 ++m;
1192#endif
1193 assert( m <= nedges );
1194 }
1195
1196 /* add the node for the constant */
1197 if ( constant != 0.0 )
1198 {
1200
1201 /* check whether we have to resize */
1204
1206 ct->value = constant;
1207
1208 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1209 {
1211 ct->color = (*nusedcolors)++;
1212 color = ct->color;
1213 nuniqueconsts++;
1214 }
1215 else
1216 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1217
1218 /* add the node with a new color */
1219 (void) G->add_vertex(color, degrees[n]);
1220 node = n++;
1221
1222 assert( node < nnodes );
1223
1224 G->add_edge((unsigned) parentnode, (unsigned) node);
1225#ifndef NDEBUG
1226 ++m;
1227#endif
1228 assert( m <= nedges );
1229 }
1230
1231 /* add a filler node since it will be removed in the next iteration anyway */
1234
1237 ++currentlevel;
1238
1239 break;
1240 }
1241 }
1242 /* for constant expressions, get the color of its type (value) or assign a new one */
1243 else if ( SCIPisExprValue(scip, expr) )
1244 {
1246
1248
1250 ct->value = SCIPgetValueExprValue(expr);
1251
1252 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1253 {
1255 ct->color = (*nusedcolors)++;
1256 color = ct->color;
1257 nuniqueconsts++;
1258 }
1259 else
1260 {
1261 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1262 }
1263 }
1264 /* for all other expressions, get the color of its operator type or assign a new one */
1265 else
1266 {
1267 SYM_OPTYPE* ot;
1268
1270
1272
1273 ot->expr = expr;
1274 ot->level = currentlevel;
1275
1276 if ( ! SCIPhashtableExists(optypemap, (void *) ot) )
1277 {
1279 ot->color = (*nusedcolors)++;
1280 color = ot->color;
1281 nuniqueops++;
1282 }
1283 else
1284 color = ((SYM_OPTYPE*) SCIPhashtableRetrieve(optypemap, (void *) ot))->color;
1285 }
1286
1287 /* if this is the root expression, add the constraint side node (will be parent of expression node) */
1289 {
1290 /* add the node corresponding to the constraint */
1291 SYM_RHSTYPE* rt;
1292 int parentcolor;
1293
1294 assert( nuniquerhs < rhsarraysize );
1295
1296 rt = &uniquerhsarray[nuniquerhs];
1297 rt->lhs = SCIPgetLhsNonlinear(conss[i]);
1298 rt->rhs = SCIPgetRhsNonlinear(conss[i]);
1299
1300 if ( ! SCIPhashtableExists(rhstypemap, (void *) rt) )
1301 {
1303 rt->color = (*nusedcolors)++;
1304 parentcolor = rt->color;
1305 nuniquerhs++;
1306 }
1307 else
1309
1310 /* add the constraint side node with the corresponding color */
1311 (void) G->add_vertex(parentcolor, degrees[n]);
1312 parentnode = n++;
1314 }
1315 /* otherwise, get the parentnode stored in visitednodes */
1316 else
1317 {
1320 }
1321
1322 /* in all cases apart from variable expressions, the new node is added with the corresponding color */
1323 if ( color != -1 )
1324 {
1325 (void) G->add_vertex(color, degrees[n]);
1326 node = n++;
1327 assert( node < nnodes );
1328 assert( n <= nnodes );
1329 }
1330
1331 /* store the new node so that it can be used as parentnode later */
1334
1335 assert( node != -1 );
1336 visitednodes[numvisitednodes++] = node;
1338
1339 /* connect the current node with its parent */
1340 assert( parentnode != -1 );
1341
1342 if ( parentnode < node )
1343 G->add_edge((unsigned) parentnode, (unsigned) node);
1344 else
1345 G->add_edge((unsigned) node, (unsigned) parentnode);
1346#ifndef NDEBUG
1347 ++m;
1348#endif
1349 assert( m <= nedges );
1350
1351 /* for sum expression, also add intermediate nodes for the coefficients */
1352 if ( SCIPisExprSum(scip, expr) )
1353 {
1354 SCIP_Real* coefs;
1355 SCIP_Real constval;
1356 int internode;
1357
1358 coefs = SCIPgetCoefsExprSum(expr);
1359
1360 /* iterate over children from last to first, such that visitednodes array is in correct order */
1361 for (j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
1362 {
1364
1365 assert( nuniquecoefs < coefarraysize );
1366
1367 ct = &sumcoefarray[nuniquecoefs];
1368 ct->value = coefs[j];
1369
1370 if ( ! SCIPhashtableExists(sumcoefmap, (void *) ct) )
1371 {
1373 ct->color = (*nusedcolors)++;
1374 color = ct->color;
1375 nuniquecoefs++;
1376 }
1377 else
1378 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
1379
1380 /* add the intermediate node with the corresponding color */
1381 (void) G->add_vertex(color, degrees[n]);
1382 internode = n++;
1383
1386
1389
1390 assert( internode < nnodes );
1391
1392 G->add_edge((unsigned) node, (unsigned) internode);
1393#ifndef NDEBUG
1394 ++m;
1395#endif
1396 assert( m <= nedges );
1397 }
1398
1399 /* add node for the constant term of the sum expression */
1401 if ( constval != 0.0 )
1402 {
1404
1405 /* check whether we have to resize */
1408
1410 ct->value = constval;
1411
1412 if ( ! SCIPhashtableExists(consttypemap, (void *) ct) )
1413 {
1415 ct->color = (*nusedcolors)++;
1416 color = ct->color;
1417 nuniqueconsts++;
1418 }
1419 else
1420 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
1421
1422 /* add the node with a new color */
1423 (void) G->add_vertex(color, degrees[n]);
1424 internode = n++;
1425
1426 assert( node < nnodes );
1427
1428 G->add_edge((unsigned) node, (unsigned) internode);
1429#ifndef NDEBUG
1430 ++m;
1431#endif
1432 assert( m <= nedges );
1433 }
1434 }
1435
1436 ++currentlevel;
1437 break;
1438 }
1439 /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
1441 {
1444 currentlevel--;
1445
1446 /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
1447 * used for the coefficients of summands
1448 */
1450 {
1453 }
1454
1455 break;
1456 }
1457
1458 default:
1459 SCIPABORT(); /* we should never be called in this stage */
1460 break;
1461 }
1462 }
1463
1464 assert( currentlevel == 0 );
1465 assert( numvisitednodes == 0 );
1466 assert( numischildofsum == 0 );
1467 }
1468 assert( n == nnodes );
1469 assert( m == nedges );
1470 assert( n == matrixdata->npermvars + matrixdata->nrhscoef + nlinearnodes + nnonlinearnodes );
1472
1473 /* free everything */
1474 SCIPfreeBlockMemoryArrayNull(scip, &vals, varssize);
1476
1488
1489 return SCIP_OKAY;
1490}
1491
1492/** return whether symmetry can be computed */
1494{
1495 return TRUE;
1496}
1497
1498/** return name of external program used to compute generators */
1499char*
1501{
1502 char* blissname = new char[100];
1503#ifdef BLISS_PATCH_PRESENT
1504 (void) SCIPsnprintf(blissname, 100, "bliss %sp", bliss::version);
1505#else
1506 (void) SCIPsnprintf(blissname, 100, "bliss %s", bliss::version);
1507#endif
1508 return blissname;
1509}
1510
1511/** return name of external program used to compute generators */
1512char*
1514{
1515 char* sassyname = new char[100];
1517 return sassyname;
1518}
1519
1522
1523/** return name of external program used to compute generators */
1524const char* SYMsymmetryGetName(void)
1525{
1526 return symmetryname;
1527}
1528
1529/** return description of external program used to compute generators */
1530const char* SYMsymmetryGetDesc(void)
1531{
1532 return "Computing Graph Automorphisms by T. Junttila and P. Kaski (users.aalto.fi/~tjunttil/bliss/)";
1533}
1534
1535/** return name of additional external program used for computing symmetries */
1536const char* SYMsymmetryGetAddName(void)
1537{
1538 return symmetryaddname;
1539}
1540
1541/** return description of additional external program used to compute symmetries */
1542const char* SYMsymmetryGetAddDesc(void)
1543{
1544 return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
1545}
1546
1547/** compute generators of symmetry group */
1549 SCIP* scip, /**< SCIP pointer */
1550 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1551 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
1552 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
1553 int* nperms, /**< pointer to store number of permutations */
1554 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1555 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1556 SCIP_Real* log10groupsize, /**< pointer to store size of group */
1557 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
1558 )
1559{
1560 SCIP_Real oldtime;
1561 SCIP_Bool success = FALSE;
1562 int* degrees;
1563 int maxdegrees;
1564 int nnodes;
1565 int nedges;
1566 int nlinearnodes;
1567 int nnonlinearnodes;
1568 int nlinearedges;
1569 int nnonlinearedges;
1570 int nusedcolors;
1571
1572 assert( scip != NULL );
1573 assert( matrixdata != NULL );
1574 assert( exprdata != NULL );
1575 assert( nperms != NULL );
1576 assert( nmaxperms != NULL );
1577 assert( perms != NULL );
1578 assert( log10groupsize != NULL );
1579 assert( maxgenerators >= 0 );
1580 assert( symcodetime != NULL );
1581
1582 /* init */
1583 *nperms = 0;
1584 *nmaxperms = 0;
1585 *perms = NULL;
1586 *log10groupsize = 0;
1587 *symcodetime = 0.0;
1588
1589 /* determine number of nodes and edges */
1592 &degrees, &maxdegrees, &success) );
1593
1594 if ( ! success )
1595 {
1596 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Stopped symmetry computation: Symmetry graph would become too large.\n");
1597 return SCIP_OKAY;
1598 }
1599
1600 /* create sassy graph */
1601 sassy::static_graph sassygraph;
1602
1603 /* init graph */
1604 sassygraph.initialize_graph((unsigned) nnodes, (unsigned) nedges);
1605
1606 /* add the nodes for linear and nonlinear constraints to the graph */
1609 degrees, &nusedcolors) );
1610
1612
1613 SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
1614
1615 /* init data */
1616 struct SYMMETRY_Data data;
1617 data.scip = scip;
1618 data.npermvars = matrixdata->npermvars;
1619 data.nperms = 0;
1620 data.nmaxperms = 0;
1622 data.perms = NULL;
1623
1625
1626 /* set up sassy preprocessor */
1627 sassy::preprocessor sassy;
1628
1629 /* turn off some preprocessing that generates redudant permutations */
1630 sassy::configstruct sconfig;
1631 sconfig.CONFIG_PREP_DEACT_PROBE = true;
1632 sassy.configure(&sconfig);
1633
1634 /* lambda function to have access to data and pass it to sassyhook above */
1635 sassy::sassy_hook sassyglue = [&](int n, const int* p, int nsupp, const int* suppa) {
1636 sassyhook((void*)&data, n, p, nsupp, suppa);
1637 };
1638
1639 /* call sassy to reduce graph */
1640 sassy.reduce(&sassygraph, &sassyglue);
1641
1642 /* create bliss graph */
1643 bliss::Graph blissgraph(0);
1644
1645 /* convert sassy to bliss graph */
1647
1648#ifdef SCIP_OUTPUT
1649 blissgraph.write_dot("debug.dot");
1650#endif
1651
1652#ifdef SCIP_DISABLED_CODE
1653 char filename[SCIP_MAXSTRLEN];
1654 (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s.dimacs", SCIPgetProbName(scip));
1655 FILE* fp = fopen(filename, "w");
1656 if ( fp )
1657 {
1658 blissgraph.write_dimacs(fp);
1659 fclose(fp);
1660 }
1661#endif
1662
1663
1664 /* compute automorphisms */
1665 bliss::Stats stats;
1666
1667 /* Prefer splitting partition cells corresponding to variables over those corresponding
1668 * to inequalities. This is because we are only interested in the action
1669 * of the automorphism group on the variables, and we need a base for this action */
1670 blissgraph.set_splitting_heuristic(bliss::Graph::shs_f);
1671 /* disable component recursion as advised by Tommi Junttila from bliss */
1672 blissgraph.set_component_recursion(false);
1673
1674 /* do not use a node limit, but set generator limit */
1675#ifdef BLISS_PATCH_PRESENT
1676 blissgraph.set_search_limits(0, (unsigned) maxgenerators);
1677#endif
1678
1679#if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
1680 /* lambda function to have access to stats and terminate the search if maxgenerators are reached */
1681 auto term = [&]() {
1682 return (stats.get_nof_generators() >= (unsigned) maxgenerators);
1683 };
1684
1685 auto hook = [&](unsigned int n, const unsigned int* aut) {
1686 sassy.bliss_hook(n, aut);
1687 };
1688
1689 /* start search */
1690 blissgraph.find_automorphisms(stats, hook, term);
1691#else
1692 /* start search */
1693 blissgraph.find_automorphisms(stats, sassy::preprocessor::bliss_hook, (void*) &sassy);
1694#endif
1696
1697#ifdef SCIP_OUTPUT
1698 (void) stats.print(stdout);
1699#endif
1700
1701 /* prepare return values */
1702 if ( data.nperms > 0 )
1703 {
1704 *perms = data.perms;
1705 *nperms = data.nperms;
1706 *nmaxperms = data.nmaxperms;
1707 }
1708 else
1709 {
1710 assert( data.perms == NULL );
1711 assert( data.nmaxperms == 0 );
1712 }
1713
1714 /* determine log10 of symmetry group size */
1715 *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
1716
1717 return SCIP_OKAY;
1718}
interface for symmetry computations
static char * blissname
const char * SYMsymmetryGetName(void)
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)
char * initStaticSymmetryName()
static SCIP_RETCODE fillGraphByConss(SCIP *scip, sassy::static_graph *G, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int nnodes, int nedges, int nlinearnodes, int nnonlinearnodes, int nlinearedges, int nnonlinearedges, int *degrees, int *nusedcolors)
static const char * symmetryname
const char * SYMsymmetryGetAddName(void)
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)
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
char * initStaticSymmetryAddName()
const char * SYMsymmetryGetAddDesc(void)
static const char * symmetryaddname
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_MAXSTRLEN
Definition def.h:302
#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)
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
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
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
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
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