SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
compute_symmetry_bliss.cpp
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file compute_symmetry_bliss.cpp
26 * @brief interface for symmetry computations to bliss
27 * @author Marc Pfetsch
28 * @author Thomas Rehn
29 * @author Fabian Wegscheider
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include "compute_symmetry.h"
35
36/* include bliss graph */
37#include <bliss/defs.hh>
38#include <bliss/graph.hh>
39
40#include <string.h>
41#include <vector>
42#include <list>
43#include <math.h>
44
45#include "scip/expr_var.h"
46#include "scip/expr_sum.h"
47#include "scip/expr_pow.h"
48#include "scip/expr.h"
49#include "scip/cons_nonlinear.h"
50#include "scip/cons_linear.h"
51
52using std::vector;
53
54
55/** struct for bliss callback */
57{
58 SCIP* scip; /**< SCIP pointer */
59 int npermvars; /**< number of variables for permutations */
60 int nperms; /**< number of permutations */
61 int** perms; /**< permutation generators as (nperms x npermvars) matrix */
62 int nmaxperms; /**< maximal number of permutations */
63 int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
64};
65
66/* ------------------- map for operator types ------------------- */
67
68/** gets the key of the given element */
69static
71{ /*lint --e{715}*/
72 return elem;
73}
74
75/** returns TRUE iff both keys are equal
76 *
77 * Compare the types of two operators according to their name, level and, in case of power, exponent.
78 */
79static
81{
84
85 k1 = (SYM_OPTYPE*) key1;
86 k2 = (SYM_OPTYPE*) key2;
87
88 /* first check operator name */
89 if ( SCIPexprGetHdlr(k1->expr) != SCIPexprGetHdlr(k2->expr) )
90 return FALSE;
91
92 /* for pow expressions, also check exponent (TODO should that happen for signpow as well?) */
93 if ( SCIPisExprPower((SCIP*)userptr, k1->expr )
94 && SCIPgetExponentExprPow(k1->expr) != SCIPgetExponentExprPow(k2->expr) ) /*lint !e777*/
95 return FALSE;
96
97 /* if still undecided, take level */
98 if ( k1->level != k2->level )
99 return FALSE;
100
101 return TRUE;
102}
103
104/** returns the hash value of the key */
105static
107{ /*lint --e{715}*/
108 SYM_OPTYPE* k;
109 SCIP_Real exponent;
110
111 k = (SYM_OPTYPE*) key;
112
113 if ( SCIPisExprPower((SCIP*)userptr, k->expr) )
114 exponent = SCIPgetExponentExprPow(k->expr);
115 else
116 exponent = 1.0;
117
118 return SCIPhashThree(SCIPrealHashCode(exponent), k->level,
119 SCIPhashKeyValString(NULL, static_cast<void*>(const_cast<char*>(SCIPexprhdlrGetName(SCIPexprGetHdlr(k->expr))))));
120}
121
122/* ------------------- map for constant types ------------------- */
123
124/** gets the key of the given element */
125static
127{ /*lint --e{715}*/
128 return elem;
129}
130
131/** returns TRUE iff both keys are equal
132 *
133 * Compare two constants according to their values.
134 */
135static
137{
140
141 k1 = (SYM_CONSTTYPE*) key1;
142 k2 = (SYM_CONSTTYPE*) key2;
143
144 return (SCIP_Bool)(k1->value == k2->value); /*lint !e777*/
145}
146
147/** returns the hash value of the key */
148static
150{ /*lint --e{715}*/
152
153 k = (SYM_CONSTTYPE*) key;
154
155 return SCIPrealHashCode(k->value);
156}
157
158/* ------------------- map for constraint side types ------------------- */
159
160/** gets the key of the given element */
161static
163{ /*lint --e{715}*/
164 return elem;
165}
166
167/** returns TRUE iff both keys are equal
168 *
169 * Compare two constraint sides according to lhs and rhs.
170 */
171static
173{
176
177 k1 = (SYM_RHSTYPE*) key1;
178 k2 = (SYM_RHSTYPE*) key2;
179
180 if ( k1->lhs != k2->lhs ) /*lint !e777*/
181 return FALSE;
182
183 return (SCIP_Bool)(k1->rhs == k2->rhs); /*lint !e777*/
184}
185
186/** returns the hash value of the key */
187static
189{ /*lint --e{715}*/
190 SYM_RHSTYPE* k;
191
192 k = (SYM_RHSTYPE*) key;
193
194 return SCIPhashTwo(SCIPrealHashCode(k->lhs), SCIPrealHashCode(k->rhs));
195}
196
197/** callback function for bliss */
198static
200 void* user_param, /**< parameter supplied at call to bliss */
201 unsigned int n, /**< size of aut vector */
202 const unsigned int* aut /**< automorphism */
203 )
204{
205 assert( aut != NULL );
206 assert( user_param != NULL );
207
208 BLISS_Data* data = static_cast<BLISS_Data*>(user_param);
209 assert( data->scip != NULL );
210 assert( data->npermvars < (int) n );
211 assert( data->maxgenerators >= 0);
212
213 /* make sure we do not generate more that maxgenerators many permutations, if the limit in bliss is not available */
214 if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
215 return;
216
217 /* copy first part of automorphism */
218 bool isIdentity = true;
219 int* p = 0;
220 if ( SCIPallocBlockMemoryArray(data->scip, &p, data->npermvars) != SCIP_OKAY )
221 return;
222
223 for (int j = 0; j < data->npermvars; ++j)
224 {
225 /* convert index of variable-level 0-nodes to variable indices */
226 p[j] = (int) aut[j];
227 if ( p[j] != j )
228 isIdentity = false;
229 }
230
231 /* ignore trivial generators, i.e. generators that only permute the constraints */
232 if ( isIdentity )
233 {
235 return;
236 }
237
238 /* check whether we should allocate space for perms */
239 if ( data->nmaxperms <= 0 )
240 {
241 if ( data->maxgenerators == 0 )
242 data->nmaxperms = 100; /* seems to cover many cases */
243 else
244 data->nmaxperms = data->maxgenerators;
245
246 if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
247 return;
248 }
249 else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
250 {
251 int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
252 assert( newsize >= data->nperms );
253 assert( data->maxgenerators == 0 );
254
255 if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
256 return;
257
258 data->nmaxperms = newsize;
259 }
260
261 data->perms[data->nperms++] = p;
262}
263
264/** Creates the nodes in the graph that correspond to variables. Each variable type gets a unique color
265 *
266 * @pre graph should be empty when this is called
267 */
268static
270 SCIP* scip, /**< SCIP instance */
271 bliss::Graph* G, /**< Graph to be constructed */
272 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix (also contains the relevant variables) */
273 int& nnodes, /**< returns number of nodes in graph */
274 int& nusedcolors /**< returns number of used colors */
275 )
276{
277 assert( scip != NULL );
278 assert( G != NULL );
279 assert( matrixdata != NULL );
280 assert( nnodes == 0 );
281 assert( nusedcolors == 0 );
282 SCIPdebugMsg(scip, "Creating graph with colored nodes for variables.\n");
283
284 /* add nodes for variables */
285 for (int v = 0; v < matrixdata->npermvars; ++v)
286 {
287 const int color = matrixdata->permvarcolors[v];
288 assert( 0 <= color && color < matrixdata->nuniquevars );
289
290#ifndef NDEBUG
291 int node = (int) G->add_vertex((unsigned) color);
292 assert( node == v );
293#else
294 (void) G->add_vertex((unsigned) color);
295#endif
296
297 ++nnodes;
298 }
299
300 /* this is not exactly true, since we skip auxvars, but it doesn't matter if some colors are not used at all */
301 nusedcolors = matrixdata->nuniquevars;
302
303 return SCIP_OKAY;
304}
305
306/** Construct linear part of colored graph for symmetry computations
307 *
308 * Construct graph:
309 * - Each variable gets a different node.
310 * - Each constraint gets a different node.
311 * - Each matrix coefficient gets a different node that is connected to the two nodes
312 * corresponding to the respective constraint and variable.
313 *
314 * Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.
315 *
316 * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
317 * their node number is equal to their index.
318 */
319static
321 SCIP* scip, /**< SCIP instance */
322 bliss::Graph* G, /**< Graph to be constructed */
323 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
324 int& nnodes, /**< number of nodes in graph */
325 int& nedges, /**< number of edges in graph */
326 int& nusedcolors, /**< number of used colors */
327 SCIP_Bool& success /**< whether the construction was successful */
328 )
329{
330 assert( nnodes == (int) G->get_nof_vertices() );
332
333 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for linear part.\n");
334
335 success = TRUE;
336
337 /* add nodes for rhs of constraints */
338 for (int c = 0; c < matrixdata->nrhscoef; ++c)
339 {
340 const int color = matrixdata->rhscoefcolors[c];
341 assert( 0 <= color && color < matrixdata->nuniquerhs );
342
343#ifndef NDEBUG
344 int node = (int) G->add_vertex((unsigned) (nusedcolors + color));
345 assert( node == matrixdata->npermvars + c );
346#else
347 (void) G->add_vertex((unsigned) (nusedcolors + color));
348#endif
349
350 ++nnodes;
351 }
352 assert( (int) G->get_nof_vertices() == matrixdata->npermvars + matrixdata->nrhscoef );
353 nusedcolors += matrixdata->nuniquerhs;
354
355 /* Grouping of nodes depends on the number of nodes in the bipartite graph class.
356 * If there are more variables than constraints, we group by constraints.
357 * That is, given several variable nodes which are incident to one constraint node by the same color,
358 * we join these variable nodes to the constraint node by only one intermediate node.
359 */
360 const bool groupByConstraints = matrixdata->nrhscoef < matrixdata->npermvars;
361 if ( groupByConstraints )
362 SCIPdebugMsg(scip, "Group intermediate nodes by constraints.\n");
363 else
364 SCIPdebugMsg(scip, "Group intermediate nodes by variables.\n");
365
366 /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
367 int ninternodes;
368 if ( groupByConstraints )
369 ninternodes = matrixdata->nrhscoef;
370 else
371 ninternodes = matrixdata->npermvars;
372
373 int* internodes = NULL;
375 for (int l = 0; l < ninternodes; ++l)
376 internodes[l] = -1;
377
378 /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
379 * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
380 * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
381 * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
382 int oldcolor = -1;
383#ifndef NDEBUG
384 SCIP_Real oldcoef = SCIP_INVALID;
385#endif
386 int firstcolornodenumber = -1;
387 for (int j = 0; j < matrixdata->nmatcoef; ++j)
388 {
389 int idx = matrixdata->matidx[j];
390 assert( 0 <= idx && idx < matrixdata->nmatcoef );
391
392 /* find color corresponding to matrix coefficient */
393 const int color = matrixdata->matcoefcolors[idx];
394 assert( 0 <= color && color < matrixdata->nuniquemat );
395
396 assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
397 assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
398
399 const int rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
400 const int varnode = matrixdata->matvaridx[idx];
401 assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
402 assert( rhsnode < (int) G->get_nof_vertices() );
403 assert( varnode < (int) G->get_nof_vertices() );
404
405 /* if we have only one color, we do not need intermediate nodes */
406 if ( matrixdata->nuniquemat == 1 )
407 {
408 G->add_edge((unsigned) varnode, (unsigned) rhsnode);
409 ++nedges;
410 }
411 else
412 {
413 /* if new group of coefficients has been reached */
414 if ( color != oldcolor )
415 {
416 assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
417 oldcolor = color;
419#ifndef NDEBUG
420 oldcoef = matrixdata->matcoef[idx];
421#endif
422 }
423 else
424 assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
425
426 int varrhsidx;
427 if ( groupByConstraints )
428 varrhsidx = matrixdata->matrhsidx[idx];
429 else
430 varrhsidx = matrixdata->matvaridx[idx];
432
433 SCIP_Bool newinternode = FALSE;
435 {
436 internodes[varrhsidx] = (int) G->add_vertex((unsigned) (nusedcolors + color));
437 ++nnodes;
439 }
441 assert( internode >= matrixdata->npermvars + matrixdata->nrhscoef );
444
445 /* determine whether graph would be too large for bliss (can only handle int) */
446 if ( nnodes >= INT_MAX/2 )
447 {
448 success = FALSE;
449 break;
450 }
451
452 if ( groupByConstraints )
453 {
454 if ( newinternode )
455 {
456 G->add_edge((unsigned) rhsnode, (unsigned) internode);
457 ++nedges;
458 }
459 G->add_edge((unsigned) varnode, (unsigned) internode);
460 ++nedges;
461 }
462 else
463 {
464 if ( newinternode )
465 {
466 G->add_edge((unsigned) varnode, (unsigned) internode);
467 ++nedges;
468 }
469 G->add_edge((unsigned) rhsnode, (unsigned) internode);
470 ++nedges;
471 }
472 }
473 }
474
475 nusedcolors += matrixdata->nuniquemat;
476
478 return SCIP_OKAY;
479}
480
481/** Construct non-linear part of colored graph for symmetry computations
482 *
483 * Construct graph:
484 * - Each node of the expression trees gets a different node.
485 * - Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
486 * - Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
487 *
488 * @note: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs
489 * and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different
490 * formulations of the same constraints would not be detected as equivalent, e.g. for
491 * 0 <= x1 + x2 <= 1
492 * 0 <= x3 + x4
493 * x3 + x4 <= 1
494 * there would be no symmetry between (x1,x2) and (x3,x4) detected.
495 *
496 * Each different constraint (sides), sum-expression coefficient, constant and operator type gets a
497 * different color that is attached to the corresponding entries.
498 *
499 * @pre This method assumes that the nodes corresponding to permutation variables are already in the graph and that
500 * their node number is equal to their index.
501 */
502static
504 SCIP* scip, /**< SCIP instance */
505 bliss::Graph* G, /**< Graph to be constructed */
506 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
507 int& nnodes, /**< number of nodes in graph */
508 int& nedges, /**< number of edges in graph */
509 int& nusedcolors, /**< number of colors in the graph so far */
510 SCIP_Bool& success /**< whether the construction was successful */
511 )
512{
521 SCIP_CONSHDLR* conshdlr;
522 SCIP_CONS** conss;
523 SCIP_VAR** vars = NULL;
524 SCIP_Real* vals = NULL;
525 int nvars;
526 int nconss;
527 int nuniqueops = 0;
528 int nuniqueconsts = 0;
529 int nuniquecoefs = 0;
530 int nuniquerhs = 0;
531 int oparraysize = exprdata->nuniqueoperators;
532 int constarraysize = exprdata->nuniqueconstants;
533 int coefarraysize = exprdata->nuniquecoefs;
534 int rhsarraysize;
535
536 assert( scip != NULL );
537 assert( G != NULL );
538 assert( exprdata != NULL );
539 assert( nnodes == (int) G->get_nof_vertices() );
541
542 success = TRUE; /*lint !e838*/
543
544 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
545 nconss = conshdlr != NULL ? SCIPconshdlrGetNConss(conshdlr) : 0;
546 if ( nconss == 0 )
547 return SCIP_OKAY;
548
549 conss = SCIPconshdlrGetConss(conshdlr);
550 rhsarraysize = nconss;
551
552 SCIPdebugMsg(scip, "Filling graph with colored coefficient nodes for non-linear part.\n");
553
554 /* create maps for optypes, constants, sum coefficients and rhs to indices */
563
564 assert( optypemap != NULL );
566 assert( sumcoefmap != NULL );
567 assert( rhstypemap != NULL );
568
569 /* allocate space for mappings from optypes, constants, sum coefficients and rhs to colors */
574
575 /* get number of variables */
577
580
581 /* iterate over all expressions and add the corresponding nodes to the graph */
582 for (int i = 0; i < nconss; ++i)
583 {
585 vector<int> visitednodes(0);
586 vector<SCIP_Bool> ischildofsum(0);
587 int currentlevel = 0;
588
590
593
594 for (SCIP_EXPR* expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
595 {
596 /* upon entering an expression, check its type and add nodes and edges if neccessary */
597 switch( SCIPexpriterGetStageDFS(it) )
598 {
600 {
601 int node = -1;
602 int parentnode = -1;
603 int color = -1;
604
605 /* for variable expressions, get the corresponding node that is already in the graph */
606 if ( SCIPisExprVar(scip, expr) )
607 {
609
610 /* check whether the variable is active; if not, then replace the inactive variable by its aggregation
611 * or its fixed value; note that this step is equivalent as representing an inactive variable as sum
612 * expression
613 */
614 if ( SCIPvarIsActive(var) )
615 {
616 node = SCIPvarGetProbindex(var);
617 assert( node < (int) G->get_nof_vertices() );
618 }
619 else
620 {
621 SCIP_Real constant = 0.0;
622 int varssize;
623 int requiredsize;
624 int k;
625
626 if ( vars == NULL )
627 {
630 }
631 assert( vars != NULL && vals != NULL );
632
633 vars[0] = var;
634 vals[0] = 1.0;
635
636 SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, vals, &varssize, nvars, &constant, &requiredsize, TRUE) );
638
640 assert( parentnode < (int) G->get_nof_vertices() );
641
642 /* create nodes for all aggregation variables and coefficients and connect them to the parent node */
643 for ( k = 0; k < requiredsize; ++k )
644 {
646 int internode;
647
648 assert( vars[k] != NULL );
649 assert( vals[k] != 0.0 );
650 assert( nuniquecoefs < coefarraysize );
651
652 ct = &sumcoefarray[nuniquecoefs];
653 ct->value = vals[k];
654
655 if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
656 {
658 ct->color = nusedcolors++;
659 color = ct->color;
660 nuniquecoefs++;
661 }
662 else
663 {
664 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
665 }
666
667 /* add the intermediate node with the corresponding color */
668 internode = (int) G->add_vertex((unsigned) color);
669 ++nnodes;
670
671 assert( internode < (int) G->get_nof_vertices() );
672
673 G->add_edge((unsigned) internode, (unsigned) parentnode);
674 ++nedges;
675
676 /* connect the intermediate node to its corresponding variable node */
677 node = SCIPvarGetProbindex(vars[k]);
678 assert( node < (int) G->get_nof_vertices() );
679
680 G->add_edge((unsigned) node, (unsigned) internode);
681 ++nedges;
682 }
683
684 /* add the node for the constant */
685 if ( constant != 0.0 )
686 {
688
689 /* check whether we have to resize */
691 {
693 assert( newsize >= 0 );
696 }
697
699
701 ct->value = constant;
702
703 if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
704 {
706 ct->color = nusedcolors++;
707 color = ct->color;
709 }
710 else
711 {
712 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
713 }
714
715 /* add the node with a new color */
716 node = (int) G->add_vertex((unsigned) color);
717 ++nnodes;
718
719 assert( node < (int) G->get_nof_vertices() );
720
721 G->add_edge((unsigned) node, (unsigned) parentnode);
722 ++nedges;
723 }
724
725 /* add a filler node since it will be removed in the next iteration anyway */
726 visitednodes.push_back(nnodes);
727 ischildofsum.push_back(FALSE);
728 ++currentlevel;
729
730 break;
731 }
732 }
733 /* for constant expressions, get the color of its type (value) or assign a new one */
734 else if ( SCIPisExprValue(scip, expr) )
735 {
737
739
741 ct->value = SCIPgetValueExprValue(expr);
742
743 if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
744 {
746 ct->color = nusedcolors++;
747 color = ct->color;
749 }
750 else
751 {
752 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
753 }
754 }
755 /* for all other expressions, get the color of its operator type or assign a new one */
756 else
757 {
758 SYM_OPTYPE* ot;
759
761
763
764 ot->expr = expr;
765 ot->level = currentlevel;
766
767 if ( !SCIPhashtableExists(optypemap, (void *) ot) )
768 {
770 ot->color = nusedcolors++;
771 color = ot->color;
772 nuniqueops++;
773 }
774 else
775 {
776 color = ((SYM_OPTYPE*) SCIPhashtableRetrieve(optypemap, (void *) ot))->color;
777 }
778 }
779
780 /* if this is the root expression, add the constraint side node (will be parent of expression node) */
782 {
783 /* add the node corresponding to the constraint */
785 int parentcolor;
786
787 assert( nuniquerhs < rhsarraysize );
788
789 rt = &uniquerhsarray[nuniquerhs];
790 rt->lhs = SCIPgetLhsNonlinear(conss[i]);
791 rt->rhs = SCIPgetRhsNonlinear(conss[i]);
792
793 if ( !SCIPhashtableExists(rhstypemap, (void *) rt) )
794 {
796 rt->color = nusedcolors++;
797 parentcolor = rt->color;
798 nuniquerhs++;
799 }
800 else
801 {
803 }
804
805 /* add the constraint side node with the corresponding color */
806 parentnode = (int) G->add_vertex((unsigned) parentcolor);
807 ++nnodes;
808
809 assert( parentnode < (int) G->get_nof_vertices() );
810 }
811 /* otherwise, get the parentnode stored in visitednodes */
812 else
813 {
815 assert( parentnode < (int) G->get_nof_vertices() );
816 }
817
818 /* in all cases apart from variable expressions, the new node is added with the corresponding color */
819 if ( color != -1 )
820 {
821 node = (int) G->add_vertex((unsigned) color);
822 ++nnodes;
823
824 assert( node < (int) G->get_nof_vertices() );
825 }
826
827 /* store the new node so that it can be used as parentnode later */
828 assert( node != -1 );
829 visitednodes.push_back(node);
830 ischildofsum.push_back(FALSE);
831
832 /* connect the current node with its parent */
833 assert( parentnode != -1 );
834 G->add_edge((unsigned) node, (unsigned) parentnode);
835 ++nedges;
836
837 /* for sum expression, also add intermediate nodes for the coefficients */
838 if ( SCIPisExprSum(scip, expr) )
839 {
840 SCIP_Real* coefs = SCIPgetCoefsExprSum(expr);
841 int internode;
842
843 /* iterate over children from last to first, such that visitednodes array is in correct order */
844 for (int j = SCIPexprGetNChildren(expr) - 1; j >= 0; --j)
845 {
847
848 assert( nuniquecoefs < coefarraysize );
849
850 ct = &sumcoefarray[nuniquecoefs];
851 ct->value = coefs[j];
852
853 if ( !SCIPhashtableExists(sumcoefmap, (void *) ct) )
854 {
856 ct->color = nusedcolors++;
857 color = ct->color;
858 nuniquecoefs++;
859 }
860 else
861 {
862 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(sumcoefmap, (void *) ct))->color;
863 }
864
865 /* add the intermediate node with the corresponding color */
866 internode = (int) G->add_vertex((unsigned) color);
867 ++nnodes;
868 visitednodes.push_back(internode);
869 ischildofsum.push_back(TRUE);
870
871 assert( internode < (int) G->get_nof_vertices() );
872
873 G->add_edge((unsigned) internode, (unsigned) node);
874 ++nedges;
875 }
876
877 /* add node for the constant term of the sum expression */
878 SCIP_Real constval = SCIPgetConstantExprSum(expr);
879 if ( constval != 0.0 )
880 {
882
883 /* check whether we have to resize */
885 {
887 assert( newsize >= 0 );
890 }
891
893
895 ct->value = constval;
896
897 if ( !SCIPhashtableExists(consttypemap, (void *) ct) )
898 {
900 ct->color = nusedcolors++;
901 color = ct->color;
903 }
904 else
905 {
906 color = ((SYM_CONSTTYPE*) SCIPhashtableRetrieve(consttypemap, (void *) ct))->color;
907 }
908
909 /* add the node with a new color */
910 internode = (int) G->add_vertex((unsigned) color);
911 ++nnodes;
912
913 assert( node < (int) G->get_nof_vertices() );
914
915 G->add_edge((unsigned) internode, (unsigned) node);
916 ++nedges;
917 }
918 }
919
920 currentlevel++;
921 break;
922 }
923
924 /* when leaving an expression, the nodes that are not needed anymore are erased from the respective arrays */
926 {
927 visitednodes.pop_back();
928 ischildofsum.pop_back();
929 currentlevel--;
930
931 /* When leaving the child of a sum expression, we have to pop again to get rid of the intermediate nodes
932 * used for the coefficients of summands
933 */
934 if ( !ischildofsum.empty() && ischildofsum[ischildofsum.size() - 1] )
935 {
936 visitednodes.pop_back();
937 ischildofsum.pop_back();
938 }
939
940 break;
941 }
942
943 default:
944 SCIPABORT(); /* we should never be called in this stage */
945 break;
946 }
947 }
948
949 assert( currentlevel == 0 );
950 assert( visitednodes.empty() );
951 assert( ischildofsum.empty() );
952
953 /* determine whether graph would be too large for bliss (can only handle int) */
954 if ( nnodes >= INT_MAX/2 )
955 {
956 success = FALSE; /*lint !e838*/
957 break;
958 }
959 }
960
961 /* free everything */
964
974
975 return SCIP_OKAY;
976}
977
978/** return whether symmetry can be computed */
980{
981 return TRUE;
982}
983
984/** return name of external program used to compute generators */
985char*
987{
988 char* name = new char[100];
989#ifdef BLISS_PATCH_PRESENT
990 (void) SCIPsnprintf(name, 100, "bliss %sp", bliss::version);
991#else
992 (void) SCIPsnprintf(name, 100, "bliss %s", bliss::version);
993#endif
994 return name;
995}
996
997/* static name for bliss */
999
1000/** return name of external program used to compute generators */
1001const char* SYMsymmetryGetName(void)
1002{
1003 return blissname;
1004}
1005
1006/** return description of external program used to compute generators */
1007const char* SYMsymmetryGetDesc(void)
1008{
1009 return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (https://users.aalto.fi/~tjunttil/bliss/)";
1010}
1011
1012/** return name of additional external program used for computing symmetries */
1013const char* SYMsymmetryGetAddName(void)
1014{
1015 return NULL;
1016}
1017
1018/** return description of additional external program used to compute symmetries */
1019const char* SYMsymmetryGetAddDesc(void)
1020{
1021 return NULL;
1022}
1023
1024/** compute generators of symmetry group */
1026 SCIP* scip, /**< SCIP pointer */
1027 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1028 SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
1029 SYM_EXPRDATA* exprdata, /**< data for nonlinear constraints */
1030 int* nperms, /**< pointer to store number of permutations */
1031 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1032 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1033 SCIP_Real* log10groupsize, /**< pointer to store size of group */
1034 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
1035 )
1036{
1037 SCIP_Real oldtime;
1038
1039 assert( scip != NULL );
1040 assert( matrixdata != NULL );
1041 assert( exprdata != NULL );
1042 assert( nperms != NULL );
1043 assert( nmaxperms != NULL );
1044 assert( perms != NULL );
1045 assert( log10groupsize != NULL );
1046 assert( maxgenerators >= 0 );
1047 assert( symcodetime != NULL );
1048
1049 /* init */
1050 *nperms = 0;
1051 *nmaxperms = 0;
1052 *perms = NULL;
1053 *log10groupsize = 0;
1054 *symcodetime = 0.0;
1055
1056 int nnodes = 0;
1057 int nedges = 0;
1058 int nusedcolors = 0;
1059 SCIP_Bool success = FALSE;
1060
1061 /* create bliss graph */
1062 bliss::Graph G(0);
1063
1064 /* create nodes corresponding to variables */
1066
1067 assert( nnodes == matrixdata->npermvars );
1068 assert( nusedcolors == matrixdata->nuniquevars );
1069
1070 /* fill graph with nodes for variables and linear constraints */
1072
1073 if ( !success )
1074 {
1075 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during linear part.\n");
1076 return SCIP_OKAY;
1077 }
1078
1079 /* add the nodes for nonlinear constraints to the graph */
1081
1082 if ( !success )
1083 {
1084 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed during non-linear part.\n");
1085 return SCIP_OKAY;
1086 }
1087
1088#ifdef SCIP_OUTPUT
1089 G.write_dot("debug.dot");
1090#endif
1091
1092#if SCIP_DISABLED_CODE
1093 char filename[SCIP_MAXSTRLEN];
1094 (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s.dimacs", SCIPgetProbName(scip));
1095 FILE* fp = fopen(filename, "w");
1096 if ( fp )
1097 {
1098 G.write_dimacs(fp);
1099 fclose(fp);
1100 }
1101#endif
1102
1103 SCIPdebugMsg(scip, "Symmetry detection graph has %u nodes.\n", G.get_nof_vertices());
1104
1105 /* compute automorphisms */
1106 bliss::Stats stats;
1107 BLISS_Data data;
1108 data.scip = scip;
1109 data.npermvars = matrixdata->npermvars;
1110 data.nperms = 0;
1111 data.nmaxperms = 0;
1112 data.maxgenerators = maxgenerators;
1113 data.perms = NULL;
1114
1115 /* Prefer splitting partition cells corresponding to variables over those corresponding
1116 * to inequalities. This is because we are only interested in the action
1117 * of the automorphism group on the variables, and we need a base for this action */
1118 G.set_splitting_heuristic(bliss::Graph::shs_f);
1119 /* disable component recursion as advised by Tommi Junttila from bliss */
1120 G.set_component_recursion(false);
1121
1122 /* do not use a node limit, but set generator limit */
1123#ifdef BLISS_PATCH_PRESENT
1124 G.set_search_limits(0, (unsigned) maxgenerators);
1125#endif
1126
1128#if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
1129 /* lambda function to have access to data and pass it to the blisshook above */
1130 auto reportglue = [&](unsigned int n, const unsigned int* aut) {
1131 blisshook((void*)&data, n, aut);
1132 };
1133
1134 /* lambda function to have access to stats and terminate the search if maxgenerators are reached */
1135 auto term = [&]() {
1136 return (stats.get_nof_generators() >= (long unsigned int) maxgenerators);
1137 };
1138
1139 /* start search */
1140 G.find_automorphisms(stats, reportglue, term);
1141#else
1142 /* start search */
1143 G.find_automorphisms(stats, blisshook, (void*) &data);
1144#endif
1146
1147#ifdef SCIP_OUTPUT
1148 (void) stats.print(stdout);
1149#endif
1150
1151 /* prepare return values */
1152 if ( data.nperms > 0 )
1153 {
1154 *perms = data.perms;
1155 *nperms = data.nperms;
1156 *nmaxperms = data.nmaxperms;
1157 }
1158 else
1159 {
1160 assert( data.perms == NULL );
1161 assert( data.nmaxperms == 0 );
1162 }
1163
1164 /* determine log10 of symmetry group size */
1165 *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
1166
1167 return SCIP_OKAY;
1168}
interface for symmetry computations
const char * SYMsymmetryGetName(void)
static char * blissname
const char * SYMsymmetryGetAddName(void)
static SCIP_RETCODE fillGraphByNonlinearConss(SCIP *scip, bliss::Graph *G, SYM_EXPRDATA *exprdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
static SCIP_RETCODE createVariableNodes(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nusedcolors)
SCIP_Bool SYMcanComputeSymmetry(void)
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
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 SCIP_RETCODE fillGraphByLinearConss(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)
const char * SYMsymmetryGetAddDesc(void)
char * initStaticBlissName()
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
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
int c
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
@ 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