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;
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];
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]];
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 )
748 if (
G1->nconsnodes <
G2->nconsnodes )
750 if (
G1->nconsnodes >
G2->nconsnodes )
754 for (
c = 0;
c <
G1->nconsnodes; ++
c)
792 if (
G1->nnodes <
G2->nnodes )
794 if (
G1->nnodes >
G2->nnodes )
797 if (
G1->nopnodes <
G2->nopnodes )
799 if (
G1->nopnodes >
G2->nopnodes )
802 if (
G1->nvalnodes <
G2->nvalnodes )
804 if (
G1->nvalnodes >
G2->nvalnodes )
807 if (
G1->nedges <
G2->nedges )
809 if (
G1->nedges >
G2->nedges )
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;
1142 SCIP_Real** permvardomaincenter,
1146 SCIP_Bool* binvaraffected,
1148 SCIP_Real compressthreshold,
1149 SCIP_Bool* compressed
1174 *binvaraffected =
FALSE;
1175 *compressed =
FALSE;
1196 for (
p = 0;
p < nperms; ++
p)
1198 if ( perms[
p][
i] !=
i )
1211 *binvaraffected =
TRUE;
1218 for (
p = 0;
p < nperms; ++
p)
1221 for (
i = 0;
i < *nmovedvars; ++
i)
1233 assert( 0 <= perms[
p][
i] && perms[
p][
i] < 2 * (*nmovedvars) );
1251 for (
i = 0;
i < *nmovedvars; ++
i)
1255 *npermvars = *nmovedvars;
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)
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;
1521#ifdef SCIP_DISPLAY_SYM_CHECK
1538 assert( nsymvars == npermvars );
1542 for (
c = 0;
c < nconss; ++
c)
1564 for (
c = 0;
c < nconss; ++
c)
1572 for (
c = 1;
c < nconss; ++
c)
1580 for (
c = 0;
c < nconss; ++
c)
1585#ifdef SCIP_DISPLAY_SYM_CHECK
1591 for (
p = 0;
p < nperms; ++
p)
1594 SCIP_Bool found =
TRUE;
1596#ifdef SCIP_DISPLAY_SYM_CHECK
1615#ifdef SCIP_DISPLAY_SYM_CHECK
1626#ifdef SCIP_DISPLAY_SYM_CHECK
1639#ifdef SCIP_DISPLAY_SYM_CHECK
1650#ifdef SCIP_DISPLAY_SYM_CHECK
1660#ifdef SCIP_DISPLAY_SYM_CHECK
1667 for (
c = nconss - 1;
c >= 0; --
c)
1681 SCIP_Bool compresssymmetries,
1682 SCIP_Real compressthreshold,
1685 SCIP_Bool checksymmetries,
1689 SCIP_Real** permvardomaincenter,
1696 SCIP_Bool* binvaraffected,
1697 SCIP_Bool* compressed,
1698 SCIP_Real* log10groupsize,
1734 *binvaraffected =
FALSE;
1735 *compressed =
FALSE;
1736 *log10groupsize = 0;
1762 nopnodes, nvalnodes, nconsnodes, nedges) );
1802 if ( checksymmetries && *nperms > 0 )
1817 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1818 compresssymmetries, compressthreshold, compressed) );
1842 for (v = 0; v <
nvars; ++v)
1872 int* componentbegins;
1879 assert( propdata->ncomponents > 0 );
1884 componentbegins = propdata->componentbegins;
1885 ncomponents = propdata->ncomponents;
1894 for (
c = 0;
c < ncomponents; ++
c)
1896 for (
i = componentbegins[
c];
i < componentbegins[
c + 1]; ++
i)
1900 propdata->componenthassignedperm[
c] =
TRUE;
1920 assert( propdata->nperms >= 0 );
1923 if ( propdata->ncomponents >= 0 )
1927 assert( propdata->ncomponents == -1 );
1932#ifdef SCIP_OUTPUT_COMPONENT
1937 propdata->permvars, propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
1938 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
1940#ifdef SCIP_OUTPUT_COMPONENT
1946 assert( propdata->ncomponents > 0 );
1950 assert( propdata->componenthassignedperm !=
NULL );
1969 assert( propdata->nperms >= 0 );
1972 if ( propdata->permvarmap !=
NULL )
1979 for (v = 0; v < propdata->npermvars; ++v)
2002 assert( propdata->nperms >= 0 );
2005 if ( propdata->permstrans !=
NULL )
2011 for (v = 0; v < propdata->npermvars; ++v)
2014 for (
p = 0;
p < propdata->nperms; ++
p)
2015 propdata->permstrans[v][
p] = propdata->perms[
p][v];
2036 assert( propdata->nperms >= 0 );
2039 if ( propdata->nmovedpermvars >= 0 )
2041 assert( propdata->nmovedpermvars == -1 );
2043 propdata->nmovedpermvars = 0;
2044 propdata->nmovedbinpermvars = 0;
2045 propdata->nmovedintpermvars = 0;
2046 propdata->nmovedimplintpermvars = 0;
2047 propdata->nmovedcontpermvars = 0;
2049 for (
p = 0;
p < propdata->nperms; ++
p)
2051 for (v = 0; v < propdata->npermvars; ++v)
2053 if ( propdata->perms[
p][v] != v )
2055 ++propdata->nmovedpermvars;
2060 ++propdata->nmovedbinpermvars;
2063 ++propdata->nmovedintpermvars;
2066 ++propdata->nmovedimplintpermvars;
2069 ++propdata->nmovedcontpermvars;
2091 if ( propdata->enforcecomputesymmetry )
2144 unsigned int type = 0;
2150 assert( propdata->usesymmetry >= 0 );
2164 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2195 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2208 if ( propdata->computedsymmetry )
2211 assert( propdata->npermvars == 0 );
2213 assert( propdata->nperms < 0 );
2214 assert( propdata->nmaxperms == 0 );
2219 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2233 maxgenerators = propdata->maxgenerators;
2238 propdata->compresssymmetries, propdata->compressthreshold,
2240 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2241 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2242 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2246 propdata->computedsymmetry =
TRUE;
2261 if ( propdata->nperms == 0 )
2268 assert( propdata->nperms > 0 );
2269 assert( propdata->npermvars > 0 );
2276 if ( maxgenerators == 0 )
2284 if ( propdata->displaynorbitvars )
2286 if ( propdata->nmovedvars == -1 )
2289 propdata->npermvars, &(propdata->nmovedvars)) );
2296 for (
i = 0;
i < propdata->npermvars; ++
i)
2381 for (
j = 0;
j < npermvars; ++
j)
2432 SCIP_Bool infeasible =
FALSE;
2468 SCIP_Bool infeasible =
FALSE;
2519 int* componentbegins;
2532 assert( propdata->computedsymmetry );
2533 assert( propdata->nperms > 0 );
2535 assert( propdata->npermvars > 0 );
2536 assert( propdata->ncomponents > 0 );
2540 perms = propdata->perms;
2541 npermvars = propdata->npermvars;
2543 componentbegins = propdata->componentbegins;
2562 if ( propdata->preferlessrows )
2566 --(*ntwocycleperms);
2568 else if ( ! propdata->preferlessrows )
2609 int* componentbegins;
2633 assert( propdata->computedsymmetry );
2634 assert( propdata->nperms > 0 );
2636 assert( propdata->npermvars > 0 );
2637 assert( propdata->ncomponents > 0 );
2642 perms = propdata->perms;
2643 npermvars = propdata->npermvars;
2645 componentbegins = propdata->componentbegins;
2654 for (
k = 0;
k < npermvars; ++
k)
2667 for (
k = 0;
k < npermvars; ++
k)
2717 if (
k < npermvars )
2740 for (
k = 0;
k < npermvars; ++
k)
2788 for (
j = 0;
j < npermvars; ++
j)
2797 (*graphcomponents)[
j] =
j;
2810 (*graphcompbegins)[0] = 0;
2811 (*compcolorbegins)[0] = 0;
2814 for (
j = 1;
j < npermvars; ++
j)
2819 idx1 = (*graphcomponents)[
j];
2820 idx2 = (*graphcomponents)[
j-1];
2841 (*graphcompbegins)[
nextcomp] = npermvars;
2870 SCIP_Bool mayinteract,
2882 SCIP_Bool infeasible =
FALSE;
2909 for (
k = 0;
k < nrows; ++
k)
2916 for (
k = 0;
k < ncols; ++
k)
2935 for (
l = 0;
l < ncols; ++
l)
2970 for (
k = nrows - 1;
k >= 0; --
k)
3018 for (
l = 0;
l < ncols; ++
l)
3032 for (
k = 0;
k < nrows; ++
k)
3056 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3057 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3058 ++propdata->norbitopes;
3060 for (
k = nrows - 1;
k >= 0; --
k)
3065 for (
k = nrows - 1;
k >= 0; --
k)
3126 SCIP_Real vals[2] = {1, -1};
3142#ifdef SCIP_MORE_DEBUG
3149 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3150 propdata->genlinconss[propdata->ngenlinconss] = cons;
3151 ++propdata->ngenlinconss;
3179 SCIP_Real vals[2] = {1, -1};
3182 int orbitsize[2] = {1, 1};
3276 propdata->permstrans, propdata->components, propdata->componentbegins,
3306 *naddedconss = orbitsize[
activeorb] - 1;
3324#ifdef SCIP_MORE_DEBUG
3331 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3332 propdata->genlinconss[propdata->ngenlinconss] = cons;
3333 ++propdata->ngenlinconss;
3350 (*lexorder)[(*nvarsorder)++] =
varidx;
3435 for (
i = 0;
i < npermvars; ++
i)
3440 for (
i = 0;
i < npermvars; ++
i)
3445 for (
l = 0;
l < nleaders; ++
l)
3462 for (
i = 0;
i < npermvars; ++
i)
3466 for (
p = 0;
p < nperms; ++
p)
3468 for (
i = 0;
i < npermvars; ++
i)
3607 assert( propdata->computedsymmetry );
3608 assert( propdata->nperms >= 0 );
3614 if ( propdata->nperms == 0 || propdata->componentblocked[
cidx] )
3621 assert( propdata->nperms > 0 );
3623 assert( propdata->npermvars > 0 );
3631 for (
p = 0;
p < propdata->nperms; ++
p)
3638 for (
p = 0;
p < propdata->npermvars; ++
p)
3640 if ( propdata->vartocomponent[
p] >= 0 )
3659#ifdef SCIP_MORE_DEBUG
3666 for (
p = propdata->componentbegins[
cidx];
p < propdata->componentbegins[
cidx+1]; ++
p)
3668 perm = propdata->components[
p];
3670 for (
k = 0;
k < propdata->npermvars; ++
k)
3675 for (
k = 0;
k < propdata->npermvars; ++
k)
3680 j = propdata->perms[perm][
k];
3692 j = propdata->perms[perm][
j];
3731 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
3741 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3773 propdata->perms[propdata->components[propdata->componentbegins[
cidx] +
k]],
3774 propdata->permvars, propdata->npermvars,
FALSE,
3780 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3781 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3782 ++propdata->nsymresacks;
3784 if ( ! propdata->componentblocked[
cidx] )
3787 ++propdata->ncompblocked;
3902 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3915 if ( ! propdata->componentblocked[
cidx] )
3918 ++propdata->ncompblocked;
3934 if( propdata->addweaksbcs )
3943 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3954 if ( ! propdata->componentblocked[
cidx] )
3957 ++propdata->ncompblocked;
3969 if ( propdata->addweaksbcs )
3998 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4041 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4042 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4043 ++propdata->nsymresacks;
4045 if ( ! propdata->componentblocked[
cidx] )
4048 ++propdata->ncompblocked;
4051 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n",
k,
cidx);
4067 SCIPdebugMsg(
scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4076 for (
p = propdata->nperms - 1;
p >= 0; --
p)
4129 for (
r = 0;
r < norbits; ++
r)
4134 orbitsize = orbitbegins[
r + 1] - orbitbegins[
r];
4135 assert( orbitsize >= 0 );
4137 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4159 for (
i = orbitbegins[
r];
i < orbitbegins[
r + 1]; ++
i)
4168 for (
j =
i + 1;
j < orbitbegins[
r + 1]; ++
j)
4241 if ( ncliques == 0 )
4243 SCIPdebugMsg(
scip,
"No cliques present --> construction of conflict structure aborted.\n");
4252 (*varconflicts)[
i].ncliques = 0;
4253 (*varconflicts)[
i].active =
TRUE;
4256 (*varconflicts)[
i].cliques =
NULL;
4257 (*varconflicts)[
i].orbitidx = -1;
4258 (*varconflicts)[
i].nconflictinorbit = 0;
4259 (*varconflicts)[
i].orbitsize = -1;
4260 (*varconflicts)[
i].posinorbit = -1;
4270 for (
c = 0;
c < ncliques; ++
c)
4272 clique = cliques[
c];
4295 (*varconflicts)[node].active =
TRUE;
4296 (*varconflicts)[node].ncliques++;
4313 for (
c = 0;
c < ncliques; ++
c)
4315 clique = cliques[
c];
4342 (*varconflicts)[node].cliques[
tmpncliques[node]++] = clique;
4366 SCIPdebugMsg(
scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4391 n = (*varconflicts)[
i].ncliques;
4409 int* componentbegins;
4411 SCIP_Bool conssaddlp;
4423 assert( propdata->npermvars >= 0 );
4424 assert( propdata->nbinpermvars >= 0 );
4427 if ( propdata->nbinpermvars == 0 )
4429 assert( propdata->binvaraffected == 0 );
4433 perms = propdata->perms;
4434 nperms = propdata->nperms;
4435 permvars = propdata->permvars;
4436 npermvars = propdata->npermvars;
4437 conssaddlp = propdata->conssaddlp;
4439 componentbegins = propdata->componentbegins;
4461 if ( propdata->componenthassignedperm[
cidx] )
4465 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4468 for (
p = 0;
p < nperms; ++
p)
4474 for (
i = 0;
i < npermvars; ++
i)
4478 propdata->leaders, propdata->nleaders) );
4482 for (
p = componentbegins[
cidx];
p < componentbegins[
cidx + 1]; ++
p)
4493 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4512 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4513 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4514 ++propdata->nsymresacks;
4518 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4524 for (
p = nperms - 1;
p >= 0; --
p)
4561 SCIP_Bool addcuts =
FALSE;
4578 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4581 if ( propdata->sstaddcuts )
4585 addcuts = propdata->addconflictcuts;
4593 if ( propdata->nsstconss == 0 )
4596 assert( propdata->maxnsstconss == 0 );
4597 propdata->maxnsstconss = 2 * ncuts;
4600 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
4606 propdata->maxnsstconss,
newsize) );
4607 propdata->maxnsstconss =
newsize;
4611 if ( propdata->nleaders == 0 )
4613 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
4616 assert( propdata->nleaders < propdata->maxnleaders );
4623 propdata->leaders[propdata->nleaders++] = orbits[
posleader];
4625 for (
i = 0,
poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++
poscur)
4635 for (
j = 0;
j < propdata->nleaders - 1; ++
j)
4671 propdata->sstconss[propdata->nsstconss++] = cons;
4681 propdata->sstconss[propdata->nsstconss++] = cons;
4744 for (
i = 0;
i < norbits; ++
i)
4764 cnt = orbitbegins[
i];
4776 cnt = orbitbegins[
i + 1] - 1;
4804 *
leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
4822 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4828 for (
i = 0;
i < orbitsize; ++
i)
4835 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4848 ++(*norbitvarinconflict);
4897 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4903 for (
i = 0;
i < orbitsize; ++
i)
4910 varmapid = orbits[orbitbegins[*orbitidx] +
i];
4922 ++(*norbitvarinconflict);
4948 int nmovedbinpermvars;
4949 int nmovedintpermvars;
4950 int nmovedimplintpermvars;
4951 int nmovedcontpermvars;
4958 int* componentbegins;
4959 int* vartocomponent;
4961 unsigned* componentblocked;
4988 assert( propdata->computedsymmetry );
4990 permvars = propdata->permvars;
4991 npermvars = propdata->npermvars;
4992 nperms = propdata->nperms;
4998 permvarmap = propdata->permvarmap;
5002 permstrans = propdata->permstrans;
5006 componentbegins = propdata->componentbegins;
5007 componentblocked = propdata->componentblocked;
5008 vartocomponent = propdata->vartocomponent;
5009 ncomponents = propdata->ncomponents;
5015 assert( ncomponents > 0 );
5019 if ( componentblocked[
cidx] )
5023 if ( propdata->componenthassignedperm[
cidx] )
5033 nmovedpermvars = propdata->nmovedpermvars;
5034 nmovedbinpermvars = propdata->nmovedbinpermvars;
5035 nmovedintpermvars = propdata->nmovedintpermvars;
5036 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5037 nmovedcontpermvars = propdata->nmovedcontpermvars;
5038 assert( nmovedpermvars > 0 );
5073 for (
p = componentbegins[
cidx];
p < componentbegins[
cidx + 1]; ++
p)
5075 perm = propdata->perms[
p];
5076 for (
i = 0;
i < propdata->npermvars; ++
i)
5111 SCIPdebugMsg(
scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5114 if ( nchgbds !=
NULL )
5118 for (
c = 0;
c < ncomponents; ++
c)
5120 for (
p = componentbegins[
c];
p < componentbegins[
c + 1]; ++
p)
5138 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5139 componentblocked, ncomponents, nmovedpermvars) );
5144 for (
p = 0;
p < norbits; ++
p)
5183 assert( 0 <= orbitidx && orbitidx < norbits );
5193 if ( nchgbds !=
NULL )
5198 for (
p = 0;
p < nperms; ++
p)
5256 assert( propdata->usedynamicprop );
5274 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5275 for (
i = 0;
i < ncols - 1; ++
i)
5286 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5294 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5299 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5310 for (
i = 0;
i < nrows; ++
i)
5313 for (
j = 0;
j < ncols; ++
j)
5335 for (
i = 0;
i < nrows; ++
i)
5354 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5358 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5372 nelem = nrows * ncols;
5374 for (
i = 0;
i < nrows; ++
i)
5376 for (
j = 0;
j < ncols; ++
j)
5394 for (
i = nrows - 1;
i >= 0; --
i)
5522 for (
i = 0;
i < propdata->npermvars; ++
i)
5586 for (
i = 0;
i < propdata->npermvars; ++
i)
5603 row[0] = propdata->permvars[
i];
5604 row[1] = propdata->permvars[
j];
5605 assert( row[0] != row[1] );
5616 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5620 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5678 && propdata->usedynamicprop
5679 && propdata->addsymresacks
5681 assert( propdata->nperms > 0 );
5683 assert( propdata->componentblocked !=
NULL );
5686 if ( propdata->componentblocked[
cidx] )
5695 assert( propdata->nmovedpermvars );
5701 componentperms[
p] = propdata->perms[propdata->components[propdata->componentbegins[
cidx] +
p]];
5710 checkpporbisack =
SCIPgetParam(
scip,
"constraints/orbisack/checkpporbisack");
5749 if ( propdata->componentblocked[
cidx] )
5750 ++propdata->ncompblocked;
5772 if ( propdata->orbitopalreddata )
5776 if ( propdata->orbitalreddata )
5780 if ( propdata->lexreddata )
5784 if ( propdata->ncomponents >= 0 )
5792 for (
i = 0;
i < propdata->ncomponents; ++
i)
5794 if ( propdata->componentblocked[
i] )
5828 if ( propdata->usedynamicprop )
5833 else if ( propdata->binvaraffected )
5845 for (
i = 0;
i < nrows; ++
i)
5852 for (
j = 0;
j < ncols; ++
j)
5870 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5871 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5872 ++propdata->norbitopes;
5942 for (
i = 0;
i < nrows; ++
i)
5963 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5972 for (
i = 0;
i < ncols; ++
i)
5993 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
6035 if ( propdata->componentblocked[
cidx] )
6039 if ( propdata->componenthassignedperm[
cidx] )
6047 compsize = propdata->componentbegins[
cidx + 1] - propdata->componentbegins[
cidx];
6049 for (
p = 0,
i = propdata->componentbegins[
cidx];
i < propdata->componentbegins[
cidx + 1]; ++
i)
6050 perms[
p++] = propdata->perms[propdata->components[
i]];
6076 for (
p = 0;
p < ncols; ++
p)
6096 for (
i = nrows - 1;
i >= 0; --
i)
6114 ++(propdata->ncompblocked);
6133 if ( propdata->componentblocked[
cidx] )
6137 if ( propdata->componenthassignedperm[
cidx] )
6141 if ( !propdata->usedynamicprop &&
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
6142 && propdata->binvaraffected && propdata->ncompblocked < propdata->ncomponents )
6186 assert( propdata->ncomponents >= 0 );
6190 if ( propdata->componentblocked[
cidx] )
6195 || (
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
6198 if ( propdata->detectdoublelex || propdata->detectorbitopes )
6227 SCIP_Bool* earlyterm
6236 if ( nchgbds !=
NULL )
6238 if ( earlyterm !=
NULL )
6244 if ( earlyterm !=
NULL )
6251 assert( propdata->usesymmetry >= 0 );
6254 if ( propdata->usesymmetry == 0 )
6256 if ( earlyterm !=
NULL )
6262 if ( propdata->triedaddsymmethods )
6264 assert( propdata->nperms >= 0 );
6266 if ( earlyterm !=
NULL )
6271 assert( !propdata->triedaddsymmethods );
6274 if ( !propdata->computedsymmetry )
6282 if ( !propdata->computedsymmetry )
6286 propdata->triedaddsymmethods =
TRUE;
6287 assert( propdata->nperms >= 0 );
6290 if ( propdata->nperms == 0 )
6295 assert( propdata->ncomponents > 0 );
6298 for (
c = 0;
c < propdata->ncomponents; ++
c)
6306#ifdef SYMMETRY_STATISTICS
6319 SCIP_Bool* infeasible,
6333 *infeasible =
FALSE;
6378 if ( propdata->usesymmetry < 0 )
6382 assert( propdata->usesymmetry >= 0 );
6385 if ( propdata->usesymmetry == 0 )
6414 assert( propdata->usesymmetry >= 0 );
6417 if ( propdata->usesymmetry == 0 )
6461 SCIP_Bool earlyterm;
6472 assert( propdata->usesymmetry >= 0 );
6475 if ( propdata->usesymmetry == 0 )
6489 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
6505 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
6508 assert( propdata->nperms > 0 );
6509 assert( propdata->triedaddsymmethods );
6514 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss -
noldngenconns;
6515 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
6518 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
6522 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6532 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
6536 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6546 propdata->ngenorbconss + propdata->ngenlinconss);
6548 for (
i = 0;
i < propdata->nsstconss; ++
i)
6552 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
6561 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
6574 SCIP_Bool infeasible;
6592 if ( propdata->usesymmetry < 0 )
6600 propdata->symfoundreduction =
TRUE;
6607 propdata->symfoundreduction =
TRUE;
6634 propdata->usesymmetry = -1;
6635 propdata->triedaddsymmethods =
FALSE;
6636 propdata->nsymresacks = 0;
6637 propdata->norbitopes = 0;
6638 propdata->lastrestart = 0;
6639 propdata->symfoundreduction =
FALSE;
6678 assert( propdata->customsymopnodetypes !=
NULL );
6688 assert( propdata->orbitopalreddata !=
NULL );
6716 propdata->npermvars = 0;
6717 propdata->nbinpermvars = 0;
6718 propdata->permvars =
NULL;
6719 propdata->nperms = -1;
6720 propdata->nmaxperms = 0;
6721 propdata->perms =
NULL;
6722 propdata->permstrans =
NULL;
6723 propdata->permvarmap =
NULL;
6724 propdata->permvardomaincenter =
NULL;
6726 propdata->ncomponents = -1;
6727 propdata->ncompblocked = 0;
6728 propdata->components =
NULL;
6729 propdata->componentbegins =
NULL;
6730 propdata->vartocomponent =
NULL;
6731 propdata->componentblocked =
NULL;
6732 propdata->componenthassignedperm =
NULL;
6734 propdata->log10groupsize = -1.0;
6735 propdata->nmovedvars = -1;
6736 propdata->binvaraffected =
FALSE;
6737 propdata->computedsymmetry =
FALSE;
6738 propdata->conshdlr_nonlinear =
NULL;
6740 propdata->usesymmetry = -1;
6741 propdata->triedaddsymmethods =
FALSE;
6742 propdata->genorbconss =
NULL;
6743 propdata->genlinconss =
NULL;
6744 propdata->ngenorbconss = 0;
6745 propdata->ngenlinconss = 0;
6746 propdata->genorbconsssize = 0;
6747 propdata->genlinconsssize = 0;
6748 propdata->nsymresacks = 0;
6749 propdata->norbitopes = 0;
6750 propdata->isnonlinvar =
NULL;
6752 propdata->nmovedpermvars = -1;
6753 propdata->nmovedbinpermvars = 0;
6754 propdata->nmovedintpermvars = 0;
6755 propdata->nmovedimplintpermvars = 0;
6756 propdata->nmovedcontpermvars = 0;
6757 propdata->lastrestart = 0;
6758 propdata->symfoundreduction =
FALSE;
6760 propdata->sstconss =
NULL;
6761 propdata->nsstconss = 0;
6762 propdata->maxnsstconss = 0;
6763 propdata->leaders =
NULL;
6764 propdata->nleaders = 0;
6765 propdata->maxnleaders = 0;
6785 tabledata->propdata = propdata;
6801 "symmetry",
"display generators of symmetry group in cycle notation, if available",
6808 "propagating/" PROP_NAME "/maxgenerators",
6809 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
6813 "propagating/" PROP_NAME "/checksymmetries",
6814 "Should all symmetries be checked after computation?",
6818 "propagating/" PROP_NAME "/displaynorbitvars",
6819 "Should the number of variables affected by some symmetry be displayed?",
6823 "propagating/" PROP_NAME "/doubleequations",
6824 "Double equations to positive/negative version?",
6830 "Should the symmetry breaking constraints be added to the LP?",
6834 "propagating/" PROP_NAME "/addsymresacks",
6835 "Add inequalities for symresacks for each generator?",
6839 "propagating/" PROP_NAME "/detectdoublelex",
6840 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
6844 "propagating/" PROP_NAME "/detectorbitopes",
6845 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
6849 "propagating/" PROP_NAME "/detectsubgroups",
6850 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
6854 "propagating/" PROP_NAME "/addweaksbcs",
6855 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
6859 "propagating/" PROP_NAME "/addconsstiming",
6860 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) [disabled parameter]",
6865 "propagating/" PROP_NAME "/ofsymcomptiming",
6866 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) [disabled parameter]",
6870 "propagating/" PROP_NAME "/performpresolving",
6871 "run orbital fixing during presolving? (disabled)",
6875 "propagating/" PROP_NAME "/recomputerestart",
6876 "recompute symmetries after a restart has occurred? (0 = never)",
6880 "propagating/" PROP_NAME "/compresssymmetries",
6881 "Should non-affected variables be removed from permutation to save memory?",
6885 "propagating/" PROP_NAME "/compressthreshold",
6886 "Compression is used if percentage of moved vars is at most the threshold.",
6890 "propagating/" PROP_NAME "/usecolumnsparsity",
6891 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
6895 "propagating/" PROP_NAME "/maxnconsssubgroup",
6896 "maximum number of constraints up to which subgroup structures are detected",
6900 "propagating/" PROP_NAME "/usedynamicprop",
6901 "whether dynamified symmetry handling constraint methods should be used",
6905 "propagating/" PROP_NAME "/addstrongsbcs",
6906 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
6910 "propagating/" PROP_NAME "/ssttiebreakrule",
6911 "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)",
6915 "propagating/" PROP_NAME "/sstleaderrule",
6916 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
6920 "propagating/" PROP_NAME "/sstleadervartype",
6921 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
6922 "if multiple types are allowed, take the one with most affected vars",
6926 "propagating/" PROP_NAME "/addconflictcuts",
6927 "Should Schreier Sims constraints be added if we use a conflict based rule?",
6932 "Should Schreier Sims constraints be added?",
6936 "propagating/" PROP_NAME "/sstmixedcomponents",
6937 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
6941 "propagating/" PROP_NAME "/symfixnonbinaryvars",
6942 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
6946 "propagating/" PROP_NAME "/enforcecomputesymmetry",
6947 "Is only symmetry on binary variables used?",
6951 "propagating/" PROP_NAME "/preferlessrows",
6952 "Shall orbitopes with less rows be preferred in detection?",
6957 "Type of symmetries that shall be computed?",
6962 "timing of symmetry computation and handling (0 = before presolving, 1 = during presolving, 2 = after presolving)",
6977 assert( propdata->shadowtreeeventhdlr !=
NULL );
6980 assert( propdata->orbitopalreddata !=
NULL );
7001 SCIP_Real* log10groupsize,
7002 SCIP_Bool* binvaraffected,
7004 int** componentbegins,
7005 int** vartocomponent,
7032 *npermvars = propdata->npermvars;
7033 *permvars = propdata->permvars;
7035 if ( permvarmap !=
NULL )
7037 if ( propdata->nperms > 0 )
7041 *permvarmap = propdata->permvarmap;
7044 *nperms = propdata->nperms;
7045 if ( perms !=
NULL )
7047 *perms = propdata->perms;
7051 if ( permstrans !=
NULL )
7053 if ( propdata->nperms > 0 )
7057 *permstrans = propdata->permstrans;
7058 assert( *permstrans !=
NULL || *nperms <= 0 );
7061 if ( log10groupsize !=
NULL )
7062 *log10groupsize = propdata->log10groupsize;
7064 if ( binvaraffected !=
NULL )
7065 *binvaraffected = propdata->binvaraffected;
7069 if ( propdata->nperms > 0 )
7078 if ( componentbegins !=
NULL )
7079 *componentbegins = propdata->componentbegins;
7081 if ( vartocomponent )
7082 *vartocomponent = propdata->vartocomponent;
7085 *ncomponents = propdata->ncomponents;
7108 if ( propdata->nperms < 0 )
7111 return propdata->nperms;
7133 SCIPerrorMessage(
"Cannot create operator node type, symmetry propagator has not been included.\n");
7139 assert( propdata->customsymopnodetypes !=
NULL );
7148 *nodetype = propdata->nopnodetypes++;
7171 SCIPerrorMessage(
"Cannot return operator node type, symmetry propagator has not been included.\n");
7177 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
@ 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