141#define PROP_NAME "symmetry"
142#define PROP_DESC "propagator for handling symmetry"
143#define PROP_TIMING SCIP_PROPTIMING_BEFORELP
144#define PROP_PRIORITY -1000000
146#define PROP_DELAY FALSE
148#define PROP_PRESOL_PRIORITY -10000000
149#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
150#define PROP_PRESOL_MAXROUNDS -1
154#define DEFAULT_MAXGENERATORS 1500
155#define DEFAULT_CHECKSYMMETRIES FALSE
156#define DEFAULT_DISPLAYNORBITVARS FALSE
157#define DEFAULT_USECOLUMNSPARSITY FALSE
158#define DEFAULT_DOUBLEEQUATIONS FALSE
159#define DEFAULT_COMPRESSSYMMETRIES TRUE
160#define DEFAULT_COMPRESSTHRESHOLD 0.5
161#define DEFAULT_SYMFIXNONBINARYVARS FALSE
162#define DEFAULT_ENFORCECOMPUTESYMMETRY FALSE
163#define DEFAULT_SYMTYPE (int) SYM_SYMTYPE_PERM
164#define DEFAULT_DISPSYMINFO FALSE
167#define DEFAULT_CONSSADDLP TRUE
168#define DEFAULT_ADDSYMRESACKS TRUE
169#define DEFAULT_DETECTDOUBLELEX TRUE
170#define DEFAULT_DETECTORBITOPES TRUE
171#define DEFAULT_DETECTSUBGROUPS TRUE
172#define DEFAULT_ADDWEAKSBCS TRUE
173#define DEFAULT_ADDSTRONGSBCS FALSE
174#define DEFAULT_ADDCONSSTIMING 2
175#define DEFAULT_MAXNCONSSSUBGROUP 500000
176#define DEFAULT_USEDYNAMICPROP TRUE
177#define DEFAULT_PREFERLESSROWS TRUE
178#define DEFAULT_HANDLESIGNEDORBITOPES TRUE
179#define DEFAULT_USESIMPLESGNCOMP TRUE
182#define DEFAULT_SYMCOMPTIMING 2
183#define DEFAULT_PERFORMPRESOLVING 0
184#define DEFAULT_RECOMPUTERESTART 0
187#define DEFAULT_SSTTIEBREAKRULE 1
188#define DEFAULT_SSTLEADERRULE 0
189#define DEFAULT_SSTLEADERVARTYPE 6
191#define DEFAULT_ADDCONFLICTCUTS TRUE
192#define DEFAULT_SSTADDCUTS TRUE
193#define DEFAULT_SSTMIXEDCOMPONENTS TRUE
194#define DEFAULT_MAXNNEWINVOLUS 100
197#define TABLE_NAME_SYMMETRY "symmetry"
198#define TABLE_DESC_SYMMETRY "symmetry handling statistics"
199#define TABLE_POSITION_SYMMETRY 7001
200#define TABLE_EARLIEST_SYMMETRY SCIP_STAGE_SOLVING
204#define MAXGENNUMERATOR INT_MAX
205#define COMPRESSNVARSLB 25000
206#define DEFAULT_NAUTYMAXLEVEL 10000
210#define ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
211#define ISORBITALREDUCTIONACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 0)
212#define ISSSTACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SST) != 0)
214#define ISSSTBINACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)
215#define ISSSTINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)
216#define ISSSTCONTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)
219#define SYMMETRY_STATISTICS 1
234 int nmovedbinpermvars;
235 int nmovedintpermvars;
236 int nmovedcontpermvars;
248 int* componentbegins;
252 unsigned* componentblocked;
296 int maxnconsssubgroup;
303 int recomputerestart;
313 int sstleadervartype;
329struct SCIP_ConflictData
334 int nconflictinorbit;
351 else if ( elem1 > elem2 )
389 cmp = compfunc(arr1[it1], arr2[it2]);
395 if ( ++it1 >= narr1 )
404 if ( ++it2 >= narr2 )
417 assert( it1 >= narr1 || it2 >= narr2 );
450 if ( perm[baseidx] == baseidx || covered[baseidx] )
457 covered[baseidx] =
TRUE;
458 while ( j != baseidx )
488 assert( propdata->nperms > 0 );
490 assert( propdata->npermvars > 0 );
493 npermvars = propdata->npermvars;
501 for (p = 0; p < propdata->nperms; ++p)
504 perm = propdata->perms[p];
506 for (
i = 0;
i < permlen; ++
i)
511 for (
i = 0;
i < permlen; ++
i)
539 assert( propdata->nperms > 0 );
541 assert( propdata->npermvars > 0 );
542 assert( propdata->ncomponents > 0 );
545 npermvars = propdata->npermvars;
554 " or signed permutations (allowing translations) if the component has signed permutations.\n\n");
555 for (
c = 0;
c < propdata->ncomponents; ++
c)
560 propdata->componenthassignedperm[
c] ?
" as signed permutations" :
"");
562 comppermlen = propdata->componenthassignedperm[
c] ? 2 * npermvars : npermvars;
564 for (p = propdata->componentbegins[
c], cnt = 0; p < propdata->componentbegins[
c + 1]; ++p, ++cnt)
567 perm = propdata->perms[propdata->components[p]];
569 for (
i = 0;
i < comppermlen; ++
i)
574 for (
i = 0;
i < comppermlen; ++
i)
624 assert( 0 <= cidx && cidx < propdata->ncomponents );
628 propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx]);
654 else if ( isdoublelex )
660 rowsbegin[1] - rowsbegin[0]);
661 for (
i = 1;
i < nrowmatrices; ++
i)
665 colsbegin[1] - colsbegin[0]);
666 for (
i = 1;
i < ncolmatrices; ++
i)
691 assert( propdata->nperms >= 0 );
694 if ( propdata->nmovedpermvars >= 0 )
696 assert( propdata->nmovedpermvars == -1 );
698 propdata->nmovedpermvars = 0;
699 propdata->nmovedbinpermvars = 0;
700 propdata->nmovedintpermvars = 0;
701 propdata->nmovedcontpermvars = 0;
703 for (v = 0; v < propdata->npermvars; ++v)
705 for (p = 0; p < propdata->nperms; ++p)
707 if ( propdata->perms[p][v] != v )
709 ++propdata->nmovedpermvars;
714 ++propdata->nmovedbinpermvars;
717 ++propdata->nmovedintpermvars;
720 ++propdata->nmovedcontpermvars;
763 if ( tabledata->propdata->nperms > 0 )
768 tabledata->propdata->nmovedpermvars, tabledata->propdata->nmovedbinpermvars,
769 tabledata->propdata->nmovedintpermvars, tabledata->propdata->nmovedcontpermvars) ;
770 if ( tabledata->propdata->orbitopalreddata )
774 " %10d cutoffs\n", nred, ncutoff);
776 if ( tabledata->propdata->orbitalreddata )
780 " %10d cutoffs\n", nred, ncutoff);
782 if ( tabledata->propdata->lexreddata )
786 " %10d cutoffs\n", nred, ncutoff);
788 if ( tabledata->propdata->shadowtreeeventhdlr )
818 if( tabledata->propdata->orbitopalreddata )
829 if( tabledata->propdata->orbitalreddata )
840 if( tabledata->propdata->lexreddata )
851 if( tabledata->propdata->shadowtreeeventhdlr )
970 if ( G1->
lhs[perm1] < G2->
lhs[perm2] )
972 if ( G1->
lhs[perm1] > G2->
lhs[perm2] )
975 if ( G1->
rhs[perm1] < G2->
rhs[perm2] )
977 if ( G1->
rhs[perm1] > G2->
rhs[perm2] )
1045 assert( propdata->ngenlinconss == 0 );
1046 assert( propdata->ngenorbconss == 0 );
1047 assert( propdata->genorbconsssize == 0 );
1048 assert( propdata->genlinconsssize == 0 );
1052 assert( propdata->permvardomaincenter ==
NULL );
1056 assert( propdata->npermvars == 0 );
1057 assert( propdata->nbinpermvars == 0 );
1058 assert( propdata->nperms == -1 || propdata->nperms == 0 );
1059 assert( propdata->nmaxperms == 0 );
1060 assert( propdata->nmovedpermvars == -1 );
1061 assert( propdata->nmovedbinpermvars == 0 );
1062 assert( propdata->nmovedintpermvars == 0 );
1063 assert( propdata->nmovedcontpermvars == 0 );
1064 assert( propdata->nmovedvars == -1 );
1069 assert( propdata->componenthassignedperm ==
NULL );
1070 assert( propdata->componentblocked ==
NULL );
1073 assert( propdata->ncomponents == -1 );
1074 assert( propdata->ncompblocked == 0 );
1092 if ( propdata->orbitalreddata !=
NULL )
1096 if ( propdata->orbitopalreddata !=
NULL )
1100 if ( propdata->lexreddata !=
NULL )
1123 if ( propdata->permvarmap !=
NULL )
1129 for (
i = 0;
i < propdata->npermvars; ++
i)
1136 if ( propdata->permstrans !=
NULL )
1138 assert( propdata->nperms > 0 );
1140 assert( propdata->npermvars > 0 );
1141 assert( propdata->nmaxperms > 0 );
1143 for (
i = 0;
i < propdata->npermvars; ++
i)
1151 if ( propdata->genorbconss !=
NULL )
1154 while ( propdata->ngenorbconss > 0 )
1156 assert( propdata->genorbconss[propdata->ngenorbconss - 1] !=
NULL );
1159 assert( propdata->ngenorbconss == 0 );
1163 propdata->genorbconsssize = 0;
1167 if ( propdata->genlinconss !=
NULL )
1170 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
1178 propdata->ngenlinconss = 0;
1179 propdata->genlinconsssize = 0;
1182 if ( propdata->sstconss !=
NULL )
1184 assert( propdata->nsstconss > 0 );
1187 for (
i = 0;
i < propdata->nsstconss; ++
i)
1195 propdata->sstconss =
NULL;
1196 propdata->nsstconss = 0;
1197 propdata->maxnsstconss = 0;
1200 if ( propdata->leaders !=
NULL )
1202 assert( propdata->maxnleaders > 0 );
1205 propdata->maxnleaders = 0;
1206 propdata->leaders =
NULL;
1207 propdata->nleaders = 0;
1211 if ( propdata->ncomponents > 0 )
1213 assert( propdata->componentblocked !=
NULL );
1224 propdata->ncomponents = -1;
1225 propdata->ncompblocked = 0;
1229 if ( propdata->nperms > 0 )
1236 permlen = 2 * propdata->npermvars;
1238 permlen = propdata->npermvars;
1243 if ( propdata->perms !=
NULL )
1245 for (
i = 0;
i < propdata->nperms; ++
i)
1255 propdata->npermvars = 0;
1256 propdata->nbinpermvars = 0;
1257 propdata->nmaxperms = 0;
1258 propdata->nmovedpermvars = -1;
1259 propdata->nmovedbinpermvars = 0;
1260 propdata->nmovedintpermvars = 0;
1261 propdata->nmovedcontpermvars = 0;
1262 propdata->nmovedvars = -1;
1263 propdata->log10groupsize = -1.0;
1264 propdata->binvaraffected =
FALSE;
1265 propdata->isnonlinvar =
NULL;
1267 propdata->nperms = -1;
1271 propdata->computedsymmetry =
FALSE;
1272 propdata->compressed =
FALSE;
1283 int* consarrsizeptr,
1292 assert( consarrsizereq > 0 );
1293 assert( *consarrsizeptr >= 0 );
1294 assert( (*consarrsizeptr == 0) == (*consarrptr ==
NULL) );
1297 if ( consarrsizereq <= *consarrsizeptr )
1302 assert( newsize > *consarrsizeptr );
1305 if ( *consarrptr ==
NULL )
1314 *consarrsizeptr = newsize;
1363 *nbinpermvars = nbinvars;
1364 *binvaraffected =
FALSE;
1365 *compressed =
FALSE;
1371 int* labelmovedvars;
1372 int* labeltopermvaridx;
1373 int nbinvarsaffected = 0;
1384 labelmovedvars[
i] = -1;
1386 for (p = 0; p < nperms; ++p)
1388 if ( perms[p][
i] !=
i )
1390 labeltopermvaridx[*nmovedvars] =
i;
1391 labelmovedvars[
i] = (*nmovedvars)++;
1400 if ( nbinvarsaffected > 0 )
1401 *binvaraffected =
TRUE;
1405 if ( *nmovedvars > 0 &&
SCIPisLE(
scip, percentagemovedvars, compressthreshold) )
1408 for (p = 0; p < nperms; ++p)
1411 for (
i = 0;
i < *nmovedvars; ++
i)
1413 assert(
i <= labeltopermvaridx[
i] );
1414 if ( perms[p][labeltopermvaridx[
i]] >=
nvars )
1420 imgvaridx = perms[p][labeltopermvaridx[
i]] -
nvars;
1421 perms[p][
i] = labelmovedvars[imgvaridx] + *nmovedvars;
1423 assert( 0 <= perms[p][
i] && perms[p][
i] < 2 * (*nmovedvars) );
1426 perms[p][
i] = labelmovedvars[perms[p][labeltopermvaridx[
i]]];
1441 for (
i = 0;
i < *nmovedvars; ++
i)
1443 (*permvars)[
i] =
vars[labeltopermvaridx[
i]];
1445 *npermvars = *nmovedvars;
1446 *nbinpermvars = nbinvarsaffected;
1457 for (
i = 0;
i < nbinvars; ++
i)
1459 for (p = 0; p < nperms && ! *binvaraffected; ++p)
1461 if ( perms[p][
i] !=
i )
1464 *binvaraffected =
TRUE;
1473 for (
i = 0;
i < *npermvars; ++
i)
1478 (*permvardomaincenter)[
i] = 0.5 * (ub + lb);
1483 for (p = 0; p < nperms; ++p)
1485 (*isproperperm)[p] =
TRUE;
1488 for (
i = 0;
i < *npermvars; ++
i)
1490 if ( perms[p][
i] >= *npermvars )
1492 (*isproperperm)[p] =
FALSE;
1537 for (
c = 0;
c < nconshdlrs; ++
c)
1539 conshdlr = conshdlrs[
c];
1552 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n"
1553 " If symmetries shall be detected, implement the %s callback.\n",
1595 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n"
1632 *nconsnodes = nconss;
1637 for (
c = 0;
c < nconss; ++
c)
1665 depth = (int) log2((
double) num);
1666 expval = (int) exp2((
double) (
depth + 1));
1667 numnodes =
MIN(expval, 100);
1669 *nopnodes += numnodes;
1670 *nvalnodes +=
MAX((
int) 0.1 * numnodes, 1);
1685 *nopnodes += num - 1;
1694 if (
nvars <= 100000 )
1695 *nedges = 100 *
nvars;
1696 else if (
nvars <= 1000000 )
1697 *nedges = 32 *
nvars;
1698 else if (
nvars <= 16700000 )
1699 *nedges = 16 *
nvars;
1701 *nedges = INT_MAX / 10;
1729#ifdef SCIP_DISPLAY_SYM_CHECK
1746 assert( nsymvars == npermvars );
1750 for (
c = 0;
c < nconss; ++
c)
1773 for (
c = 0;
c < nconss; ++
c)
1778 SCIPsort(graphperm, SYMsortSymgraphs, graphs, nconss);
1781 for (
c = 1;
c < nconss; ++
c)
1784 groupbegins[ngroups++] =
c;
1786 groupbegins[ngroups] = nconss;
1789 for (
c = 0;
c < nconss; ++
c)
1794#ifdef SCIP_DISPLAY_SYM_CHECK
1800 for (p = 0; p < nperms; ++p)
1805#ifdef SCIP_DISPLAY_SYM_CHECK
1809 for (
i = 0;
i < permlen; ++
i)
1814 for (
i = 0;
i < permlen; ++
i)
1820 for (g = 0; g < ngroups; ++g)
1822 for (
c = groupbegins[g];
c < groupbegins[g+1]; ++
c)
1824#ifdef SCIP_DISPLAY_SYM_CHECK
1835#ifdef SCIP_DISPLAY_SYM_CHECK
1844 for (d = groupbegins[g]; d < groupbegins[g+1] && ! found; ++d)
1848#ifdef SCIP_DISPLAY_SYM_CHECK
1859#ifdef SCIP_DISPLAY_SYM_CHECK
1869#ifdef SCIP_DISPLAY_SYM_CHECK
1876 for (
c = nconss - 1;
c >= 0; --
c)
1944 *binvaraffected =
FALSE;
1945 *compressed =
FALSE;
1946 *log10groupsize = 0;
1972 nopnodes, nvalnodes, nconsnodes, nedges) );
1975 for (
c = 0;
c < nconss && *success; ++
c)
2010 perms, log10groupsize, symcodetime) );
2012 if ( checksymmetries && *nperms > 0 )
2027 permvardomaincenter, isproperperm, *perms, *nperms, nmovedvars, binvaraffected,
2028 compresssymmetries, compressthreshold, compressed) );
2052 for (v = 0; v <
nvars; ++v)
2055 if ( symmetry[v] >=
nvars )
2082 int* componentbegins;
2089 assert( propdata->ncomponents > 0 );
2094 componentbegins = propdata->componentbegins;
2095 ncomponents = propdata->ncomponents;
2104 for (
c = 0;
c < ncomponents; ++
c)
2106 for (
i = componentbegins[
c];
i < componentbegins[
c + 1]; ++
i)
2110 propdata->componenthassignedperm[
c] =
TRUE;
2130 assert( propdata->nperms >= 0 );
2133 if ( propdata->ncomponents >= 0 )
2137 assert( propdata->ncomponents == -1 );
2142#ifdef SCIP_OUTPUT_COMPONENT
2147 propdata->permvars, propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
2148 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
2150#ifdef SCIP_OUTPUT_COMPONENT
2156 assert( propdata->ncomponents > 0 );
2160 assert( propdata->componenthassignedperm !=
NULL );
2179 assert( propdata->nperms >= 0 );
2182 if ( propdata->permvarmap !=
NULL )
2189 for (v = 0; v < propdata->npermvars; ++v)
2212 assert( propdata->nperms >= 0 );
2215 if ( propdata->permstrans !=
NULL )
2221 for (v = 0; v < propdata->npermvars; ++v)
2224 for (p = 0; p < propdata->nperms; ++p)
2225 propdata->permstrans[v][p] = propdata->perms[p][v];
2256 for (
i = start;
i < end; ++
i)
2285 for (
i = start;
i < end; ++
i)
2295 for (
i = start;
i < end; ++
i)
2313 if ( propdata->enforcecomputesymmetry )
2367 unsigned int type = 0;
2373 assert( propdata->usesymmetry >= 0 );
2387 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2415 if ( ! (type & symspecrequire) )
2418 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2431 if ( propdata->computedsymmetry )
2434 assert( propdata->npermvars == 0 );
2436 assert( propdata->nperms < 0 );
2437 assert( propdata->nmaxperms == 0 );
2442 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2449 (symspecrequirefixed & (
int)
SYM_SPEC_REAL) != 0 ?
'+' :
'-');
2452 if ( symspecrequire & symspecrequirefixed )
2456 maxgenerators = propdata->maxgenerators;
2461 propdata->compresssymmetries, propdata->compressthreshold,
2462 maxgenerators, symspecrequirefixed, propdata->checksymmetries, &propdata->permvars,
2463 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2464 &propdata->isproperperm, &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2465 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2466 &propdata->log10groupsize, &symcodetime, &successful) );
2469 propdata->computedsymmetry =
TRUE;
2484 if ( propdata->nperms == 0 )
2491 assert( propdata->nperms > 0 );
2492 assert( propdata->npermvars > 0 );
2499 if ( maxgenerators == 0 )
2507 if ( propdata->displaynorbitvars )
2509 if ( propdata->nmovedvars == -1 )
2512 propdata->npermvars, &(propdata->nmovedvars)) );
2519 for (
i = 0;
i < propdata->npermvars; ++
i)
2555 int** orbitopevaridx,
2569 int ntestedperms = 0;
2581 assert( nactiveperms > 0 );
2582 assert( ntwocycles > 0 );
2584 assert( activevars ==
NULL || (0 <= nactiveperms && nactiveperms < npermvars) );
2587 if ( nusedcols !=
NULL )
2596 while ( ! foundperm )
2600 assert( ntestedperms < nactiveperms );
2602 permidx = activeperms[ntestedperms];
2604 for (j = 0; j < npermvars; ++j)
2606 if ( activevars !=
NULL && ! activevars[j] )
2609 assert( activevars ==
NULL || activevars[perms[permidx][j]] );
2612 if ( perms[permidx][j] > j )
2617 rowisbinary[row] =
TRUE;
2619 orbitopevaridx[row][0] = j;
2620 orbitopevaridx[row++][1] = perms[permidx][j];
2622 ++(nusedelems[perms[permidx][j]]);
2627 if ( row == ntwocycles )
2635 if ( row != ntwocycles )
2637 *isorbitope =
FALSE;
2642 usedperm[ntestedperms - 1] =
TRUE;
2652 for (j = ntestedperms; j < nactiveperms; ++j)
2657 if ( nusedperms == nactiveperms )
2664 perms[activeperms[j]],
TRUE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2668 *isorbitope =
FALSE;
2675 coltoextend = nfilledcols;
2676 columnorder[nfilledcols++] = -1;
2681 if ( ! *isorbitope )
2688 for (j = ntestedperms; j < nactiveperms; ++j)
2693 if ( nusedperms == nactiveperms )
2700 perms[activeperms[j]],
FALSE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2704 *isorbitope =
FALSE;
2711 coltoextend = nfilledcols;
2712 columnorder[nfilledcols] = 1;
2718 if ( activevars ==
NULL && nusedperms < nactiveperms )
2719 *isorbitope =
FALSE;
2721 if ( nusedcols !=
NULL )
2722 *nusedcols = nfilledcols;
2723 assert( ! *isorbitope || activevars ==
NULL || nusedperms < nfilledcols );
2742 int* componentbegins;
2751 assert( compidx < propdata->ncomponents );
2755 assert( propdata->computedsymmetry );
2756 assert( propdata->nperms > 0 );
2758 assert( propdata->npermvars > 0 );
2759 assert( propdata->ncomponents > 0 );
2763 perms = propdata->perms;
2764 npermvars = propdata->npermvars;
2766 componentbegins = propdata->componentbegins;
2767 npermsincomp = componentbegins[compidx + 1] - componentbegins[compidx];
2768 *ntwocycleperms = npermsincomp;
2772 for (
i = 0;
i < npermsincomp; ++
i)
2777 perm = perms[
components[componentbegins[compidx] +
i]];
2782 if ( ntwocycles[
i] == 0 )
2785 if ( propdata->preferlessrows )
2786 ntwocycles[
i] = npermvars;
2789 --(*ntwocycleperms);
2791 else if ( ! propdata->preferlessrows )
2792 ntwocycles[
i] = - ntwocycles[
i];
2816 int** graphcomponents,
2817 int** graphcompbegins,
2818 int** compcolorbegins,
2819 int* ngraphcomponents,
2832 int* componentbegins;
2833 int* componentslastperm;
2851 assert( usedpermssize > 0 );
2853 assert( ntwocycleperms >= 0 );
2855 assert( compidx < propdata->ncomponents );
2856 assert( propdata->computedsymmetry );
2857 assert( propdata->nperms > 0 );
2859 assert( propdata->npermvars > 0 );
2860 assert( propdata->ncomponents > 0 );
2863 assert( ! propdata->componentblocked[compidx] );
2865 perms = propdata->perms;
2866 npermvars = propdata->npermvars;
2868 componentbegins = propdata->componentbegins;
2871 assert( ntwocycleperms <= componentbegins[compidx + 1] - componentbegins[compidx] );
2877 for (k = 0; k < npermvars; ++k)
2878 componentslastperm[k] = -1;
2880 for (j = 0; j < ntwocycleperms; ++j)
2883 int firstcolor = -1;
2886 perm = perms[
components[componentbegins[compidx] + genorder[j]]];
2890 for (k = 0; k < npermvars; ++k)
2899 assert( perm[img] == k );
2907 if ( comp1 == comp2 )
2910 if ( firstcolor < 0 )
2915 componentslastperm[comp1] = j;
2922 if ( componentslastperm[comp1] == j || componentslastperm[comp2] == j )
2929 if ( color1 == color2 )
2932 componentslastperm[comp1] = j;
2933 componentslastperm[comp2] = j;
2935 if ( firstcolor < 0 )
2936 firstcolor = color1;
2940 if ( k < npermvars )
2944 if ( firstcolor == -1 )
2948 if ( *nusedperms >= usedpermssize )
2951 assert( newsize > usedpermssize );
2955 usedpermssize = newsize;
2958 (*usedperms)[*nusedperms] =
components[componentbegins[compidx] + genorder[j]];
2960 permused[genorder[j]] =
TRUE;
2963 for (k = 0; k < npermvars; ++k)
2972 assert( perm[img] == k );
2981 if ( comp1 == comp2 )
2987 if ( color1 != color2 )
3011 for (j = 0; j < npermvars; ++j)
3020 (*graphcomponents)[j] = j;
3024 SCIPsort(*graphcomponents, SYMsortGraphCompVars, (
void*) &graphcompvartype, npermvars);
3033 (*graphcompbegins)[0] = 0;
3034 (*compcolorbegins)[0] = 0;
3037 for (j = 1; j < npermvars; ++j)
3042 idx1 = (*graphcomponents)[j];
3043 idx2 = (*graphcomponents)[j-1];
3049 (*graphcompbegins)[nextcomp] = j;
3051 if ( graphcompvartype.
colors[idx1] > graphcompvartype.
colors[idx2] )
3053 (*compcolorbegins)[nextcolor] = nextcomp;
3060 assert( nextcomp == *ngraphcomponents );
3061 assert( nextcolor == *ncompcolors );
3063 (*compcolorbegins)[nextcolor] = *ngraphcomponents;
3064 (*graphcompbegins)[nextcomp] = npermvars;
3082 int* compcolorbegins,
3083 int* graphcompbegins,
3084 int* graphcomponents,
3089 int* compidxfirstrow,
3092 int* maxnvarslexorder,
3099 int** orbitopevaridx;
3106 int nactivevars = 0;
3117 assert( nusedperms > 0 );
3131 for (k = 0; k < nrows; ++k)
3138 for (k = 0; k < ncols; ++k)
3139 columnorder[k] = ncols + 1;
3145 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1]; ++k)
3151 compstart = graphcompbegins[k];
3152 firstvar = propdata->permvars[graphcomponents[compstart]];
3157 for (l = 0; l < ncols; ++l)
3161 varidx = graphcomponents[compstart + l];
3170 assert( nactivevars == nrows * ncols );
3182 propdata->perms, usedperms, nrows, nusedperms, orbitopevaridx, columnorder,
3183 nusedelems, &ngencols,
NULL, &isorbitope, activevars) );
3192 for (k = nrows - 1; k >= 0; --k)
3212 if ( firstvaridx !=
NULL )
3214 if ( columnorder[ngencols-1] > -1 )
3215 *firstvaridx = orbitopevaridx[0][ngencols-1];
3217 *firstvaridx = orbitopevaridx[0][1];
3221 if ( compidxfirstrow !=
NULL && firstvaridx !=
NULL )
3223 *compidxfirstrow = -1;
3225 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3231 compstart = graphcompbegins[k];
3232 firstvar = propdata->permvars[graphcomponents[compstart]];
3240 for (l = 0; l < ncols; ++l)
3242 if ( graphcomponents[compstart + l] == *firstvaridx )
3244 *compidxfirstrow = k;
3249 assert( *compidxfirstrow > -1 );
3254 for (k = 0; k < nrows; ++k)
3261 propdata->permvars, propdata->npermvars, orbitopevaridx, columnorder,
3262 nusedelems,
NULL, &infeasible,
TRUE, lexorder, nvarslexorder, maxnvarslexorder) );
3265 assert( firstvaridx ==
NULL || propdata->permvars[*firstvaridx] == orbitopevarmatrix[0][0] );
3276 if( propdata->dispsyminfo )
3285 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3286 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3287 ++propdata->norbitopes;
3289 for (k = nrows - 1; k >= 0; --k)
3294 for (k = nrows - 1; k >= 0; --k)
3307 int* graphcompbegins,
3308 int* graphcomponents,
3322 assert( graphcompidx >= 0 );
3323 assert( ! storelexorder || lexorder !=
NULL );
3324 assert( ! storelexorder || nvarsorder !=
NULL );
3325 assert( ! storelexorder || maxnvarsorder !=
NULL );
3328 if ( storelexorder )
3330 if ( *maxnvarsorder == 0 )
3332 *maxnvarsorder = graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx];
3339 assert( *nvarsorder == *maxnvarsorder );
3341 *maxnvarsorder += graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx];
3346 (*lexorder)[*nvarsorder++] = graphcomponents[graphcompbegins[graphcompidx]];
3350 for (k = graphcompbegins[graphcompidx]+1; k < graphcompbegins[graphcompidx+1]; ++k)
3357 vars[0] = propdata->permvars[graphcomponents[k-1]];
3358 vars[1] = propdata->permvars[graphcomponents[k]];
3360 if ( storelexorder )
3361 (*lexorder)[*nvarsorder++] = graphcomponents[k];
3371#ifdef SCIP_MORE_DEBUG
3378 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3379 propdata->genlinconss[propdata->ngenlinconss] = cons;
3380 ++propdata->ngenlinconss;
3383 if( propdata->dispsyminfo )
3385 graphcompbegins[graphcompidx+1] - graphcompbegins[graphcompidx] - 1);
3395 int* compcolorbegins,
3396 int* graphcompbegins,
3397 int* graphcomponents,
3399 int* chosencomppercolor,
3400 int* firstvaridxpercolor,
3415 int orbitsize[2] = {1, 1};
3417 int chosencolor = -1;
3429 assert( symgrpcompidx >= 0 );
3430 assert( symgrpcompidx < propdata->ncomponents );
3431 assert( ! storelexorder || lexorder !=
NULL );
3432 assert( ! storelexorder || nvarsorder !=
NULL );
3433 assert( ! storelexorder || maxnvarsorder !=
NULL );
3443 if ( lexorder ==
NULL || *lexorder ==
NULL )
3446 varsinlexorder =
NULL;
3450 assert( *maxnvarsorder >= 0 );
3451 assert( *nvarsorder >= 0 );
3455 for (k = 0; k < *nvarsorder; ++k)
3459 assert((*lexorder)[k] >= 0);
3467 if ( ncompcolors > 0 )
3471 for (j = 0; j < ncompcolors; ++j)
3478 if ( chosencomppercolor[j] < 0 )
3481 assert( firstvaridxpercolor[j] >= 0 );
3483 graphcomp = chosencomppercolor[j];
3484 graphcompsize = graphcompbegins[graphcomp+1] - graphcompbegins[graphcomp];
3485 varidx = firstvaridxpercolor[j];
3490 if ( varfound[
varidx] || graphcompsize == propdata->npermvars )
3494 if ( varsinlexorder !=
NULL
3496 && lexorder !=
NULL && *lexorder !=
NULL && *maxnvarsorder > 0 && *nvarsorder > 0
3497 && (*lexorder)[0] !=
varidx )
3501 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3503 assert( 0 <= graphcomponents[k] && graphcomponents[k] < propdata->npermvars );
3505 usedvars[graphcomponents[k]] =
TRUE;
3509 propdata->permstrans, propdata->components, propdata->componentbegins,
3510 usedvars, varfound,
varidx, symgrpcompidx,
3511 orbit[activeorb], &orbitsize[activeorb]) );
3515 if ( orbitsize[activeorb] > orbitsize[1 - activeorb] )
3518 activeorb = 1 - activeorb;
3523 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3524 usedvars[graphcomponents[k]] =
FALSE;
3528 if ( chosencolor > -1 )
3531 activeorb = 1 - activeorb;
3533 assert( orbit[activeorb][0] == firstvaridxpercolor[chosencolor] );
3534 vars[0] = propdata->permvars[orbit[activeorb][0]];
3536 assert( chosencolor > -1 );
3537 SCIPdebugMsg(
scip,
" adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3539 *naddedconss = orbitsize[activeorb] - 1;
3542 for (j = 1; j < orbitsize[activeorb]; ++j)
3547 vars[1] = propdata->permvars[orbit[activeorb][j]];
3557#ifdef SCIP_MORE_DEBUG
3564 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3565 propdata->genlinconss[propdata->ngenlinconss] = cons;
3566 ++propdata->ngenlinconss;
3568 if ( orbitsize[activeorb] > 0 && propdata->dispsyminfo )
3572 if ( storelexorder )
3576 varidx = orbit[activeorb][0];
3579 if ( *maxnvarsorder == 0 )
3585 (*lexorder)[(*nvarsorder)++] =
varidx;
3589 assert( *nvarsorder == *maxnvarsorder );
3595 if (
varidx == (*lexorder)[0] )
3612 for (k = *maxnvarsorder - 1; k >= 1; --k)
3613 (*lexorder)[k] = (*lexorder)[k - 1];
3625 if ( varsinlexorder !=
NULL )
3639 int** modifiedperms,
3670 for (
i = 0;
i < npermvars; ++
i)
3675 for (
i = 0;
i < npermvars; ++
i)
3676 posinpermvar[
i] =
i;
3680 for (l = 0; l < nleaders; ++l)
3682 leader = leaders[l];
3683 curposleader = posinpermvar[leader];
3684 varidx = permvaridx[curposleader];
3685 lidx = permvaridx[l];
3688 permvaridx[curposleader] = lidx;
3692 posinpermvar[lidx] = curposleader;
3693 posinpermvar[leader] = l;
3697 for (
i = 0;
i < npermvars; ++
i)
3698 modifiedpermvars[
i] = origpermvars[permvaridx[
i]];
3701 for (p = 0; p < nperms; ++p)
3703 for (
i = 0;
i < npermvars; ++
i)
3704 modifiedperms[p][
i] = posinpermvar[origperms[p][permvaridx[
i]]];
3720 int* graphcomponents,
3721 int* graphcompbegins,
3722 int* compcolorbegins,
3734 assert( ncompcolors >= 0 );
3735 assert( symcompsize > 0 );
3737 for (j = 0; j < ncompcolors; ++j)
3740 int largestcompsize = 0;
3745 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3749 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3753 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3756 if ( largestcompsize < 1 )
3761 largestcompsize = compsize;
3763 else if ( compsize != largestcompsize )
3766 firstvar = permvars[graphcomponents[graphcompbegins[k]]];
3774 if ( k == compcolorbegins[j+1] )
3780 ncols = graphcompbegins[compcolorbegins[j] + 1] - graphcompbegins[compcolorbegins[j]];
3782 threshold = 0.7 * (
SCIP_Real) symcompsize;
3785 if ( nbinrows <= 2 * ncols || (nbinrows <= 8 * ncols && nbinrows < 100) )
3786 multorbitopecriterion =
TRUE;
3787 else if ( nbinrows <= 3 * ncols || (
SCIP_Real) nbinrows * ncols >= threshold )
3788 oneorbitopecriterion =
TRUE;
3792 if ( (norbitopes == 1 && oneorbitopecriterion) || (norbitopes >= 2 && multorbitopecriterion) )
3811 int nstrongsbcs = 0;
3814 int** modifiedperms;
3816 int* nvarsincomponent;
3818 int* graphcomponents;
3819 int* graphcompbegins;
3820 int* compcolorbegins;
3821 int* chosencomppercolor =
NULL;
3822 int* firstvaridxpercolor =
NULL;
3825 int ngraphcomponents;
3830 int ntrivialcolors = 0;
3832 int* lexorder =
NULL;
3833 int nvarslexorder = 0;
3834 int maxnvarslexorder = 0;
3837 int norbitopesincomp;
3841 assert( propdata->computedsymmetry );
3842 assert( propdata->nperms >= 0 );
3843 assert( 0 <= cidx && cidx < propdata->ncomponents );
3848 if ( propdata->nperms == 0 || propdata->componentblocked[cidx] )
3855 assert( propdata->nperms > 0 );
3857 assert( propdata->npermvars > 0 );
3865 for (p = 0; p < propdata->nperms; ++p)
3872 for (p = 0; p < propdata->npermvars; ++p)
3874 if ( propdata->vartocomponent[p] >= 0 )
3875 ++nvarsincomponent[propdata->vartocomponent[p]];
3878 SCIPdebugMsg(
scip,
"starting subgroup detection routine for component %d\n", cidx);
3880 npermsincomp = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
3883 for (j = 0; j < npermsincomp; ++j)
3888 assert( ntwocycleperms >= 0 );
3889 assert( ntwocycleperms <= npermsincomp );
3891 SCIPdebugMsg(
scip,
"component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
3893#ifdef SCIP_MORE_DEBUG
3899 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx+1]; ++p)
3903 perm = propdata->components[p];
3905 for (k = 0; k < propdata->npermvars; ++k)
3910 for (k = 0; k < propdata->npermvars; ++k)
3915 j = propdata->perms[perm][k];
3927 j = propdata->perms[perm][j];
3937 if ( ntwocycleperms < 2 )
3943 usedpermssize = ntwocycleperms / 2;
3948 &graphcomponents, &graphcompbegins, &compcolorbegins, &ngraphcomponents,
3949 &ncompcolors, &usedperms, &nusedperms, usedpermssize, permused) );
3951 SCIPdebugMsg(
scip,
" created subgroup detection graph using %d of the permutations\n", nusedperms);
3956 assert( ngraphcomponents > 0 );
3957 assert( ncompcolors > 0 );
3958 assert( nusedperms <= ntwocycleperms );
3959 assert( ncompcolors < propdata->npermvars );
3961 if ( nusedperms == 0 )
3963 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
3971 SCIPdebugMsg(
scip,
" number of different colors in the graph: %d\n", ncompcolors);
3973 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3982 for (j = 0; j < ncompcolors; ++j)
3984 chosencomppercolor[j] = -1;
3985 firstvaridxpercolor[j] = -1;
3989 norbitopesincomp =
getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3990 ncompcolors, nvarsincomponent[cidx]);
3993 if ( norbitopesincomp == 1 )
3997 if( propdata->dispsyminfo )
4004 for (k = 0; k < npermsincomp; ++k)
4012 propdata->perms[propdata->components[propdata->componentbegins[cidx] + k]],
4013 propdata->permvars, propdata->npermvars,
FALSE,
4019 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4020 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4021 ++propdata->nsymresacks;
4023 if ( ! propdata->componentblocked[cidx] )
4026 ++propdata->ncompblocked;
4029 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d\n", k, cidx);
4035 for (j = 0; j < ncompcolors; ++j)
4037 int nbinarycomps = 0;
4038 int largestcolorcomp = -1;
4039 int largestcompsize = 0;
4051 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
4053 if( chosencomppercolor !=
NULL )
4054 chosencomppercolor[j] = -1;
4060 SCIPdebugMsg(
scip,
" color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4061 graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]]);
4064 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
4069 compsize = graphcompbegins[k+1] - graphcompbegins[k];
4072 if ( largestcompsize < 1 )
4080 largestcompsize = compsize;
4081 largestcolorcomp = k;
4083 else if ( compsize != largestcompsize )
4090 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
4098 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
4102 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
4109 contaffected =
TRUE;
4112 SCIPdebugMsg(
scip,
" affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4116 useorbitope =
FALSE;
4117 if ( norbitopesincomp > 0 && nbinarycomps > 0 )
4120 if ( isorbitope && useorbitope )
4125 SCIPdebugMsg(
scip,
" detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4127 assert( nbinarycomps > 0 );
4128 assert( largestcompsize > 2 );
4136 graphcompbegins, graphcomponents, j, nbinarycomps, largestcompsize, &firstvaridx, &chosencomp,
4137 &lexorder, &nvarslexorder, &maxnvarslexorder, &orbitopeadded) );
4139 if ( orbitopeadded )
4141 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
4147 assert( compcolorbegins[j] <= chosencomp && chosencomp < compcolorbegins[j+1] );
4148 assert( 0 <= firstvaridx && firstvaridx < propdata->npermvars );
4150 chosencomppercolor[j] = chosencomp;
4151 firstvaridxpercolor[j] = firstvaridx;
4154 if ( ! propdata->componentblocked[cidx] )
4157 ++propdata->ncompblocked;
4167 if ( propdata->addstrongsbcs && ! orbitopeadded )
4169 assert( largestcolorcomp >= 0 );
4170 assert( largestcolorcomp < ngraphcomponents );
4171 assert( largestcompsize > 0 );
4173 if( propdata->addweaksbcs )
4178 chosencomppercolor[j] = largestcolorcomp;
4179 firstvaridxpercolor[j] = graphcomponents[graphcompbegins[largestcolorcomp]];
4182 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
4183 largestcolorcomp, graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp]);
4187 propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
4190 if ( !
SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4191 handlednonbinarysymmetry =
TRUE;
4193 if ( ! propdata->componentblocked[cidx] )
4196 ++propdata->ncompblocked;
4200 nstrongsbcs += graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp] - 1;
4203 else if ( ! orbitopeadded )
4208 if ( propdata->addweaksbcs )
4211 chosencomppercolor[j] = -1;
4219 if ( propdata->addweaksbcs && propdata->componentblocked[cidx] && nusedperms < npermsincomp )
4227 graphcomponents, ncompcolors, chosencomppercolor, firstvaridxpercolor,
4228 cidx, &naddedconss, propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
4230 assert( naddedconss < propdata->npermvars );
4233 nweaksbcs += naddedconss;
4237 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4242 if ( nvarslexorder > 0 && propdata->addsymresacks && ! handlednonbinarysymmetry )
4244 int naddedconss = 0;
4248 propdata->permvars, modifiedpermvars, propdata->npermvars, lexorder, nvarslexorder) );
4250 for (k = 0; k < npermsincomp; ++k)
4262 symresackperm = modifiedperms[propdata->components[propdata->componentbegins[cidx] + k]];
4263 for (j = 0; j < propdata->nperms && !actsonbinary; ++j)
4266 actsonbinary =
TRUE;
4269 if ( ! actsonbinary )
4275 symresackperm, modifiedpermvars, propdata->npermvars,
FALSE,
4281 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4282 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4283 ++propdata->nsymresacks;
4286 if ( ! propdata->componentblocked[cidx] )
4289 ++propdata->ncompblocked;
4292 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, cidx);
4295 if ( propdata->dispsyminfo )
4311 SCIPdebugMsg(
scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4312 SCIPdebugMsg(
scip,
"total number of added strong sbcs: %d\n", nstrongsbcs);
4320 for (p = propdata->nperms - 1; p >= 0; --p)
4357 assert( nconflictvars > 0 );
4363 for (
i = 0;
i < nconflictvars; ++
i)
4366 varconflicts[
i].orbitidx = -1;
4367 varconflicts[
i].nconflictinorbit = 0;
4368 varconflicts[
i].orbitsize = -1;
4369 varconflicts[
i].posinorbit = -1;
4373 for (
r = 0;
r < norbits; ++
r)
4378 orbitsize = orbitbegins[
r + 1] - orbitbegins[
r];
4379 assert( orbitsize >= 0 );
4381 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4387 assert( pos < nconflictvars );
4388 assert( varconflicts[pos].
var == conflictvars[pos] );
4390 varconflicts[pos].orbitidx =
r;
4391 varconflicts[pos].nconflictinorbit = 0;
4392 varconflicts[pos].orbitsize = orbitsize;
4393 varconflicts[pos].posinorbit = posinorbit++;
4403 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4406 assert( varconflicts[ii].orbitidx ==
r );
4409 if ( ! varconflicts[ii].
active )
4412 for (j =
i + 1; j < orbitbegins[
r + 1]; ++j)
4415 assert( varconflicts[jj].orbitidx ==
r );
4418 if ( ! varconflicts[jj].
active )
4428 varconflicts[ii].ncliques, (
void**)varconflicts[jj].cliques, varconflicts[jj].ncliques,
4429 sortByPointerValue) )
4432 ++varconflicts[ii].nconflictinorbit;
4433 ++varconflicts[jj].nconflictinorbit;
4470 int varncliques = 0;
4476 assert( nconflictvars > 0 );
4479 *varconflicts =
NULL;
4485 if ( ncliques == 0 )
4487 SCIPdebugMsg(
scip,
"No cliques present --> construction of conflict structure aborted.\n");
4494 for (
i = 0;
i < nconflictvars; ++
i)
4496 (*varconflicts)[
i].ncliques = 0;
4497 (*varconflicts)[
i].active =
TRUE;
4498 (*varconflicts)[
i].var = conflictvars[
i];
4500 (*varconflicts)[
i].cliques =
NULL;
4501 (*varconflicts)[
i].orbitidx = -1;
4502 (*varconflicts)[
i].nconflictinorbit = 0;
4503 (*varconflicts)[
i].orbitsize = -1;
4504 (*varconflicts)[
i].posinorbit = -1;
4514 for (
c = 0;
c < ncliques; ++
c)
4516 clique = cliques[
c];
4522 assert( ncliquevars > 0 );
4528 for (
i = 0;
i < ncliquevars; ++
i)
4533 if ( node == INT_MAX )
4536 assert( node < nconflictvars );
4538 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4539 (*varconflicts)[node].active =
TRUE;
4540 (*varconflicts)[node].ncliques++;
4545 for (
i = 0;
i < nconflictvars; ++
i)
4547 assert( (*varconflicts)[
i].ncliques >= 0 );
4549 if ( (*varconflicts)[
i].ncliques > 0 )
4557 for (
c = 0;
c < ncliques; ++
c)
4559 clique = cliques[
c];
4565 assert( ncliquevars > 0 );
4571 for (
i = 0;
i < ncliquevars; ++
i)
4576 if ( node == INT_MAX )
4580 assert( node < nconflictvars );
4581 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4584 assert( tmpncliques[node] < (*varconflicts)[node].ncliques );
4585 assert( (*varconflicts)[node].cliques !=
NULL );
4586 (*varconflicts)[node].cliques[tmpncliques[node]++] = clique;
4595 for (
i = 0;
i < nconflictvars; ++
i)
4597 SCIPsortPtr((
void**)(*varconflicts)[
i].cliques, sortByPointerValue, (*varconflicts)[
i].ncliques);
4601 for (
i = 0;
i < nconflictvars; ++
i)
4603 assert( tmpncliques[
i] == (*varconflicts)[
i].ncliques );
4610 SCIPdebugMsg(
scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4635 n = (*varconflicts)[
i].ncliques;
4653 int* componentbegins;
4656 int** modifiedperms =
NULL;
4659 int nsymresackcons = 0;
4667 assert( propdata->npermvars >= 0 );
4668 assert( propdata->nbinpermvars >= 0 );
4671 if ( propdata->nbinpermvars == 0 )
4673 assert( propdata->binvaraffected == 0 );
4677 perms = propdata->perms;
4678 nperms = propdata->nperms;
4679 permvars = propdata->permvars;
4680 npermvars = propdata->npermvars;
4681 conssaddlp = propdata->conssaddlp;
4683 componentbegins = propdata->componentbegins;
4690 assert( 0 <= cidx && cidx < propdata->ncomponents );
4704 if ( propdata->componenthassignedperm[cidx] )
4708 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4711 for (p = 0; p < nperms; ++p)
4717 for (
i = 0;
i < npermvars; ++
i)
4718 modifiedpermvars[
i] = permvars[
i];
4721 propdata->leaders, propdata->nleaders) );
4725 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
4736 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4755 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4756 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4757 ++propdata->nsymresacks;
4761 if ( nsymresackcons > 0 && propdata->dispsyminfo )
4764 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4770 for (p = nperms - 1; p >= 0; --p)
4795 int norbitvarinconflict,
4820 assert( orbitleaderidx >= 0 );
4822 assert( norbitvarinconflict >= 0 );
4825 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4828 if ( propdata->sstaddcuts )
4832 addcuts = propdata->addconflictcuts;
4835 ncuts = orbitsize - norbitvarinconflict - 1;
4837 if ( propdata->dispsyminfo )
4841 leadervar = permvars[orbits[orbitbegins[orbitidx] + orbitleaderidx]];
4860 if ( propdata->nsstconss == 0 )
4863 assert( propdata->maxnsstconss == 0 );
4864 propdata->maxnsstconss = 2 * ncuts;
4867 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
4873 propdata->maxnsstconss, newsize) );
4874 propdata->maxnsstconss = newsize;
4878 if ( propdata->nleaders == 0 )
4880 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
4883 assert( propdata->nleaders < propdata->maxnleaders );
4886 posleader = orbitbegins[orbitidx] + orbitleaderidx;
4887 vars[0] = permvars[orbits[posleader]];
4890 propdata->leaders[propdata->nleaders++] = orbits[posleader];
4892 for (
i = 0, poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++poscur)
4894 if (
i == orbitleaderidx )
4896 assert( orbitvarinconflict ==
NULL || ! orbitvarinconflict[
i] );
4900 vars[1] = permvars[orbits[poscur]];
4902 for (j = 0; j < propdata->nleaders - 1; ++j)
4904 assert( propdata->leaders[j] != orbits[poscur] );
4910 rhs = propdata->permvardomaincenter[orbits[poscur]] - propdata->permvardomaincenter[orbits[posleader]];
4913 if ( varconflicts !=
NULL )
4915 if ( orbitvarinconflict[
i] )
4929 varconflicts[orbits[poscur]].active =
FALSE;
4933 orbitvarinconflict[
i] =
FALSE;
4942 propdata->sstconss[propdata->nsstconss++] = cons;
4952 propdata->sstconss[propdata->nsstconss++] = cons;
4976 int* norbitvarinconflict,
4982 int curcriterion = INT_MIN;
4989 assert( nconflictvars > 0 );
5001 *norbitvarinconflict = 0;
5012 orbitcriterion = INT_MIN;
5015 for (
i = 0;
i < norbits; ++
i)
5023 curcriterion = orbitbegins[
i] - orbitbegins[
i + 1];
5025 curcriterion = orbitbegins[
i + 1] - orbitbegins[
i];
5035 cnt = orbitbegins[
i];
5047 cnt = orbitbegins[
i + 1] - 1;
5062 curcriterion = varconflicts[
varidx].nconflictinorbit;
5066 if ( curcriterion > orbitcriterion )
5068 orbitcriterion = curcriterion;
5075 *leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
5080 if ( *success && varconflicts !=
NULL )
5082 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
5083 assert( leader < nconflictvars );
5086 && varconflicts[leader].ncliques > 0 )
5093 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
5095 assert( leader >= 0 && leader < nconflictvars );
5099 for (
i = 0;
i < orbitsize; ++
i)
5102 if (
i == *leaderidx )
5106 varmapid = orbits[orbitbegins[*orbitidx] +
i];
5109 if ( ! varconflicts[varmapid].
active )
5114 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
5115 varconflicts[varmapid].ncliques, sortByPointerValue) )
5118 orbitvarinconflict[
i] =
TRUE;
5119 ++(*norbitvarinconflict);
5136 for (
i = 0;
i < nconflictvars; ++
i)
5144 if ( varconflicts[
i].orbitidx == -1 )
5147 curcriterion = varconflicts[
i].nconflictinorbit;
5149 if ( curcriterion > orbitcriterion )
5151 orbitcriterion = curcriterion;
5152 *orbitidx = varconflicts[
i].orbitidx;
5153 *leaderidx = varconflicts[
i].posinorbit;
5159 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
5160 assert( leader < nconflictvars );
5163 if ( *success && varconflicts[leader].ncliques > 0 )
5168 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
5170 assert( leader >= 0 && leader < nconflictvars );
5174 for (
i = 0;
i < orbitsize; ++
i)
5177 if (
i == *leaderidx )
5181 varmapid = orbits[orbitbegins[*orbitidx] +
i];
5183 if ( ! varconflicts[varmapid].
active )
5188 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
5189 varconflicts[varmapid].ncliques, sortByPointerValue) )
5192 orbitvarinconflict[
i] =
TRUE;
5193 ++(*norbitvarinconflict);
5219 int nmovedbinpermvars;
5220 int nmovedintpermvars;
5221 int nmovedcontpermvars;
5228 int* componentbegins;
5229 int* vartocomponent;
5231 unsigned* componentblocked;
5236 int norbitvarinconflict;
5244 int nvarsselectedtype;
5247 int norbitleadercomponent;
5258 assert( propdata->computedsymmetry );
5260 permvars = propdata->permvars;
5261 npermvars = propdata->npermvars;
5262 nperms = propdata->nperms;
5268 permvarmap = propdata->permvarmap;
5272 permstrans = propdata->permstrans;
5276 componentbegins = propdata->componentbegins;
5277 componentblocked = propdata->componentblocked;
5278 vartocomponent = propdata->vartocomponent;
5279 ncomponents = propdata->ncomponents;
5285 assert( ncomponents > 0 );
5286 assert( 0 <= cidx && cidx < ncomponents );
5288 if ( nchgbds !=
NULL )
5292 if ( componentblocked[cidx] )
5295 leaderrule = propdata->sstleaderrule;
5296 tiebreakrule = propdata->ssttiebreakrule;
5297 leadervartype = propdata->sstleadervartype;
5298 mixedcomponents = propdata->sstmixedcomponents;
5302 nmovedpermvars = propdata->nmovedpermvars;
5303 nmovedbinpermvars = propdata->nmovedbinpermvars;
5304 nmovedintpermvars = propdata->nmovedintpermvars;
5305 nmovedcontpermvars = propdata->nmovedcontpermvars;
5306 assert( nmovedpermvars > 0 );
5309 nvarsselectedtype = 0;
5310 if (
ISSSTBINACTIVE(leadervartype) && nmovedbinpermvars > nvarsselectedtype )
5313 nvarsselectedtype = nmovedbinpermvars;
5316 if (
ISSSTINTACTIVE(leadervartype) && nmovedintpermvars > nvarsselectedtype )
5319 nvarsselectedtype = nmovedintpermvars;
5322 if (
ISSSTCONTACTIVE(leadervartype) && nmovedcontpermvars > nvarsselectedtype )
5325 nvarsselectedtype = nmovedcontpermvars;
5329 if ( nvarsselectedtype == 0 )
5333 if ( onlywithcontvars )
5335 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
5337 perm = propdata->perms[p];
5338 for (
i = 0;
i < propdata->npermvars; ++
i)
5360 conflictgraphcreated = varconflicts !=
NULL;
5368 if ( conflictgraphcreated )
5373 SCIPdebugMsg(
scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5378 for (
c = 0;
c < ncomponents; ++
c)
5380 for (p = componentbegins[
c]; p < componentbegins[
c + 1]; ++p)
5385 if ( propdata->componenthassignedperm[cidx] )
5403 norbitleadercomponent = 0;
5404 while ( ninactiveperms < nperms )
5410 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5411 componentblocked, ncomponents, nmovedpermvars) );
5414 if ( ! mixedcomponents )
5416 for (p = 0; p < norbits; ++p)
5431 if ( conflictgraphcreated )
5449 propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype, &orbitidx,
5450 &orbitleaderidx, orbitvarinconflict, &norbitvarinconflict, &success) );
5455 assert( 0 <= orbitidx && orbitidx < norbits );
5456 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5457 SCIPdebugMsg(
scip,
"%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5461 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5463 ++norbitleadercomponent;
5465 if ( nchgbds !=
NULL )
5466 *nchgbds += nchanges;
5469 posleader = orbits[orbitbegins[orbitidx] + orbitleaderidx];
5470 for (p = 0; p < nperms; ++p)
5472 if ( inactiveperms[p] )
5475 if ( permstrans[posleader][p] != posleader )
5477 inactiveperms[p] =
TRUE;
5484 if ( norbitleadercomponent > 0 )
5487 if ( conflictgraphcreated )
5493 if ( varconflicts !=
NULL )
5529 assert( propdata->usedynamicprop );
5545 if ( propdata->dispsyminfo )
5552 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5553 for (
i = 0;
i < ncols - 1; ++
i)
5557 consvars[0] = propdata->permvars[varidxmatrix[0][
i]];
5558 consvars[1] = propdata->permvars[varidxmatrix[0][
i + 1]];
5564 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5572 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5576 if ( propdata->dispsyminfo )
5582 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[componentid]]];
5585 propdata->permvars, propdata->npermvars, orbisackperm, (
SYM_SYMTYPE) propdata->symtype,
5586 propdata->permvardomaincenter,
TRUE, success) );
5593 for (
i = 0;
i < nrows; ++
i)
5596 for (j = 0; j < ncols; ++j)
5597 varmatrix[
i][j] = propdata->permvars[varidxmatrix[
i][j]];
5604 ispporbitope = npprows >= 3;
5618 for (
i = 0;
i < nrows; ++
i)
5623 ppvarsarrayonlypprows[
r++] = varmatrix[
i];
5628 if ( propdata->dispsyminfo )
5642 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5646 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5659 if ( propdata->dispsyminfo )
5665 nelem = nrows * ncols;
5667 for (
i = 0;
i < nrows; ++
i)
5669 for (j = 0; j < ncols; ++j)
5670 orbitopevarmatrix[pos++] = varmatrix[
i][j];
5679 orbitopevarmatrix, nrows, ncols, success) );
5687 for (
i = nrows - 1;
i >= 0; --
i)
5702 int** componentperms,
5722 int** pporbisackperms;
5723 int npporbisackperms;
5727 int* npermvarssetppcconss;
5728 int* maxnpermvarssetppcconss;
5735 assert( componentsize > 0 );
5743 if ( hassignedperm )
5747 if ( setppcconshdlr ==
NULL )
5751 if ( nsetppcconss == 0 )
5762 for (
c = 0;
c < nsetppcconss; ++
c)
5764 cons = setppcconss[
c];
5770 setppconsssort[nsetppconss++] = cons;
5772 SCIPsortPtr((
void**) setppconsssort, sortByPointerValue, nsetppconss);
5780 for (
c = 0;
c < nsetppconss; ++
c)
5784 cons = setppconsssort[
c];
5790 for (
i = 0;
i < nsetppcvars; ++
i)
5792 var = setppcvars[
i];
5795 assert( varid == INT_MAX || varid < propdata->npermvars );
5797 if ( varid < propdata->npermvars )
5800 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5801 assert( npermvarssetppcconss[varid] < maxnpermvarssetppcconss[varid] );
5802 permvarssetppcconss[varid][npermvarssetppcconss[varid]++] = cons;
5810 npporbisackperms = 0;
5811 for (p = 0; p < componentsize; ++p)
5813 perm = componentperms[p];
5817 for (
i = 0;
i < propdata->npermvars; ++
i)
5836 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) )
5845 if ( ntwocycles > 0 )
5847 pporbisackperms[npporbisackperms++] = perm;
5848 if ( ntwocycles > maxntwocycles )
5849 maxntwocycles = ntwocycles;
5857 if ( npporbisackperms * 2 >= componentsize )
5865 assert( npporbisackperms > 0 );
5866 assert( maxntwocycles > 0 );
5871 for (
i = 0;
i < maxntwocycles; ++
i)
5872 ppvarsmatrix[
i] = &(ppvarsblock[2 *
i]);
5875 for (p = 0; p < npporbisackperms; ++p)
5877 perm = pporbisackperms[p];
5881 for (
i = 0;
i < propdata->npermvars; ++
i)
5894 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) );
5896 assert( nrows < maxntwocycles );
5897 row = ppvarsmatrix[nrows++];
5898 row[0] = propdata->permvars[
i];
5899 row[1] = propdata->permvars[j];
5900 assert( row[0] != row[1] );
5911 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5915 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5930 for (varid = 0; varid < propdata->npermvars; ++varid)
5932 assert( (permvarssetppcconss[varid] ==
NULL) == (maxnpermvarssetppcconss[varid] == 0) );
5933 assert( npermvarssetppcconss[varid] >= 0 );
5934 assert( maxnpermvarssetppcconss[varid] >= 0 );
5935 assert( npermvarssetppcconss[varid] <= maxnpermvarssetppcconss[varid] );
5936 if ( npermvarssetppcconss[varid] == 0 )
5939 permvarssetppcconss[varid] =
NULL;
5940 npermvarssetppcconss[varid] = 0;
5941 maxnpermvarssetppcconss[varid] = 0;
5961 int** componentperms =
NULL;
5962 int** properperms =
NULL;
5973 assert( propdata->nperms > 0 );
5974 assert( 0 <= cidx && cidx < propdata->ncomponents );
5975 assert( propdata->componentblocked !=
NULL );
5978 if ( propdata->componentblocked[cidx] )
5983 checklexred =
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5985 if ( checkorbired || checklexred )
5988 assert( propdata->nmovedpermvars );
5992 componentsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
5995 if ( checkorbired || checklexred )
5998 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx] + componentsize; ++p)
6000 if ( propdata->isproperperm[propdata->components[p]] )
6001 properperms[nproperperms++] = propdata->perms[propdata->components[p]];
6005 if ( propdata->componenthassignedperm[cidx] )
6008 for (p = 0; p < componentsize; ++p)
6009 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
6020 checkpporbisack =
SCIPgetParam(
scip,
"constraints/orbisack/checkpporbisack");
6022 && nproperperms > 0 && propdata->nmovedbinpermvars > 0 )
6024 int naddedconss = 0;
6028 properperms, nproperperms,
FALSE , &success, &naddedconss) );
6032 if ( propdata->dispsyminfo )
6035 goto FINISHCOMPONENT;
6040 if ( checkorbired && nproperperms > 0 )
6043 propdata->permvars, propdata->npermvars, properperms, nproperperms, &success) );
6048 if ( propdata->dispsyminfo )
6056 assert( componentperms !=
NULL || componentsize == nproperperms );
6059 for (p = 0; p < componentsize; ++p)
6062 propdata->permvars, propdata->npermvars, componentperms !=
NULL ? componentperms[p] : properperms[p],
6063 (
SYM_SYMTYPE) propdata->symtype, propdata->permvardomaincenter,
TRUE, &success) );
6068 if ( propdata->dispsyminfo )
6071 else if ( propdata->usesimplesgncomp && ! propdata->componentblocked[cidx] )
6074 if ( propdata->componenthassignedperm[cidx] )
6080 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx + 1] && ! found; ++p)
6082 perm = propdata->perms[propdata->components[p]];
6083 for (v = 0; v < propdata->npermvars; ++v)
6085 if ( perm[v] != propdata->npermvars + v && perm[v] != v )
6090 if ( v == propdata->npermvars )
6109 for (p = 0; p < propdata->npermvars; ++p)
6111 if ( perm[p] == propdata->npermvars + p )
6114 vals[
nvars++] = 1.0;
6115 lhs += propdata->permvardomaincenter[p];
6120 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
6124 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6132 if ( propdata->dispsyminfo )
6140 if ( propdata->componentblocked[cidx] )
6141 ++propdata->ncompblocked;
6157 int ncomponentshandled;
6164 if ( propdata->orbitopalreddata )
6168 if ( propdata->orbitalreddata )
6172 if ( propdata->lexreddata )
6176 if ( propdata->ncomponents >= 0 )
6183 ncomponentshandled = 0;
6184 for (
i = 0;
i < propdata->ncomponents; ++
i)
6186 if ( propdata->componentblocked[
i] )
6187 ++ncomponentshandled;
6189 assert( propdata->ncompblocked <= ncomponentshandled );
6190 assert( ncomponentshandled <= propdata->ncomponents );
6192 ncomponentshandled, propdata->ncomponents);
6213 int flipcolumn = -1;
6218 assert( 0 <= startrow && startrow < endrow );
6219 assert( 0 <= startcol && startcol < endcol );
6221 assert( npermvars >= (endrow - startrow) * (endcol - startcol) );
6228 for (
i = startrow;
i < endrow; ++
i)
6230 for (j = startcol; j < endcol; ++j )
6232 if ( signedperm[varidxmatrix[
i][j]] == npermvars + varidxmatrix[
i][j] )
6234 if ( flipcolumn == -1 )
6236 flipcolumn = transposed ?
i : j;
6237 flipablerows[(*nflipablerows)++] = transposed ? j :
i;
6239 else if ( (transposed && flipcolumn !=
i) || (!transposed && flipcolumn != j) )
6246 flipablerows[(*nflipablerows)++] = transposed ? j :
i;
6248 else if ( signedperm[varidxmatrix[
i][j]] != varidxmatrix[
i][j] )
6279 assert( 0 <= startrow && startrow < endrow );
6280 assert( 0 <= startcol && startcol < endcol );
6282 if ( equalrowcenters )
6284 for (
i = startrow;
i < endrow; ++
i)
6286 for (j = startcol; j < endcol - 1; ++j)
6290 vardomaincenter[varidxmatrix[
i][j + 1]]) )
6297 for (j = startcol; j < endcol; ++j)
6299 for (
i = startrow;
i < endrow - 1; ++
i)
6303 vardomaincenter[varidxmatrix[
i + 1][j]]) )
6338 if ( handlestatically )
6352 nelem = nrows * ncols;
6354 for (
i = 0, pos = 0;
i < nrows; ++
i)
6356 for (j = 0; j < ncols; ++j)
6357 orbitopevarmatrix[pos++] = propdata->permvars[varidxmatrix[
i][j]];
6360 if ( propdata->dispsyminfo )
6364 ncols - 1, nrows, ncols);
6371 orbitopevarmatrix, nrows, ncols, success) );
6380 &propdata->genlinconsssize, propdata->ngenlinconss + nconss) );
6383 for (j = 0; j < ncols - 1; ++j)
6386 consvars[0] = orbitopevarmatrix[j];
6387 consvars[1] = orbitopevarmatrix[j + 1];
6392 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6402 for (j = 0; j < ncols; ++j)
6404 var = orbitopevarmatrix[j];
6405 bound = propdata->permvardomaincenter[varidxmatrix[0][j]];
6414 if( nchgbds !=
NULL )
6426 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6441 if ( propdata->usedynamicprop )
6446 else if ( propdata->binvaraffected )
6455 for (
i = 0;
i < nrows; ++
i)
6462 for (j = 0; j < ncols; ++j)
6465 orbitopematrix[nbinrows][j] = propdata->permvars[varidxmatrix[
i][j]];
6472 if ( propdata->dispsyminfo )
6484 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
6485 propdata->genorbconss[propdata->ngenorbconss++] = cons;
6486 ++propdata->norbitopes;
6490 for (
i = nbinrows - 1;
i >= 0; --
i)
6536 assert( 0 <= nsignedrows && nsignedrows <= nrows );
6540 nelem = nrows * ncols;
6545 nsortconss = ncols - 1;
6546 if ( nsignedrows > 0 )
6548 nactiverows = nsignedrows;
6549 nactrowsprev = nrows;
6551 for (j = 0; j < ncols; ++j)
6553 nsortconss +=
MAX(nactrowsprev - nactiverows - 1, 0);
6554 nsignedconss += nactiverows;
6555 nactrowsprev = nactiverows;
6558 nactiverows = (int) ((nactiverows + 1) / 2);
6560 assert( nactiverows >= 1 );
6562 nsortconss += nactiverows - 1;
6565 nsortconss += nrows - 1;
6567 if ( propdata->dispsyminfo )
6571 ncols - 1, nrows, ncols);
6572 if ( nsignedconss > 0 )
6574 "upper half and sort by static orbitopal reduction\n");
6579 &propdata->genlinconsssize, propdata->ngenlinconss + nsortconss + nsignedconss) );
6582 for (j = 0; j < ncols - 1; ++j)
6585 consvars[0] = propdata->permvars[varidxmatrix[0][j]];
6586 consvars[1] = propdata->permvars[varidxmatrix[0][j + 1]];
6590 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6595 for (
i = 0, pos = 0;
i < nrows; ++
i)
6597 for (j = 0; j < ncols; ++j)
6598 orbitopevarmatrix[pos++] = propdata->permvars[varidxmatrix[
i][j]];
6602 orbitopevarmatrix, nrows, ncols, success) );
6604 if ( nsignedconss > 0 )
6608 nactiverows = nsignedrows;
6609 nactrowsprev = nrows;
6610 for (j = 0; j < ncols; ++j)
6613 nactiverows = (int) ((nactiverows + 1) / 2);
6616 for (
i = nactiverows;
i < nactrowsprev - 1; ++
i)
6620 consvars[0] = propdata->permvars[varidxmatrix[
i][0]];
6621 consvars[1] = propdata->permvars[varidxmatrix[
i + 1][0]];
6626 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6631 if ( nactrowsprev - nactiverows > 1 )
6633 for (k = 0, pos = 0; k < ncols; ++k)
6635 for (
i = nactiverows;
i < nactrowsprev; ++
i)
6636 orbitopevarmatrix[pos++] = propdata->permvars[varidxmatrix[
i][k]];
6640 orbitopevarmatrix, ncols, nactrowsprev - nactiverows, success) );
6642 nactrowsprev = nactiverows;
6645 for (
i = 0;
i < nactiverows; ++
i)
6649 consvars[0] = propdata->permvars[varidxmatrix[
i][j]];
6650 bound = propdata->permvardomaincenter[varidxmatrix[
i][j]];
6658 if ( nchgbds !=
NULL )
6668 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6676 if ( nactiverows > 1 )
6678 for (
i = 0;
i < nactiverows - 1; ++
i)
6682 consvars[0] = propdata->permvars[varidxmatrix[
i][0]];
6683 consvars[1] = propdata->permvars[varidxmatrix[
i + 1][0]];
6688 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6693 for (j = 0, pos = 0; j < ncols; ++j)
6695 for (
i = 0;
i < nactiverows; ++
i)
6696 orbitopevarmatrix[pos++] = propdata->permvars[varidxmatrix[
i][j]];
6700 orbitopevarmatrix, ncols, nactiverows, success) );
6702 assert( propdata->ngenlinconss <= propdata->genlinconsssize );
6707 for (
i = 0;
i < nrows - 1; ++
i)
6711 consvars[0] = propdata->permvars[varidxmatrix[
i][0]];
6712 consvars[1] = propdata->permvars[varidxmatrix[
i + 1][0]];
6717 propdata->genlinconss[propdata->ngenlinconss++] = cons;
6722 for (j = 0, pos = 0; j < ncols; ++j)
6724 for (
i = 0;
i < nrows; ++
i)
6725 orbitopevarmatrix[pos++] = propdata->permvars[varidxmatrix[
i][j]];
6729 orbitopevarmatrix, ncols, nrows, success) );
6760 int** orbitopematrix;
6778 assert( nrowblocks > 0 );
6779 assert( ncolblocks > 0 );
6781 assert( nsignedperms >= 0 );
6786 maxdim =
MAX(nrows, ncols);
6788 for (
i = 0;
i < maxdim; ++
i)
6808 if ( nrowblocks == 1 && ncolblocks == 1 )
6819 canusecolorbitope =
TRUE;
6821 canuseroworbitope =
TRUE;
6824 if ( propdata->handlesignedorbitopes && canusecolorbitope )
6827 for (q = 0; q < nsignedperms && nflipableidx == 0; ++q)
6830 signedperms[q], propdata->npermvars,
FALSE, flipableidx, &nflipableidx) );
6834 if ( nflipableidx > 0 )
6838 if ( propdata->handlesignedorbitopes && !hascolflip && canuseroworbitope )
6840 assert( nflipableidx == 0 );
6843 for (q = 0; q < nsignedperms && nflipableidx == 0; ++q)
6846 signedperms[q], propdata->npermvars,
TRUE, flipableidx, &nflipableidx) );
6850 if ( nflipableidx > 0 )
6861 iunsigned = nflipableidx;
6862 for (
i = 0;
i < nrows; ++
i)
6864 if ( isigned < nflipableidx && flipableidx[isigned] ==
i )
6866 for (j = 0; j < ncols; ++j)
6867 orbitopematrix[isigned][j] = varidxmatrix[
i][j];
6872 for (j = 0; j < ncols; ++j)
6873 orbitopematrix[iunsigned][j] = varidxmatrix[
i][j];
6877 assert( isigned == nflipableidx );
6878 assert( iunsigned == nrows );
6883 nflipableidx, &tmpsuccess, allowchgbds, nchgbds) );
6884 *success = *success || tmpsuccess;
6886 else if ( hasrowflip )
6892 junsigned = nflipableidx;
6893 for (j = 0; j < ncols; ++j)
6895 if ( jsigned < nflipableidx && flipableidx[jsigned] == j )
6897 for (
i = 0;
i < nrows; ++
i)
6898 orbitopematrix[jsigned][
i] = varidxmatrix[
i][j];
6903 for (
i = 0;
i < nrows; ++
i)
6904 orbitopematrix[junsigned][
i] = varidxmatrix[
i][j];
6908 assert( jsigned == nflipableidx );
6909 assert( junsigned == ncols );
6914 nflipableidx, &tmpsuccess, allowchgbds, nchgbds) );
6915 *success = *success || tmpsuccess;
6924 &propdata->genorbconsssize, propdata->ngenorbconss + nrowblocks + ncolblocks) );
6927 for (p = 0; p < ncolblocks; ++p)
6934 colsbegin[p], colsbegin[p + 1],
TRUE) )
6938 for (
i = 0;
i < nrows; ++
i)
6940 for (j = 0, jj = colsbegin[p]; jj < colsbegin[p + 1]; ++j, ++jj)
6941 orbitopematrix[
i][j] = varidxmatrix[
i][jj];
6947 &tmpsuccess, allowchgbds, nchgbds) );
6948 *success = *success || tmpsuccess;
6952 for (p = 0; p < nrowblocks; ++p)
6958 rowsbegin[p], rowsbegin[p + 1], 0, ncols,
FALSE) )
6962 for (
i = 0, ii = rowsbegin[p]; ii < rowsbegin[p + 1]; ++
i, ++ii)
6964 for (j = 0; j < ncols; ++j)
6965 orbitopematrix[j][
i] = varidxmatrix[ii][j];
6971 &tmpsuccess, allowchgbds, nchgbds) );
6972 *success = *success || tmpsuccess;
6980 for (
i = maxdim - 1;
i >= 0; --
i)
7000 int** lexmatrix =
NULL;
7001 int* lexrowsbegin =
NULL;
7002 int* lexcolsbegin =
NULL;
7011 int nonpermidx = -1;
7015 int nselectedperms = 0;
7019 assert( 0 <= cidx && cidx < propdata->ncomponents );
7021 if ( nchgbds !=
NULL )
7025 if ( propdata->componentblocked[cidx] )
7029 compsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
7031 for (
i = propdata->componentbegins[cidx];
i < propdata->componentbegins[cidx + 1]; ++
i)
7033 permidx = propdata->components[
i];
7034 if ( propdata->isproperperm[permidx] )
7035 perms[nselectedperms++] = propdata->perms[permidx];
7041 if ( nselectedperms == 0 )
7048 &success, &isorbitope, &lexmatrix, &nrows, &ncols,
7049 &lexrowsbegin, &lexcolsbegin, &nrowmatrices, &ncolmatrices) );
7059 if ( nselectedperms != compsize )
7061 assert( nselectedperms < compsize );
7063 if ( nselectedperms == compsize - 1 )
7065 perms[0] = propdata->perms[nonpermidx];
7071 for (
i = propdata->componentbegins[cidx];
i < propdata->componentbegins[cidx + 1]; ++
i)
7073 permidx = propdata->components[
i];
7074 if ( ! propdata->isproperperm[permidx] )
7075 perms[nselectedperms++] = propdata->perms[permidx];
7082 int** orbitopematrix;
7094 if ( propdata->dispsyminfo )
7101 if ( propdata->handlesignedorbitopes )
7104 int nflipablerows = 0;
7114 for (p = 0; p < nselectedperms && nflipablerows == 0; ++p)
7117 flipablerows, &nflipablerows) );
7121 if ( nflipablerows > 0 )
7127 iunsigned = nflipablerows;
7129 for (
i = 0;
i < nrows; ++
i)
7133 if ( isigned < nflipablerows && flipablerows[isigned] ==
i )
7135 for (j = 0; j < ncols; ++j)
7136 orbitopematrix[isigned][j] = lexmatrix[
i][j];
7141 for (j = 0; j < ncols; ++j)
7142 orbitopematrix[iunsigned][j] = lexmatrix[
i][j];
7146 assert( isigned == nflipablerows );
7147 assert( iunsigned == nrows );
7150 TRUE,
TRUE, &success, allowchgbds, nchgbds) );
7152 for (
i = nrows - 1;
i >= 0; --
i)
7162 if ( (!success) && percentageunsigned > 0.8 )
7165 FALSE,
FALSE, &success, allowchgbds, nchgbds) );
7170 if ( propdata->dispsyminfo )
7173 nrowmatrices, ncolmatrices, lexrowsbegin, lexcolsbegin) );
7177 lexrowsbegin, lexcolsbegin, nrowmatrices, ncolmatrices, perms, nselectedperms, &success,
7178 allowchgbds, nchgbds) );
7183 for (
i = nrows - 1;
i >= 0; --
i)
7188 if ( ncolmatrices > 0 )
7192 if ( nrowmatrices > 0 )
7202 ++(propdata->ncompblocked);
7218 assert( 0 <= cidx && cidx < propdata->ncomponents );
7221 if ( propdata->componentblocked[cidx] )
7225 if ( propdata->componenthassignedperm[cidx] )
7229 if ( !propdata->usedynamicprop &&
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
7230 && propdata->binvaraffected && propdata->ncompblocked < propdata->ncomponents )
7257 assert( nknownperms >= 0 );
7259 for (p = 0; p < nknownperms; ++p)
7261 pidx = permmap ==
NULL ? p : permmap[p];
7263 for (
i = 0;
i < permlen; ++
i)
7266 if ( perm[
i] != knownperms[pidx][
i] )
7292 *istransposition =
FALSE;
7294 for (
i = 0;
i < lenperm; ++
i)
7296 if ( perm[perm[
i]] !=
i )
7302 if ( lensupport == 2 )
7303 *istransposition =
TRUE;
7347 lennewinvols = propdata->maxnnewinvolus;
7348 if( lennewinvols == 0 )
7352 assert( 0 <= cidx && cidx < propdata->ncomponents );
7357 permlen = propdata->symtype == (int)
SYM_SYMTYPE_PERM ? propdata->npermvars : 2 * propdata->npermvars;
7358 complen = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
7364 for( p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx + 1]; ++p )
7366 perm1 = propdata->perms[propdata->components[p]];
7367 if ( !
isInvolution(perm1, propdata->npermvars, &istransposition) )
7371 if ( istransposition )
7374 for( q = p + 1; q < propdata->componentbegins[cidx + 1]; ++q )
7376 perm2 = propdata->perms[propdata->components[q]];
7377 if ( !
isInvolution(perm2, propdata->npermvars, &istransposition) )
7379 if ( istransposition )
7384 for (
i = 0;
i < propdata->npermvars && commute; ++
i)
7386 if ( perm1[perm2[
i]] != perm2[perm1[
i]] )
7393 for (
i = 0;
i < propdata->npermvars; ++
i)
7394 tmpperm[
i] = perm1[perm2[
i]];
7396 if (
isPermKnown(tmpperm, propdata->npermvars, propdata->perms, complen,
7397 &propdata->components[propdata->componentbegins[cidx]]) )
7399 if (
isPermKnown(tmpperm, propdata->npermvars, newinvols, nnewinvols,
NULL) )
7401 assert( nnewinvols < lennewinvols );
7405 for (
i = 0;
i < permlen; ++
i)
7406 newinvols[nnewinvols][
i] = perm1[perm2[
i]];
7412 for (
i = 0;
i < propdata->npermvars; ++
i)
7413 tmpperm[
i] = perm1[perm2[perm1[
i]]];
7419 if (
isPermKnown(tmpperm, propdata->npermvars, propdata->perms, complen,
7420 &propdata->components[propdata->componentbegins[cidx]]) )
7422 if (
isPermKnown(tmpperm, propdata->npermvars, newinvols, nnewinvols,
NULL) )
7426 assert( nnewinvols < lennewinvols );
7430 for (
i = 0;
i < permlen; ++
i)
7431 newinvols[nnewinvols][
i] = perm1[perm2[perm1[
i]]];
7434 if ( nnewinvols == lennewinvols )
7438 for (
i = 0;
i < propdata->npermvars; ++
i)
7439 tmpperm[
i] = perm2[perm1[perm2[
i]]];
7442 if (
isPermKnown(tmpperm, propdata->npermvars, propdata->perms, complen,
7443 &propdata->components[propdata->componentbegins[cidx]]) )
7445 if (
isPermKnown(tmpperm, propdata->npermvars, newinvols, nnewinvols,
NULL) )
7450 for (
i = 0;
i < permlen; ++
i)
7451 newinvols[nnewinvols][
i] = perm2[perm1[perm2[
i]]];
7455 if ( nnewinvols >= lennewinvols )
7458 if ( nnewinvols >= lennewinvols )
7462 if ( nnewinvols == 0 )
7470 nnewperms = propdata->nperms + nnewinvols;
7471 newsize = propdata->nmaxperms;
7472 if ( nnewperms > propdata->nmaxperms )
7475 newsize = nnewperms;
7477 for (p = 0, q = propdata->nperms; p < nnewinvols; ++p, ++q)
7480 for (
i = 0;
i < permlen; ++
i)
7481 propdata->perms[q][
i] = newinvols[p][
i];
7485 if ( propdata->permstrans !=
NULL )
7487 for (
i = 0;
i < permlen; ++
i)
7489 if ( newsize > propdata->nmaxperms )
7493 for (p = propdata->nperms; p < nnewperms; ++p)
7494 propdata->permstrans[
i][p] = propdata->perms[p][
i];
7497 propdata->nmaxperms = newsize;
7501 for (
i = propdata->nperms - 1;
i >= propdata->componentbegins[cidx + 1]; --
i)
7502 propdata->components[
i + nnewinvols] = propdata->components[
i];
7505 for (p = propdata->nperms, q = propdata->componentbegins[cidx + 1]; p < nnewperms; ++p, ++q)
7506 propdata->components[q] = p;
7509 for (
i = cidx + 1;
i <= propdata->ncomponents; ++
i)
7510 propdata->componentbegins[
i] += nnewinvols;
7514 for (p = propdata->nperms; p < nnewperms; ++p)
7516 propdata->isproperperm[p] =
TRUE;
7519 for (
i = 0;
i < propdata->npermvars; ++
i)
7521 if ( propdata->perms[p][
i] >= propdata->npermvars )
7523 propdata->isproperperm[p] =
FALSE;
7529 propdata->nperms = nnewperms;
7532 for (
i = nnewinvols - 1;
i >= 0; --
i)
7578 assert( propdata->ncomponents >= 0 );
7579 assert( 0 <= cidx && cidx < propdata->ncomponents );
7582 if ( propdata->componentblocked[cidx] )
7585 if ( propdata->dispsyminfo )
7591 if ( propdata->detectdoublelex || propdata->detectorbitopes )
7595 detectsinglelex = propdata->detectdoublelex ?
FALSE :
TRUE;
7599 allowchgbds, &nlocchgs) );
7601 if ( nchgbds !=
NULL )
7602 (*nchgbds) += nlocchgs;
7609 if ( ! propdata->componentblocked[cidx] )
7620 || (
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
7624 if ( nchgbds !=
NULL )
7625 (*nchgbds) += nlocchgs;
7650 if ( nchgbds !=
NULL )
7652 if ( earlyterm !=
NULL )
7658 if ( earlyterm !=
NULL )
7665 assert( propdata->usesymmetry >= 0 );
7668 if ( propdata->usesymmetry == 0 )
7670 if ( earlyterm !=
NULL )
7676 if ( propdata->triedaddsymmethods )
7678 assert( propdata->nperms >= 0 );
7680 if ( earlyterm !=
NULL )
7685 assert( !propdata->triedaddsymmethods );
7688 if ( !propdata->computedsymmetry )
7696 if ( !propdata->computedsymmetry )
7700 propdata->triedaddsymmethods =
TRUE;
7701 assert( propdata->nperms >= 0 );
7704 if ( propdata->nperms == 0 )
7709 assert( propdata->ncomponents > 0 );
7711 if ( propdata->dispsyminfo )
7717 for (
c = 0;
c < propdata->ncomponents; ++
c)
7725 if ( propdata->dispsyminfo )
7730#ifdef SYMMETRY_STATISTICS
7762 *didrun |= didrunlocal;
7769 *didrun |= didrunlocal;
7776 *didrun |= didrunlocal;
7804 if ( propdata->usesymmetry < 0 )
7808 assert( propdata->usesymmetry >= 0 );
7811 if ( propdata->usesymmetry == 0 )
7840 assert( propdata->usesymmetry >= 0 );
7843 if ( propdata->usesymmetry == 0 )
7898 assert( propdata->usesymmetry >= 0 );
7901 if ( propdata->usesymmetry == 0 )
7915 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
7927 *nchgbds += nchanges;
7931 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
7934 assert( propdata->nperms > 0 );
7935 assert( propdata->triedaddsymmethods );
7940 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
7941 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
7944 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
7947 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7948 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7958 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
7961 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7962 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7972 propdata->ngenorbconss + propdata->ngenlinconss);
7974 for (
i = 0;
i < propdata->nsstconss; ++
i)
7977 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7978 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7987 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
8019 if ( propdata->usesymmetry <= 0 )
8027 propdata->symfoundreduction =
TRUE;
8034 propdata->symfoundreduction =
TRUE;
8061 propdata->usesymmetry = -1;
8062 propdata->triedaddsymmethods =
FALSE;
8063 propdata->nsymresacks = 0;
8064 propdata->norbitopes = 0;
8065 propdata->lastrestart = 0;
8066 propdata->symfoundreduction =
FALSE;
8105 assert( propdata->customsymopnodetypes !=
NULL );
8115 assert( propdata->orbitopalreddata !=
NULL );
8140 propdata->npermvars = 0;
8141 propdata->nbinpermvars = 0;
8142 propdata->permvars =
NULL;
8143 propdata->nperms = -1;
8144 propdata->nmaxperms = 0;
8145 propdata->perms =
NULL;
8146 propdata->permstrans =
NULL;
8147 propdata->permvarmap =
NULL;
8148 propdata->permvardomaincenter =
NULL;
8150 propdata->ncomponents = -1;
8151 propdata->ncompblocked = 0;
8152 propdata->components =
NULL;
8153 propdata->componentbegins =
NULL;
8154 propdata->vartocomponent =
NULL;
8155 propdata->componentblocked =
NULL;
8156 propdata->componenthassignedperm =
NULL;
8158 propdata->log10groupsize = -1.0;
8159 propdata->nmovedvars = -1;
8160 propdata->binvaraffected =
FALSE;
8161 propdata->computedsymmetry =
FALSE;
8162 propdata->conshdlr_nonlinear =
NULL;
8164 propdata->usesymmetry = -1;
8165 propdata->triedaddsymmethods =
FALSE;
8166 propdata->genorbconss =
NULL;
8167 propdata->genlinconss =
NULL;
8168 propdata->ngenorbconss = 0;
8169 propdata->ngenlinconss = 0;
8170 propdata->genorbconsssize = 0;
8171 propdata->genlinconsssize = 0;
8172 propdata->nsymresacks = 0;
8173 propdata->norbitopes = 0;
8174 propdata->isnonlinvar =
NULL;
8175 propdata->isproperperm =
NULL;
8177 propdata->nmovedpermvars = -1;
8178 propdata->nmovedbinpermvars = 0;
8179 propdata->nmovedintpermvars = 0;
8180 propdata->nmovedcontpermvars = 0;
8181 propdata->lastrestart = 0;
8182 propdata->symfoundreduction =
FALSE;
8184 propdata->sstconss =
NULL;
8185 propdata->nsstconss = 0;
8186 propdata->maxnsstconss = 0;
8187 propdata->leaders =
NULL;
8188 propdata->nleaders = 0;
8189 propdata->maxnleaders = 0;
8209 tabledata->propdata = propdata;
8216 "propagating/" PROP_NAME "/maxgenerators",
8217 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
8221 "propagating/" PROP_NAME "/checksymmetries",
8222 "Should all symmetries be checked after computation?",
8226 "propagating/" PROP_NAME "/displaynorbitvars",
8227 "Should the number of variables affected by some symmetry be displayed?",
8231 "propagating/" PROP_NAME "/doubleequations",
8232 "Double equations to positive/negative version?",
8236 "propagating/" PROP_NAME "/dispsyminfo",
8237 "Shall symmetry information be printed to the terminal?",
8243 "Should the symmetry breaking constraints be added to the LP?",
8247 "propagating/" PROP_NAME "/addsymresacks",
8248 "Add inequalities for symresacks for each generator?",
8252 "propagating/" PROP_NAME "/detectdoublelex",
8253 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
8257 "propagating/" PROP_NAME "/detectorbitopes",
8258 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
8262 "propagating/" PROP_NAME "/detectsubgroups",
8263 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
8267 "propagating/" PROP_NAME "/addweaksbcs",
8268 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
8272 "propagating/" PROP_NAME "/addconsstiming",
8273 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) [disabled parameter]",
8278 "propagating/" PROP_NAME "/ofsymcomptiming",
8279 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) [disabled parameter]",
8283 "propagating/" PROP_NAME "/performpresolving",
8284 "run orbital fixing during presolving? (disabled)",
8288 "propagating/" PROP_NAME "/recomputerestart",
8289 "recompute symmetries after a restart has occurred? (0 = never)",
8293 "propagating/" PROP_NAME "/compresssymmetries",
8294 "Should non-affected variables be removed from permutation to save memory?",
8298 "propagating/" PROP_NAME "/compressthreshold",
8299 "Compression is used if percentage of moved vars is at most the threshold.",
8303 "propagating/" PROP_NAME "/usecolumnsparsity",
8304 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
8308 "propagating/" PROP_NAME "/maxnconsssubgroup",
8309 "maximum number of constraints up to which subgroup structures are detected",
8313 "propagating/" PROP_NAME "/usedynamicprop",
8314 "whether dynamified symmetry handling constraint methods should be used",
8318 "propagating/" PROP_NAME "/addstrongsbcs",
8319 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
8323 "propagating/" PROP_NAME "/ssttiebreakrule",
8324 "rule to select the orbit in Schreier Sims inequalities (variable in 0: minimum size orbit; 1: maximum size orbit; 2: orbit with most variables in conflict with leader)",
8328 "propagating/" PROP_NAME "/sstleaderrule",
8329 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
8333 "propagating/" PROP_NAME "/sstleadervartype",
8334 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: continuous);" \
8335 "if multiple types are allowed, take the one with most affected vars",
8339 "propagating/" PROP_NAME "/addconflictcuts",
8340 "Should Schreier Sims constraints be added if we use a conflict based rule?",
8345 "Should Schreier Sims constraints be added?",
8349 "propagating/" PROP_NAME "/sstmixedcomponents",
8350 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
8354 "propagating/" PROP_NAME "/symfixnonbinaryvars",
8355 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
8359 "propagating/" PROP_NAME "/enforcecomputesymmetry",
8360 "Is only symmetry on binary variables used?",
8364 "propagating/" PROP_NAME "/preferlessrows",
8365 "Shall orbitopes with less rows be preferred in detection?",
8370 "Type of symmetries that shall be computed?",
8374 "propagating/" PROP_NAME "/handlesignedorbitopes",
8375 "Should orbitopes on which proper signed permutations act be handled?",
8379 "propagating/" PROP_NAME "/usesimplesgncomp",
8380 "Should components consisting of a single full reflection be handled?",
8385 "timing of symmetry computation and handling (0 = before presolving, 1 = during presolving, 2 = after presolving)",
8389 "propagating/" PROP_NAME "/maxnnewivolus",
8390 "maximum number of newly generated involutions per symmetry component",
8397 "propagating/" PROP_NAME "/nautymaxlevel",
8398 "terminate symmetry detection using Nauty when depth level of Nauty's search tree exceeds this number (-1: unlimited)",
8414 assert( propdata->shadowtreeeventhdlr !=
NULL );
8417 assert( propdata->orbitopalreddata !=
NULL );
8441 int** componentbegins,
8442 int** vartocomponent,
8469 *npermvars = propdata->npermvars;
8470 *permvars = propdata->permvars;
8472 if ( permvarmap !=
NULL )
8474 if ( propdata->nperms > 0 )
8478 *permvarmap = propdata->permvarmap;
8481 *nperms = propdata->nperms;
8482 if ( perms !=
NULL )
8484 *perms = propdata->perms;
8488 if ( permstrans !=
NULL )
8490 if ( propdata->nperms > 0 )
8494 *permstrans = propdata->permstrans;
8495 assert( *permstrans !=
NULL || *nperms <= 0 );
8498 if ( log10groupsize !=
NULL )
8499 *log10groupsize = propdata->log10groupsize;
8501 if ( binvaraffected !=
NULL )
8502 *binvaraffected = propdata->binvaraffected;
8506 if ( propdata->nperms > 0 )
8515 if ( componentbegins !=
NULL )
8516 *componentbegins = propdata->componentbegins;
8518 if ( vartocomponent )
8519 *vartocomponent = propdata->vartocomponent;
8522 *ncomponents = propdata->ncomponents;
8545 if ( propdata->nperms < 0 )
8548 return propdata->nperms;
8566 if ( propdata->nperms == -1 )
8570 else if ( propdata->nperms == 0 )
8574 else if ( propdata->ncomponents < 0 )
8592 const char* opnodename,
8605 SCIPerrorMessage(
"Cannot create operator node type, symmetry propagator has not been included.\n");
8611 assert( propdata->customsymopnodetypes !=
NULL );
8615 SCIPerrorMessage(
"Cannot create operator node type %s, it already exists.\n", opnodename);
8620 *nodetype = propdata->nopnodetypes++;
8631 const char* opnodename,
8643 SCIPerrorMessage(
"Cannot return operator node type, symmetry propagator has not been included.\n");
8649 assert( propdata->customsymopnodetypes !=
NULL );
static GRAPHNODE ** active
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
const char * SYMsymmetryGetAddName(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
SCIP_Bool SYMcanComputeSymmetry(void)
const char * SYMsymmetryGetDesc(void)
const char * SYMsymmetryGetAddDesc(void)
Constraint handler for AND constraints, .
constraint handler for bound disjunction constraints
constraint handler for indicator constraints
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
constraint handler for linking binary variables to a linking (continuous or integer) variable
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for nonlinear constraints specified by algebraic expressions
Constraint handler for "or" constraints, .
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nrows, int ncols, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool checkpporbitope, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
interface for constraint handlers of type partitioning, packing, and full
Constraint handler for the set partitioning / packing / covering constraints .
constraint handler for SOS type 1 constraints
constraint handler for SOS type 2 constraints
constraint handler for symresack constraints
Constraint handler for variable bound constraints .
Constraint handler for XOR constraints, .
SCIP_Real SCIPgetShadowTreeEventHandlerExecutionTime(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
SCIP_RETCODE SCIPincludeEventHdlrShadowTree(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr)
power and signed power expression handlers
product expression handler
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
@ SCIP_SETPPCTYPE_COVERING
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNBinImplVars(SCIP *scip)
SCIP_CONS ** SCIPgetConss(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_PARAM * SCIPgetParam(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
int SCIPgetNActiveBenders(SCIP *scip)
int SCIPgetNConshdlrs(SCIP *scip)
SCIP_Bool SCIPconshdlrSupportsSignedPermsymDetection(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Bool SCIPconshdlrSupportsPermsymDetection(SCIP_CONSHDLR *conshdlr)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR ** SCIPgetConshdlrs(SCIP *scip)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsSignedPermsymGraph(SCIP *scip, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPpresolCons(SCIP *scip, SCIP_CONS *cons, int nrounds, SCIP_PRESOLTIMING presoltiming, int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, int *nfixedvars, int *naggrvars, int *nchgvartypes, int *nchgbds, int *naddholes, int *ndelconss, int *naddconss, int *nupgdconss, int *nchgcoefs, int *nchgsides, SCIP_RESULT *result)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
SCIP_RETCODE SCIPgetConsPermsymGraph(SCIP *scip, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPcreateDatatreeInTree(SCIP *scip, SCIP_DATATREE *datatree, SCIP_DATATREE **newtree, const char *name, int capacity)
SCIP_RETCODE SCIPinsertDatatreeInt(SCIP *scip, SCIP_DATATREE *datatree, const char *name, int value)
SCIP_RETCODE SCIPinsertDatatreeReal(SCIP *scip, SCIP_DATATREE *datatree, const char *name, SCIP_Real value)
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
int SCIPgetNExprhdlrs(SCIP *scip)
SCIP_Bool SCIPexprhdlrHasGetSymData(SCIP_EXPRHDLR *exprhdlr)
SCIP_EXPRHDLR ** SCIPgetExprhdlrs(SCIP *scip)
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_PROP * SCIPfindProp(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop,)
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop,)
const char * SCIPpropGetName(SCIP_PROP *prop)
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop,)
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisReoptEnabled(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
SCIP_RETCODE SCIPcomputeOrbitVar(SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
SCIP_VARTYPE SCIPgetSymInferredVarType(SCIP_VAR *var)
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
SCIP_TABLEDATA * SCIPtableGetData(SCIP_TABLE *table)
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_DECL_TABLECOLLECT((*tablecollect)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNCliques(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_RETCODE SCIPfreeSymgraph(SCIP *scip, SYM_GRAPH **graph)
SCIP_RETCODE SCIPcreateSymgraph(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH **graph, SCIP_VAR **symvars, int nsymvars, int nopnodes, int nvalnodes, int nconsnodes, int nedges)
SCIP_RETCODE SCIPcomputeSymgraphColors(SCIP *scip, SYM_GRAPH *graph, SYM_SPEC fixedtype)
SCIP_RETCODE SCIPcreateSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPfreeSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPcopySymgraph(SCIP *scip, SYM_GRAPH **graph, SYM_GRAPH *origgraph, int *perm, SYM_SPEC fixedtype)
int SCIPgetSymgraphNVarcolors(SYM_GRAPH *graph)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
internal miscellaneous methods
SCIP_Bool SCIPparamGetBool(SCIP_PARAM *param)
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define PROP_PRESOL_PRIORITY
#define DEFAULT_CONSSADDLP
static SCIP_RETCODE handleOrbitope(SCIP *scip, SCIP_PROPDATA *propdata, int componentid, int **varidxmatrix, int nrows, int ncols, char *partialname, SCIP_Bool issigned, SCIP_Bool handlestatically, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
static SCIP_Bool conshdlrCanProvideSymInformation(SCIP_CONSHDLR *conshdlr, SYM_SYMTYPE symtype)
static SCIP_RETCODE printSyminfoComponentHeader(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
#define DEFAULT_MAXGENERATORS
static SCIP_RETCODE ensureSymmetryMovedPermvarsCountsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_HANDLESIGNEDORBITOPES
#define DEFAULT_DETECTSUBGROUPS
#define DEFAULT_SSTLEADERRULE
#define DEFAULT_PREFERLESSROWS
static SCIP_Bool isInvolution(int *perm, int lenperm, SCIP_Bool *istransposition)
#define ISSSTINTACTIVE(x)
static SCIP_RETCODE tryAddSymmetryHandlingMethodsComponent(SCIP *scip, SCIP_PROPDATA *propdata, int cidx, SCIP_Bool allowchgbds, int *nchgbds)
static SCIP_Bool hasInferredIntVar(SCIP *scip)
#define TABLE_POSITION_SYMMETRY
#define DEFAULT_ADDWEAKSBCS
static SCIP_Bool checkSortedArraysHaveOverlappingEntry(void **arr1, int narr1, void **arr2, int narr2,)
static SCIP_RETCODE buildSubgroupGraph(SCIP *scip, SCIP_PROPDATA *propdata, int *genorder, int ntwocycleperms, int compidx, int **graphcomponents, int **graphcompbegins, int **compcolorbegins, int *ngraphcomponents, int *ncompcolors, int **usedperms, int *nusedperms, int usedpermssize, SCIP_Shortbool *permused)
#define DEFAULT_ADDSTRONGSBCS
static SCIP_RETCODE propagateSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
static SCIP_RETCODE handleDoubleLexOrbitope(SCIP *scip, SCIP_PROPDATA *propdata, int **varidxmatrix, int nrows, int ncols, char *partialname, int nsignedrows, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
#define DEFAULT_SYMCOMPTIMING
SCIP_RETCODE SCIPgetSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents)
static SCIP_RETCODE ensureSymmetryPermvarmapComputed(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE createConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA **varconflicts, SCIP_VAR **conflictvars, int nconflictvars, SCIP_HASHMAP *conflictvarmap)
static SCIP_RETCODE ensureDynamicConsArrayAllocatedAndSufficientlyLarge(SCIP *scip, SCIP_CONS ***consarrptr, int *consarrsizeptr, int consarrsizereq)
#define DEFAULT_SSTLEADERVARTYPE
static SCIP_Bool isPermKnown(int *perm, int permlen, int **knownperms, int nknownperms, int *permmap)
#define DEFAULT_COMPRESSSYMMETRIES
static SCIP_RETCODE adaptSymmetryDataSST(SCIP *scip, int **origperms, int **modifiedperms, int nperms, SCIP_VAR **origpermvars, SCIP_VAR **modifiedpermvars, int npermvars, int *leaders, int nleaders)
#define ISSYMRETOPESACTIVE(x)
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)
static SCIP_RETCODE addWeakSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int ncompcolors, int *chosencomppercolor, int *firstvaridxpercolor, int symgrpcompidx, int *naddedconss, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
#define DEFAULT_ADDSYMRESACKS
static SCIP_RETCODE hasOrbitopeColumnFlip(int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, int *signedperm, int npermvars, SCIP_Bool transposed, int *flipablerows, int *nflipablerows)
#define DEFAULT_NAUTYMAXLEVEL
static int getNOrbitopesInComp(SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
#define DEFAULT_SSTTIEBREAKRULE
#define DEFAULT_DOUBLEEQUATIONS
#define DEFAULT_SSTMIXEDCOMPONENTS
SCIP_RETCODE SCIPcreateSymOpNodeType(SCIP *scip, const char *opnodename, int *nodetype)
static SCIP_RETCODE displaySymmetriesWithComponents(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_RETCODE SCIPdisplaySymmetryGenerators(SCIP *scip, SCIP_PROP *prop)
#define DEFAULT_ADDCONFLICTCUTS
static SCIP_RETCODE tryHandleSingleOrDoubleLexMatricesComponent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool detectsinglelex, int cidx, SCIP_Bool allowchgbds, int *nchgbds)
static SCIP_RETCODE updateSymInfoConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits)
#define ISSSTBINACTIVE(x)
static SCIP_RETCODE estimateSymgraphSize(SCIP *scip, int *nopnodes, int *nvalnodes, int *nconsnodes, int *nedges)
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
#define DEFAULT_DETECTDOUBLELEX
static SCIP_Bool isNonstandardPerm(SCIP *scip, int *symmetry, SCIP_VAR **vars, int nvars)
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
static SCIP_RETCODE tryHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE tryAddSymmetryHandlingMethods(SCIP *scip, SCIP_PROP *prop, SCIP_Bool allowchgbds, int *nchgbds, SCIP_Bool *earlyterm)
static SCIP_RETCODE printSyminfoHeader(SCIP *scip)
static SCIP_Bool testSymmetryComputationRequired(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE printSyminfoFooter(SCIP *scip)
static int compareSymgraphs(SCIP *scip, SYM_GRAPH *G1, SYM_GRAPH *G2)
struct SCIP_ConflictData SCIP_CONFLICTDATA
static SCIP_RETCODE resetDynamicSymmetryHandling(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_USESIMPLESGNCOMP
static SCIP_RETCODE selectOrbitLeaderSSTConss(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool *success)
#define DEFAULT_COMPRESSTHRESHOLD
#define TABLE_EARLIEST_SYMMETRY
#define DEFAULT_DETECTORBITOPES
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE SCIPdisplaySymmetryStatistics(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE printSyminfoGroupAction(SCIP *scip, SCIP_Bool isorbitope, SCIP_Bool isdoublelex, int nrows, int ncols, int nrowmatrices, int ncolmatrices, int *rowsbegin, int *colsbegin)
#define DEFAULT_DISPSYMINFO
#define DEFAULT_ADDCONSSTIMING
#define DEFAULT_SSTADDCUTS
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, int npermvars, SYM_SPEC fixedtype)
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
#define TABLE_NAME_SYMMETRY
#define DEFAULT_CHECKSYMMETRIES
#define DEFAULT_USEDYNAMICPROP
#define DEFAULT_RECOMPUTERESTART
static SCIP_RETCODE checkComponentsForNonstandardPerms(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_MAXNCONSSSUBGROUP
static SCIP_RETCODE tryAddOrbitalRedLexRed(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS
#define TABLE_DESC_SYMMETRY
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA **varconflicts, int nvars)
static SCIP_RETCODE addStrongSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
#define DEFAULT_ENFORCECOMPUTESYMMETRY
#define ISORBITALREDUCTIONACTIVE(x)
static SCIP_RETCODE tryGenerateInvolutions(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool onlywithcontvars, int *nchgbds, int cidx)
static SCIP_RETCODE addOrbitopeSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *usedperms, int nusedperms, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int graphcoloridx, int nrows, int ncols, int *firstvaridx, int *compidxfirstrow, int **lexorder, int *nvarslexorder, int *maxnvarslexorder, SCIP_Bool *success)
static SCIP_Bool hasInferredBinVar(SCIP *scip)
static SCIP_RETCODE handleDoublelLexMatrix(SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, int *rowsbegin, int *colsbegin, int nrowblocks, int ncolblocks, int **signedperms, int nsignedperms, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
#define DEFAULT_PERFORMPRESOLVING
#define DEFAULT_MAXNNEWINVOLUS
static SCIP_RETCODE checkTwoCyclePermsAreOrbitope(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int *activeperms, int ntwocycles, int nactiveperms, int **orbitopevaridx, int *columnorder, int *nusedelems, int *nusedcols, SCIP_Shortbool *rowisbinary, SCIP_Bool *isorbitope, SCIP_Shortbool *activevars)
static SCIP_RETCODE ensureSymmetryPermstransComputed(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE displaySymmetriesWithoutComponents(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE addSSTConssOrbitAndUpdateSST(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds)
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
static SCIP_RETCODE displayCycleOfSymmetry(SCIP *scip, int *perm, SYM_SYMTYPE symtype, int baseidx, SCIP_Bool *covered, int nvars, SCIP_VAR **vars)
int SCIPgetSymmetryNGenerators(SCIP *scip)
#define DEFAULT_SYMFIXNONBINARYVARS
static SCIP_RETCODE ensureSymmetryComponentsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE setSymmetryData(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, SCIP_Bool **isproperperm, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE componentPackingPartitioningOrbisackUpgrade(SCIP *scip, SCIP_PROPDATA *propdata, int **componentperms, int componentsize, SCIP_Bool hassignedperm, SCIP_Bool *success, int *naddedconss)
#define ISSSTCONTACTIVE(x)
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SYM_SYMTYPE symtype, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool checksymmetries, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, SCIP_Bool **isproperperm, int ***perms, int *nperms, int *nmaxperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *log10groupsize, SCIP_Real *symcodetime, SCIP_Bool *success)
#define DEFAULT_DISPLAYNORBITVARS
static SCIP_Bool isEquallyCenteredOrbitope(SCIP *scip, SCIP_Real *vardomaincenter, int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, SCIP_Bool equalrowcenters)
static SCIP_RETCODE addOrbitopesDynamic(SCIP *scip, SCIP_PROPDATA *propdata, int componentid, char *partialname, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
SCIP_RETCODE SCIPgetSymOpNodeType(SCIP *scip, const char *opnodename, int *nodetype)
static SCIP_Bool conshdlrsCanProvideSymInformation(SCIP *scip, SYM_SYMTYPE symtype)
#define DEFAULT_USECOLUMNSPARSITY
propagator for symmetry handling
public functions to work with algebraic expressions
public methods for data structures
methods for handling symmetries
methods for dealing with symmetry detection graphs
SCIP_RETCODE SCIPlexicographicReductionPropagate(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
SCIP_RETCODE SCIPlexicographicReductionGetStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
SCIP_RETCODE SCIPlexicographicReductionReset(SCIP *scip, SCIP_LEXREDDATA *masterdata)
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata)
SCIP_RETCODE SCIPlexicographicReductionFree(SCIP *scip, SCIP_LEXREDDATA **masterdata)
SCIP_RETCODE SCIPlexicographicReductionAddPermutation(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_VAR **permvars, int npermvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success)
SCIP_RETCODE SCIPincludeLexicographicReduction(SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
methods for handling symmetries by dynamic lexicographic ordering reduction
struct SCIP_LexRedData SCIP_LEXREDDATA
SCIP_RETCODE SCIPorbitalReductionFree(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitalReductionGetStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
SCIP_RETCODE SCIPincludeOrbitalReduction(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
SCIP_RETCODE SCIPorbitalReductionPrintStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
SCIP_RETCODE SCIPorbitalReductionAddComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
SCIP_RETCODE SCIPorbitalReductionReset(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
SCIP_RETCODE SCIPincludeOrbitopalReduction(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionFree(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE SCIPorbitopalReductionReset(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
SCIP_RETCODE SCIPorbitopalReductionPropagate(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
SCIP_RETCODE SCIPorbitopalReductionGetStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(SCIP_ORBITOPALREDDATA *orbireddata)
@ SCIP_COLUMNORDERING_NONE
enum SCIP_ColumnOrdering SCIP_COLUMNORDERING
@ SCIP_ROWORDERING_BRANCHING
struct SCIP_OrbitopalReductionData SCIP_ORBITOPALREDDATA
struct SCIP_Cons SCIP_CONS
struct SYM_Graph SYM_GRAPH
struct SCIP_Conshdlr SCIP_CONSHDLR
struct SCIP_Datatree SCIP_DATATREE
struct SCIP_Eventhdlr SCIP_EVENTHDLR
struct SCIP_Exprhdlr SCIP_EXPRHDLR
struct SCIP_Clique SCIP_CLIQUE
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_SORTINDCOMP(x)
struct SCIP_DisjointSet SCIP_DISJOINTSET
struct SCIP_Param SCIP_PARAM
#define SCIP_DECL_PROPEXITPRE(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXITSOL(x)
#define SCIP_DECL_PROPEXIT(x)
struct SCIP_Prop SCIP_PROP
#define SCIP_DECL_PROPPRESOL(x)
#define SCIP_DECL_PROPINITPRE(x)
#define SCIP_DECL_PROPRESPROP(x)
struct SCIP_PropData SCIP_PROPDATA
#define SCIP_DECL_PROPEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_ORBITOPETYPE_PACKING
enum SYM_Symtype SYM_SYMTYPE
@ SCIP_LEADERRULE_LASTINORBIT
@ SCIP_LEADERRULE_MAXCONFLICTSINORBIT
@ SCIP_LEADERRULE_FIRSTINORBIT
#define SYM_TIMING_DURINGPRESOL
@ SCIP_LEADERTIEBREAKRULE_MAXORBIT
@ SCIP_LEADERTIEBREAKRULE_MINORBIT
@ SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT
#define SYM_TIMING_AFTERPRESOL
#define SYM_TIMING_BEFOREPRESOL
#define SYM_HANDLETYPE_SYMBREAK
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
#define SYM_HANDLETYPE_SST
#define SYM_HANDLETYPE_ORBITALREDUCTION
#define SCIP_DECL_TABLEFREE(x)
struct SCIP_TableData SCIP_TABLEDATA
#define SCIP_DECL_TABLEOUTPUT(x)
#define SCIP_DECL_TABLECOLLECT(x)
#define SCIP_PROPTIMING_ALWAYS
@ SCIP_VARTYPE_CONTINUOUS
enum SCIP_Vartype SCIP_VARTYPE