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
166#define DEFAULT_CONSSADDLP TRUE
167#define DEFAULT_ADDSYMRESACKS TRUE
168#define DEFAULT_DETECTDOUBLELEX TRUE
169#define DEFAULT_DETECTORBITOPES TRUE
170#define DEFAULT_DETECTSUBGROUPS TRUE
171#define DEFAULT_ADDWEAKSBCS TRUE
172#define DEFAULT_ADDSTRONGSBCS FALSE
173#define DEFAULT_ADDCONSSTIMING 2
174#define DEFAULT_MAXNCONSSSUBGROUP 500000
175#define DEFAULT_USEDYNAMICPROP TRUE
176#define DEFAULT_PREFERLESSROWS TRUE
179#define DEFAULT_SYMCOMPTIMING 2
180#define DEFAULT_PERFORMPRESOLVING 0
181#define DEFAULT_RECOMPUTERESTART 0
184#define DEFAULT_SSTTIEBREAKRULE 1
185#define DEFAULT_SSTLEADERRULE 0
186#define DEFAULT_SSTLEADERVARTYPE 14
188#define DEFAULT_ADDCONFLICTCUTS TRUE
189#define DEFAULT_SSTADDCUTS TRUE
190#define DEFAULT_SSTMIXEDCOMPONENTS TRUE
193#define TABLE_NAME_SYMMETRY "symmetry"
194#define TABLE_DESC_SYMMETRY "symmetry handling statistics"
195#define TABLE_POSITION_SYMMETRY 7001
196#define TABLE_EARLIEST_SYMMETRY SCIP_STAGE_SOLVING
200#define MAXGENNUMERATOR 64000000
201#define COMPRESSNVARSLB 25000
202#define DEFAULT_NAUTYMAXNCELLS 100000
204#define DEFAULT_NAUTYMAXNNODES 10000000
209#define ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
210#define ISORBITALREDUCTIONACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 0)
211#define ISSSTACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SST) != 0)
213#define ISSSTBINACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)
214#define ISSSTINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)
215#define ISSSTIMPLINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)
216#define ISSSTCONTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)
219#define SYMMETRY_STATISTICS 1
234 int nmovedbinpermvars;
235 int nmovedintpermvars;
236 int nmovedimplintpermvars;
237 int nmovedcontpermvars;
248 int* componentbegins;
252 unsigned* componentblocked;
294 int maxnconsssubgroup;
299 int recomputerestart;
309 int sstleadervartype;
325struct SCIP_ConflictData
330 int nconflictinorbit;
347 else if ( elem1 > elem2 )
385 cmp = compfunc(arr1[it1], arr2[it2]);
391 if ( ++it1 >= narr1 )
400 if ( ++it2 >= narr2 )
413 assert( it1 >= narr1 || it2 >= narr2 );
446 if ( perm[baseidx] == baseidx || covered[baseidx] )
453 covered[baseidx] =
TRUE;
454 while ( j != baseidx )
484 assert( propdata->nperms > 0 );
486 assert( propdata->npermvars > 0 );
489 npermvars = propdata->npermvars;
497 for (p = 0; p < propdata->nperms; ++p)
500 perm = propdata->perms[p];
502 for (
i = 0;
i < permlen; ++
i)
507 for (
i = 0;
i < permlen; ++
i)
535 assert( propdata->nperms > 0 );
537 assert( propdata->npermvars > 0 );
538 assert( propdata->ncomponents > 0 );
541 npermvars = propdata->npermvars;
546 for (
c = 0;
c < propdata->ncomponents; ++
c)
551 if ( propdata->componenthassignedperm[
c] )
556 comppermlen = propdata->componenthassignedperm[
c] ? 2 * npermvars : npermvars;
558 for (p = propdata->componentbegins[
c], cnt = 0; p < propdata->componentbegins[
c + 1]; ++p, ++cnt)
561 perm = propdata->perms[propdata->components[p]];
563 for (
i = 0;
i < comppermlen; ++
i)
568 for (
i = 0;
i < comppermlen; ++
i)
590 if ( propdata->nperms == -1 )
594 else if ( propdata->nperms == 0 )
598 else if ( propdata->ncomponents < 0 )
641 if ( tabledata->propdata->orbitopalreddata || tabledata->propdata->orbitalreddata
642 || tabledata->propdata->lexreddata )
645 if ( tabledata->propdata->orbitopalreddata )
649 " %10d cutoffs\n", nred, ncutoff);
651 if ( tabledata->propdata->orbitalreddata )
655 " %10d cutoffs\n", nred, ncutoff);
657 if ( tabledata->propdata->lexreddata )
661 " %10d cutoffs\n", nred, ncutoff);
663 if ( tabledata->propdata->shadowtreeeventhdlr )
784 if ( G1->
lhs[perm1] < G2->
lhs[perm2] )
786 if ( G1->
lhs[perm1] > G2->
lhs[perm2] )
789 if ( G1->
rhs[perm1] < G2->
rhs[perm2] )
791 if ( G1->
rhs[perm1] > G2->
rhs[perm2] )
859 assert( propdata->ngenlinconss == 0 );
860 assert( propdata->ngenorbconss == 0 );
861 assert( propdata->genorbconsssize == 0 );
862 assert( propdata->genlinconsssize == 0 );
866 assert( propdata->permvardomaincenter ==
NULL );
870 assert( propdata->npermvars == 0 );
871 assert( propdata->nbinpermvars == 0 );
872 assert( propdata->nperms == -1 || propdata->nperms == 0 );
873 assert( propdata->nmaxperms == 0 );
874 assert( propdata->nmovedpermvars == -1 );
875 assert( propdata->nmovedbinpermvars == 0 );
876 assert( propdata->nmovedintpermvars == 0 );
877 assert( propdata->nmovedimplintpermvars == 0 );
878 assert( propdata->nmovedcontpermvars == 0 );
879 assert( propdata->nmovedvars == -1 );
883 assert( propdata->componenthassignedperm ==
NULL );
887 assert( propdata->ncomponents == -1 );
888 assert( propdata->ncompblocked == 0 );
906 if ( propdata->orbitalreddata !=
NULL )
910 if ( propdata->orbitopalreddata !=
NULL )
914 if ( propdata->lexreddata !=
NULL )
937 if ( propdata->permvarmap !=
NULL )
943 for (
i = 0;
i < propdata->npermvars; ++
i)
950 if ( propdata->permstrans !=
NULL )
952 assert( propdata->nperms > 0 );
954 assert( propdata->npermvars > 0 );
955 assert( propdata->nmaxperms > 0 );
957 for (
i = 0;
i < propdata->npermvars; ++
i)
965 if ( propdata->genorbconss !=
NULL )
967 assert( propdata->ngenorbconss > 0 );
970 while ( propdata->ngenorbconss > 0 )
972 assert( propdata->genorbconss[propdata->ngenorbconss - 1] !=
NULL );
975 assert( propdata->ngenorbconss == 0 );
979 propdata->genorbconsssize = 0;
983 if ( propdata->genlinconss !=
NULL )
986 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
994 propdata->ngenlinconss = 0;
995 propdata->genlinconsssize = 0;
998 if ( propdata->sstconss !=
NULL )
1000 assert( propdata->nsstconss > 0 );
1003 for (
i = 0;
i < propdata->nsstconss; ++
i)
1011 propdata->sstconss =
NULL;
1012 propdata->nsstconss = 0;
1013 propdata->maxnsstconss = 0;
1016 if ( propdata->leaders !=
NULL )
1018 assert( propdata->maxnleaders > 0 );
1021 propdata->maxnleaders = 0;
1022 propdata->leaders =
NULL;
1023 propdata->nleaders = 0;
1027 if ( propdata->ncomponents > 0 )
1029 assert( propdata->componentblocked !=
NULL );
1040 propdata->ncomponents = -1;
1041 propdata->ncompblocked = 0;
1045 if ( propdata->nperms > 0 )
1052 permlen = 2 * propdata->npermvars;
1054 permlen = propdata->npermvars;
1059 if ( propdata->perms !=
NULL )
1061 for (
i = 0;
i < propdata->nperms; ++
i)
1070 propdata->npermvars = 0;
1071 propdata->nbinpermvars = 0;
1072 propdata->nperms = -1;
1073 propdata->nmaxperms = 0;
1074 propdata->nmovedpermvars = -1;
1075 propdata->nmovedbinpermvars = 0;
1076 propdata->nmovedintpermvars = 0;
1077 propdata->nmovedimplintpermvars = 0;
1078 propdata->nmovedcontpermvars = 0;
1079 propdata->nmovedvars = -1;
1080 propdata->log10groupsize = -1.0;
1081 propdata->binvaraffected =
FALSE;
1082 propdata->isnonlinvar =
NULL;
1084 propdata->nperms = -1;
1088 propdata->computedsymmetry =
FALSE;
1089 propdata->compressed =
FALSE;
1100 int* consarrsizeptr,
1109 assert( consarrsizereq > 0 );
1110 assert( *consarrsizeptr >= 0 );
1111 assert( (*consarrsizeptr == 0) == (*consarrptr ==
NULL) );
1114 if ( consarrsizereq <= *consarrsizeptr )
1119 assert( newsize > *consarrsizeptr );
1122 if ( *consarrptr ==
NULL )
1131 *consarrsizeptr = newsize;
1179 *binvaraffected =
FALSE;
1180 *compressed =
FALSE;
1186 int* labelmovedvars;
1187 int* labeltopermvaridx;
1188 int nbinvarsaffected = 0;
1199 labelmovedvars[
i] = -1;
1201 for (p = 0; p < nperms; ++p)
1203 if ( perms[p][
i] !=
i )
1205 labeltopermvaridx[*nmovedvars] =
i;
1206 labelmovedvars[
i] = (*nmovedvars)++;
1215 if ( nbinvarsaffected > 0 )
1216 *binvaraffected =
TRUE;
1220 if ( *nmovedvars > 0 &&
SCIPisLE(
scip, percentagemovedvars, compressthreshold) )
1223 for (p = 0; p < nperms; ++p)
1226 for (
i = 0;
i < *nmovedvars; ++
i)
1228 assert(
i <= labeltopermvaridx[
i] );
1229 if ( perms[p][labeltopermvaridx[
i]] >=
nvars )
1235 imgvaridx = perms[p][labeltopermvaridx[
i]] -
nvars;
1236 perms[p][
i] = labelmovedvars[imgvaridx] + *nmovedvars;
1238 assert( 0 <= perms[p][
i] && perms[p][
i] < 2 * (*nmovedvars) );
1241 perms[p][
i] = labelmovedvars[perms[p][labeltopermvaridx[
i]]];
1256 for (
i = 0;
i < *nmovedvars; ++
i)
1258 (*permvars)[
i] =
vars[labeltopermvaridx[
i]];
1260 *npermvars = *nmovedvars;
1261 *nbinpermvars = nbinvarsaffected;
1274 for (p = 0; p < nperms && ! *binvaraffected; ++p)
1276 if ( perms[p][
i] !=
i )
1279 *binvaraffected =
TRUE;
1288 for (
i = 0;
i < *npermvars; ++
i)
1293 (*permvardomaincenter)[
i] = 0.5 * (ub + lb);
1334 for (
c = 0;
c < nconshdlrs; ++
c)
1336 conshdlr = conshdlrs[
c];
1349 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n"
1350 " If symmetries shall be detected, implement the %s callback.\n",
1392 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n"
1429 *nconsnodes = nconss;
1434 for (
c = 0;
c < nconss; ++
c)
1462 depth = (int) log2((
double) num);
1463 expval = (int) exp2((
double) (
depth + 1));
1464 numnodes =
MIN(expval, 100);
1466 *nopnodes += numnodes;
1467 *nvalnodes +=
MAX((
int) 0.1 * numnodes, 1);
1482 *nopnodes += num - 1;
1491 if (
nvars <= 100000 )
1492 *nedges = 100 *
nvars;
1493 else if (
nvars <= 1000000 )
1494 *nedges = 32 *
nvars;
1495 else if (
nvars <= 16700000 )
1496 *nedges = 16 *
nvars;
1498 *nedges = INT_MAX / 10;
1526#ifdef SCIP_DISPLAY_SYM_CHECK
1543 assert( nsymvars == npermvars );
1547 for (
c = 0;
c < nconss; ++
c)
1570 for (
c = 0;
c < nconss; ++
c)
1575 SCIPsort(graphperm, SYMsortSymgraphs, graphs, nconss);
1578 for (
c = 1;
c < nconss; ++
c)
1581 groupbegins[ngroups++] =
c;
1583 groupbegins[ngroups] = nconss;
1586 for (
c = 0;
c < nconss; ++
c)
1591#ifdef SCIP_DISPLAY_SYM_CHECK
1597 for (p = 0; p < nperms; ++p)
1602#ifdef SCIP_DISPLAY_SYM_CHECK
1606 for (
i = 0;
i < permlen; ++
i)
1611 for (
i = 0;
i < permlen; ++
i)
1617 for (g = 0; g < ngroups; ++g)
1619 for (
c = groupbegins[g];
c < groupbegins[g+1]; ++
c)
1621#ifdef SCIP_DISPLAY_SYM_CHECK
1632#ifdef SCIP_DISPLAY_SYM_CHECK
1641 for (d = groupbegins[g]; d < groupbegins[g+1] && ! found; ++d)
1645#ifdef SCIP_DISPLAY_SYM_CHECK
1656#ifdef SCIP_DISPLAY_SYM_CHECK
1666#ifdef SCIP_DISPLAY_SYM_CHECK
1673 for (
c = nconss - 1;
c >= 0; --
c)
1740 *binvaraffected =
FALSE;
1741 *compressed =
FALSE;
1742 *log10groupsize = 0;
1768 nopnodes, nvalnodes, nconsnodes, nedges) );
1771 for (
c = 0;
c < nconss && *success; ++
c)
1806 perms, log10groupsize, symcodetime) );
1808 if ( checksymmetries && *nperms > 0 )
1823 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1824 compresssymmetries, compressthreshold, compressed) );
1848 for (v = 0; v <
nvars; ++v)
1851 if ( symmetry[v] >=
nvars )
1878 int* componentbegins;
1885 assert( propdata->ncomponents > 0 );
1890 componentbegins = propdata->componentbegins;
1891 ncomponents = propdata->ncomponents;
1900 for (
c = 0;
c < ncomponents; ++
c)
1902 for (
i = componentbegins[
c];
i < componentbegins[
c + 1]; ++
i)
1906 propdata->componenthassignedperm[
c] =
TRUE;
1926 assert( propdata->nperms >= 0 );
1929 if ( propdata->ncomponents >= 0 )
1933 assert( propdata->ncomponents == -1 );
1938#ifdef SCIP_OUTPUT_COMPONENT
1943 propdata->permvars, propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
1944 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
1946#ifdef SCIP_OUTPUT_COMPONENT
1952 assert( propdata->ncomponents > 0 );
1956 assert( propdata->componenthassignedperm !=
NULL );
1975 assert( propdata->nperms >= 0 );
1978 if ( propdata->permvarmap !=
NULL )
1985 for (v = 0; v < propdata->npermvars; ++v)
2008 assert( propdata->nperms >= 0 );
2011 if ( propdata->permstrans !=
NULL )
2017 for (v = 0; v < propdata->npermvars; ++v)
2020 for (p = 0; p < propdata->nperms; ++p)
2021 propdata->permstrans[v][p] = propdata->perms[p][v];
2042 assert( propdata->nperms >= 0 );
2045 if ( propdata->nmovedpermvars >= 0 )
2047 assert( propdata->nmovedpermvars == -1 );
2049 propdata->nmovedpermvars = 0;
2050 propdata->nmovedbinpermvars = 0;
2051 propdata->nmovedintpermvars = 0;
2052 propdata->nmovedimplintpermvars = 0;
2053 propdata->nmovedcontpermvars = 0;
2055 for (p = 0; p < propdata->nperms; ++p)
2057 for (v = 0; v < propdata->npermvars; ++v)
2059 if ( propdata->perms[p][v] != v )
2061 ++propdata->nmovedpermvars;
2066 ++propdata->nmovedbinpermvars;
2069 ++propdata->nmovedintpermvars;
2072 ++propdata->nmovedimplintpermvars;
2075 ++propdata->nmovedcontpermvars;
2097 if ( propdata->enforcecomputesymmetry )
2150 unsigned int type = 0;
2156 assert( propdata->usesymmetry >= 0 );
2170 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2198 if ( ! (type & symspecrequire) )
2201 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2214 if ( propdata->computedsymmetry )
2217 assert( propdata->npermvars == 0 );
2219 assert( propdata->nperms < 0 );
2220 assert( propdata->nmaxperms == 0 );
2225 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2232 (symspecrequirefixed & (
int)
SYM_SPEC_REAL) != 0 ?
'+' :
'-');
2235 if ( symspecrequire & symspecrequirefixed )
2239 maxgenerators = propdata->maxgenerators;
2244 propdata->compresssymmetries, propdata->compressthreshold,
2245 maxgenerators, symspecrequirefixed, propdata->checksymmetries, &propdata->permvars,
2246 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2247 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2248 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2249 &propdata->log10groupsize, &symcodetime, &successful) );
2252 propdata->computedsymmetry =
TRUE;
2267 if ( propdata->nperms == 0 )
2274 assert( propdata->nperms > 0 );
2275 assert( propdata->npermvars > 0 );
2282 if ( maxgenerators == 0 )
2290 if ( propdata->displaynorbitvars )
2292 if ( propdata->nmovedvars == -1 )
2295 propdata->npermvars, &(propdata->nmovedvars)) );
2302 for (
i = 0;
i < propdata->npermvars; ++
i)
2338 int** orbitopevaridx,
2352 int ntestedperms = 0;
2364 assert( nactiveperms > 0 );
2365 assert( ntwocycles > 0 );
2367 assert( activevars ==
NULL || (0 <= nactiveperms && nactiveperms < npermvars) );
2370 if ( nusedcols !=
NULL )
2379 while ( ! foundperm )
2383 assert( ntestedperms < nactiveperms );
2385 permidx = activeperms[ntestedperms];
2387 for (j = 0; j < npermvars; ++j)
2389 if ( activevars !=
NULL && ! activevars[j] )
2392 assert( activevars ==
NULL || activevars[perms[permidx][j]] );
2395 if ( perms[permidx][j] > j )
2400 rowisbinary[row] =
TRUE;
2402 orbitopevaridx[row][0] = j;
2403 orbitopevaridx[row++][1] = perms[permidx][j];
2405 ++(nusedelems[perms[permidx][j]]);
2410 if ( row == ntwocycles )
2418 if ( row != ntwocycles )
2420 *isorbitope =
FALSE;
2425 usedperm[ntestedperms - 1] =
TRUE;
2435 for (j = ntestedperms; j < nactiveperms; ++j)
2440 if ( nusedperms == nactiveperms )
2447 perms[activeperms[j]],
TRUE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2451 *isorbitope =
FALSE;
2458 coltoextend = nfilledcols;
2459 columnorder[nfilledcols++] = -1;
2464 if ( ! *isorbitope )
2471 for (j = ntestedperms; j < nactiveperms; ++j)
2476 if ( nusedperms == nactiveperms )
2483 perms[activeperms[j]],
FALSE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2487 *isorbitope =
FALSE;
2494 coltoextend = nfilledcols;
2495 columnorder[nfilledcols] = 1;
2501 if ( activevars ==
NULL && nusedperms < nactiveperms )
2502 *isorbitope =
FALSE;
2504 if ( nusedcols !=
NULL )
2505 *nusedcols = nfilledcols;
2506 assert( ! *isorbitope || activevars ==
NULL || nusedperms < nfilledcols );
2525 int* componentbegins;
2534 assert( compidx < propdata->ncomponents );
2538 assert( propdata->computedsymmetry );
2539 assert( propdata->nperms > 0 );
2541 assert( propdata->npermvars > 0 );
2542 assert( propdata->ncomponents > 0 );
2546 perms = propdata->perms;
2547 npermvars = propdata->npermvars;
2549 componentbegins = propdata->componentbegins;
2550 npermsincomp = componentbegins[compidx + 1] - componentbegins[compidx];
2551 *ntwocycleperms = npermsincomp;
2555 for (
i = 0;
i < npermsincomp; ++
i)
2560 perm = perms[
components[componentbegins[compidx] +
i]];
2565 if ( ntwocycles[
i] == 0 )
2568 if ( propdata->preferlessrows )
2569 ntwocycles[
i] = npermvars;
2572 --(*ntwocycleperms);
2574 else if ( ! propdata->preferlessrows )
2575 ntwocycles[
i] = - ntwocycles[
i];
2599 int** graphcomponents,
2600 int** graphcompbegins,
2601 int** compcolorbegins,
2602 int* ngraphcomponents,
2615 int* componentbegins;
2616 int* componentslastperm;
2634 assert( usedpermssize > 0 );
2636 assert( ntwocycleperms >= 0 );
2638 assert( compidx < propdata->ncomponents );
2639 assert( propdata->computedsymmetry );
2640 assert( propdata->nperms > 0 );
2642 assert( propdata->npermvars > 0 );
2643 assert( propdata->ncomponents > 0 );
2646 assert( ! propdata->componentblocked[compidx] );
2648 perms = propdata->perms;
2649 npermvars = propdata->npermvars;
2651 componentbegins = propdata->componentbegins;
2654 assert( ntwocycleperms <= componentbegins[compidx + 1] - componentbegins[compidx] );
2660 for (k = 0; k < npermvars; ++k)
2661 componentslastperm[k] = -1;
2663 for (j = 0; j < ntwocycleperms; ++j)
2666 int firstcolor = -1;
2669 perm = perms[
components[componentbegins[compidx] + genorder[j]]];
2673 for (k = 0; k < npermvars; ++k)
2682 assert( perm[img] == k );
2690 if ( comp1 == comp2 )
2693 if ( firstcolor < 0 )
2698 componentslastperm[comp1] = j;
2705 if ( componentslastperm[comp1] == j || componentslastperm[comp2] == j )
2712 if ( color1 == color2 )
2715 componentslastperm[comp1] = j;
2716 componentslastperm[comp2] = j;
2718 if ( firstcolor < 0 )
2719 firstcolor = color1;
2723 if ( k < npermvars )
2727 if ( firstcolor == -1 )
2731 if ( *nusedperms >= usedpermssize )
2734 assert( newsize > usedpermssize );
2738 usedpermssize = newsize;
2741 (*usedperms)[*nusedperms] =
components[componentbegins[compidx] + genorder[j]];
2743 permused[genorder[j]] =
TRUE;
2746 for (k = 0; k < npermvars; ++k)
2755 assert( perm[img] == k );
2764 if ( comp1 == comp2 )
2770 if ( color1 != color2 )
2794 for (j = 0; j < npermvars; ++j)
2803 (*graphcomponents)[j] = j;
2807 SCIPsort(*graphcomponents, SYMsortGraphCompVars, (
void*) &graphcompvartype, npermvars);
2816 (*graphcompbegins)[0] = 0;
2817 (*compcolorbegins)[0] = 0;
2820 for (j = 1; j < npermvars; ++j)
2825 idx1 = (*graphcomponents)[j];
2826 idx2 = (*graphcomponents)[j-1];
2832 (*graphcompbegins)[nextcomp] = j;
2834 if ( graphcompvartype.
colors[idx1] > graphcompvartype.
colors[idx2] )
2836 (*compcolorbegins)[nextcolor] = nextcomp;
2843 assert( nextcomp == *ngraphcomponents );
2844 assert( nextcolor == *ncompcolors );
2846 (*compcolorbegins)[nextcolor] = *ngraphcomponents;
2847 (*graphcompbegins)[nextcomp] = npermvars;
2865 int* compcolorbegins,
2866 int* graphcompbegins,
2867 int* graphcomponents,
2872 int* compidxfirstrow,
2875 int* maxnvarslexorder,
2883 int** orbitopevaridx;
2890 int nactivevars = 0;
2901 assert( nusedperms > 0 );
2915 for (k = 0; k < nrows; ++k)
2922 for (k = 0; k < ncols; ++k)
2923 columnorder[k] = ncols + 1;
2929 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1]; ++k)
2935 compstart = graphcompbegins[k];
2936 firstvar = propdata->permvars[graphcomponents[compstart]];
2941 for (l = 0; l < ncols; ++l)
2945 varidx = graphcomponents[compstart + l];
2954 assert( nactivevars == nrows * ncols );
2966 propdata->perms, usedperms, nrows, nusedperms, orbitopevaridx, columnorder,
2967 nusedelems, &ngencols,
NULL, &isorbitope, activevars) );
2976 for (k = nrows - 1; k >= 0; --k)
2996 if ( firstvaridx !=
NULL )
2998 if ( columnorder[ngencols-1] > -1 )
2999 *firstvaridx = orbitopevaridx[0][ngencols-1];
3001 *firstvaridx = orbitopevaridx[0][1];
3005 if ( compidxfirstrow !=
NULL && firstvaridx !=
NULL )
3007 *compidxfirstrow = -1;
3009 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3015 compstart = graphcompbegins[k];
3016 firstvar = propdata->permvars[graphcomponents[compstart]];
3024 for (l = 0; l < ncols; ++l)
3026 if ( graphcomponents[compstart + l] == *firstvaridx )
3028 *compidxfirstrow = k;
3033 assert( *compidxfirstrow > -1 );
3038 for (k = 0; k < nrows; ++k)
3045 propdata->permvars, propdata->npermvars, orbitopevaridx, columnorder,
3046 nusedelems,
NULL, &infeasible,
TRUE, lexorder, nvarslexorder, maxnvarslexorder) );
3049 assert( firstvaridx ==
NULL || propdata->permvars[*firstvaridx] == orbitopevarmatrix[0][0] );
3062 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3063 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3064 ++propdata->norbitopes;
3066 for (k = nrows - 1; k >= 0; --k)
3071 for (k = nrows - 1; k >= 0; --k)
3084 int* graphcompbegins,
3085 int* graphcomponents,
3099 assert( graphcompidx >= 0 );
3100 assert( ! storelexorder || lexorder !=
NULL );
3101 assert( ! storelexorder || nvarsorder !=
NULL );
3102 assert( ! storelexorder || maxnvarsorder !=
NULL );
3105 if ( storelexorder )
3107 if ( *maxnvarsorder == 0 )
3109 *maxnvarsorder = graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3116 assert( *nvarsorder == *maxnvarsorder );
3118 *maxnvarsorder += graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3123 (*lexorder)[*nvarsorder++] = graphcomponents[graphcompbegins[graphcompidx]];
3127 for (k = graphcompbegins[graphcompidx]+1; k < graphcompbegins[graphcompidx+1]; ++k)
3134 vars[0] = propdata->permvars[graphcomponents[k-1]];
3135 vars[1] = propdata->permvars[graphcomponents[k]];
3137 if ( storelexorder )
3138 (*lexorder)[*nvarsorder++] = graphcomponents[k];
3148#ifdef SCIP_MORE_DEBUG
3155 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3156 propdata->genlinconss[propdata->ngenlinconss] = cons;
3157 ++propdata->ngenlinconss;
3168 int* compcolorbegins,
3169 int* graphcompbegins,
3170 int* graphcomponents,
3172 int* chosencomppercolor,
3173 int* firstvaridxpercolor,
3188 int orbitsize[2] = {1, 1};
3190 int chosencolor = -1;
3202 assert( symgrpcompidx >= 0 );
3203 assert( symgrpcompidx < propdata->ncomponents );
3204 assert( ! storelexorder || lexorder !=
NULL );
3205 assert( ! storelexorder || nvarsorder !=
NULL );
3206 assert( ! storelexorder || maxnvarsorder !=
NULL );
3216 if ( lexorder ==
NULL || *lexorder ==
NULL )
3219 varsinlexorder =
NULL;
3223 assert( *maxnvarsorder >= 0 );
3224 assert( *nvarsorder >= 0 );
3228 for (k = 0; k < *nvarsorder; ++k)
3232 assert((*lexorder)[k] >= 0);
3240 if ( ncompcolors > 0 )
3244 for (j = 0; j < ncompcolors; ++j)
3251 if ( chosencomppercolor[j] < 0 )
3254 assert( firstvaridxpercolor[j] >= 0 );
3256 graphcomp = chosencomppercolor[j];
3257 graphcompsize = graphcompbegins[graphcomp+1] - graphcompbegins[graphcomp];
3258 varidx = firstvaridxpercolor[j];
3263 if ( varfound[
varidx] || graphcompsize == propdata->npermvars )
3267 if ( varsinlexorder !=
NULL
3269 && lexorder !=
NULL && *lexorder !=
NULL && *maxnvarsorder > 0 && *nvarsorder > 0
3270 && (*lexorder)[0] !=
varidx )
3274 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3276 assert( 0 <= graphcomponents[k] && graphcomponents[k] < propdata->npermvars );
3278 usedvars[graphcomponents[k]] =
TRUE;
3282 propdata->permstrans, propdata->components, propdata->componentbegins,
3283 usedvars, varfound,
varidx, symgrpcompidx,
3284 orbit[activeorb], &orbitsize[activeorb]) );
3288 if ( orbitsize[activeorb] > orbitsize[1 - activeorb] )
3291 activeorb = 1 - activeorb;
3296 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3297 usedvars[graphcomponents[k]] =
FALSE;
3301 if ( chosencolor > -1 )
3304 activeorb = 1 - activeorb;
3306 assert( orbit[activeorb][0] == firstvaridxpercolor[chosencolor] );
3307 vars[0] = propdata->permvars[orbit[activeorb][0]];
3309 assert( chosencolor > -1 );
3310 SCIPdebugMsg(
scip,
" adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3312 *naddedconss = orbitsize[activeorb] - 1;
3315 for (j = 1; j < orbitsize[activeorb]; ++j)
3320 vars[1] = propdata->permvars[orbit[activeorb][j]];
3330#ifdef SCIP_MORE_DEBUG
3337 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3338 propdata->genlinconss[propdata->ngenlinconss] = cons;
3339 ++propdata->ngenlinconss;
3343 if ( storelexorder )
3347 varidx = orbit[activeorb][0];
3350 if ( *maxnvarsorder == 0 )
3356 (*lexorder)[(*nvarsorder)++] =
varidx;
3360 assert( *nvarsorder == *maxnvarsorder );
3366 if (
varidx == (*lexorder)[0] )
3383 for (k = *maxnvarsorder - 1; k >= 1; --k)
3384 (*lexorder)[k] = (*lexorder)[k - 1];
3396 if ( varsinlexorder !=
NULL )
3410 int** modifiedperms,
3441 for (
i = 0;
i < npermvars; ++
i)
3446 for (
i = 0;
i < npermvars; ++
i)
3447 posinpermvar[
i] =
i;
3451 for (l = 0; l < nleaders; ++l)
3453 leader = leaders[l];
3454 curposleader = posinpermvar[leader];
3455 varidx = permvaridx[curposleader];
3456 lidx = permvaridx[l];
3459 permvaridx[curposleader] = lidx;
3463 posinpermvar[lidx] = curposleader;
3464 posinpermvar[leader] = l;
3468 for (
i = 0;
i < npermvars; ++
i)
3469 modifiedpermvars[
i] = origpermvars[permvaridx[
i]];
3472 for (p = 0; p < nperms; ++p)
3474 for (
i = 0;
i < npermvars; ++
i)
3475 modifiedperms[p][
i] = posinpermvar[origperms[p][permvaridx[
i]]];
3491 int* graphcomponents,
3492 int* graphcompbegins,
3493 int* compcolorbegins,
3505 assert( ncompcolors >= 0 );
3506 assert( symcompsize > 0 );
3508 for (j = 0; j < ncompcolors; ++j)
3511 int largestcompsize = 0;
3516 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3520 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3524 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3527 if ( largestcompsize < 1 )
3532 largestcompsize = compsize;
3534 else if ( compsize != largestcompsize )
3537 firstvar = permvars[graphcomponents[graphcompbegins[k]]];
3545 if ( k == compcolorbegins[j+1] )
3551 ncols = graphcompbegins[compcolorbegins[j] + 1] - graphcompbegins[compcolorbegins[j]];
3553 threshold = 0.7 * (
SCIP_Real) symcompsize;
3556 if ( nbinrows <= 2 * ncols || (nbinrows <= 8 * ncols && nbinrows < 100) )
3557 multorbitopecriterion =
TRUE;
3558 else if ( nbinrows <= 3 * ncols || (
SCIP_Real) nbinrows * ncols >= threshold )
3559 oneorbitopecriterion =
TRUE;
3563 if ( (norbitopes == 1 && oneorbitopecriterion) || (norbitopes >= 2 && multorbitopecriterion) )
3582 int nstrongsbcs = 0;
3585 int** modifiedperms;
3587 int* nvarsincomponent;
3589 int* graphcomponents;
3590 int* graphcompbegins;
3591 int* compcolorbegins;
3592 int* chosencomppercolor =
NULL;
3593 int* firstvaridxpercolor =
NULL;
3596 int ngraphcomponents;
3601 int ntrivialcolors = 0;
3603 int* lexorder =
NULL;
3604 int nvarslexorder = 0;
3605 int maxnvarslexorder = 0;
3609 int norbitopesincomp;
3613 assert( propdata->computedsymmetry );
3614 assert( propdata->nperms >= 0 );
3615 assert( 0 <= cidx && cidx < propdata->ncomponents );
3620 if ( propdata->nperms == 0 || propdata->componentblocked[cidx] )
3627 assert( propdata->nperms > 0 );
3629 assert( propdata->npermvars > 0 );
3637 for (p = 0; p < propdata->nperms; ++p)
3644 for (p = 0; p < propdata->npermvars; ++p)
3646 if ( propdata->vartocomponent[p] >= 0 )
3647 ++nvarsincomponent[propdata->vartocomponent[p]];
3650 SCIPdebugMsg(
scip,
"starting subgroup detection routine for component %d\n", cidx);
3652 npermsincomp = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
3655 for (j = 0; j < npermsincomp; ++j)
3660 assert( ntwocycleperms >= 0 );
3661 assert( ntwocycleperms <= npermsincomp );
3663 SCIPdebugMsg(
scip,
"component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
3665#ifdef SCIP_MORE_DEBUG
3672 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx+1]; ++p)
3674 perm = propdata->components[p];
3676 for (k = 0; k < propdata->npermvars; ++k)
3681 for (k = 0; k < propdata->npermvars; ++k)
3686 j = propdata->perms[perm][k];
3698 j = propdata->perms[perm][j];
3708 if ( ntwocycleperms < 2 )
3714 usedpermssize = ntwocycleperms / 2;
3719 &graphcomponents, &graphcompbegins, &compcolorbegins, &ngraphcomponents,
3720 &ncompcolors, &usedperms, &nusedperms, usedpermssize, permused) );
3722 SCIPdebugMsg(
scip,
" created subgroup detection graph using %d of the permutations\n", nusedperms);
3724 if ( nusedperms == npermsincomp )
3725 allpermsused =
TRUE;
3730 assert( ngraphcomponents > 0 );
3731 assert( ncompcolors > 0 );
3732 assert( nusedperms <= ntwocycleperms );
3733 assert( ncompcolors < propdata->npermvars );
3735 if ( nusedperms == 0 )
3737 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
3745 SCIPdebugMsg(
scip,
" number of different colors in the graph: %d\n", ncompcolors);
3747 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3756 for (j = 0; j < ncompcolors; ++j)
3758 chosencomppercolor[j] = -1;
3759 firstvaridxpercolor[j] = -1;
3763 norbitopesincomp =
getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3764 ncompcolors, nvarsincomponent[cidx]);
3767 if ( norbitopesincomp == 1 )
3771 for (k = 0; k < npermsincomp; ++k)
3779 propdata->perms[propdata->components[propdata->componentbegins[cidx] + k]],
3780 propdata->permvars, propdata->npermvars,
FALSE,
3786 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3787 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3788 ++propdata->nsymresacks;
3790 if ( ! propdata->componentblocked[cidx] )
3793 ++propdata->ncompblocked;
3796 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d\n", k, cidx);
3802 for (j = 0; j < ncompcolors; ++j)
3804 int nbinarycomps = 0;
3805 int largestcolorcomp = -1;
3806 int largestcompsize = 0;
3818 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3820 if( chosencomppercolor !=
NULL )
3821 chosencomppercolor[j] = -1;
3827 SCIPdebugMsg(
scip,
" color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
3828 graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]]);
3831 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3836 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3839 if ( largestcompsize < 1 )
3847 largestcompsize = compsize;
3848 largestcolorcomp = k;
3850 else if ( compsize != largestcompsize )
3857 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3865 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3869 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3876 contaffected =
TRUE;
3879 SCIPdebugMsg(
scip,
" affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
3883 useorbitope =
FALSE;
3884 if ( norbitopesincomp > 0 && nbinarycomps > 0 )
3887 if ( isorbitope && useorbitope )
3892 SCIPdebugMsg(
scip,
" detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
3894 assert( nbinarycomps > 0 );
3895 assert( largestcompsize > 2 );
3903 graphcompbegins, graphcomponents, j, nbinarycomps, largestcompsize, &firstvaridx, &chosencomp,
3904 &lexorder, &nvarslexorder, &maxnvarslexorder, allpermsused, &orbitopeadded) );
3906 if ( orbitopeadded )
3908 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3914 assert( compcolorbegins[j] <= chosencomp && chosencomp < compcolorbegins[j+1] );
3915 assert( 0 <= firstvaridx && firstvaridx < propdata->npermvars );
3917 chosencomppercolor[j] = chosencomp;
3918 firstvaridxpercolor[j] = firstvaridx;
3921 if ( ! propdata->componentblocked[cidx] )
3924 ++propdata->ncompblocked;
3934 if ( propdata->addstrongsbcs && ! orbitopeadded )
3936 assert( largestcolorcomp >= 0 );
3937 assert( largestcolorcomp < ngraphcomponents );
3938 assert( largestcompsize > 0 );
3940 if( propdata->addweaksbcs )
3945 chosencomppercolor[j] = largestcolorcomp;
3946 firstvaridxpercolor[j] = graphcomponents[graphcompbegins[largestcolorcomp]];
3949 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3950 largestcolorcomp, graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp]);
3954 propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3957 if ( !
SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
3958 handlednonbinarysymmetry =
TRUE;
3960 if ( ! propdata->componentblocked[cidx] )
3963 ++propdata->ncompblocked;
3967 nstrongsbcs += graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp] - 1;
3970 else if ( ! orbitopeadded )
3975 if ( propdata->addweaksbcs )
3978 chosencomppercolor[j] = -1;
3986 if ( propdata->addweaksbcs && propdata->componentblocked[cidx] && nusedperms < npermsincomp )
3994 graphcomponents, ncompcolors, chosencomppercolor, firstvaridxpercolor,
3995 cidx, &naddedconss, propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3997 assert( naddedconss < propdata->npermvars );
4000 nweaksbcs += naddedconss;
4004 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4009 if ( nvarslexorder > 0 && propdata->addsymresacks && ! handlednonbinarysymmetry )
4014 propdata->permvars, modifiedpermvars, propdata->npermvars, lexorder, nvarslexorder) );
4016 for (k = 0; k < npermsincomp; ++k)
4028 symresackperm = modifiedperms[propdata->components[propdata->componentbegins[cidx] + k]];
4029 for (j = 0; j < propdata->nperms && !actsonbinary; ++j)
4032 actsonbinary =
TRUE;
4035 if ( ! actsonbinary )
4041 symresackperm, modifiedpermvars, propdata->npermvars,
FALSE,
4047 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4048 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4049 ++propdata->nsymresacks;
4051 if ( ! propdata->componentblocked[cidx] )
4054 ++propdata->ncompblocked;
4057 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, cidx);
4073 SCIPdebugMsg(
scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4074 SCIPdebugMsg(
scip,
"total number of added strong sbcs: %d\n", nstrongsbcs);
4082 for (p = propdata->nperms - 1; p >= 0; --p)
4119 assert( nconflictvars > 0 );
4125 for (
i = 0;
i < nconflictvars; ++
i)
4128 varconflicts[
i].orbitidx = -1;
4129 varconflicts[
i].nconflictinorbit = 0;
4130 varconflicts[
i].orbitsize = -1;
4131 varconflicts[
i].posinorbit = -1;
4135 for (
r = 0;
r < norbits; ++
r)
4140 orbitsize = orbitbegins[
r + 1] - orbitbegins[
r];
4141 assert( orbitsize >= 0 );
4143 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4149 assert( pos < nconflictvars );
4150 assert( varconflicts[pos].
var == conflictvars[pos] );
4152 varconflicts[pos].orbitidx =
r;
4153 varconflicts[pos].nconflictinorbit = 0;
4154 varconflicts[pos].orbitsize = orbitsize;
4155 varconflicts[pos].posinorbit = posinorbit++;
4165 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4168 assert( varconflicts[ii].orbitidx ==
r );
4171 if ( ! varconflicts[ii].
active )
4174 for (j =
i + 1; j < orbitbegins[
r + 1]; ++j)
4177 assert( varconflicts[jj].orbitidx ==
r );
4180 if ( ! varconflicts[jj].
active )
4190 varconflicts[ii].ncliques, (
void**)varconflicts[jj].cliques, varconflicts[jj].ncliques,
4191 sortByPointerValue) )
4194 ++varconflicts[ii].nconflictinorbit;
4195 ++varconflicts[jj].nconflictinorbit;
4232 int varncliques = 0;
4238 assert( nconflictvars > 0 );
4241 *varconflicts =
NULL;
4247 if ( ncliques == 0 )
4249 SCIPdebugMsg(
scip,
"No cliques present --> construction of conflict structure aborted.\n");
4256 for (
i = 0;
i < nconflictvars; ++
i)
4258 (*varconflicts)[
i].ncliques = 0;
4259 (*varconflicts)[
i].active =
TRUE;
4260 (*varconflicts)[
i].var = conflictvars[
i];
4262 (*varconflicts)[
i].cliques =
NULL;
4263 (*varconflicts)[
i].orbitidx = -1;
4264 (*varconflicts)[
i].nconflictinorbit = 0;
4265 (*varconflicts)[
i].orbitsize = -1;
4266 (*varconflicts)[
i].posinorbit = -1;
4276 for (
c = 0;
c < ncliques; ++
c)
4278 clique = cliques[
c];
4284 assert( ncliquevars > 0 );
4290 for (
i = 0;
i < ncliquevars; ++
i)
4295 if ( node == INT_MAX )
4298 assert( node < nconflictvars );
4300 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4301 (*varconflicts)[node].active =
TRUE;
4302 (*varconflicts)[node].ncliques++;
4307 for (
i = 0;
i < nconflictvars; ++
i)
4309 assert( (*varconflicts)[
i].ncliques >= 0 );
4311 if ( (*varconflicts)[
i].ncliques > 0 )
4319 for (
c = 0;
c < ncliques; ++
c)
4321 clique = cliques[
c];
4327 assert( ncliquevars > 0 );
4333 for (
i = 0;
i < ncliquevars; ++
i)
4338 if ( node == INT_MAX )
4342 assert( node < nconflictvars );
4343 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4346 assert( tmpncliques[node] < (*varconflicts)[node].ncliques );
4347 assert( (*varconflicts)[node].cliques !=
NULL );
4348 (*varconflicts)[node].cliques[tmpncliques[node]++] = clique;
4357 for (
i = 0;
i < nconflictvars; ++
i)
4359 SCIPsortPtr((
void**)(*varconflicts)[
i].cliques, sortByPointerValue, (*varconflicts)[
i].ncliques);
4363 for (
i = 0;
i < nconflictvars; ++
i)
4365 assert( tmpncliques[
i] == (*varconflicts)[
i].ncliques );
4372 SCIPdebugMsg(
scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4397 n = (*varconflicts)[
i].ncliques;
4415 int* componentbegins;
4418 int** modifiedperms =
NULL;
4421 int nsymresackcons = 0;
4429 assert( propdata->npermvars >= 0 );
4430 assert( propdata->nbinpermvars >= 0 );
4433 if ( propdata->nbinpermvars == 0 )
4435 assert( propdata->binvaraffected == 0 );
4439 perms = propdata->perms;
4440 nperms = propdata->nperms;
4441 permvars = propdata->permvars;
4442 npermvars = propdata->npermvars;
4443 conssaddlp = propdata->conssaddlp;
4445 componentbegins = propdata->componentbegins;
4452 assert( 0 <= cidx && cidx < propdata->ncomponents );
4467 if ( propdata->componenthassignedperm[cidx] )
4471 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4474 for (p = 0; p < nperms; ++p)
4480 for (
i = 0;
i < npermvars; ++
i)
4481 modifiedpermvars[
i] = permvars[
i];
4484 propdata->leaders, propdata->nleaders) );
4488 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
4499 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4518 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4519 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4520 ++propdata->nsymresacks;
4524 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4530 for (p = nperms - 1; p >= 0; --p)
4555 int norbitvarinconflict,
4579 assert( orbitleaderidx >= 0 );
4581 assert( norbitvarinconflict >= 0 );
4584 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4587 if ( propdata->sstaddcuts )
4591 addcuts = propdata->addconflictcuts;
4594 ncuts = orbitsize - norbitvarinconflict - 1;
4599 if ( propdata->nsstconss == 0 )
4602 assert( propdata->maxnsstconss == 0 );
4603 propdata->maxnsstconss = 2 * ncuts;
4606 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
4612 propdata->maxnsstconss, newsize) );
4613 propdata->maxnsstconss = newsize;
4617 if ( propdata->nleaders == 0 )
4619 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
4622 assert( propdata->nleaders < propdata->maxnleaders );
4625 posleader = orbitbegins[orbitidx] + orbitleaderidx;
4626 vars[0] = permvars[orbits[posleader]];
4629 propdata->leaders[propdata->nleaders++] = orbits[posleader];
4631 for (
i = 0, poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++poscur)
4633 if (
i == orbitleaderidx )
4635 assert( orbitvarinconflict ==
NULL || ! orbitvarinconflict[
i] );
4639 vars[1] = permvars[orbits[poscur]];
4641 for (j = 0; j < propdata->nleaders - 1; ++j)
4643 assert( propdata->leaders[j] != orbits[poscur] );
4648 if ( varconflicts !=
NULL )
4650 if ( orbitvarinconflict[
i] )
4664 varconflicts[orbits[poscur]].active =
FALSE;
4668 orbitvarinconflict[
i] =
FALSE;
4677 propdata->sstconss[propdata->nsstconss++] = cons;
4687 propdata->sstconss[propdata->nsstconss++] = cons;
4711 int* norbitvarinconflict,
4717 int curcriterion = INT_MIN;
4724 assert( nconflictvars > 0 );
4736 *norbitvarinconflict = 0;
4747 orbitcriterion = INT_MIN;
4750 for (
i = 0;
i < norbits; ++
i)
4754 if (
SCIPvarGetType(conflictvars[orbits[orbitbegins[
i]]]) != leadervartype )
4758 curcriterion = orbitbegins[
i] - orbitbegins[
i + 1];
4760 curcriterion = orbitbegins[
i + 1] - orbitbegins[
i];
4770 cnt = orbitbegins[
i];
4782 cnt = orbitbegins[
i + 1] - 1;
4797 curcriterion = varconflicts[
varidx].nconflictinorbit;
4801 if ( curcriterion > orbitcriterion )
4803 orbitcriterion = curcriterion;
4810 *leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
4815 if ( *success && varconflicts !=
NULL )
4817 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4818 assert( leader < nconflictvars );
4821 && varconflicts[leader].ncliques > 0 )
4828 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4830 assert( leader >= 0 && leader < nconflictvars );
4834 for (
i = 0;
i < orbitsize; ++
i)
4837 if (
i == *leaderidx )
4841 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4844 if ( ! varconflicts[varmapid].
active )
4849 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4850 varconflicts[varmapid].ncliques, sortByPointerValue) )
4853 orbitvarinconflict[
i] =
TRUE;
4854 ++(*norbitvarinconflict);
4871 for (
i = 0;
i < nconflictvars; ++
i)
4879 if ( varconflicts[
i].orbitidx == -1 )
4882 curcriterion = varconflicts[
i].nconflictinorbit;
4884 if ( curcriterion > orbitcriterion )
4886 orbitcriterion = curcriterion;
4887 *orbitidx = varconflicts[
i].orbitidx;
4888 *leaderidx = varconflicts[
i].posinorbit;
4894 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4895 assert( leader < nconflictvars );
4898 if ( *success && varconflicts[leader].ncliques > 0 )
4903 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4905 assert( leader >= 0 && leader < nconflictvars );
4909 for (
i = 0;
i < orbitsize; ++
i)
4912 if (
i == *leaderidx )
4916 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4918 if ( ! varconflicts[varmapid].
active )
4923 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4924 varconflicts[varmapid].ncliques, sortByPointerValue) )
4927 orbitvarinconflict[
i] =
TRUE;
4928 ++(*norbitvarinconflict);
4954 int nmovedbinpermvars;
4955 int nmovedintpermvars;
4956 int nmovedimplintpermvars;
4957 int nmovedcontpermvars;
4964 int* componentbegins;
4965 int* vartocomponent;
4967 unsigned* componentblocked;
4972 int norbitvarinconflict;
4980 int nvarsselectedtype;
4983 int norbitleadercomponent;
4994 assert( propdata->computedsymmetry );
4996 permvars = propdata->permvars;
4997 npermvars = propdata->npermvars;
4998 nperms = propdata->nperms;
5004 permvarmap = propdata->permvarmap;
5008 permstrans = propdata->permstrans;
5012 componentbegins = propdata->componentbegins;
5013 componentblocked = propdata->componentblocked;
5014 vartocomponent = propdata->vartocomponent;
5015 ncomponents = propdata->ncomponents;
5021 assert( ncomponents > 0 );
5022 assert( 0 <= cidx && cidx < ncomponents );
5025 if ( componentblocked[cidx] )
5029 if ( propdata->componenthassignedperm[cidx] )
5032 leaderrule = propdata->sstleaderrule;
5033 tiebreakrule = propdata->ssttiebreakrule;
5034 leadervartype = propdata->sstleadervartype;
5035 mixedcomponents = propdata->sstmixedcomponents;
5039 nmovedpermvars = propdata->nmovedpermvars;
5040 nmovedbinpermvars = propdata->nmovedbinpermvars;
5041 nmovedintpermvars = propdata->nmovedintpermvars;
5042 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5043 nmovedcontpermvars = propdata->nmovedcontpermvars;
5044 assert( nmovedpermvars > 0 );
5047 nvarsselectedtype = 0;
5048 if (
ISSSTBINACTIVE(leadervartype) && nmovedbinpermvars > nvarsselectedtype )
5051 nvarsselectedtype = nmovedbinpermvars;
5054 if (
ISSSTINTACTIVE(leadervartype) && nmovedintpermvars > nvarsselectedtype )
5057 nvarsselectedtype = nmovedintpermvars;
5060 if (
ISSSTIMPLINTACTIVE(leadervartype) && nmovedimplintpermvars > nvarsselectedtype )
5063 nvarsselectedtype = nmovedimplintpermvars;
5066 if (
ISSSTCONTACTIVE(leadervartype) && nmovedcontpermvars > nvarsselectedtype )
5069 nvarsselectedtype = nmovedcontpermvars;
5073 if ( nvarsselectedtype == 0 )
5077 if ( onlywithcontvars )
5079 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
5081 perm = propdata->perms[p];
5082 for (
i = 0;
i < propdata->npermvars; ++
i)
5104 conflictgraphcreated = varconflicts !=
NULL;
5112 if ( conflictgraphcreated )
5117 SCIPdebugMsg(
scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5120 if ( nchgbds !=
NULL )
5124 for (
c = 0;
c < ncomponents; ++
c)
5126 for (p = componentbegins[
c]; p < componentbegins[
c + 1]; ++p)
5134 ninactiveperms = nperms - componentbegins[cidx + 1] + componentbegins[cidx];
5137 norbitleadercomponent = 0;
5138 while ( ninactiveperms < nperms )
5144 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5145 componentblocked, ncomponents, nmovedpermvars) );
5148 if ( ! mixedcomponents )
5150 for (p = 0; p < norbits; ++p)
5153 if (
SCIPvarGetType(permvars[orbits[orbitbegins[p]]]) != selectedtype )
5165 if ( conflictgraphcreated )
5183 norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype, &orbitidx, &orbitleaderidx,
5184 orbitvarinconflict, &norbitvarinconflict, &success) );
5189 assert( 0 <= orbitidx && orbitidx < norbits );
5190 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5191 SCIPdebugMsg(
scip,
"%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5195 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5197 ++norbitleadercomponent;
5199 if ( nchgbds !=
NULL )
5200 *nchgbds += nchanges;
5203 posleader = orbits[orbitbegins[orbitidx] + orbitleaderidx];
5204 for (p = 0; p < nperms; ++p)
5206 if ( inactiveperms[p] )
5209 if ( permstrans[posleader][p] != posleader )
5211 inactiveperms[p] =
TRUE;
5218 if ( norbitleadercomponent > 0 )
5221 if ( conflictgraphcreated )
5227 if ( varconflicts !=
NULL )
5262 assert( propdata->usedynamicprop );
5280 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5281 for (
i = 0;
i < ncols - 1; ++
i)
5285 consvars[0] = propdata->permvars[varidxmatrix[0][
i]];
5286 consvars[1] = propdata->permvars[varidxmatrix[0][
i + 1]];
5292 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5300 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5305 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5308 propdata->permvars, propdata->npermvars, orbisackperm, (
SYM_SYMTYPE) propdata->symtype,
5309 propdata->permvardomaincenter,
TRUE, success) );
5316 for (
i = 0;
i < nrows; ++
i)
5319 for (j = 0; j < ncols; ++j)
5320 varmatrix[
i][j] = propdata->permvars[varidxmatrix[
i][j]];
5327 ispporbitope = npprows >= 3;
5341 for (
i = 0;
i < nrows; ++
i)
5346 ppvarsarrayonlypprows[
r++] = varmatrix[
i];
5360 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5364 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5378 nelem = nrows * ncols;
5380 for (
i = 0;
i < nrows; ++
i)
5382 for (j = 0; j < ncols; ++j)
5383 orbitopevarmatrix[pos++] = varmatrix[
i][j];
5392 orbitopevarmatrix, nrows, ncols, success) );
5400 for (
i = nrows - 1;
i >= 0; --
i)
5415 int** componentperms,
5434 int** pporbisackperms;
5435 int npporbisackperms;
5439 int* npermvarssetppcconss;
5440 int* maxnpermvarssetppcconss;
5447 assert( componentsize > 0 );
5454 if ( hassignedperm )
5458 if ( setppcconshdlr ==
NULL )
5462 if ( nsetppcconss == 0 )
5473 for (
c = 0;
c < nsetppcconss; ++
c)
5475 cons = setppcconss[
c];
5481 setppconsssort[nsetppconss++] = cons;
5483 SCIPsortPtr((
void**) setppconsssort, sortByPointerValue, nsetppconss);
5491 for (
c = 0;
c < nsetppconss; ++
c)
5495 cons = setppconsssort[
c];
5501 for (
i = 0;
i < nsetppcvars; ++
i)
5503 var = setppcvars[
i];
5506 assert( varid == INT_MAX || varid < propdata->npermvars );
5508 if ( varid < propdata->npermvars )
5511 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5512 assert( npermvarssetppcconss[varid] < maxnpermvarssetppcconss[varid] );
5513 permvarssetppcconss[varid][npermvarssetppcconss[varid]++] = cons;
5521 npporbisackperms = 0;
5522 for (p = 0; p < componentsize; ++p)
5524 perm = componentperms[p];
5528 for (
i = 0;
i < propdata->npermvars; ++
i)
5547 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) )
5556 if ( ntwocycles > 0 )
5558 pporbisackperms[npporbisackperms++] = perm;
5559 if ( ntwocycles > maxntwocycles )
5560 maxntwocycles = ntwocycles;
5568 if ( npporbisackperms * 2 >= componentsize )
5576 assert( npporbisackperms > 0 );
5577 assert( maxntwocycles > 0 );
5582 for (
i = 0;
i < maxntwocycles; ++
i)
5583 ppvarsmatrix[
i] = &(ppvarsblock[2 *
i]);
5586 for (p = 0; p < npporbisackperms; ++p)
5588 perm = pporbisackperms[p];
5592 for (
i = 0;
i < propdata->npermvars; ++
i)
5605 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) );
5607 assert( nrows < maxntwocycles );
5608 row = ppvarsmatrix[nrows++];
5609 row[0] = propdata->permvars[
i];
5610 row[1] = propdata->permvars[j];
5611 assert( row[0] != row[1] );
5622 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5626 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5640 for (varid = 0; varid < propdata->npermvars; ++varid)
5642 assert( (permvarssetppcconss[varid] ==
NULL) == (maxnpermvarssetppcconss[varid] == 0) );
5643 assert( npermvarssetppcconss[varid] >= 0 );
5644 assert( maxnpermvarssetppcconss[varid] >= 0 );
5645 assert( npermvarssetppcconss[varid] <= maxnpermvarssetppcconss[varid] );
5646 if ( npermvarssetppcconss[varid] == 0 )
5649 permvarssetppcconss[varid] =
NULL;
5650 npermvarssetppcconss[varid] = 0;
5651 maxnpermvarssetppcconss[varid] = 0;
5671 int** componentperms;
5684 && propdata->usedynamicprop
5685 && propdata->addsymresacks
5687 assert( propdata->nperms > 0 );
5688 assert( 0 <= cidx && cidx < propdata->ncomponents );
5689 assert( propdata->componentblocked !=
NULL );
5692 if ( propdata->componentblocked[cidx] )
5697 checklexred =
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5698 assert( checkorbired || checklexred );
5701 assert( propdata->nmovedpermvars );
5704 componentsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
5706 for (p = 0; p < componentsize; ++p)
5707 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
5716 checkpporbisack =
SCIPgetParam(
scip,
"constraints/orbisack/checkpporbisack");
5720 componentperms, componentsize, propdata->componenthassignedperm[cidx], &success) );
5725 goto FINISHCOMPONENT;
5730 if ( checkorbired && !propdata->componenthassignedperm[cidx] )
5733 propdata->permvars, propdata->npermvars, componentperms, componentsize, &success) );
5742 for (p = 0; p < componentsize; ++p)
5746 propdata->permvars, propdata->npermvars, componentperms[p],
5747 (
SYM_SYMTYPE) propdata->symtype, propdata->permvardomaincenter,
TRUE, &success) );
5755 if ( propdata->componentblocked[cidx] )
5756 ++propdata->ncompblocked;
5771 int ncomponentshandled;
5778 if ( propdata->orbitopalreddata )
5782 if ( propdata->orbitalreddata )
5786 if ( propdata->lexreddata )
5790 if ( propdata->ncomponents >= 0 )
5797 ncomponentshandled = 0;
5798 for (
i = 0;
i < propdata->ncomponents; ++
i)
5800 if ( propdata->componentblocked[
i] )
5801 ++ncomponentshandled;
5803 assert( propdata->ncompblocked <= ncomponentshandled );
5804 assert( ncomponentshandled <= propdata->ncomponents );
5806 ncomponentshandled, propdata->ncomponents);
5834 if ( propdata->usedynamicprop )
5839 else if ( propdata->binvaraffected )
5851 for (
i = 0;
i < nrows; ++
i)
5858 for (j = 0; j < ncols; ++j)
5861 orbitopematrix[nbinrows][j] = propdata->permvars[varidxmatrix[
i][j]];
5876 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5877 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5878 ++propdata->norbitopes;
5883 for (
i = nbinrows - 1;
i >= 0; --
i)
5929 assert( nrowblocks > 0 );
5930 assert( ncolblocks > 0 );
5935 &propdata->genorbconsssize, propdata->ngenorbconss + nrowblocks + ncolblocks) );
5937 maxdim =
MAX(nrows, ncols);
5939 for (
i = 0;
i < maxdim; ++
i)
5945 for (p = 0; p < ncolblocks; ++p)
5948 for (
i = 0;
i < nrows; ++
i)
5951 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[
i][colsbegin[p]]]) )
5954 for (col = 0, j = colsbegin[p]; j < colsbegin[p + 1]; ++j, ++col)
5957 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[
i][j]];
5969 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5975 for (p = 0; p < nrowblocks; ++p)
5978 for (
i = 0;
i < ncols; ++
i)
5981 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[rowsbegin[p]][
i]]) )
5984 for (col = 0, j = rowsbegin[p]; j < rowsbegin[p + 1]; ++j, ++col)
5987 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[j][
i]];
5999 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
6004 for (
i = maxdim - 1;
i >= 0; --
i)
6022 int** lexmatrix =
NULL;
6023 int* lexrowsbegin =
NULL;
6024 int* lexcolsbegin =
NULL;
6038 assert( 0 <= cidx && cidx < propdata->ncomponents );
6041 if ( propdata->componentblocked[cidx] )
6045 if ( propdata->componenthassignedperm[cidx] )
6053 compsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
6055 for (p = 0,
i = propdata->componentbegins[cidx];
i < propdata->componentbegins[cidx + 1]; ++
i)
6056 perms[p++] = propdata->perms[propdata->components[
i]];
6059 &success, &isorbitope, &lexmatrix, &nrows, &ncols,
6060 &lexrowsbegin, &lexcolsbegin, &nrowmatrices, &ncolmatrices) );
6080 for (
i = 0;
i < nrows && !hasbinaryvar; ++
i)
6082 for (p = 0; p < ncols; ++p)
6086 hasbinaryvar =
TRUE;
6095 lexrowsbegin, lexcolsbegin, nrowmatrices, ncolmatrices, &success) );
6102 for (
i = nrows - 1;
i >= 0; --
i)
6107 if ( ncolmatrices > 0 )
6111 if ( nrowmatrices > 0 )
6120 ++(propdata->ncompblocked);
6136 assert( 0 <= cidx && cidx < propdata->ncomponents );
6139 if ( propdata->componentblocked[cidx] )
6143 if ( propdata->componenthassignedperm[cidx] )
6147 if ( !propdata->usedynamicprop &&
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
6148 && propdata->binvaraffected && propdata->ncompblocked < propdata->ncomponents )
6192 assert( propdata->ncomponents >= 0 );
6193 assert( 0 <= cidx && cidx < propdata->ncomponents );
6196 if ( propdata->componentblocked[cidx] )
6201 || (
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
6204 if ( propdata->detectdoublelex || propdata->detectorbitopes )
6208 detectsinglelex = propdata->detectdoublelex ?
FALSE :
TRUE;
6217 if ( useorbitalredorlexred )
6242 if ( nchgbds !=
NULL )
6244 if ( earlyterm !=
NULL )
6250 if ( earlyterm !=
NULL )
6257 assert( propdata->usesymmetry >= 0 );
6260 if ( propdata->usesymmetry == 0 )
6262 if ( earlyterm !=
NULL )
6268 if ( propdata->triedaddsymmethods )
6270 assert( propdata->nperms >= 0 );
6272 if ( earlyterm !=
NULL )
6277 assert( !propdata->triedaddsymmethods );
6280 if ( !propdata->computedsymmetry )
6288 if ( !propdata->computedsymmetry )
6292 propdata->triedaddsymmethods =
TRUE;
6293 assert( propdata->nperms >= 0 );
6296 if ( propdata->nperms == 0 )
6301 assert( propdata->ncomponents > 0 );
6304 for (
c = 0;
c < propdata->ncomponents; ++
c)
6312#ifdef SYMMETRY_STATISTICS
6339 *infeasible =
FALSE;
6384 if ( propdata->usesymmetry < 0 )
6388 assert( propdata->usesymmetry >= 0 );
6391 if ( propdata->usesymmetry == 0 )
6420 assert( propdata->usesymmetry >= 0 );
6423 if ( propdata->usesymmetry == 0 )
6478 assert( propdata->usesymmetry >= 0 );
6481 if ( propdata->usesymmetry == 0 )
6495 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
6507 *nchgbds += nchanges;
6511 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
6514 assert( propdata->nperms > 0 );
6515 assert( propdata->triedaddsymmethods );
6520 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
6521 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
6524 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
6527 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6528 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6538 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
6541 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6542 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6552 propdata->ngenorbconss + propdata->ngenlinconss);
6554 for (
i = 0;
i < propdata->nsstconss; ++
i)
6557 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6558 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6567 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
6598 if ( propdata->usesymmetry < 0 )
6606 propdata->symfoundreduction =
TRUE;
6613 propdata->symfoundreduction =
TRUE;
6640 propdata->usesymmetry = -1;
6641 propdata->triedaddsymmethods =
FALSE;
6642 propdata->nsymresacks = 0;
6643 propdata->norbitopes = 0;
6644 propdata->lastrestart = 0;
6645 propdata->symfoundreduction =
FALSE;
6684 assert( propdata->customsymopnodetypes !=
NULL );
6694 assert( propdata->orbitopalreddata !=
NULL );
6722 propdata->npermvars = 0;
6723 propdata->nbinpermvars = 0;
6724 propdata->permvars =
NULL;
6725 propdata->nperms = -1;
6726 propdata->nmaxperms = 0;
6727 propdata->perms =
NULL;
6728 propdata->permstrans =
NULL;
6729 propdata->permvarmap =
NULL;
6730 propdata->permvardomaincenter =
NULL;
6732 propdata->ncomponents = -1;
6733 propdata->ncompblocked = 0;
6734 propdata->components =
NULL;
6735 propdata->componentbegins =
NULL;
6736 propdata->vartocomponent =
NULL;
6737 propdata->componentblocked =
NULL;
6738 propdata->componenthassignedperm =
NULL;
6740 propdata->log10groupsize = -1.0;
6741 propdata->nmovedvars = -1;
6742 propdata->binvaraffected =
FALSE;
6743 propdata->computedsymmetry =
FALSE;
6744 propdata->conshdlr_nonlinear =
NULL;
6746 propdata->usesymmetry = -1;
6747 propdata->triedaddsymmethods =
FALSE;
6748 propdata->genorbconss =
NULL;
6749 propdata->genlinconss =
NULL;
6750 propdata->ngenorbconss = 0;
6751 propdata->ngenlinconss = 0;
6752 propdata->genorbconsssize = 0;
6753 propdata->genlinconsssize = 0;
6754 propdata->nsymresacks = 0;
6755 propdata->norbitopes = 0;
6756 propdata->isnonlinvar =
NULL;
6758 propdata->nmovedpermvars = -1;
6759 propdata->nmovedbinpermvars = 0;
6760 propdata->nmovedintpermvars = 0;
6761 propdata->nmovedimplintpermvars = 0;
6762 propdata->nmovedcontpermvars = 0;
6763 propdata->lastrestart = 0;
6764 propdata->symfoundreduction =
FALSE;
6766 propdata->sstconss =
NULL;
6767 propdata->nsstconss = 0;
6768 propdata->maxnsstconss = 0;
6769 propdata->leaders =
NULL;
6770 propdata->nleaders = 0;
6771 propdata->maxnleaders = 0;
6791 tabledata->propdata = propdata;
6798 if( rootdialog !=
NULL )
6808 "symmetry",
"display generators of symmetry group in cycle notation, if available",
6816 "propagating/" PROP_NAME "/maxgenerators",
6817 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
6821 "propagating/" PROP_NAME "/checksymmetries",
6822 "Should all symmetries be checked after computation?",
6826 "propagating/" PROP_NAME "/displaynorbitvars",
6827 "Should the number of variables affected by some symmetry be displayed?",
6831 "propagating/" PROP_NAME "/doubleequations",
6832 "Double equations to positive/negative version?",
6838 "Should the symmetry breaking constraints be added to the LP?",
6842 "propagating/" PROP_NAME "/addsymresacks",
6843 "Add inequalities for symresacks for each generator?",
6847 "propagating/" PROP_NAME "/detectdoublelex",
6848 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
6852 "propagating/" PROP_NAME "/detectorbitopes",
6853 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
6857 "propagating/" PROP_NAME "/detectsubgroups",
6858 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
6862 "propagating/" PROP_NAME "/addweaksbcs",
6863 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
6867 "propagating/" PROP_NAME "/addconsstiming",
6868 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) [disabled parameter]",
6873 "propagating/" PROP_NAME "/ofsymcomptiming",
6874 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) [disabled parameter]",
6878 "propagating/" PROP_NAME "/performpresolving",
6879 "run orbital fixing during presolving? (disabled)",
6883 "propagating/" PROP_NAME "/recomputerestart",
6884 "recompute symmetries after a restart has occurred? (0 = never)",
6888 "propagating/" PROP_NAME "/compresssymmetries",
6889 "Should non-affected variables be removed from permutation to save memory?",
6893 "propagating/" PROP_NAME "/compressthreshold",
6894 "Compression is used if percentage of moved vars is at most the threshold.",
6898 "propagating/" PROP_NAME "/usecolumnsparsity",
6899 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
6903 "propagating/" PROP_NAME "/maxnconsssubgroup",
6904 "maximum number of constraints up to which subgroup structures are detected",
6908 "propagating/" PROP_NAME "/usedynamicprop",
6909 "whether dynamified symmetry handling constraint methods should be used",
6913 "propagating/" PROP_NAME "/addstrongsbcs",
6914 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
6918 "propagating/" PROP_NAME "/ssttiebreakrule",
6919 "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)",
6923 "propagating/" PROP_NAME "/sstleaderrule",
6924 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
6928 "propagating/" PROP_NAME "/sstleadervartype",
6929 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
6930 "if multiple types are allowed, take the one with most affected vars",
6934 "propagating/" PROP_NAME "/addconflictcuts",
6935 "Should Schreier Sims constraints be added if we use a conflict based rule?",
6940 "Should Schreier Sims constraints be added?",
6944 "propagating/" PROP_NAME "/sstmixedcomponents",
6945 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
6949 "propagating/" PROP_NAME "/symfixnonbinaryvars",
6950 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
6954 "propagating/" PROP_NAME "/enforcecomputesymmetry",
6955 "Is only symmetry on binary variables used?",
6959 "propagating/" PROP_NAME "/preferlessrows",
6960 "Shall orbitopes with less rows be preferred in detection?",
6965 "Type of symmetries that shall be computed?",
6970 "timing of symmetry computation and handling (0 = before presolving, 1 = during presolving, 2 = after presolving)",
6977 "propagating/" PROP_NAME "/nautymaxncells",
6978 "terminate symmetry detection using Nauty when number of cells in color refinment is at least this number",
6982 "propagating/" PROP_NAME "/nautymaxnnodes",
6983 "terminate symmetry detection using Nauty when its search tree has at least this number of nodes",
6999 assert( propdata->shadowtreeeventhdlr !=
NULL );
7002 assert( propdata->orbitopalreddata !=
NULL );
7026 int** componentbegins,
7027 int** vartocomponent,
7054 *npermvars = propdata->npermvars;
7055 *permvars = propdata->permvars;
7057 if ( permvarmap !=
NULL )
7059 if ( propdata->nperms > 0 )
7063 *permvarmap = propdata->permvarmap;
7066 *nperms = propdata->nperms;
7067 if ( perms !=
NULL )
7069 *perms = propdata->perms;
7073 if ( permstrans !=
NULL )
7075 if ( propdata->nperms > 0 )
7079 *permstrans = propdata->permstrans;
7080 assert( *permstrans !=
NULL || *nperms <= 0 );
7083 if ( log10groupsize !=
NULL )
7084 *log10groupsize = propdata->log10groupsize;
7086 if ( binvaraffected !=
NULL )
7087 *binvaraffected = propdata->binvaraffected;
7091 if ( propdata->nperms > 0 )
7100 if ( componentbegins !=
NULL )
7101 *componentbegins = propdata->componentbegins;
7103 if ( vartocomponent )
7104 *vartocomponent = propdata->vartocomponent;
7107 *ncomponents = propdata->ncomponents;
7130 if ( propdata->nperms < 0 )
7133 return propdata->nperms;
7142 const char* opnodename,
7155 SCIPerrorMessage(
"Cannot create operator node type, symmetry propagator has not been included.\n");
7161 assert( propdata->customsymopnodetypes !=
NULL );
7165 SCIPerrorMessage(
"Cannot create operator node type %s, it already exists.\n", opnodename);
7170 *nodetype = propdata->nopnodetypes++;
7181 const char* opnodename,
7193 SCIPerrorMessage(
"Cannot return operator node type, symmetry propagator has not been included.\n");
7199 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, .
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
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_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool mayinteract, SCIP_Bool resolveprop, 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)
@ 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)
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 SCIPreleaseDialog(SCIP *scip, SCIP_DIALOG **dialog)
SCIP_DIALOG * SCIPdialoghdlrGetRoot(SCIP_DIALOGHDLR *dialoghdlr)
SCIP_Bool SCIPdialogHasEntry(SCIP_DIALOG *dialog, const char *entryname)
SCIP_RETCODE SCIPdialoghdlrAddHistory(SCIP_DIALOGHDLR *dialoghdlr, SCIP_DIALOG *dialog, const char *command, SCIP_Bool escapecommand)
SCIP_RETCODE SCIPincludeDialog(SCIP *scip, SCIP_DIALOG **dialog, SCIP_DECL_DIALOGCOPY((*dialogcopy)), SCIP_DECL_DIALOGEXEC((*dialogexec)), SCIP_DECL_DIALOGDESC((*dialogdesc)), SCIP_DECL_DIALOGFREE((*dialogfree)), const char *name, const char *desc, SCIP_Bool issubmenu, SCIP_DIALOGDATA *dialogdata)
SCIP_RETCODE SCIPaddDialogEntry(SCIP *scip, SCIP_DIALOG *dialog, SCIP_DIALOG *subdialog)
SCIP_DIALOGDATA * SCIPdialogGetData(SCIP_DIALOG *dialog)
SCIP_DIALOG * SCIPgetRootDialog(SCIP *scip)
int SCIPdialogFindEntry(SCIP_DIALOG *dialog, const char *entryname, SCIP_DIALOG **subdialog)
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)
#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_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_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_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
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
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_Bool SCIPparamGetBool(SCIP_PARAM *param)
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define PROP_PRESOL_PRIORITY
#define DEFAULT_CONSSADDLP
static SCIP_Bool conshdlrCanProvideSymInformation(SCIP_CONSHDLR *conshdlr, SYM_SYMTYPE symtype)
#define DEFAULT_MAXGENERATORS
static SCIP_RETCODE tryAddSymmetryHandlingMethodsComponent(SCIP *scip, SCIP_PROPDATA *propdata, int cidx, int *nchgbds)
#define DEFAULT_DETECTSUBGROUPS
#define DEFAULT_SSTLEADERRULE
#define DEFAULT_PREFERLESSROWS
#define ISSSTINTACTIVE(x)
static SCIP_RETCODE tryAddSymmetryHandlingMethods(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
#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)
#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_RETCODE tryHandleSingleOrDoubleLexMatricesComponent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool detectsinglelex, int cidx)
#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 setSymmetryData(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
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)
#define DEFAULT_ADDCONFLICTCUTS
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_Bool testSymmetryComputationRequired(SCIP *scip, SCIP_PROPDATA *propdata)
#define ISSSTIMPLINTACTIVE(x)
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)
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 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, int ***perms, int *nperms, int *nmaxperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *log10groupsize, SCIP_Real *symcodetime, SCIP_Bool *success)
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, SCIP_Bool *success)
#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
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 mayinteract, SCIP_Bool *success)
static SCIP_RETCODE addOrbitopesDynamic(SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
#define DEFAULT_USEDYNAMICPROP
#define DEFAULT_RECOMPUTERESTART
static SCIP_RETCODE checkComponentsForNonstandardPerms(SCIP *scip, SCIP_PROPDATA *propdata)
#define DEFAULT_NAUTYMAXNCELLS
#define DEFAULT_MAXNCONSSSUBGROUP
static SCIP_RETCODE ensureSymmetryMovedpermvarscountsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
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 addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool onlywithcontvars, int *nchgbds, int cidx)
#define DEFAULT_PERFORMPRESOLVING
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)
static SCIP_RETCODE componentPackingPartitioningOrbisackUpgrade(SCIP *scip, SCIP_PROPDATA *propdata, int **componentperms, int componentsize, SCIP_Bool hassignedperm, SCIP_Bool *success)
int SCIPgetSymmetryNGenerators(SCIP *scip)
#define DEFAULT_SYMFIXNONBINARYVARS
static SCIP_RETCODE handleOrbitope(SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
static SCIP_RETCODE ensureSymmetryComponentsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
#define ISSSTCONTACTIVE(x)
#define DEFAULT_DISPLAYNORBITVARS
SCIP_RETCODE SCIPgetSymOpNodeType(SCIP *scip, const char *opnodename, int *nodetype)
static SCIP_Bool conshdlrsCanProvideSymInformation(SCIP *scip, SYM_SYMTYPE symtype)
#define DEFAULT_NAUTYMAXNNODES
#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)
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_Dialog SCIP_DIALOG
#define SCIP_DECL_DIALOGEXEC(x)
struct SCIP_DialogData SCIP_DIALOGDATA
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_PROPTIMING_ALWAYS
@ SCIP_VARTYPE_CONTINUOUS
enum SCIP_Vartype SCIP_VARTYPE