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;
270 SCIP_Bool triedaddsymmethods;
271 SCIP_Bool conssaddlp;
272 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;
297 SCIP_Bool symfoundreduction;
305 int sstleadervartype;
310 SCIP_Bool addconflictcuts;
311 SCIP_Bool sstaddcuts;
312 SCIP_Bool sstmixedcomponents;
321struct SCIP_ConflictData
326 int nconflictinorbit;
480 assert( propdata->nperms > 0 );
482 assert( propdata->npermvars > 0 );
485 npermvars = propdata->npermvars;
493 for (
p = 0;
p < propdata->nperms; ++
p)
496 perm = propdata->perms[
p];
531 assert( propdata->nperms > 0 );
533 assert( propdata->npermvars > 0 );
534 assert( propdata->ncomponents > 0 );
537 npermvars = propdata->npermvars;
542 for (
c = 0;
c < propdata->ncomponents; ++
c)
547 if ( propdata->componenthassignedperm[
c] )
552 comppermlen = propdata->componenthassignedperm[
c] ? 2 * npermvars : npermvars;
554 for (
p = propdata->componentbegins[
c], cnt = 0;
p < propdata->componentbegins[
c + 1]; ++
p, ++cnt)
557 perm = propdata->perms[propdata->components[
p]];
586 if ( propdata->nperms == -1 )
590 else if ( propdata->nperms == 0 )
594 else if ( propdata->ncomponents < 0 )
637 if ( tabledata->propdata->orbitopalreddata || tabledata->propdata->orbitalreddata
638 || tabledata->propdata->lexreddata )
641 if ( tabledata->propdata->orbitopalreddata )
645 " %10d cutoffs\n", nred, ncutoff);
647 if ( tabledata->propdata->orbitalreddata )
651 " %10d cutoffs\n", nred, ncutoff);
653 if ( tabledata->propdata->lexreddata )
657 " %10d cutoffs\n", nred, ncutoff);
659 if ( tabledata->propdata->shadowtreeeventhdlr )
749 if (
G1->nconsnodes <
G2->nconsnodes )
751 if (
G1->nconsnodes >
G2->nconsnodes )
755 for (
c = 0;
c <
G1->nconsnodes; ++
c)
793 if (
G1->nnodes <
G2->nnodes )
795 if (
G1->nnodes >
G2->nnodes )
798 if (
G1->nopnodes <
G2->nopnodes )
800 if (
G1->nopnodes >
G2->nopnodes )
803 if (
G1->nvalnodes <
G2->nvalnodes )
805 if (
G1->nvalnodes >
G2->nvalnodes )
808 if (
G1->nedges <
G2->nedges )
810 if (
G1->nedges >
G2->nedges )
855 assert( propdata->ngenlinconss == 0 );
856 assert( propdata->ngenorbconss == 0 );
857 assert( propdata->genorbconsssize == 0 );
858 assert( propdata->genlinconsssize == 0 );
862 assert( propdata->permvardomaincenter ==
NULL );
866 assert( propdata->npermvars == 0 );
867 assert( propdata->nbinpermvars == 0 );
868 assert( propdata->nperms == -1 || propdata->nperms == 0 );
869 assert( propdata->nmaxperms == 0 );
870 assert( propdata->nmovedpermvars == -1 );
871 assert( propdata->nmovedbinpermvars == 0 );
872 assert( propdata->nmovedintpermvars == 0 );
873 assert( propdata->nmovedimplintpermvars == 0 );
874 assert( propdata->nmovedcontpermvars == 0 );
875 assert( propdata->nmovedvars == -1 );
879 assert( propdata->componenthassignedperm ==
NULL );
883 assert( propdata->ncomponents == -1 );
884 assert( propdata->ncompblocked == 0 );
902 if ( propdata->orbitalreddata !=
NULL )
906 if ( propdata->orbitopalreddata !=
NULL )
910 if ( propdata->lexreddata !=
NULL )
933 if ( propdata->permvarmap !=
NULL )
939 for (
i = 0;
i < propdata->npermvars; ++
i)
946 if ( propdata->permstrans !=
NULL )
948 assert( propdata->nperms > 0 );
950 assert( propdata->npermvars > 0 );
951 assert( propdata->nmaxperms > 0 );
953 for (
i = 0;
i < propdata->npermvars; ++
i)
961 if ( propdata->genorbconss !=
NULL )
963 assert( propdata->ngenorbconss > 0 );
966 while ( propdata->ngenorbconss > 0 )
968 assert( propdata->genorbconss[propdata->ngenorbconss - 1] !=
NULL );
971 assert( propdata->ngenorbconss == 0 );
975 propdata->genorbconsssize = 0;
979 if ( propdata->genlinconss !=
NULL )
982 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
990 propdata->ngenlinconss = 0;
991 propdata->genlinconsssize = 0;
994 if ( propdata->sstconss !=
NULL )
996 assert( propdata->nsstconss > 0 );
999 for (
i = 0;
i < propdata->nsstconss; ++
i)
1007 propdata->sstconss =
NULL;
1008 propdata->nsstconss = 0;
1009 propdata->maxnsstconss = 0;
1012 if ( propdata->leaders !=
NULL )
1014 assert( propdata->maxnleaders > 0 );
1017 propdata->maxnleaders = 0;
1018 propdata->leaders =
NULL;
1019 propdata->nleaders = 0;
1023 if ( propdata->ncomponents > 0 )
1025 assert( propdata->componentblocked !=
NULL );
1036 propdata->ncomponents = -1;
1037 propdata->ncompblocked = 0;
1041 if ( propdata->nperms > 0 )
1048 permlen = 2 * propdata->npermvars;
1050 permlen = propdata->npermvars;
1055 if ( propdata->perms !=
NULL )
1057 for (
i = 0;
i < propdata->nperms; ++
i)
1066 propdata->npermvars = 0;
1067 propdata->nbinpermvars = 0;
1068 propdata->nperms = -1;
1069 propdata->nmaxperms = 0;
1070 propdata->nmovedpermvars = -1;
1071 propdata->nmovedbinpermvars = 0;
1072 propdata->nmovedintpermvars = 0;
1073 propdata->nmovedimplintpermvars = 0;
1074 propdata->nmovedcontpermvars = 0;
1075 propdata->nmovedvars = -1;
1076 propdata->log10groupsize = -1.0;
1077 propdata->binvaraffected =
FALSE;
1078 propdata->isnonlinvar =
NULL;
1080 propdata->nperms = -1;
1084 propdata->computedsymmetry =
FALSE;
1085 propdata->compressed =
FALSE;
1143 SCIP_Real** permvardomaincenter,
1147 SCIP_Bool* binvaraffected,
1149 SCIP_Real compressthreshold,
1150 SCIP_Bool* compressed
1175 *binvaraffected =
FALSE;
1176 *compressed =
FALSE;
1197 for (
p = 0;
p < nperms; ++
p)
1199 if ( perms[
p][
i] !=
i )
1212 *binvaraffected =
TRUE;
1219 for (
p = 0;
p < nperms; ++
p)
1222 for (
i = 0;
i < *nmovedvars; ++
i)
1234 assert( 0 <= perms[
p][
i] && perms[
p][
i] < 2 * (*nmovedvars) );
1252 for (
i = 0;
i < *nmovedvars; ++
i)
1256 *npermvars = *nmovedvars;
1270 for (
p = 0;
p < nperms && ! *binvaraffected; ++
p)
1272 if ( perms[
p][
i] !=
i )
1275 *binvaraffected =
TRUE;
1284 for (
i = 0;
i < *npermvars; ++
i)
1289 (*permvardomaincenter)[
i] = 0.5 * (ub + lb);
1330 for (
c = 0;
c < nconshdlrs; ++
c)
1332 conshdlr = conshdlrs[
c];
1345 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n"
1346 " If symmetries shall be detected, implement the %s callback.\n",
1361 SCIP_Bool found =
FALSE;
1388 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n"
1425 *nconsnodes = nconss;
1430 for (
c = 0;
c < nconss; ++
c)
1478 *nopnodes += num - 1;
1487 if (
nvars <= 100000 )
1488 *nedges = 100 *
nvars;
1489 else if (
nvars <= 1000000 )
1490 *nedges = 32 *
nvars;
1491 else if (
nvars <= 16700000 )
1492 *nedges = 16 *
nvars;
1522#ifdef SCIP_DISPLAY_SYM_CHECK
1539 assert( nsymvars == npermvars );
1543 for (
c = 0;
c < nconss; ++
c)
1565 for (
c = 0;
c < nconss; ++
c)
1573 for (
c = 1;
c < nconss; ++
c)
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
1616#ifdef SCIP_DISPLAY_SYM_CHECK
1627#ifdef SCIP_DISPLAY_SYM_CHECK
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,
1735 *binvaraffected =
FALSE;
1736 *compressed =
FALSE;
1737 *log10groupsize = 0;
1763 nopnodes, nvalnodes, nconsnodes, nedges) );
1803 if ( checksymmetries && *nperms > 0 )
1818 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1819 compresssymmetries, compressthreshold, compressed) );
1843 for (v = 0; v <
nvars; ++v)
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 )
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");
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",
2234 maxgenerators = propdata->maxgenerators;
2239 propdata->compresssymmetries, propdata->compressthreshold,
2241 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2242 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2243 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
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)
2382 for (
j = 0;
j < npermvars; ++
j)
2433 SCIP_Bool infeasible =
FALSE;
2469 SCIP_Bool infeasible =
FALSE;
2520 int* componentbegins;
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;
2563 if ( propdata->preferlessrows )
2567 --(*ntwocycleperms);
2569 else if ( ! propdata->preferlessrows )
2610 int* componentbegins;
2634 assert( propdata->computedsymmetry );
2635 assert( propdata->nperms > 0 );
2637 assert( propdata->npermvars > 0 );
2638 assert( propdata->ncomponents > 0 );
2643 perms = propdata->perms;
2644 npermvars = propdata->npermvars;
2646 componentbegins = propdata->componentbegins;
2655 for (
k = 0;
k < npermvars; ++
k)
2668 for (
k = 0;
k < npermvars; ++
k)
2718 if (
k < npermvars )
2741 for (
k = 0;
k < npermvars; ++
k)
2789 for (
j = 0;
j < npermvars; ++
j)
2798 (*graphcomponents)[
j] =
j;
2811 (*graphcompbegins)[0] = 0;
2812 (*compcolorbegins)[0] = 0;
2815 for (
j = 1;
j < npermvars; ++
j)
2820 idx1 = (*graphcomponents)[
j];
2821 idx2 = (*graphcomponents)[
j-1];
2842 (*graphcompbegins)[
nextcomp] = npermvars;
2871 SCIP_Bool mayinteract,
2883 SCIP_Bool infeasible =
FALSE;
2910 for (
k = 0;
k < nrows; ++
k)
2917 for (
k = 0;
k < ncols; ++
k)
2936 for (
l = 0;
l < ncols; ++
l)
2971 for (
k = nrows - 1;
k >= 0; --
k)
3019 for (
l = 0;
l < ncols; ++
l)
3033 for (
k = 0;
k < nrows; ++
k)
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)
3127 SCIP_Real vals[2] = {1, -1};
3143#ifdef SCIP_MORE_DEBUG
3150 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3151 propdata->genlinconss[propdata->ngenlinconss] = cons;
3152 ++propdata->ngenlinconss;
3180 SCIP_Real vals[2] = {1, -1};
3183 int orbitsize[2] = {1, 1};
3277 propdata->permstrans, propdata->components, propdata->componentbegins,
3307 *naddedconss = orbitsize[
activeorb] - 1;
3325#ifdef SCIP_MORE_DEBUG
3332 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3333 propdata->genlinconss[propdata->ngenlinconss] = cons;
3334 ++propdata->ngenlinconss;
3351 (*lexorder)[(*nvarsorder)++] =
varidx;
3436 for (
i = 0;
i < npermvars; ++
i)
3441 for (
i = 0;
i < npermvars; ++
i)
3446 for (
l = 0;
l < nleaders; ++
l)
3463 for (
i = 0;
i < npermvars; ++
i)
3467 for (
p = 0;
p < nperms; ++
p)
3469 for (
i = 0;
i < npermvars; ++
i)
3608 assert( propdata->computedsymmetry );
3609 assert( propdata->nperms >= 0 );
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 )
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];
3732 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
3742 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
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;
3903 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3916 if ( ! propdata->componentblocked[
cidx] )
3919 ++propdata->ncompblocked;
3935 if( propdata->addweaksbcs )
3944 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3955 if ( ! propdata->componentblocked[
cidx] )
3958 ++propdata->ncompblocked;
3970 if ( propdata->addweaksbcs )
3999 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
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);
4077 for (
p = propdata->nperms - 1;
p >= 0; --
p)
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)
4160 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4169 for (
j =
i + 1;
j < orbitbegins[
r + 1]; ++
j)
4242 if ( ncliques == 0 )
4244 SCIPdebugMsg(
scip,
"No cliques present --> construction of conflict structure aborted.\n");
4253 (*varconflicts)[
i].ncliques = 0;
4254 (*varconflicts)[
i].active =
TRUE;
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];
4296 (*varconflicts)[node].active =
TRUE;
4297 (*varconflicts)[node].ncliques++;
4314 for (
c = 0;
c < ncliques; ++
c)
4316 clique = cliques[
c];
4343 (*varconflicts)[node].cliques[
tmpncliques[node]++] = clique;
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;
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;
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)
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)
4562 SCIP_Bool addcuts =
FALSE;
4579 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4582 if ( propdata->sstaddcuts )
4586 addcuts = propdata->addconflictcuts;
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 );
4624 propdata->leaders[propdata->nleaders++] = orbits[
posleader];
4626 for (
i = 0,
poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++
poscur)
4636 for (
j = 0;
j < propdata->nleaders - 1; ++
j)
4672 propdata->sstconss[propdata->nsstconss++] = cons;
4682 propdata->sstconss[propdata->nsstconss++] = cons;
4745 for (
i = 0;
i < norbits; ++
i)
4765 cnt = orbitbegins[
i];
4777 cnt = orbitbegins[
i + 1] - 1;
4805 *
leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
4823 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4829 for (
i = 0;
i < orbitsize; ++
i)
4836 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4849 ++(*norbitvarinconflict);
4898 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4904 for (
i = 0;
i < orbitsize; ++
i)
4911 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4923 ++(*norbitvarinconflict);
4949 int nmovedbinpermvars;
4950 int nmovedintpermvars;
4951 int nmovedimplintpermvars;
4952 int nmovedcontpermvars;
4959 int* componentbegins;
4960 int* vartocomponent;
4962 unsigned* componentblocked;
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 );
5020 if ( componentblocked[
cidx] )
5024 if ( propdata->componenthassignedperm[
cidx] )
5034 nmovedpermvars = propdata->nmovedpermvars;
5035 nmovedbinpermvars = propdata->nmovedbinpermvars;
5036 nmovedintpermvars = propdata->nmovedintpermvars;
5037 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5038 nmovedcontpermvars = propdata->nmovedcontpermvars;
5039 assert( nmovedpermvars > 0 );
5074 for (
p = componentbegins[
cidx];
p < componentbegins[
cidx + 1]; ++
p)
5076 perm = propdata->perms[
p];
5077 for (
i = 0;
i < propdata->npermvars; ++
i)
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)
5139 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5140 componentblocked, ncomponents, nmovedpermvars) );
5145 for (
p = 0;
p < norbits; ++
p)
5184 assert( 0 <= orbitidx && orbitidx < norbits );
5194 if ( nchgbds !=
NULL )
5199 for (
p = 0;
p < nperms; ++
p)
5257 assert( propdata->usedynamicprop );
5275 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5276 for (
i = 0;
i < ncols - 1; ++
i)
5288 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5296 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5301 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5312 for (
i = 0;
i < nrows; ++
i)
5315 for (
j = 0;
j < ncols; ++
j)
5337 for (
i = 0;
i < nrows; ++
i)
5356 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5360 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5374 nelem = nrows * ncols;
5376 for (
i = 0;
i < nrows; ++
i)
5378 for (
j = 0;
j < ncols; ++
j)
5396 for (
i = nrows - 1;
i >= 0; --
i)
5524 for (
i = 0;
i < propdata->npermvars; ++
i)
5588 for (
i = 0;
i < propdata->npermvars; ++
i)
5605 row[0] = propdata->permvars[
i];
5606 row[1] = propdata->permvars[
j];
5607 assert( row[0] != row[1] );
5618 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5622 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5680 && propdata->usedynamicprop
5681 && propdata->addsymresacks
5683 assert( propdata->nperms > 0 );
5685 assert( propdata->componentblocked !=
NULL );
5688 if ( propdata->componentblocked[
cidx] )
5697 assert( propdata->nmovedpermvars );
5703 componentperms[
p] = propdata->perms[propdata->components[propdata->componentbegins[
cidx] +
p]];
5712 checkpporbisack =
SCIPgetParam(
scip,
"constraints/orbisack/checkpporbisack");
5751 if ( propdata->componentblocked[
cidx] )
5752 ++propdata->ncompblocked;
5774 if ( propdata->orbitopalreddata )
5778 if ( propdata->orbitalreddata )
5782 if ( propdata->lexreddata )
5786 if ( propdata->ncomponents >= 0 )
5794 for (
i = 0;
i < propdata->ncomponents; ++
i)
5796 if ( propdata->componentblocked[
i] )
5830 if ( propdata->usedynamicprop )
5835 else if ( propdata->binvaraffected )
5847 for (
i = 0;
i < nrows; ++
i)
5854 for (
j = 0;
j < ncols; ++
j)
5872 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5873 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5874 ++propdata->norbitopes;
5944 for (
i = 0;
i < nrows; ++
i)
5965 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5974 for (
i = 0;
i < ncols; ++
i)
5995 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
6037 if ( propdata->componentblocked[
cidx] )
6041 if ( propdata->componenthassignedperm[
cidx] )
6049 compsize = propdata->componentbegins[
cidx + 1] - propdata->componentbegins[
cidx];
6051 for (
p = 0,
i = propdata->componentbegins[
cidx];
i < propdata->componentbegins[
cidx + 1]; ++
i)
6052 perms[
p++] = propdata->perms[propdata->components[
i]];
6078 for (
p = 0;
p < ncols; ++
p)
6098 for (
i = nrows - 1;
i >= 0; --
i)
6116 ++(propdata->ncompblocked);
6135 if ( propdata->componentblocked[
cidx] )
6139 if ( propdata->componenthassignedperm[
cidx] )
6143 if ( !propdata->usedynamicprop &&
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
6144 && propdata->binvaraffected && propdata->ncompblocked < propdata->ncomponents )
6188 assert( propdata->ncomponents >= 0 );
6192 if ( propdata->componentblocked[
cidx] )
6197 || (
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
6200 if ( propdata->detectdoublelex || propdata->detectorbitopes )
6229 SCIP_Bool* earlyterm
6238 if ( nchgbds !=
NULL )
6240 if ( earlyterm !=
NULL )
6246 if ( earlyterm !=
NULL )
6253 assert( propdata->usesymmetry >= 0 );
6256 if ( propdata->usesymmetry == 0 )
6258 if ( earlyterm !=
NULL )
6264 if ( propdata->triedaddsymmethods )
6266 assert( propdata->nperms >= 0 );
6268 if ( earlyterm !=
NULL )
6273 assert( !propdata->triedaddsymmethods );
6276 if ( !propdata->computedsymmetry )
6284 if ( !propdata->computedsymmetry )
6288 propdata->triedaddsymmethods =
TRUE;
6289 assert( propdata->nperms >= 0 );
6292 if ( propdata->nperms == 0 )
6297 assert( propdata->ncomponents > 0 );
6300 for (
c = 0;
c < propdata->ncomponents; ++
c)
6308#ifdef SYMMETRY_STATISTICS
6321 SCIP_Bool* infeasible,
6335 *infeasible =
FALSE;
6380 if ( propdata->usesymmetry < 0 )
6384 assert( propdata->usesymmetry >= 0 );
6387 if ( propdata->usesymmetry == 0 )
6391 if ( propdata->addconsstiming == 0 )
6393 SCIPdebugMsg(
scip,
"Try to add symmetry handling constraints before presolving.\n");
6397 else if ( propdata->symcomptiming == 0 )
6422 assert( propdata->usesymmetry >= 0 );
6425 if ( propdata->usesymmetry == 0 )
6477 SCIP_Bool earlyterm;
6488 assert( propdata->usesymmetry >= 0 );
6491 if ( propdata->usesymmetry == 0 )
6505 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
6521 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
6524 assert( propdata->nperms > 0 );
6525 assert( propdata->triedaddsymmethods );
6530 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss -
noldngenconns;
6531 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
6534 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
6538 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6548 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
6552 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6562 propdata->ngenorbconss + propdata->ngenlinconss);
6564 for (
i = 0;
i < propdata->nsstconss; ++
i)
6568 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6577 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
6590 SCIP_Bool infeasible;
6608 if ( propdata->usesymmetry < 0 )
6616 propdata->symfoundreduction =
TRUE;
6623 propdata->symfoundreduction =
TRUE;
6650 propdata->usesymmetry = -1;
6651 propdata->triedaddsymmethods =
FALSE;
6652 propdata->nsymresacks = 0;
6653 propdata->norbitopes = 0;
6654 propdata->lastrestart = 0;
6655 propdata->symfoundreduction =
FALSE;
6694 assert( propdata->customsymopnodetypes !=
NULL );
6704 assert( propdata->orbitopalreddata !=
NULL );
6732 propdata->npermvars = 0;
6733 propdata->nbinpermvars = 0;
6734 propdata->permvars =
NULL;
6735 propdata->nperms = -1;
6736 propdata->nmaxperms = 0;
6737 propdata->perms =
NULL;
6738 propdata->permstrans =
NULL;
6739 propdata->permvarmap =
NULL;
6740 propdata->permvardomaincenter =
NULL;
6742 propdata->ncomponents = -1;
6743 propdata->ncompblocked = 0;
6744 propdata->components =
NULL;
6745 propdata->componentbegins =
NULL;
6746 propdata->vartocomponent =
NULL;
6747 propdata->componentblocked =
NULL;
6748 propdata->componenthassignedperm =
NULL;
6750 propdata->log10groupsize = -1.0;
6751 propdata->nmovedvars = -1;
6752 propdata->binvaraffected =
FALSE;
6753 propdata->computedsymmetry =
FALSE;
6754 propdata->conshdlr_nonlinear =
NULL;
6756 propdata->usesymmetry = -1;
6757 propdata->triedaddsymmethods =
FALSE;
6758 propdata->genorbconss =
NULL;
6759 propdata->genlinconss =
NULL;
6760 propdata->ngenorbconss = 0;
6761 propdata->ngenlinconss = 0;
6762 propdata->genorbconsssize = 0;
6763 propdata->genlinconsssize = 0;
6764 propdata->nsymresacks = 0;
6765 propdata->norbitopes = 0;
6766 propdata->isnonlinvar =
NULL;
6768 propdata->nmovedpermvars = -1;
6769 propdata->nmovedbinpermvars = 0;
6770 propdata->nmovedintpermvars = 0;
6771 propdata->nmovedimplintpermvars = 0;
6772 propdata->nmovedcontpermvars = 0;
6773 propdata->lastrestart = 0;
6774 propdata->symfoundreduction =
FALSE;
6776 propdata->sstconss =
NULL;
6777 propdata->nsstconss = 0;
6778 propdata->maxnsstconss = 0;
6779 propdata->leaders =
NULL;
6780 propdata->nleaders = 0;
6781 propdata->maxnleaders = 0;
6801 tabledata->propdata = propdata;
6817 "symmetry",
"display generators of symmetry group in cycle notation, if available",
6824 "propagating/" PROP_NAME "/maxgenerators",
6825 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
6829 "propagating/" PROP_NAME "/checksymmetries",
6830 "Should all symmetries be checked after computation?",
6834 "propagating/" PROP_NAME "/displaynorbitvars",
6835 "Should the number of variables affected by some symmetry be displayed?",
6839 "propagating/" PROP_NAME "/doubleequations",
6840 "Double equations to positive/negative version?",
6846 "Should the symmetry breaking constraints be added to the LP?",
6850 "propagating/" PROP_NAME "/addsymresacks",
6851 "Add inequalities for symresacks for each generator?",
6855 "propagating/" PROP_NAME "/detectdoublelex",
6856 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
6860 "propagating/" PROP_NAME "/detectorbitopes",
6861 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
6865 "propagating/" PROP_NAME "/detectsubgroups",
6866 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
6870 "propagating/" PROP_NAME "/addweaksbcs",
6871 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
6875 "propagating/" PROP_NAME "/addconsstiming",
6876 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
6881 "propagating/" PROP_NAME "/ofsymcomptiming",
6882 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call)",
6886 "propagating/" PROP_NAME "/performpresolving",
6887 "run orbital fixing during presolving? (disabled)",
6891 "propagating/" PROP_NAME "/recomputerestart",
6892 "recompute symmetries after a restart has occurred? (0 = never)",
6896 "propagating/" PROP_NAME "/compresssymmetries",
6897 "Should non-affected variables be removed from permutation to save memory?",
6901 "propagating/" PROP_NAME "/compressthreshold",
6902 "Compression is used if percentage of moved vars is at most the threshold.",
6906 "propagating/" PROP_NAME "/usecolumnsparsity",
6907 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
6911 "propagating/" PROP_NAME "/maxnconsssubgroup",
6912 "maximum number of constraints up to which subgroup structures are detected",
6916 "propagating/" PROP_NAME "/usedynamicprop",
6917 "whether dynamified symmetry handling constraint methods should be used",
6921 "propagating/" PROP_NAME "/addstrongsbcs",
6922 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
6926 "propagating/" PROP_NAME "/ssttiebreakrule",
6927 "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)",
6931 "propagating/" PROP_NAME "/sstleaderrule",
6932 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
6936 "propagating/" PROP_NAME "/sstleadervartype",
6937 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
6938 "if multiple types are allowed, take the one with most affected vars",
6942 "propagating/" PROP_NAME "/addconflictcuts",
6943 "Should Schreier Sims constraints be added if we use a conflict based rule?",
6948 "Should Schreier Sims constraints be added?",
6952 "propagating/" PROP_NAME "/sstmixedcomponents",
6953 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
6957 "propagating/" PROP_NAME "/symfixnonbinaryvars",
6958 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
6962 "propagating/" PROP_NAME "/enforcecomputesymmetry",
6963 "Is only symmetry on binary variables used?",
6967 "propagating/" PROP_NAME "/preferlessrows",
6968 "Shall orbitopes with less rows be preferred in detection?",
6973 "Type of symmetries that shall be computed?",
6988 assert( propdata->shadowtreeeventhdlr !=
NULL );
6991 assert( propdata->orbitopalreddata !=
NULL );
7012 SCIP_Real* log10groupsize,
7013 SCIP_Bool* binvaraffected,
7015 int** componentbegins,
7016 int** vartocomponent,
7043 *npermvars = propdata->npermvars;
7044 *permvars = propdata->permvars;
7046 if ( permvarmap !=
NULL )
7048 if ( propdata->nperms > 0 )
7052 *permvarmap = propdata->permvarmap;
7055 *nperms = propdata->nperms;
7056 if ( perms !=
NULL )
7058 *perms = propdata->perms;
7062 if ( permstrans !=
NULL )
7064 if ( propdata->nperms > 0 )
7068 *permstrans = propdata->permstrans;
7069 assert( *permstrans !=
NULL || *nperms <= 0 );
7072 if ( log10groupsize !=
NULL )
7073 *log10groupsize = propdata->log10groupsize;
7075 if ( binvaraffected !=
NULL )
7076 *binvaraffected = propdata->binvaraffected;
7080 if ( propdata->nperms > 0 )
7089 if ( componentbegins !=
NULL )
7090 *componentbegins = propdata->componentbegins;
7092 if ( vartocomponent )
7093 *vartocomponent = propdata->vartocomponent;
7096 *ncomponents = propdata->ncomponents;
7119 if ( propdata->nperms < 0 )
7122 return propdata->nperms;
7144 SCIPerrorMessage(
"Cannot create operator node type, symmetry propagator has not been included.\n");
7150 assert( propdata->customsymopnodetypes !=
NULL );
7159 *nodetype = propdata->nopnodetypes++;
7182 SCIPerrorMessage(
"Cannot return operator node type, symmetry propagator has not been included.\n");
7188 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)
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
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
#define SYM_COMPUTETIMING_DURINGPRESOL
@ SCIP_ORBITOPETYPE_PACKING
enum SYM_Symtype SYM_SYMTYPE
@ SCIP_LEADERRULE_LASTINORBIT
@ SCIP_LEADERRULE_MAXCONFLICTSINORBIT
@ SCIP_LEADERRULE_FIRSTINORBIT
@ SCIP_LEADERTIEBREAKRULE_MAXORBIT
@ SCIP_LEADERTIEBREAKRULE_MINORBIT
@ SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT
#define SYM_HANDLETYPE_SYMBREAK
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
#define SYM_COMPUTETIMING_AFTERPRESOL
#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