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
204#define ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
205#define ISORBITALREDUCTIONACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 0)
206#define ISSSTACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SST) != 0)
208#define ISSSTBINACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)
209#define ISSSTINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)
210#define ISSSTIMPLINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)
211#define ISSSTCONTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)
214#define SYMMETRY_STATISTICS 1
229 int nmovedbinpermvars;
230 int nmovedintpermvars;
231 int nmovedimplintpermvars;
232 int nmovedcontpermvars;
236 SCIP_Real* permvardomaincenter;
243 int* componentbegins;
247 unsigned* componentblocked;
249 SCIP_Bool* componenthassignedperm;
253 SCIP_Real log10groupsize;
254 SCIP_Bool binvaraffected;
258 SCIP_Bool checksymmetries;
259 SCIP_Bool displaynorbitvars;
260 SCIP_Bool compresssymmetries;
261 SCIP_Real compressthreshold;
262 SCIP_Bool compressed;
263 SCIP_Bool computedsymmetry;
265 SCIP_Bool usecolumnsparsity;
266 SCIP_Bool doubleequations;
267 SCIP_Bool enforcecomputesymmetry;
271 SCIP_Bool triedaddsymmethods;
272 SCIP_Bool conssaddlp;
273 SCIP_Bool addsymresacks;
281 SCIP_Bool detectdoublelex;
282 SCIP_Bool detectorbitopes;
283 SCIP_Bool detectsubgroups;
284 SCIP_Bool addweaksbcs;
285 SCIP_Bool addstrongsbcs;
287 SCIP_Bool* isnonlinvar;
289 int maxnconsssubgroup;
290 SCIP_Bool usedynamicprop;
291 SCIP_Bool preferlessrows;
294 int recomputerestart;
296 SCIP_Bool symfoundreduction;
304 int sstleadervartype;
309 SCIP_Bool addconflictcuts;
310 SCIP_Bool sstaddcuts;
311 SCIP_Bool sstmixedcomponents;
320struct SCIP_ConflictData
325 int nconflictinorbit;
342 else if ( elem1 > elem2 )
380 cmp = compfunc(arr1[it1], arr2[it2]);
386 if ( ++it1 >= narr1 )
395 if ( ++it2 >= narr2 )
408 assert( it1 >= narr1 || it2 >= narr2 );
441 if ( perm[baseidx] == baseidx || covered[baseidx] )
448 covered[baseidx] =
TRUE;
449 while ( j != baseidx )
479 assert( propdata->nperms > 0 );
481 assert( propdata->npermvars > 0 );
484 npermvars = propdata->npermvars;
492 for (p = 0; p < propdata->nperms; ++p)
495 perm = propdata->perms[p];
497 for (
i = 0;
i < permlen; ++
i)
502 for (
i = 0;
i < permlen; ++
i)
530 assert( propdata->nperms > 0 );
532 assert( propdata->npermvars > 0 );
533 assert( propdata->ncomponents > 0 );
536 npermvars = propdata->npermvars;
541 for (
c = 0;
c < propdata->ncomponents; ++
c)
546 if ( propdata->componenthassignedperm[
c] )
551 comppermlen = propdata->componenthassignedperm[
c] ? 2 * npermvars : npermvars;
553 for (p = propdata->componentbegins[
c], cnt = 0; p < propdata->componentbegins[
c + 1]; ++p, ++cnt)
556 perm = propdata->perms[propdata->components[p]];
558 for (
i = 0;
i < comppermlen; ++
i)
563 for (
i = 0;
i < comppermlen; ++
i)
585 if ( propdata->nperms == -1 )
589 else if ( propdata->nperms == 0 )
593 else if ( propdata->ncomponents < 0 )
636 if ( tabledata->propdata->orbitopalreddata || tabledata->propdata->orbitalreddata
637 || tabledata->propdata->lexreddata )
640 if ( tabledata->propdata->orbitopalreddata )
644 " %10d cutoffs\n", nred, ncutoff);
646 if ( tabledata->propdata->orbitalreddata )
650 " %10d cutoffs\n", nred, ncutoff);
652 if ( tabledata->propdata->lexreddata )
656 " %10d cutoffs\n", nred, ncutoff);
658 if ( tabledata->propdata->shadowtreeeventhdlr )
779 if ( G1->
lhs[perm1] < G2->
lhs[perm2] )
781 if ( G1->
lhs[perm1] > G2->
lhs[perm2] )
784 if ( G1->
rhs[perm1] < G2->
rhs[perm2] )
786 if ( G1->
rhs[perm1] > G2->
rhs[perm2] )
854 assert( propdata->ngenlinconss == 0 );
855 assert( propdata->ngenorbconss == 0 );
856 assert( propdata->genorbconsssize == 0 );
857 assert( propdata->genlinconsssize == 0 );
861 assert( propdata->permvardomaincenter ==
NULL );
865 assert( propdata->npermvars == 0 );
866 assert( propdata->nbinpermvars == 0 );
867 assert( propdata->nperms == -1 || propdata->nperms == 0 );
868 assert( propdata->nmaxperms == 0 );
869 assert( propdata->nmovedpermvars == -1 );
870 assert( propdata->nmovedbinpermvars == 0 );
871 assert( propdata->nmovedintpermvars == 0 );
872 assert( propdata->nmovedimplintpermvars == 0 );
873 assert( propdata->nmovedcontpermvars == 0 );
874 assert( propdata->nmovedvars == -1 );
878 assert( propdata->componenthassignedperm ==
NULL );
882 assert( propdata->ncomponents == -1 );
883 assert( propdata->ncompblocked == 0 );
901 if ( propdata->orbitalreddata !=
NULL )
905 if ( propdata->orbitopalreddata !=
NULL )
909 if ( propdata->lexreddata !=
NULL )
932 if ( propdata->permvarmap !=
NULL )
938 for (
i = 0;
i < propdata->npermvars; ++
i)
945 if ( propdata->permstrans !=
NULL )
947 assert( propdata->nperms > 0 );
949 assert( propdata->npermvars > 0 );
950 assert( propdata->nmaxperms > 0 );
952 for (
i = 0;
i < propdata->npermvars; ++
i)
960 if ( propdata->genorbconss !=
NULL )
962 assert( propdata->ngenorbconss > 0 );
965 while ( propdata->ngenorbconss > 0 )
967 assert( propdata->genorbconss[propdata->ngenorbconss - 1] !=
NULL );
970 assert( propdata->ngenorbconss == 0 );
974 propdata->genorbconsssize = 0;
978 if ( propdata->genlinconss !=
NULL )
981 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
989 propdata->ngenlinconss = 0;
990 propdata->genlinconsssize = 0;
993 if ( propdata->sstconss !=
NULL )
995 assert( propdata->nsstconss > 0 );
998 for (
i = 0;
i < propdata->nsstconss; ++
i)
1006 propdata->sstconss =
NULL;
1007 propdata->nsstconss = 0;
1008 propdata->maxnsstconss = 0;
1011 if ( propdata->leaders !=
NULL )
1013 assert( propdata->maxnleaders > 0 );
1016 propdata->maxnleaders = 0;
1017 propdata->leaders =
NULL;
1018 propdata->nleaders = 0;
1022 if ( propdata->ncomponents > 0 )
1024 assert( propdata->componentblocked !=
NULL );
1035 propdata->ncomponents = -1;
1036 propdata->ncompblocked = 0;
1040 if ( propdata->nperms > 0 )
1047 permlen = 2 * propdata->npermvars;
1049 permlen = propdata->npermvars;
1054 if ( propdata->perms !=
NULL )
1056 for (
i = 0;
i < propdata->nperms; ++
i)
1065 propdata->npermvars = 0;
1066 propdata->nbinpermvars = 0;
1067 propdata->nperms = -1;
1068 propdata->nmaxperms = 0;
1069 propdata->nmovedpermvars = -1;
1070 propdata->nmovedbinpermvars = 0;
1071 propdata->nmovedintpermvars = 0;
1072 propdata->nmovedimplintpermvars = 0;
1073 propdata->nmovedcontpermvars = 0;
1074 propdata->nmovedvars = -1;
1075 propdata->log10groupsize = -1.0;
1076 propdata->binvaraffected =
FALSE;
1077 propdata->isnonlinvar =
NULL;
1079 propdata->nperms = -1;
1083 propdata->computedsymmetry =
FALSE;
1084 propdata->compressed =
FALSE;
1095 int* consarrsizeptr,
1104 assert( consarrsizereq > 0 );
1105 assert( *consarrsizeptr >= 0 );
1106 assert( (*consarrsizeptr == 0) == (*consarrptr ==
NULL) );
1109 if ( consarrsizereq <= *consarrsizeptr )
1114 assert( newsize > *consarrsizeptr );
1117 if ( *consarrptr ==
NULL )
1126 *consarrsizeptr = newsize;
1142 SCIP_Real** permvardomaincenter,
1146 SCIP_Bool* binvaraffected,
1147 SCIP_Bool usecompression,
1148 SCIP_Real compressthreshold,
1149 SCIP_Bool* compressed
1174 *binvaraffected =
FALSE;
1175 *compressed =
FALSE;
1180 SCIP_Real percentagemovedvars;
1181 int* labelmovedvars;
1182 int* labeltopermvaridx;
1183 int nbinvarsaffected = 0;
1194 labelmovedvars[
i] = -1;
1196 for (p = 0; p < nperms; ++p)
1198 if ( perms[p][
i] !=
i )
1200 labeltopermvaridx[*nmovedvars] =
i;
1201 labelmovedvars[
i] = (*nmovedvars)++;
1210 if ( nbinvarsaffected > 0 )
1211 *binvaraffected =
TRUE;
1214 percentagemovedvars = (
SCIP_Real) *nmovedvars / (SCIP_Real)
nvars;
1215 if ( *nmovedvars > 0 &&
SCIPisLE(
scip, percentagemovedvars, compressthreshold) )
1218 for (p = 0; p < nperms; ++p)
1221 for (
i = 0;
i < *nmovedvars; ++
i)
1223 assert(
i <= labeltopermvaridx[
i] );
1224 if ( perms[p][labeltopermvaridx[
i]] >=
nvars )
1230 imgvaridx = perms[p][labeltopermvaridx[
i]] -
nvars;
1231 perms[p][
i] = labelmovedvars[imgvaridx] + *nmovedvars;
1233 assert( 0 <= perms[p][
i] && perms[p][
i] < 2 * (*nmovedvars) );
1236 perms[p][
i] = labelmovedvars[perms[p][labeltopermvaridx[
i]]];
1251 for (
i = 0;
i < *nmovedvars; ++
i)
1253 (*permvars)[
i] =
vars[labeltopermvaridx[
i]];
1255 *npermvars = *nmovedvars;
1256 *nbinpermvars = nbinvarsaffected;
1269 for (p = 0; p < nperms && ! *binvaraffected; ++p)
1271 if ( perms[p][
i] !=
i )
1274 *binvaraffected =
TRUE;
1283 for (
i = 0;
i < *npermvars; ++
i)
1288 (*permvardomaincenter)[
i] = 0.5 * (ub + lb);
1329 for (
c = 0;
c < nconshdlrs; ++
c)
1331 conshdlr = conshdlrs[
c];
1344 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n"
1345 " If symmetries shall be detected, implement the %s callback.\n",
1360 SCIP_Bool found =
FALSE;
1387 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n"
1424 *nconsnodes = nconss;
1429 for (
c = 0;
c < nconss; ++
c)
1457 depth = (int) log2((
double) num);
1458 expval = (int) exp2((
double) (
depth + 1));
1459 numnodes =
MIN(expval, 100);
1461 *nopnodes += numnodes;
1462 *nvalnodes +=
MAX((
int) 0.1 * numnodes, 1);
1477 *nopnodes += num - 1;
1486 if (
nvars <= 100000 )
1487 *nedges = 100 *
nvars;
1488 else if (
nvars <= 1000000 )
1489 *nedges = 32 *
nvars;
1490 else if (
nvars <= 16700000 )
1491 *nedges = 16 *
nvars;
1493 *nedges = INT_MAX / 10;
1521#ifdef SCIP_DISPLAY_SYM_CHECK
1538 assert( nsymvars == npermvars );
1542 for (
c = 0;
c < nconss; ++
c)
1565 for (
c = 0;
c < nconss; ++
c)
1570 SCIPsort(graphperm, SYMsortSymgraphs, graphs, nconss);
1573 for (
c = 1;
c < nconss; ++
c)
1576 groupbegins[ngroups++] =
c;
1578 groupbegins[ngroups] = nconss;
1581 for (
c = 0;
c < nconss; ++
c)
1586#ifdef SCIP_DISPLAY_SYM_CHECK
1592 for (p = 0; p < nperms; ++p)
1595 SCIP_Bool found =
TRUE;
1597#ifdef SCIP_DISPLAY_SYM_CHECK
1601 for (
i = 0;
i < permlen; ++
i)
1606 for (
i = 0;
i < permlen; ++
i)
1612 for (g = 0; g < ngroups; ++g)
1614 for (
c = groupbegins[g];
c < groupbegins[g+1]; ++
c)
1616#ifdef SCIP_DISPLAY_SYM_CHECK
1627#ifdef SCIP_DISPLAY_SYM_CHECK
1636 for (d = groupbegins[g]; d < groupbegins[g+1] && ! found; ++d)
1640#ifdef SCIP_DISPLAY_SYM_CHECK
1651#ifdef SCIP_DISPLAY_SYM_CHECK
1661#ifdef SCIP_DISPLAY_SYM_CHECK
1668 for (
c = nconss - 1;
c >= 0; --
c)
1682 SCIP_Bool compresssymmetries,
1683 SCIP_Real compressthreshold,
1686 SCIP_Bool checksymmetries,
1690 SCIP_Real** permvardomaincenter,
1697 SCIP_Bool* binvaraffected,
1698 SCIP_Bool* compressed,
1699 SCIP_Real* log10groupsize,
1700 SCIP_Real* symcodetime,
1735 *binvaraffected =
FALSE;
1736 *compressed =
FALSE;
1737 *log10groupsize = 0;
1763 nopnodes, nvalnodes, nconsnodes, nedges) );
1766 for (
c = 0;
c < nconss && *success; ++
c)
1801 perms, log10groupsize, symcodetime) );
1803 if ( checksymmetries && *nperms > 0 )
1818 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1819 compresssymmetries, compressthreshold, compressed) );
1843 for (v = 0; v <
nvars; ++v)
1846 if ( symmetry[v] >=
nvars )
1873 int* componentbegins;
1880 assert( propdata->ncomponents > 0 );
1885 componentbegins = propdata->componentbegins;
1886 ncomponents = propdata->ncomponents;
1895 for (
c = 0;
c < ncomponents; ++
c)
1897 for (
i = componentbegins[
c];
i < componentbegins[
c + 1]; ++
i)
1901 propdata->componenthassignedperm[
c] =
TRUE;
1921 assert( propdata->nperms >= 0 );
1924 if ( propdata->ncomponents >= 0 )
1928 assert( propdata->ncomponents == -1 );
1933#ifdef SCIP_OUTPUT_COMPONENT
1938 propdata->permvars, propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
1939 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
1941#ifdef SCIP_OUTPUT_COMPONENT
1947 assert( propdata->ncomponents > 0 );
1951 assert( propdata->componenthassignedperm !=
NULL );
1970 assert( propdata->nperms >= 0 );
1973 if ( propdata->permvarmap !=
NULL )
1980 for (v = 0; v < propdata->npermvars; ++v)
2003 assert( propdata->nperms >= 0 );
2006 if ( propdata->permstrans !=
NULL )
2012 for (v = 0; v < propdata->npermvars; ++v)
2015 for (p = 0; p < propdata->nperms; ++p)
2016 propdata->permstrans[v][p] = propdata->perms[p][v];
2037 assert( propdata->nperms >= 0 );
2040 if ( propdata->nmovedpermvars >= 0 )
2042 assert( propdata->nmovedpermvars == -1 );
2044 propdata->nmovedpermvars = 0;
2045 propdata->nmovedbinpermvars = 0;
2046 propdata->nmovedintpermvars = 0;
2047 propdata->nmovedimplintpermvars = 0;
2048 propdata->nmovedcontpermvars = 0;
2050 for (p = 0; p < propdata->nperms; ++p)
2052 for (v = 0; v < propdata->npermvars; ++v)
2054 if ( propdata->perms[p][v] != v )
2056 ++propdata->nmovedpermvars;
2061 ++propdata->nmovedbinpermvars;
2064 ++propdata->nmovedintpermvars;
2067 ++propdata->nmovedimplintpermvars;
2070 ++propdata->nmovedcontpermvars;
2092 if ( propdata->enforcecomputesymmetry )
2142 SCIP_Bool successful;
2143 SCIP_Real symcodetime = 0.0;
2145 unsigned int type = 0;
2151 assert( propdata->usesymmetry >= 0 );
2165 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2193 if ( ! (type & symspecrequire) )
2196 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2209 if ( propdata->computedsymmetry )
2212 assert( propdata->npermvars == 0 );
2214 assert( propdata->nperms < 0 );
2215 assert( propdata->nmaxperms == 0 );
2220 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2227 (symspecrequirefixed & (
int)
SYM_SPEC_REAL) != 0 ?
'+' :
'-');
2230 if ( symspecrequire & symspecrequirefixed )
2234 maxgenerators = propdata->maxgenerators;
2239 propdata->compresssymmetries, propdata->compressthreshold,
2240 maxgenerators, symspecrequirefixed, propdata->checksymmetries, &propdata->permvars,
2241 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2242 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2243 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2244 &propdata->log10groupsize, &symcodetime, &successful) );
2247 propdata->computedsymmetry =
TRUE;
2262 if ( propdata->nperms == 0 )
2269 assert( propdata->nperms > 0 );
2270 assert( propdata->npermvars > 0 );
2277 if ( maxgenerators == 0 )
2285 if ( propdata->displaynorbitvars )
2287 if ( propdata->nmovedvars == -1 )
2290 propdata->npermvars, &(propdata->nmovedvars)) );
2297 for (
i = 0;
i < propdata->npermvars; ++
i)
2333 int** orbitopevaridx,
2338 SCIP_Bool* isorbitope,
2342 SCIP_Bool* usedperm;
2343 SCIP_Bool foundperm =
FALSE;
2347 int ntestedperms = 0;
2359 assert( nactiveperms > 0 );
2360 assert( ntwocycles > 0 );
2362 assert( activevars ==
NULL || (0 <= nactiveperms && nactiveperms < npermvars) );
2365 if ( nusedcols !=
NULL )
2374 while ( ! foundperm )
2378 assert( ntestedperms < nactiveperms );
2380 permidx = activeperms[ntestedperms];
2382 for (j = 0; j < npermvars; ++j)
2384 if ( activevars !=
NULL && ! activevars[j] )
2387 assert( activevars ==
NULL || activevars[perms[permidx][j]] );
2390 if ( perms[permidx][j] > j )
2395 rowisbinary[row] =
TRUE;
2397 orbitopevaridx[row][0] = j;
2398 orbitopevaridx[row++][1] = perms[permidx][j];
2400 ++(nusedelems[perms[permidx][j]]);
2405 if ( row == ntwocycles )
2413 if ( row != ntwocycles )
2415 *isorbitope =
FALSE;
2420 usedperm[ntestedperms - 1] =
TRUE;
2430 for (j = ntestedperms; j < nactiveperms; ++j)
2432 SCIP_Bool success =
FALSE;
2433 SCIP_Bool infeasible =
FALSE;
2435 if ( nusedperms == nactiveperms )
2442 perms[activeperms[j]],
TRUE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2446 *isorbitope =
FALSE;
2453 coltoextend = nfilledcols;
2454 columnorder[nfilledcols++] = -1;
2459 if ( ! *isorbitope )
2466 for (j = ntestedperms; j < nactiveperms; ++j)
2468 SCIP_Bool success =
FALSE;
2469 SCIP_Bool infeasible =
FALSE;
2471 if ( nusedperms == nactiveperms )
2478 perms[activeperms[j]],
FALSE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2482 *isorbitope =
FALSE;
2489 coltoextend = nfilledcols;
2490 columnorder[nfilledcols] = 1;
2496 if ( activevars ==
NULL && nusedperms < nactiveperms )
2497 *isorbitope =
FALSE;
2499 if ( nusedcols !=
NULL )
2500 *nusedcols = nfilledcols;
2501 assert( ! *isorbitope || activevars ==
NULL || nusedperms < nfilledcols );
2520 int* componentbegins;
2529 assert( compidx < propdata->ncomponents );
2533 assert( propdata->computedsymmetry );
2534 assert( propdata->nperms > 0 );
2536 assert( propdata->npermvars > 0 );
2537 assert( propdata->ncomponents > 0 );
2541 perms = propdata->perms;
2542 npermvars = propdata->npermvars;
2544 componentbegins = propdata->componentbegins;
2545 npermsincomp = componentbegins[compidx + 1] - componentbegins[compidx];
2546 *ntwocycleperms = npermsincomp;
2550 for (
i = 0;
i < npermsincomp; ++
i)
2555 perm = perms[
components[componentbegins[compidx] +
i]];
2560 if ( ntwocycles[
i] == 0 )
2563 if ( propdata->preferlessrows )
2564 ntwocycles[
i] = npermvars;
2567 --(*ntwocycleperms);
2569 else if ( ! propdata->preferlessrows )
2570 ntwocycles[
i] = - ntwocycles[
i];
2594 int** graphcomponents,
2595 int** graphcompbegins,
2596 int** compcolorbegins,
2597 int* ngraphcomponents,
2610 int* componentbegins;
2611 int* componentslastperm;
2629 assert( usedpermssize > 0 );
2631 assert( ntwocycleperms >= 0 );
2633 assert( compidx < propdata->ncomponents );
2634 assert( propdata->computedsymmetry );
2635 assert( propdata->nperms > 0 );
2637 assert( propdata->npermvars > 0 );
2638 assert( propdata->ncomponents > 0 );
2641 assert( ! propdata->componentblocked[compidx] );
2643 perms = propdata->perms;
2644 npermvars = propdata->npermvars;
2646 componentbegins = propdata->componentbegins;
2649 assert( ntwocycleperms <= componentbegins[compidx + 1] - componentbegins[compidx] );
2655 for (k = 0; k < npermvars; ++k)
2656 componentslastperm[k] = -1;
2658 for (j = 0; j < ntwocycleperms; ++j)
2661 int firstcolor = -1;
2664 perm = perms[
components[componentbegins[compidx] + genorder[j]]];
2668 for (k = 0; k < npermvars; ++k)
2677 assert( perm[img] == k );
2685 if ( comp1 == comp2 )
2688 if ( firstcolor < 0 )
2693 componentslastperm[comp1] = j;
2700 if ( componentslastperm[comp1] == j || componentslastperm[comp2] == j )
2707 if ( color1 == color2 )
2710 componentslastperm[comp1] = j;
2711 componentslastperm[comp2] = j;
2713 if ( firstcolor < 0 )
2714 firstcolor = color1;
2718 if ( k < npermvars )
2722 if ( firstcolor == -1 )
2726 if ( *nusedperms >= usedpermssize )
2729 assert( newsize > usedpermssize );
2733 usedpermssize = newsize;
2736 (*usedperms)[*nusedperms] =
components[componentbegins[compidx] + genorder[j]];
2738 permused[genorder[j]] =
TRUE;
2741 for (k = 0; k < npermvars; ++k)
2750 assert( perm[img] == k );
2759 if ( comp1 == comp2 )
2765 if ( color1 != color2 )
2789 for (j = 0; j < npermvars; ++j)
2798 (*graphcomponents)[j] = j;
2802 SCIPsort(*graphcomponents, SYMsortGraphCompVars, (
void*) &graphcompvartype, npermvars);
2811 (*graphcompbegins)[0] = 0;
2812 (*compcolorbegins)[0] = 0;
2815 for (j = 1; j < npermvars; ++j)
2820 idx1 = (*graphcomponents)[j];
2821 idx2 = (*graphcomponents)[j-1];
2827 (*graphcompbegins)[nextcomp] = j;
2829 if ( graphcompvartype.
colors[idx1] > graphcompvartype.
colors[idx2] )
2831 (*compcolorbegins)[nextcolor] = nextcomp;
2838 assert( nextcomp == *ngraphcomponents );
2839 assert( nextcolor == *ncompcolors );
2841 (*compcolorbegins)[nextcolor] = *ngraphcomponents;
2842 (*graphcompbegins)[nextcomp] = npermvars;
2860 int* compcolorbegins,
2861 int* graphcompbegins,
2862 int* graphcomponents,
2867 int* compidxfirstrow,
2870 int* maxnvarslexorder,
2871 SCIP_Bool mayinteract,
2878 int** orbitopevaridx;
2882 SCIP_Bool isorbitope;
2883 SCIP_Bool infeasible =
FALSE;
2885 int nactivevars = 0;
2896 assert( nusedperms > 0 );
2910 for (k = 0; k < nrows; ++k)
2917 for (k = 0; k < ncols; ++k)
2918 columnorder[k] = ncols + 1;
2924 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1]; ++k)
2930 compstart = graphcompbegins[k];
2931 firstvar = propdata->permvars[graphcomponents[compstart]];
2936 for (l = 0; l < ncols; ++l)
2940 varidx = graphcomponents[compstart + l];
2949 assert( nactivevars == nrows * ncols );
2961 propdata->perms, usedperms, nrows, nusedperms, orbitopevaridx, columnorder,
2962 nusedelems, &ngencols,
NULL, &isorbitope, activevars) );
2971 for (k = nrows - 1; k >= 0; --k)
2991 if ( firstvaridx !=
NULL )
2993 if ( columnorder[ngencols-1] > -1 )
2994 *firstvaridx = orbitopevaridx[0][ngencols-1];
2996 *firstvaridx = orbitopevaridx[0][1];
3000 if ( compidxfirstrow !=
NULL && firstvaridx !=
NULL )
3002 *compidxfirstrow = -1;
3004 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3010 compstart = graphcompbegins[k];
3011 firstvar = propdata->permvars[graphcomponents[compstart]];
3019 for (l = 0; l < ncols; ++l)
3021 if ( graphcomponents[compstart + l] == *firstvaridx )
3023 *compidxfirstrow = k;
3028 assert( *compidxfirstrow > -1 );
3033 for (k = 0; k < nrows; ++k)
3040 propdata->permvars, propdata->npermvars, orbitopevaridx, columnorder,
3041 nusedelems,
NULL, &infeasible,
TRUE, lexorder, nvarslexorder, maxnvarslexorder) );
3044 assert( firstvaridx ==
NULL || propdata->permvars[*firstvaridx] == orbitopevarmatrix[0][0] );
3057 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3058 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3059 ++propdata->norbitopes;
3061 for (k = nrows - 1; k >= 0; --k)
3066 for (k = nrows - 1; k >= 0; --k)
3079 int* graphcompbegins,
3080 int* graphcomponents,
3082 SCIP_Bool storelexorder,
3094 assert( graphcompidx >= 0 );
3095 assert( ! storelexorder || lexorder !=
NULL );
3096 assert( ! storelexorder || nvarsorder !=
NULL );
3097 assert( ! storelexorder || maxnvarsorder !=
NULL );
3100 if ( storelexorder )
3102 if ( *maxnvarsorder == 0 )
3104 *maxnvarsorder = graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3111 assert( *nvarsorder == *maxnvarsorder );
3113 *maxnvarsorder += graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3118 (*lexorder)[*nvarsorder++] = graphcomponents[graphcompbegins[graphcompidx]];
3122 for (k = graphcompbegins[graphcompidx]+1; k < graphcompbegins[graphcompidx+1]; ++k)
3127 SCIP_Real vals[2] = {1, -1};
3129 vars[0] = propdata->permvars[graphcomponents[k-1]];
3130 vars[1] = propdata->permvars[graphcomponents[k]];
3132 if ( storelexorder )
3133 (*lexorder)[*nvarsorder++] = graphcomponents[k];
3143#ifdef SCIP_MORE_DEBUG
3150 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3151 propdata->genlinconss[propdata->ngenlinconss] = cons;
3152 ++propdata->ngenlinconss;
3163 int* compcolorbegins,
3164 int* graphcompbegins,
3165 int* graphcomponents,
3167 int* chosencomppercolor,
3168 int* firstvaridxpercolor,
3171 SCIP_Bool storelexorder,
3180 SCIP_Real vals[2] = {1, -1};
3183 int orbitsize[2] = {1, 1};
3185 int chosencolor = -1;
3197 assert( symgrpcompidx >= 0 );
3198 assert( symgrpcompidx < propdata->ncomponents );
3199 assert( ! storelexorder || lexorder !=
NULL );
3200 assert( ! storelexorder || nvarsorder !=
NULL );
3201 assert( ! storelexorder || maxnvarsorder !=
NULL );
3211 if ( lexorder ==
NULL || *lexorder ==
NULL )
3214 varsinlexorder =
NULL;
3218 assert( *maxnvarsorder >= 0 );
3219 assert( *nvarsorder >= 0 );
3223 for (k = 0; k < *nvarsorder; ++k)
3227 assert((*lexorder)[k] >= 0);
3235 if ( ncompcolors > 0 )
3239 for (j = 0; j < ncompcolors; ++j)
3246 if ( chosencomppercolor[j] < 0 )
3249 assert( firstvaridxpercolor[j] >= 0 );
3251 graphcomp = chosencomppercolor[j];
3252 graphcompsize = graphcompbegins[graphcomp+1] - graphcompbegins[graphcomp];
3253 varidx = firstvaridxpercolor[j];
3258 if ( varfound[
varidx] || graphcompsize == propdata->npermvars )
3262 if ( varsinlexorder !=
NULL
3264 && lexorder !=
NULL && *lexorder !=
NULL && *maxnvarsorder > 0 && *nvarsorder > 0
3265 && (*lexorder)[0] !=
varidx )
3269 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3271 assert( 0 <= graphcomponents[k] && graphcomponents[k] < propdata->npermvars );
3273 usedvars[graphcomponents[k]] =
TRUE;
3277 propdata->permstrans, propdata->components, propdata->componentbegins,
3278 usedvars, varfound,
varidx, symgrpcompidx,
3279 orbit[activeorb], &orbitsize[activeorb]) );
3283 if ( orbitsize[activeorb] > orbitsize[1 - activeorb] )
3286 activeorb = 1 - activeorb;
3291 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3292 usedvars[graphcomponents[k]] =
FALSE;
3296 if ( chosencolor > -1 )
3299 activeorb = 1 - activeorb;
3301 assert( orbit[activeorb][0] == firstvaridxpercolor[chosencolor] );
3302 vars[0] = propdata->permvars[orbit[activeorb][0]];
3304 assert( chosencolor > -1 );
3305 SCIPdebugMsg(
scip,
" adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3307 *naddedconss = orbitsize[activeorb] - 1;
3310 for (j = 1; j < orbitsize[activeorb]; ++j)
3315 vars[1] = propdata->permvars[orbit[activeorb][j]];
3325#ifdef SCIP_MORE_DEBUG
3332 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3333 propdata->genlinconss[propdata->ngenlinconss] = cons;
3334 ++propdata->ngenlinconss;
3338 if ( storelexorder )
3342 varidx = orbit[activeorb][0];
3345 if ( *maxnvarsorder == 0 )
3351 (*lexorder)[(*nvarsorder)++] =
varidx;
3355 assert( *nvarsorder == *maxnvarsorder );
3361 if (
varidx == (*lexorder)[0] )
3378 for (k = *maxnvarsorder - 1; k >= 1; --k)
3379 (*lexorder)[k] = (*lexorder)[k - 1];
3391 if ( varsinlexorder !=
NULL )
3405 int** modifiedperms,
3436 for (
i = 0;
i < npermvars; ++
i)
3441 for (
i = 0;
i < npermvars; ++
i)
3442 posinpermvar[
i] =
i;
3446 for (l = 0; l < nleaders; ++l)
3448 leader = leaders[l];
3449 curposleader = posinpermvar[leader];
3450 varidx = permvaridx[curposleader];
3451 lidx = permvaridx[l];
3454 permvaridx[curposleader] = lidx;
3458 posinpermvar[lidx] = curposleader;
3459 posinpermvar[leader] = l;
3463 for (
i = 0;
i < npermvars; ++
i)
3464 modifiedpermvars[
i] = origpermvars[permvaridx[
i]];
3467 for (p = 0; p < nperms; ++p)
3469 for (
i = 0;
i < npermvars; ++
i)
3470 modifiedperms[p][
i] = posinpermvar[origperms[p][permvaridx[
i]]];
3486 int* graphcomponents,
3487 int* graphcompbegins,
3488 int* compcolorbegins,
3493 SCIP_Bool oneorbitopecriterion =
FALSE;
3494 SCIP_Bool multorbitopecriterion =
FALSE;
3500 assert( ncompcolors >= 0 );
3501 assert( symcompsize > 0 );
3503 for (j = 0; j < ncompcolors; ++j)
3506 int largestcompsize = 0;
3511 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3515 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3519 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3522 if ( largestcompsize < 1 )
3527 largestcompsize = compsize;
3529 else if ( compsize != largestcompsize )
3532 firstvar = permvars[graphcomponents[graphcompbegins[k]]];
3540 if ( k == compcolorbegins[j+1] )
3542 SCIP_Real threshold;
3546 ncols = graphcompbegins[compcolorbegins[j] + 1] - graphcompbegins[compcolorbegins[j]];
3548 threshold = 0.7 * (
SCIP_Real) symcompsize;
3551 if ( nbinrows <= 2 * ncols || (nbinrows <= 8 * ncols && nbinrows < 100) )
3552 multorbitopecriterion =
TRUE;
3553 else if ( nbinrows <= 3 * ncols || (SCIP_Real) nbinrows * ncols >= threshold )
3554 oneorbitopecriterion =
TRUE;
3558 if ( (norbitopes == 1 && oneorbitopecriterion) || (norbitopes >= 2 && multorbitopecriterion) )
3577 int nstrongsbcs = 0;
3580 int** modifiedperms;
3582 int* nvarsincomponent;
3584 int* graphcomponents;
3585 int* graphcompbegins;
3586 int* compcolorbegins;
3587 int* chosencomppercolor =
NULL;
3588 int* firstvaridxpercolor =
NULL;
3591 int ngraphcomponents;
3596 int ntrivialcolors = 0;
3598 int* lexorder =
NULL;
3599 int nvarslexorder = 0;
3600 int maxnvarslexorder = 0;
3602 SCIP_Bool allpermsused =
FALSE;
3603 SCIP_Bool handlednonbinarysymmetry =
FALSE;
3604 int norbitopesincomp;
3608 assert( propdata->computedsymmetry );
3609 assert( propdata->nperms >= 0 );
3610 assert( 0 <= cidx && cidx < propdata->ncomponents );
3615 if ( propdata->nperms == 0 || propdata->componentblocked[cidx] )
3622 assert( propdata->nperms > 0 );
3624 assert( propdata->npermvars > 0 );
3632 for (p = 0; p < propdata->nperms; ++p)
3639 for (p = 0; p < propdata->npermvars; ++p)
3641 if ( propdata->vartocomponent[p] >= 0 )
3642 ++nvarsincomponent[propdata->vartocomponent[p]];
3645 SCIPdebugMsg(
scip,
"starting subgroup detection routine for component %d\n", cidx);
3647 npermsincomp = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
3650 for (j = 0; j < npermsincomp; ++j)
3655 assert( ntwocycleperms >= 0 );
3656 assert( ntwocycleperms <= npermsincomp );
3658 SCIPdebugMsg(
scip,
"component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
3660#ifdef SCIP_MORE_DEBUG
3667 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx+1]; ++p)
3669 perm = propdata->components[p];
3671 for (k = 0; k < propdata->npermvars; ++k)
3676 for (k = 0; k < propdata->npermvars; ++k)
3681 j = propdata->perms[perm][k];
3693 j = propdata->perms[perm][j];
3703 if ( ntwocycleperms < 2 )
3709 usedpermssize = ntwocycleperms / 2;
3714 &graphcomponents, &graphcompbegins, &compcolorbegins, &ngraphcomponents,
3715 &ncompcolors, &usedperms, &nusedperms, usedpermssize, permused) );
3717 SCIPdebugMsg(
scip,
" created subgroup detection graph using %d of the permutations\n", nusedperms);
3719 if ( nusedperms == npermsincomp )
3720 allpermsused =
TRUE;
3725 assert( ngraphcomponents > 0 );
3726 assert( ncompcolors > 0 );
3727 assert( nusedperms <= ntwocycleperms );
3728 assert( ncompcolors < propdata->npermvars );
3730 if ( nusedperms == 0 )
3732 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
3740 SCIPdebugMsg(
scip,
" number of different colors in the graph: %d\n", ncompcolors);
3742 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3751 for (j = 0; j < ncompcolors; ++j)
3753 chosencomppercolor[j] = -1;
3754 firstvaridxpercolor[j] = -1;
3758 norbitopesincomp =
getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3759 ncompcolors, nvarsincomponent[cidx]);
3762 if ( norbitopesincomp == 1 )
3766 for (k = 0; k < npermsincomp; ++k)
3774 propdata->perms[propdata->components[propdata->componentbegins[cidx] + k]],
3775 propdata->permvars, propdata->npermvars,
FALSE,
3781 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3782 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3783 ++propdata->nsymresacks;
3785 if ( ! propdata->componentblocked[cidx] )
3788 ++propdata->ncompblocked;
3791 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d\n", k, cidx);
3797 for (j = 0; j < ncompcolors; ++j)
3799 int nbinarycomps = 0;
3800 int largestcolorcomp = -1;
3801 int largestcompsize = 0;
3803 SCIP_Bool isorbitope =
TRUE;
3804 SCIP_Bool orbitopeadded =
FALSE;
3805 SCIP_Bool useorbitope;
3807 SCIP_Bool binaffected =
FALSE;
3808 SCIP_Bool intaffected =
FALSE;
3809 SCIP_Bool contaffected =
FALSE;
3813 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3815 if( chosencomppercolor !=
NULL )
3816 chosencomppercolor[j] = -1;
3822 SCIPdebugMsg(
scip,
" color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
3823 graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]]);
3826 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3831 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3834 if ( largestcompsize < 1 )
3842 largestcompsize = compsize;
3843 largestcolorcomp = k;
3845 else if ( compsize != largestcompsize )
3852 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3860 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3864 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3871 contaffected =
TRUE;
3874 SCIPdebugMsg(
scip,
" affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
3878 useorbitope =
FALSE;
3879 if ( norbitopesincomp > 0 && nbinarycomps > 0 )
3882 if ( isorbitope && useorbitope )
3887 SCIPdebugMsg(
scip,
" detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
3889 assert( nbinarycomps > 0 );
3890 assert( largestcompsize > 2 );
3898 graphcompbegins, graphcomponents, j, nbinarycomps, largestcompsize, &firstvaridx, &chosencomp,
3899 &lexorder, &nvarslexorder, &maxnvarslexorder, allpermsused, &orbitopeadded) );
3901 if ( orbitopeadded )
3903 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3909 assert( compcolorbegins[j] <= chosencomp && chosencomp < compcolorbegins[j+1] );
3910 assert( 0 <= firstvaridx && firstvaridx < propdata->npermvars );
3912 chosencomppercolor[j] = chosencomp;
3913 firstvaridxpercolor[j] = firstvaridx;
3916 if ( ! propdata->componentblocked[cidx] )
3919 ++propdata->ncompblocked;
3929 if ( propdata->addstrongsbcs && ! orbitopeadded )
3931 assert( largestcolorcomp >= 0 );
3932 assert( largestcolorcomp < ngraphcomponents );
3933 assert( largestcompsize > 0 );
3935 if( propdata->addweaksbcs )
3940 chosencomppercolor[j] = largestcolorcomp;
3941 firstvaridxpercolor[j] = graphcomponents[graphcompbegins[largestcolorcomp]];
3944 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3945 largestcolorcomp, graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp]);
3949 propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3952 if ( !
SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
3953 handlednonbinarysymmetry =
TRUE;
3955 if ( ! propdata->componentblocked[cidx] )
3958 ++propdata->ncompblocked;
3962 nstrongsbcs += graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp] - 1;
3965 else if ( ! orbitopeadded )
3970 if ( propdata->addweaksbcs )
3973 chosencomppercolor[j] = -1;
3981 if ( propdata->addweaksbcs && propdata->componentblocked[cidx] && nusedperms < npermsincomp )
3989 graphcomponents, ncompcolors, chosencomppercolor, firstvaridxpercolor,
3990 cidx, &naddedconss, propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3992 assert( naddedconss < propdata->npermvars );
3995 nweaksbcs += naddedconss;
3999 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4004 if ( nvarslexorder > 0 && propdata->addsymresacks && ! handlednonbinarysymmetry )
4009 propdata->permvars, modifiedpermvars, propdata->npermvars, lexorder, nvarslexorder) );
4011 for (k = 0; k < npermsincomp; ++k)
4016 SCIP_Bool actsonbinary =
FALSE;
4023 symresackperm = modifiedperms[propdata->components[propdata->componentbegins[cidx] + k]];
4024 for (j = 0; j < propdata->nperms && !actsonbinary; ++j)
4027 actsonbinary =
TRUE;
4030 if ( ! actsonbinary )
4036 symresackperm, modifiedpermvars, propdata->npermvars,
FALSE,
4042 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4043 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4044 ++propdata->nsymresacks;
4046 if ( ! propdata->componentblocked[cidx] )
4049 ++propdata->ncompblocked;
4052 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, cidx);
4068 SCIPdebugMsg(
scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4069 SCIPdebugMsg(
scip,
"total number of added strong sbcs: %d\n", nstrongsbcs);
4077 for (p = propdata->nperms - 1; p >= 0; --p)
4114 assert( nconflictvars > 0 );
4120 for (
i = 0;
i < nconflictvars; ++
i)
4123 varconflicts[
i].orbitidx = -1;
4124 varconflicts[
i].nconflictinorbit = 0;
4125 varconflicts[
i].orbitsize = -1;
4126 varconflicts[
i].posinorbit = -1;
4130 for (
r = 0;
r < norbits; ++
r)
4135 orbitsize = orbitbegins[
r + 1] - orbitbegins[
r];
4136 assert( orbitsize >= 0 );
4138 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4144 assert( pos < nconflictvars );
4145 assert( varconflicts[pos].
var == conflictvars[pos] );
4147 varconflicts[pos].orbitidx =
r;
4148 varconflicts[pos].nconflictinorbit = 0;
4149 varconflicts[pos].orbitsize = orbitsize;
4150 varconflicts[pos].posinorbit = posinorbit++;
4160 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4163 assert( varconflicts[ii].orbitidx ==
r );
4166 if ( ! varconflicts[ii].
active )
4169 for (j =
i + 1; j < orbitbegins[
r + 1]; ++j)
4172 assert( varconflicts[jj].orbitidx ==
r );
4175 if ( ! varconflicts[jj].
active )
4185 varconflicts[ii].ncliques, (
void**)varconflicts[jj].cliques, varconflicts[jj].ncliques,
4186 sortByPointerValue) )
4189 ++varconflicts[ii].nconflictinorbit;
4190 ++varconflicts[jj].nconflictinorbit;
4227 int varncliques = 0;
4233 assert( nconflictvars > 0 );
4236 *varconflicts =
NULL;
4242 if ( ncliques == 0 )
4244 SCIPdebugMsg(
scip,
"No cliques present --> construction of conflict structure aborted.\n");
4251 for (
i = 0;
i < nconflictvars; ++
i)
4253 (*varconflicts)[
i].ncliques = 0;
4254 (*varconflicts)[
i].active =
TRUE;
4255 (*varconflicts)[
i].var = conflictvars[
i];
4257 (*varconflicts)[
i].cliques =
NULL;
4258 (*varconflicts)[
i].orbitidx = -1;
4259 (*varconflicts)[
i].nconflictinorbit = 0;
4260 (*varconflicts)[
i].orbitsize = -1;
4261 (*varconflicts)[
i].posinorbit = -1;
4271 for (
c = 0;
c < ncliques; ++
c)
4273 clique = cliques[
c];
4279 assert( ncliquevars > 0 );
4285 for (
i = 0;
i < ncliquevars; ++
i)
4290 if ( node == INT_MAX )
4293 assert( node < nconflictvars );
4295 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4296 (*varconflicts)[node].active =
TRUE;
4297 (*varconflicts)[node].ncliques++;
4302 for (
i = 0;
i < nconflictvars; ++
i)
4304 assert( (*varconflicts)[
i].ncliques >= 0 );
4306 if ( (*varconflicts)[
i].ncliques > 0 )
4314 for (
c = 0;
c < ncliques; ++
c)
4316 clique = cliques[
c];
4322 assert( ncliquevars > 0 );
4328 for (
i = 0;
i < ncliquevars; ++
i)
4333 if ( node == INT_MAX )
4337 assert( node < nconflictvars );
4338 assert( (*varconflicts)[node].
var == cliquevars[
i] );
4341 assert( tmpncliques[node] < (*varconflicts)[node].ncliques );
4342 assert( (*varconflicts)[node].cliques !=
NULL );
4343 (*varconflicts)[node].cliques[tmpncliques[node]++] = clique;
4352 for (
i = 0;
i < nconflictvars; ++
i)
4354 SCIPsortPtr((
void**)(*varconflicts)[
i].cliques, sortByPointerValue, (*varconflicts)[
i].ncliques);
4358 for (
i = 0;
i < nconflictvars; ++
i)
4360 assert( tmpncliques[
i] == (*varconflicts)[
i].ncliques );
4367 SCIPdebugMsg(
scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4392 n = (*varconflicts)[
i].ncliques;
4410 int* componentbegins;
4412 SCIP_Bool conssaddlp;
4413 int** modifiedperms =
NULL;
4416 int nsymresackcons = 0;
4424 assert( propdata->npermvars >= 0 );
4425 assert( propdata->nbinpermvars >= 0 );
4428 if ( propdata->nbinpermvars == 0 )
4430 assert( propdata->binvaraffected == 0 );
4434 perms = propdata->perms;
4435 nperms = propdata->nperms;
4436 permvars = propdata->permvars;
4437 npermvars = propdata->npermvars;
4438 conssaddlp = propdata->conssaddlp;
4440 componentbegins = propdata->componentbegins;
4447 assert( 0 <= cidx && cidx < propdata->ncomponents );
4462 if ( propdata->componenthassignedperm[cidx] )
4466 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4469 for (p = 0; p < nperms; ++p)
4475 for (
i = 0;
i < npermvars; ++
i)
4476 modifiedpermvars[
i] = permvars[
i];
4479 propdata->leaders, propdata->nleaders) );
4483 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
4494 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4513 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4514 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4515 ++propdata->nsymresacks;
4519 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4525 for (p = nperms - 1; p >= 0; --p)
4550 int norbitvarinconflict,
4562 SCIP_Bool addcuts =
FALSE;
4574 assert( orbitleaderidx >= 0 );
4576 assert( norbitvarinconflict >= 0 );
4579 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4582 if ( propdata->sstaddcuts )
4586 addcuts = propdata->addconflictcuts;
4589 ncuts = orbitsize - norbitvarinconflict - 1;
4594 if ( propdata->nsstconss == 0 )
4597 assert( propdata->maxnsstconss == 0 );
4598 propdata->maxnsstconss = 2 * ncuts;
4601 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
4607 propdata->maxnsstconss, newsize) );
4608 propdata->maxnsstconss = newsize;
4612 if ( propdata->nleaders == 0 )
4614 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
4617 assert( propdata->nleaders < propdata->maxnleaders );
4620 posleader = orbitbegins[orbitidx] + orbitleaderidx;
4621 vars[0] = permvars[orbits[posleader]];
4624 propdata->leaders[propdata->nleaders++] = orbits[posleader];
4626 for (
i = 0, poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++poscur)
4628 if (
i == orbitleaderidx )
4630 assert( orbitvarinconflict ==
NULL || ! orbitvarinconflict[
i] );
4634 vars[1] = permvars[orbits[poscur]];
4636 for (j = 0; j < propdata->nleaders - 1; ++j)
4638 assert( propdata->leaders[j] != orbits[poscur] );
4643 if ( varconflicts !=
NULL )
4645 if ( orbitvarinconflict[
i] )
4659 varconflicts[orbits[poscur]].active =
FALSE;
4663 orbitvarinconflict[
i] =
FALSE;
4672 propdata->sstconss[propdata->nsstconss++] = cons;
4682 propdata->sstconss[propdata->nsstconss++] = cons;
4706 int* norbitvarinconflict,
4712 int curcriterion = INT_MIN;
4719 assert( nconflictvars > 0 );
4731 *norbitvarinconflict = 0;
4742 orbitcriterion = INT_MIN;
4745 for (
i = 0;
i < norbits; ++
i)
4749 if (
SCIPvarGetType(conflictvars[orbits[orbitbegins[
i]]]) != leadervartype )
4753 curcriterion = orbitbegins[
i] - orbitbegins[
i + 1];
4755 curcriterion = orbitbegins[
i + 1] - orbitbegins[
i];
4765 cnt = orbitbegins[
i];
4777 cnt = orbitbegins[
i + 1] - 1;
4792 curcriterion = varconflicts[
varidx].nconflictinorbit;
4796 if ( curcriterion > orbitcriterion )
4798 orbitcriterion = curcriterion;
4805 *leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
4810 if ( *success && varconflicts !=
NULL )
4812 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4813 assert( leader < nconflictvars );
4816 && varconflicts[leader].ncliques > 0 )
4823 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4825 assert( leader >= 0 && leader < nconflictvars );
4829 for (
i = 0;
i < orbitsize; ++
i)
4832 if (
i == *leaderidx )
4836 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4839 if ( ! varconflicts[varmapid].
active )
4844 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4845 varconflicts[varmapid].ncliques, sortByPointerValue) )
4848 orbitvarinconflict[
i] =
TRUE;
4849 ++(*norbitvarinconflict);
4866 for (
i = 0;
i < nconflictvars; ++
i)
4874 if ( varconflicts[
i].orbitidx == -1 )
4877 curcriterion = varconflicts[
i].nconflictinorbit;
4879 if ( curcriterion > orbitcriterion )
4881 orbitcriterion = curcriterion;
4882 *orbitidx = varconflicts[
i].orbitidx;
4883 *leaderidx = varconflicts[
i].posinorbit;
4889 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4890 assert( leader < nconflictvars );
4893 if ( *success && varconflicts[leader].ncliques > 0 )
4898 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4900 assert( leader >= 0 && leader < nconflictvars );
4904 for (
i = 0;
i < orbitsize; ++
i)
4907 if (
i == *leaderidx )
4911 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4913 if ( ! varconflicts[varmapid].
active )
4918 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4919 varconflicts[varmapid].ncliques, sortByPointerValue) )
4922 orbitvarinconflict[
i] =
TRUE;
4923 ++(*norbitvarinconflict);
4938 SCIP_Bool onlywithcontvars,
4949 int nmovedbinpermvars;
4950 int nmovedintpermvars;
4951 int nmovedimplintpermvars;
4952 int nmovedcontpermvars;
4959 int* componentbegins;
4960 int* vartocomponent;
4962 unsigned* componentblocked;
4967 int norbitvarinconflict;
4975 int nvarsselectedtype;
4976 SCIP_Bool conflictgraphcreated =
FALSE;
4977 SCIP_Bool mixedcomponents;
4978 int norbitleadercomponent;
4985 SCIP_Bool success =
TRUE;
4989 assert( propdata->computedsymmetry );
4991 permvars = propdata->permvars;
4992 npermvars = propdata->npermvars;
4993 nperms = propdata->nperms;
4999 permvarmap = propdata->permvarmap;
5003 permstrans = propdata->permstrans;
5007 componentbegins = propdata->componentbegins;
5008 componentblocked = propdata->componentblocked;
5009 vartocomponent = propdata->vartocomponent;
5010 ncomponents = propdata->ncomponents;
5016 assert( ncomponents > 0 );
5017 assert( 0 <= cidx && cidx < ncomponents );
5020 if ( componentblocked[cidx] )
5024 if ( propdata->componenthassignedperm[cidx] )
5027 leaderrule = propdata->sstleaderrule;
5028 tiebreakrule = propdata->ssttiebreakrule;
5029 leadervartype = propdata->sstleadervartype;
5030 mixedcomponents = propdata->sstmixedcomponents;
5034 nmovedpermvars = propdata->nmovedpermvars;
5035 nmovedbinpermvars = propdata->nmovedbinpermvars;
5036 nmovedintpermvars = propdata->nmovedintpermvars;
5037 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5038 nmovedcontpermvars = propdata->nmovedcontpermvars;
5039 assert( nmovedpermvars > 0 );
5042 nvarsselectedtype = 0;
5043 if (
ISSSTBINACTIVE(leadervartype) && nmovedbinpermvars > nvarsselectedtype )
5046 nvarsselectedtype = nmovedbinpermvars;
5049 if (
ISSSTINTACTIVE(leadervartype) && nmovedintpermvars > nvarsselectedtype )
5052 nvarsselectedtype = nmovedintpermvars;
5055 if (
ISSSTIMPLINTACTIVE(leadervartype) && nmovedimplintpermvars > nvarsselectedtype )
5058 nvarsselectedtype = nmovedimplintpermvars;
5061 if (
ISSSTCONTACTIVE(leadervartype) && nmovedcontpermvars > nvarsselectedtype )
5064 nvarsselectedtype = nmovedcontpermvars;
5068 if ( nvarsselectedtype == 0 )
5072 if ( onlywithcontvars )
5074 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
5076 perm = propdata->perms[p];
5077 for (
i = 0;
i < propdata->npermvars; ++
i)
5099 conflictgraphcreated = varconflicts !=
NULL;
5107 if ( conflictgraphcreated )
5112 SCIPdebugMsg(
scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5115 if ( nchgbds !=
NULL )
5119 for (
c = 0;
c < ncomponents; ++
c)
5121 for (p = componentbegins[
c]; p < componentbegins[
c + 1]; ++p)
5129 ninactiveperms = nperms - componentbegins[cidx + 1] + componentbegins[cidx];
5132 norbitleadercomponent = 0;
5133 while ( ninactiveperms < nperms )
5139 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5140 componentblocked, ncomponents, nmovedpermvars) );
5143 if ( ! mixedcomponents )
5145 for (p = 0; p < norbits; ++p)
5148 if (
SCIPvarGetType(permvars[orbits[orbitbegins[p]]]) != selectedtype )
5160 if ( conflictgraphcreated )
5178 norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype, &orbitidx, &orbitleaderidx,
5179 orbitvarinconflict, &norbitvarinconflict, &success) );
5184 assert( 0 <= orbitidx && orbitidx < norbits );
5185 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5186 SCIPdebugMsg(
scip,
"%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5190 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5192 ++norbitleadercomponent;
5194 if ( nchgbds !=
NULL )
5195 *nchgbds += nchanges;
5198 posleader = orbits[orbitbegins[orbitidx] + orbitleaderidx];
5199 for (p = 0; p < nperms; ++p)
5201 if ( inactiveperms[p] )
5204 if ( permstrans[posleader][p] != posleader )
5206 inactiveperms[p] =
TRUE;
5213 if ( norbitleadercomponent > 0 )
5216 if ( conflictgraphcreated )
5222 if ( varconflicts !=
NULL )
5249 SCIP_Bool ispporbitope;
5257 assert( propdata->usedynamicprop );
5271 SCIP_Real conscoefs[2] = { -1.0, 1.0 };
5275 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5276 for (
i = 0;
i < ncols - 1; ++
i)
5280 consvars[0] = propdata->permvars[varidxmatrix[0][
i]];
5281 consvars[1] = propdata->permvars[varidxmatrix[0][
i + 1]];
5287 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5295 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5300 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5303 propdata->permvars, propdata->npermvars, orbisackperm, (
SYM_SYMTYPE) propdata->symtype,
5304 propdata->permvardomaincenter,
TRUE, success) );
5311 for (
i = 0;
i < nrows; ++
i)
5314 for (j = 0; j < ncols; ++j)
5315 varmatrix[
i][j] = propdata->permvars[varidxmatrix[
i][j]];
5322 ispporbitope = npprows >= 3;
5336 for (
i = 0;
i < nrows; ++
i)
5341 ppvarsarrayonlypprows[
r++] = varmatrix[
i];
5355 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5359 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5373 nelem = nrows * ncols;
5375 for (
i = 0;
i < nrows; ++
i)
5377 for (j = 0; j < ncols; ++j)
5378 orbitopevarmatrix[pos++] = varmatrix[
i][j];
5387 orbitopevarmatrix, nrows, ncols, success) );
5395 for (
i = nrows - 1;
i >= 0; --
i)
5410 int** componentperms,
5412 SCIP_Bool hassignedperm,
5429 int** pporbisackperms;
5430 int npporbisackperms;
5434 int* npermvarssetppcconss;
5435 int* maxnpermvarssetppcconss;
5442 assert( componentsize > 0 );
5449 if ( hassignedperm )
5453 if ( setppcconshdlr ==
NULL )
5457 if ( nsetppcconss == 0 )
5468 for (
c = 0;
c < nsetppcconss; ++
c)
5470 cons = setppcconss[
c];
5476 setppconsssort[nsetppconss++] = cons;
5478 SCIPsortPtr((
void**) setppconsssort, sortByPointerValue, nsetppconss);
5486 for (
c = 0;
c < nsetppconss; ++
c)
5490 cons = setppconsssort[
c];
5496 for (
i = 0;
i < nsetppcvars; ++
i)
5498 var = setppcvars[
i];
5501 assert( varid == INT_MAX || varid < propdata->npermvars );
5503 if ( varid < propdata->npermvars )
5506 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5507 assert( npermvarssetppcconss[varid] < maxnpermvarssetppcconss[varid] );
5508 permvarssetppcconss[varid][npermvarssetppcconss[varid]++] = cons;
5516 npporbisackperms = 0;
5517 for (p = 0; p < componentsize; ++p)
5519 perm = componentperms[p];
5523 for (
i = 0;
i < propdata->npermvars; ++
i)
5542 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) )
5551 if ( ntwocycles > 0 )
5553 pporbisackperms[npporbisackperms++] = perm;
5554 if ( ntwocycles > maxntwocycles )
5555 maxntwocycles = ntwocycles;
5563 if ( npporbisackperms * 2 >= componentsize )
5571 assert( npporbisackperms > 0 );
5572 assert( maxntwocycles > 0 );
5577 for (
i = 0;
i < maxntwocycles; ++
i)
5578 ppvarsmatrix[
i] = &(ppvarsblock[2 *
i]);
5581 for (p = 0; p < npporbisackperms; ++p)
5583 perm = pporbisackperms[p];
5587 for (
i = 0;
i < propdata->npermvars; ++
i)
5600 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) );
5602 assert( nrows < maxntwocycles );
5603 row = ppvarsmatrix[nrows++];
5604 row[0] = propdata->permvars[
i];
5605 row[1] = propdata->permvars[j];
5606 assert( row[0] != row[1] );
5617 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5621 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5635 for (varid = 0; varid < propdata->npermvars; ++varid)
5637 assert( (permvarssetppcconss[varid] ==
NULL) == (maxnpermvarssetppcconss[varid] == 0) );
5638 assert( npermvarssetppcconss[varid] >= 0 );
5639 assert( maxnpermvarssetppcconss[varid] >= 0 );
5640 assert( npermvarssetppcconss[varid] <= maxnpermvarssetppcconss[varid] );
5641 if ( npermvarssetppcconss[varid] == 0 )
5644 permvarssetppcconss[varid] =
NULL;
5645 npermvarssetppcconss[varid] = 0;
5646 maxnpermvarssetppcconss[varid] = 0;
5666 int** componentperms;
5669 SCIP_Bool checkorbired;
5670 SCIP_Bool checklexred;
5679 && propdata->usedynamicprop
5680 && propdata->addsymresacks
5682 assert( propdata->nperms > 0 );
5683 assert( 0 <= cidx && cidx < propdata->ncomponents );
5684 assert( propdata->componentblocked !=
NULL );
5687 if ( propdata->componentblocked[cidx] )
5692 checklexred =
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5693 assert( checkorbired || checklexred );
5696 assert( propdata->nmovedpermvars );
5699 componentsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
5701 for (p = 0; p < componentsize; ++p)
5702 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
5711 checkpporbisack =
SCIPgetParam(
scip,
"constraints/orbisack/checkpporbisack");
5715 componentperms, componentsize, propdata->componenthassignedperm[cidx], &success) );
5720 goto FINISHCOMPONENT;
5725 if ( checkorbired && !propdata->componenthassignedperm[cidx] )
5728 propdata->permvars, propdata->npermvars, componentperms, componentsize, &success) );
5737 for (p = 0; p < componentsize; ++p)
5741 propdata->permvars, propdata->npermvars, componentperms[p],
5742 (
SYM_SYMTYPE) propdata->symtype, propdata->permvardomaincenter,
TRUE, &success) );
5750 if ( propdata->componentblocked[cidx] )
5751 ++propdata->ncompblocked;
5766 int ncomponentshandled;
5773 if ( propdata->orbitopalreddata )
5777 if ( propdata->orbitalreddata )
5781 if ( propdata->lexreddata )
5785 if ( propdata->ncomponents >= 0 )
5792 ncomponentshandled = 0;
5793 for (
i = 0;
i < propdata->ncomponents; ++
i)
5795 if ( propdata->componentblocked[
i] )
5796 ++ncomponentshandled;
5798 assert( propdata->ncompblocked <= ncomponentshandled );
5799 assert( ncomponentshandled <= propdata->ncomponents );
5801 ncomponentshandled, propdata->ncomponents);
5829 if ( propdata->usedynamicprop )
5834 else if ( propdata->binvaraffected )
5846 for (
i = 0;
i < nrows; ++
i)
5853 for (j = 0; j < ncols; ++j)
5856 orbitopematrix[nbinrows][j] = propdata->permvars[varidxmatrix[
i][j]];
5871 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5872 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5873 ++propdata->norbitopes;
5878 for (
i = nbinrows - 1;
i >= 0; --
i)
5924 assert( nrowblocks > 0 );
5925 assert( ncolblocks > 0 );
5930 &propdata->genorbconsssize, propdata->ngenorbconss + nrowblocks + ncolblocks) );
5932 maxdim =
MAX(nrows, ncols);
5934 for (
i = 0;
i < maxdim; ++
i)
5940 for (p = 0; p < ncolblocks; ++p)
5943 for (
i = 0;
i < nrows; ++
i)
5946 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[
i][colsbegin[p]]]) )
5949 for (col = 0, j = colsbegin[p]; j < colsbegin[p + 1]; ++j, ++col)
5952 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[
i][j]];
5964 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5970 for (p = 0; p < nrowblocks; ++p)
5973 for (
i = 0;
i < ncols; ++
i)
5976 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[rowsbegin[p]][
i]]) )
5979 for (col = 0, j = rowsbegin[p]; j < rowsbegin[p + 1]; ++j, ++col)
5982 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[j][
i]];
5994 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5999 for (
i = maxdim - 1;
i >= 0; --
i)
6013 SCIP_Bool detectsinglelex,
6017 int** lexmatrix =
NULL;
6018 int* lexrowsbegin =
NULL;
6019 int* lexcolsbegin =
NULL;
6028 SCIP_Bool isorbitope;
6029 SCIP_Bool success =
FALSE;
6033 assert( 0 <= cidx && cidx < propdata->ncomponents );
6036 if ( propdata->componentblocked[cidx] )
6040 if ( propdata->componenthassignedperm[cidx] )
6048 compsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
6050 for (p = 0,
i = propdata->componentbegins[cidx];
i < propdata->componentbegins[cidx + 1]; ++
i)
6051 perms[p++] = propdata->perms[propdata->components[
i]];
6054 &success, &isorbitope, &lexmatrix, &nrows, &ncols,
6055 &lexrowsbegin, &lexcolsbegin, &nrowmatrices, &ncolmatrices) );
6072 SCIP_Bool hasbinaryvar =
FALSE;
6075 for (
i = 0;
i < nrows && !hasbinaryvar; ++
i)
6077 for (p = 0; p < ncols; ++p)
6081 hasbinaryvar =
TRUE;
6090 lexrowsbegin, lexcolsbegin, nrowmatrices, ncolmatrices, &success) );
6097 for (
i = nrows - 1;
i >= 0; --
i)
6102 if ( ncolmatrices > 0 )
6106 if ( nrowmatrices > 0 )
6115 ++(propdata->ncompblocked);
6131 assert( 0 <= cidx && cidx < propdata->ncomponents );
6134 if ( propdata->componentblocked[cidx] )
6138 if ( propdata->componenthassignedperm[cidx] )
6142 if ( !propdata->usedynamicprop &&
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
6143 && propdata->binvaraffected && propdata->ncompblocked < propdata->ncomponents )
6183 SCIP_Bool useorbitalredorlexred;
6187 assert( propdata->ncomponents >= 0 );
6188 assert( 0 <= cidx && cidx < propdata->ncomponents );
6191 if ( propdata->componentblocked[cidx] )
6196 || (
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
6199 if ( propdata->detectdoublelex || propdata->detectorbitopes )
6201 SCIP_Bool detectsinglelex;
6203 detectsinglelex = propdata->detectdoublelex ?
FALSE :
TRUE;
6212 if ( useorbitalredorlexred )
6228 SCIP_Bool* earlyterm
6237 if ( nchgbds !=
NULL )
6239 if ( earlyterm !=
NULL )
6245 if ( earlyterm !=
NULL )
6252 assert( propdata->usesymmetry >= 0 );
6255 if ( propdata->usesymmetry == 0 )
6257 if ( earlyterm !=
NULL )
6263 if ( propdata->triedaddsymmethods )
6265 assert( propdata->nperms >= 0 );
6267 if ( earlyterm !=
NULL )
6272 assert( !propdata->triedaddsymmethods );
6275 if ( !propdata->computedsymmetry )
6283 if ( !propdata->computedsymmetry )
6287 propdata->triedaddsymmethods =
TRUE;
6288 assert( propdata->nperms >= 0 );
6291 if ( propdata->nperms == 0 )
6296 assert( propdata->ncomponents > 0 );
6299 for (
c = 0;
c < propdata->ncomponents; ++
c)
6307#ifdef SYMMETRY_STATISTICS
6320 SCIP_Bool* infeasible,
6334 *infeasible =
FALSE;
6379 if ( propdata->usesymmetry < 0 )
6383 assert( propdata->usesymmetry >= 0 );
6386 if ( propdata->usesymmetry == 0 )
6415 assert( propdata->usesymmetry >= 0 );
6418 if ( propdata->usesymmetry == 0 )
6462 SCIP_Bool earlyterm;
6473 assert( propdata->usesymmetry >= 0 );
6476 if ( propdata->usesymmetry == 0 )
6490 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
6502 *nchgbds += nchanges;
6506 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
6509 assert( propdata->nperms > 0 );
6510 assert( propdata->triedaddsymmethods );
6515 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
6516 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
6519 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
6522 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6523 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6533 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
6536 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6537 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6547 propdata->ngenorbconss + propdata->ngenlinconss);
6549 for (
i = 0;
i < propdata->nsstconss; ++
i)
6552 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
6553 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6562 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
6575 SCIP_Bool infeasible;
6593 if ( propdata->usesymmetry < 0 )
6601 propdata->symfoundreduction =
TRUE;
6608 propdata->symfoundreduction =
TRUE;
6635 propdata->usesymmetry = -1;
6636 propdata->triedaddsymmethods =
FALSE;
6637 propdata->nsymresacks = 0;
6638 propdata->norbitopes = 0;
6639 propdata->lastrestart = 0;
6640 propdata->symfoundreduction =
FALSE;
6679 assert( propdata->customsymopnodetypes !=
NULL );
6689 assert( propdata->orbitopalreddata !=
NULL );
6717 propdata->npermvars = 0;
6718 propdata->nbinpermvars = 0;
6719 propdata->permvars =
NULL;
6720 propdata->nperms = -1;
6721 propdata->nmaxperms = 0;
6722 propdata->perms =
NULL;
6723 propdata->permstrans =
NULL;
6724 propdata->permvarmap =
NULL;
6725 propdata->permvardomaincenter =
NULL;
6727 propdata->ncomponents = -1;
6728 propdata->ncompblocked = 0;
6729 propdata->components =
NULL;
6730 propdata->componentbegins =
NULL;
6731 propdata->vartocomponent =
NULL;
6732 propdata->componentblocked =
NULL;
6733 propdata->componenthassignedperm =
NULL;
6735 propdata->log10groupsize = -1.0;
6736 propdata->nmovedvars = -1;
6737 propdata->binvaraffected =
FALSE;
6738 propdata->computedsymmetry =
FALSE;
6739 propdata->conshdlr_nonlinear =
NULL;
6741 propdata->usesymmetry = -1;
6742 propdata->triedaddsymmethods =
FALSE;
6743 propdata->genorbconss =
NULL;
6744 propdata->genlinconss =
NULL;
6745 propdata->ngenorbconss = 0;
6746 propdata->ngenlinconss = 0;
6747 propdata->genorbconsssize = 0;
6748 propdata->genlinconsssize = 0;
6749 propdata->nsymresacks = 0;
6750 propdata->norbitopes = 0;
6751 propdata->isnonlinvar =
NULL;
6753 propdata->nmovedpermvars = -1;
6754 propdata->nmovedbinpermvars = 0;
6755 propdata->nmovedintpermvars = 0;
6756 propdata->nmovedimplintpermvars = 0;
6757 propdata->nmovedcontpermvars = 0;
6758 propdata->lastrestart = 0;
6759 propdata->symfoundreduction =
FALSE;
6761 propdata->sstconss =
NULL;
6762 propdata->nsstconss = 0;
6763 propdata->maxnsstconss = 0;
6764 propdata->leaders =
NULL;
6765 propdata->nleaders = 0;
6766 propdata->maxnleaders = 0;
6786 tabledata->propdata = propdata;
6802 "symmetry",
"display generators of symmetry group in cycle notation, if available",
6809 "propagating/" PROP_NAME "/maxgenerators",
6810 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
6814 "propagating/" PROP_NAME "/checksymmetries",
6815 "Should all symmetries be checked after computation?",
6819 "propagating/" PROP_NAME "/displaynorbitvars",
6820 "Should the number of variables affected by some symmetry be displayed?",
6824 "propagating/" PROP_NAME "/doubleequations",
6825 "Double equations to positive/negative version?",
6831 "Should the symmetry breaking constraints be added to the LP?",
6835 "propagating/" PROP_NAME "/addsymresacks",
6836 "Add inequalities for symresacks for each generator?",
6840 "propagating/" PROP_NAME "/detectdoublelex",
6841 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
6845 "propagating/" PROP_NAME "/detectorbitopes",
6846 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
6850 "propagating/" PROP_NAME "/detectsubgroups",
6851 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
6855 "propagating/" PROP_NAME "/addweaksbcs",
6856 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
6860 "propagating/" PROP_NAME "/addconsstiming",
6861 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) [disabled parameter]",
6866 "propagating/" PROP_NAME "/ofsymcomptiming",
6867 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) [disabled parameter]",
6871 "propagating/" PROP_NAME "/performpresolving",
6872 "run orbital fixing during presolving? (disabled)",
6876 "propagating/" PROP_NAME "/recomputerestart",
6877 "recompute symmetries after a restart has occurred? (0 = never)",
6881 "propagating/" PROP_NAME "/compresssymmetries",
6882 "Should non-affected variables be removed from permutation to save memory?",
6886 "propagating/" PROP_NAME "/compressthreshold",
6887 "Compression is used if percentage of moved vars is at most the threshold.",
6891 "propagating/" PROP_NAME "/usecolumnsparsity",
6892 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
6896 "propagating/" PROP_NAME "/maxnconsssubgroup",
6897 "maximum number of constraints up to which subgroup structures are detected",
6901 "propagating/" PROP_NAME "/usedynamicprop",
6902 "whether dynamified symmetry handling constraint methods should be used",
6906 "propagating/" PROP_NAME "/addstrongsbcs",
6907 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
6911 "propagating/" PROP_NAME "/ssttiebreakrule",
6912 "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)",
6916 "propagating/" PROP_NAME "/sstleaderrule",
6917 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
6921 "propagating/" PROP_NAME "/sstleadervartype",
6922 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
6923 "if multiple types are allowed, take the one with most affected vars",
6927 "propagating/" PROP_NAME "/addconflictcuts",
6928 "Should Schreier Sims constraints be added if we use a conflict based rule?",
6933 "Should Schreier Sims constraints be added?",
6937 "propagating/" PROP_NAME "/sstmixedcomponents",
6938 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
6942 "propagating/" PROP_NAME "/symfixnonbinaryvars",
6943 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
6947 "propagating/" PROP_NAME "/enforcecomputesymmetry",
6948 "Is only symmetry on binary variables used?",
6952 "propagating/" PROP_NAME "/preferlessrows",
6953 "Shall orbitopes with less rows be preferred in detection?",
6958 "Type of symmetries that shall be computed?",
6963 "timing of symmetry computation and handling (0 = before presolving, 1 = during presolving, 2 = after presolving)",
6978 assert( propdata->shadowtreeeventhdlr !=
NULL );
6981 assert( propdata->orbitopalreddata !=
NULL );
7002 SCIP_Real* log10groupsize,
7003 SCIP_Bool* binvaraffected,
7005 int** componentbegins,
7006 int** vartocomponent,
7033 *npermvars = propdata->npermvars;
7034 *permvars = propdata->permvars;
7036 if ( permvarmap !=
NULL )
7038 if ( propdata->nperms > 0 )
7042 *permvarmap = propdata->permvarmap;
7045 *nperms = propdata->nperms;
7046 if ( perms !=
NULL )
7048 *perms = propdata->perms;
7052 if ( permstrans !=
NULL )
7054 if ( propdata->nperms > 0 )
7058 *permstrans = propdata->permstrans;
7059 assert( *permstrans !=
NULL || *nperms <= 0 );
7062 if ( log10groupsize !=
NULL )
7063 *log10groupsize = propdata->log10groupsize;
7065 if ( binvaraffected !=
NULL )
7066 *binvaraffected = propdata->binvaraffected;
7070 if ( propdata->nperms > 0 )
7079 if ( componentbegins !=
NULL )
7080 *componentbegins = propdata->componentbegins;
7082 if ( vartocomponent )
7083 *vartocomponent = propdata->vartocomponent;
7086 *ncomponents = propdata->ncomponents;
7109 if ( propdata->nperms < 0 )
7112 return propdata->nperms;
7121 const char* opnodename,
7134 SCIPerrorMessage(
"Cannot create operator node type, symmetry propagator has not been included.\n");
7140 assert( propdata->customsymopnodetypes !=
NULL );
7144 SCIPerrorMessage(
"Cannot create operator node type %s, it already exists.\n", opnodename);
7149 *nodetype = propdata->nopnodetypes++;
7160 const char* opnodename,
7172 SCIPerrorMessage(
"Cannot return operator node type, symmetry propagator has not been included.\n");
7178 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 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)
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,...)
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 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_MAXNCONSSSUBGROUP
static SCIP_RETCODE ensureSymmetryMovedpermvarscountsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE tryAddOrbitalRedLexRed(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
#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 PROP_PRESOL_PRIORITY
#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
#define SCIP_DECL_DIALOGEXEC(x)
struct SCIP_DialogData SCIP_DIALOGDATA
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_SORTINDCOMP(x)
#define SCIP_DECL_PROPEXITPRE(x)
#define SCIP_DECL_PROPFREE(x)
#define SCIP_DECL_PROPEXITSOL(x)
#define SCIP_DECL_PROPEXIT(x)
#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