162#define PROP_NAME "symmetry"
163#define PROP_DESC "propagator for handling symmetry"
164#define PROP_TIMING SCIP_PROPTIMING_BEFORELP
165#define PROP_PRIORITY -1000000
167#define PROP_DELAY FALSE
169#define PROP_PRESOL_PRIORITY -10000000
170#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
171#define PROP_PRESOL_MAXROUNDS -1
175#define DEFAULT_MAXGENERATORS 1500
176#define DEFAULT_CHECKSYMMETRIES FALSE
177#define DEFAULT_DISPLAYNORBITVARS FALSE
178#define DEFAULT_USECOLUMNSPARSITY FALSE
179#define DEFAULT_DOUBLEEQUATIONS FALSE
180#define DEFAULT_COMPRESSSYMMETRIES TRUE
181#define DEFAULT_COMPRESSTHRESHOLD 0.5
182#define DEFAULT_SYMFIXNONBINARYVARS FALSE
183#define DEFAULT_ONLYBINARYSYMMETRY TRUE
186#define DEFAULT_CONSSADDLP TRUE
187#define DEFAULT_ADDSYMRESACKS FALSE
188#define DEFAULT_DETECTORBITOPES TRUE
189#define DEFAULT_DETECTSUBGROUPS TRUE
190#define DEFAULT_ADDWEAKSBCS TRUE
191#define DEFAULT_ADDSTRONGSBCS FALSE
192#define DEFAULT_ADDCONSSTIMING 2
193#define DEFAULT_MAXNCONSSSUBGROUP 500000
194#define DEFAULT_USEDYNAMICPROP TRUE
195#define DEFAULT_PREFERLESSROWS TRUE
198#define DEFAULT_OFSYMCOMPTIMING 2
199#define DEFAULT_PERFORMPRESOLVING FALSE
200#define DEFAULT_RECOMPUTERESTART 0
203#define DEFAULT_SSTTIEBREAKRULE 1
204#define DEFAULT_SSTLEADERRULE 0
205#define DEFAULT_SSTLEADERVARTYPE 14
207#define DEFAULT_ADDCONFLICTCUTS TRUE
208#define DEFAULT_SSTADDCUTS TRUE
209#define DEFAULT_SSTMIXEDCOMPONENTS TRUE
212#define EVENTHDLR_SYMMETRY_NAME "symmetry"
213#define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"
216#define TABLE_NAME_ORBITALFIXING "orbitalfixing"
217#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"
218#define TABLE_POSITION_ORBITALFIXING 7001
219#define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING
223#define MAXGENNUMERATOR 64000000
224#define SCIP_SPECIALVAL 1.12345678912345e+19
225#define COMPRESSNVARSLB 25000
228#define ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
229#define ISORBITALFIXINGACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0)
230#define ISSSTACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SST) != 0)
232#define ISSSTBINACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)
233#define ISSSTINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)
234#define ISSSTIMPLINTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)
235#define ISSSTCONTACTIVE(x) (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)
246 SCIP_Real* permvarsobj;
254 int nmovedbinpermvars;
255 int nmovedintpermvars;
256 int nmovedimplintpermvars;
257 int nmovedcontpermvars;
265 int* componentbegins;
269 unsigned* componentblocked;
274 SCIP_Real log10groupsize;
275 SCIP_Bool binvaraffected;
279 SCIP_Bool checksymmetries;
280 SCIP_Bool displaynorbitvars;
281 SCIP_Bool compresssymmetries;
282 SCIP_Real compressthreshold;
283 SCIP_Bool compressed;
284 SCIP_Bool computedsymmetry;
286 SCIP_Bool usecolumnsparsity;
287 SCIP_Bool doubleequations;
288 SCIP_Bool symfixnonbinaryvars;
289 SCIP_Bool onlybinarysymmetry;
292 SCIP_Bool symconsenabled;
293 SCIP_Bool triedaddconss;
294 SCIP_Bool conssaddlp;
295 SCIP_Bool addsymresacks;
303 SCIP_Bool detectorbitopes;
304 SCIP_Bool detectsubgroups;
305 SCIP_Bool addweaksbcs;
306 SCIP_Bool addstrongsbcs;
308 SCIP_Bool* isnonlinvar;
310 int maxnconsssubgroup;
311 SCIP_Bool usedynamicprop;
312 SCIP_Bool preferlessrows;
325 SCIP_Bool performpresolving;
326 int recomputerestart;
331 SCIP_Longint nodenumber;
332 SCIP_Bool offoundreduction;
335 SCIP_Bool sstenabled;
341 int sstleadervartype;
346 SCIP_Bool addconflictcuts;
347 SCIP_Bool sstaddcuts;
348 SCIP_Bool sstmixedcomponents;
357 int nconflictinorbit;
393 assert( propdata->nperms > 0 );
395 assert( propdata->npermvars > 0 );
419 propdata->bg0list[propdata->nbg0++] =
varidx;
420 assert( propdata->nbg0 <= propdata->npermvars );
431 propdata->bg1list[propdata->nbg1++] =
varidx;
432 assert( propdata->nbg1 <= propdata->npermvars );
465 if ( tabledata->propdata->nperms > 0 )
530 if (
k1->type !=
k2->type )
534 if (
k1->nconss !=
k2->nconss )
617 vals = (SCIP_Real*) dataptr;
677 assert( propdata->nbg0 == 0 );
678 assert( propdata->nbg1 == 0 );
689 assert( propdata->nonbinpermvarcaptured ==
NULL );
690 assert( propdata->npermvars == 0 );
691 assert( propdata->nbinpermvars == 0 );
692 assert( propdata->nperms == -1 || propdata->nperms == 0 );
693 assert( propdata->nmaxperms == 0 );
694 assert( propdata->nmovedpermvars == -1 );
695 assert( propdata->nmovedbinpermvars == 0 );
696 assert( propdata->nmovedintpermvars == 0 );
697 assert( propdata->nmovedimplintpermvars == 0 );
698 assert( propdata->nmovedcontpermvars == 0 );
699 assert( propdata->nmovedvars == -1 );
706 assert( propdata->ncomponents == -1 );
707 assert( propdata->ncompblocked == 0 );
752 propdata->symconsenabled =
TRUE;
754 propdata->symconsenabled =
FALSE;
757 propdata->ofenabled =
TRUE;
759 propdata->ofenabled =
FALSE;
762 propdata->sstenabled =
TRUE;
764 propdata->sstenabled =
FALSE;
782 if ( propdata->permvarmap !=
NULL )
788 if ( propdata->permvarsevents !=
NULL )
791 assert( propdata->npermvars > 0 );
793 for (
i = 0;
i < propdata->npermvars; ++
i)
800 if ( propdata->permvarsevents[
i] >= 0 )
803 propdata->eventhdlr, (
SCIP_EVENTDATA*) propdata, propdata->permvarsevents[
i]) );
811 if ( propdata->nonbinpermvarcaptured !=
NULL )
818 for (
i = propdata->nbinpermvars, cnt = 0;
i < propdata->npermvars; ++
i, ++cnt)
823 if ( propdata->nonbinpermvarcaptured[cnt] )
829 propdata->nonbinpermvarcaptured =
NULL;
832 if ( propdata->binvaraffected )
834 for (
i = 0;
i < propdata->nbinpermvars; ++
i)
841 if ( propdata->bg0list !=
NULL )
860 if ( propdata->permstrans !=
NULL )
862 assert( propdata->nperms > 0 );
864 assert( propdata->npermvars > 0 );
865 assert( propdata->nmaxperms > 0 );
867 for (
i = 0;
i < propdata->npermvars; ++
i)
875 if ( propdata->genorbconss !=
NULL )
877 assert( propdata->ngenorbconss + propdata->ngenlinconss > 0
881 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
889 propdata->ngenorbconss = 0;
893 if ( propdata->genlinconss !=
NULL )
896 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
904 propdata->ngenlinconss = 0;
905 propdata->genlinconsssize = 0;
908 if ( propdata->sstconss !=
NULL )
910 assert( propdata->nsstconss > 0 );
913 for (
i = 0;
i < propdata->nsstconss; ++
i)
921 propdata->sstconss =
NULL;
922 propdata->nsstconss = 0;
923 propdata->maxnsstconss = 0;
926 if ( propdata->leaders !=
NULL )
928 assert( propdata->maxnleaders > 0 );
931 propdata->maxnleaders = 0;
932 propdata->leaders =
NULL;
933 propdata->nleaders = 0;
937 if ( propdata->ncomponents > 0 )
949 propdata->ncomponents = -1;
950 propdata->ncompblocked = 0;
954 if ( propdata->nperms > 0 )
961 if ( propdata->perms !=
NULL )
963 for (
i = 0;
i < propdata->nperms; ++
i)
976 propdata->npermvars = 0;
977 propdata->nbinpermvars = 0;
978 propdata->nperms = -1;
979 propdata->nmaxperms = 0;
980 propdata->nmovedpermvars = -1;
981 propdata->nmovedbinpermvars = 0;
982 propdata->nmovedintpermvars = 0;
983 propdata->nmovedimplintpermvars = 0;
984 propdata->nmovedcontpermvars = 0;
985 propdata->nmovedvars = -1;
986 propdata->log10groupsize = -1.0;
987 propdata->binvaraffected =
FALSE;
988 propdata->isnonlinvar =
NULL;
990 propdata->nperms = -1;
994 propdata->computedsymmetry =
FALSE;
995 propdata->compressed =
FALSE;
1029 SCIP_Real* constant,
1030 SCIP_Bool transformed
1059 for (v = 0; v < *
nvars; ++v)
1072 SCIP_Bool doubleequations,
1078 SCIP_Bool istransformed,
1086 SCIP_Real constant = 0.0;
1097 if ( nlinvars == 0 )
1318 SCIPdebugMsg(
scip,
"Checking whether symmetries are symmetries (generators: %d).\n", nperms);
1356 for (
p = 0;
p < nperms; ++
p)
1362 SCIPdebugMsg(
scip,
"Verifying automorphism group generator #%d for linear part ...\n",
p);
1408 SCIP_Bool found =
FALSE;
1456 SCIPdebugMsg(
scip,
"Verifying automorphism group generator #%d for non-linear part ...\n",
p);
1465 for (
i = 0;
i < nconss; ++
i)
1468 SCIP_Bool permuted =
FALSE;
1494 SCIP_Bool found =
FALSE;
1495 SCIP_Bool infeasible;
1512 for (
j = 0;
j < nconss; ++
j)
1585 if( conshdlr_nonlinear !=
NULL )
1615 SCIP_Bool* binvaraffected,
1617 SCIP_Real compressthreshold,
1618 SCIP_Bool* compressed
1641 *binvaraffected =
FALSE;
1642 *compressed =
FALSE;
1663 for (
p = 0;
p < nperms; ++
p)
1665 if ( perms[
p][
i] !=
i )
1678 *binvaraffected =
TRUE;
1685 for (
p = 0;
p < nperms; ++
p)
1688 for (
i = 0;
i < *nmovedvars; ++
i)
1699 for (
i = 0;
i < *nmovedvars; ++
i)
1703 *npermvars = *nmovedvars;
1717 for (
p = 0;
p < nperms && ! *binvaraffected; ++
p)
1719 if ( perms[
p][
i] !=
i )
1722 *binvaraffected =
TRUE;
1737 SCIP_Bool doubleequations,
1738 SCIP_Bool compresssymmetries,
1739 SCIP_Real compressthreshold,
1743 SCIP_Bool checksymmetries,
1744 SCIP_Bool usecolumnsparsity,
1752 SCIP_Real* log10groupsize,
1754 SCIP_Bool** isnonlinvar,
1755 SCIP_Bool* binvaraffected,
1756 SCIP_Bool* compressed,
1811 *log10groupsize = 0;
1813 *binvaraffected =
FALSE;
1814 *compressed =
FALSE;
1824 if ( nconss == 0 ||
nvars == 0 )
1838 if ( nactiveconss == 0 )
1855 SCIPdebugMsg(
scip,
"Detecting %ssymmetry on %d variables and %d constraints.\n", local ?
"local " :
"",
nvars, nactiveconss);
1864 if (
nvars <= 100000 )
1866 else if (
nvars <= 1000000 )
1868 else if (
nvars <= 16700000 )
1912 *isnonlinvar =
NULL;
1915 if ( usecolumnsparsity )
1921 for (
c = 0;
c < nconss; ++
c)
1967 for (
i = 0;
i < nconsvars - 1;
i++)
1990 SCIP_CALL(
collectCoefficients(
scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0,
SCIPconsIsTransformed(cons),
SYM_SENSE_EQUATION, &
matrixdata,
nconssforvar) );
1993 SCIP_CALL(
collectCoefficients(
scip, doubleequations, linvars, 0, nconsvars, -
SCIPinfinity(
scip), 1.0,
SCIPconsIsTransformed(cons),
SYM_SENSE_INEQUALITY, &
matrixdata,
nconssforvar) );
1996 SCIP_CALL(
collectCoefficients(
scip, doubleequations, linvars, 0, nconsvars, 1.0,
SCIPinfinity(
scip),
SCIPconsIsTransformed(cons),
SYM_SENSE_INEQUALITY, &
matrixdata,
nconssforvar) );
2013 for (
j = 0;
j < nconsvars; ++
j)
2024 consvars[nconsvars] =
var;
2027 assert( nconsvars <= nallvars );
2042 for (
j = 0;
j < nconsvars; ++
j)
2052 assert( nconsvars <= nallvars );
2067 for (
j = 0;
j < nconsvars; ++
j)
2077 assert( nconsvars <= nallvars );
2089 SCIP_Longint* weights;
2095 for (
j = 0;
j < nconsvars; ++
j)
2097 assert( nconsvars <= nallvars );
2171 if ( consvars[
j] == consvars[
k] )
2181 " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
2183 if ( usecolumnsparsity )
2271 SCIPerrorMessage(
"Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
2287 if ( usecolumnsparsity )
2369 SCIPdebugMsg(
scip,
"Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
2396 if ( usecolumnsparsity )
2492 assert( *nperms <= *nmaxperms );
2503 nmovedvars, binvaraffected, compresssymmetries, compressthreshold, compressed) );
2526 if ( usecolumnsparsity )
2565 unsigned int type = 0;
2572 assert( propdata->usesymmetry >= 0 );
2573 assert( propdata->ofenabled || propdata->symconsenabled || propdata->sstenabled );
2578 propdata->ofenabled =
FALSE;
2579 propdata->symconsenabled =
FALSE;
2580 propdata->sstenabled =
FALSE;
2587 propdata->ofenabled =
FALSE;
2588 propdata->symconsenabled =
FALSE;
2589 propdata->sstenabled =
FALSE;
2596 propdata->ofenabled =
FALSE;
2597 propdata->symconsenabled =
FALSE;
2598 propdata->sstenabled =
FALSE;
2609 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2617 propdata->ofenabled =
FALSE;
2618 propdata->symconsenabled =
FALSE;
2619 propdata->sstenabled =
FALSE;
2628 propdata->ofenabled =
FALSE;
2629 propdata->symconsenabled =
FALSE;
2630 propdata->sstenabled =
FALSE;
2638 propdata->ofenabled =
FALSE;
2639 propdata->symconsenabled =
FALSE;
2642 if ( propdata->sstenabled )
2666 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2675 propdata->ofenabled =
FALSE;
2676 propdata->symconsenabled =
FALSE;
2677 propdata->sstenabled =
FALSE;
2683 if ( propdata->computedsymmetry )
2692 " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2695 propdata->ofenabled =
FALSE;
2696 propdata->symconsenabled =
FALSE;
2697 propdata->sstenabled =
FALSE;
2702 assert( propdata->npermvars == 0 );
2707 assert( propdata->nperms < 0 );
2708 assert( propdata->nmaxperms == 0 );
2713 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2727 maxgenerators = propdata->maxgenerators;
2732 maxgenerators,
symspecrequirefixed,
FALSE, propdata->checksymmetries, propdata->usecolumnsparsity, propdata->conshdlr_nonlinear,
2733 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2734 &propdata->perms, &propdata->log10groupsize, &propdata->nmovedvars, &propdata->isnonlinvar,
2738 propdata->computedsymmetry =
TRUE;
2749 propdata->ofenabled =
FALSE;
2750 propdata->symconsenabled =
FALSE;
2751 propdata->sstenabled =
FALSE;
2757 if ( propdata->nperms == 0 )
2762 propdata->ofenabled =
FALSE;
2763 propdata->symconsenabled =
FALSE;
2764 propdata->sstenabled =
FALSE;
2774 if ( maxgenerators == 0 )
2782 if ( propdata->displaynorbitvars )
2784 if ( propdata->nmovedvars == -1 )
2787 propdata->npermvars, &(propdata->nmovedvars)) );
2794 if ( ! propdata->binvaraffected )
2799 propdata->ofenabled =
FALSE;
2800 propdata->symconsenabled =
FALSE;
2801 if ( ! propdata->sstenabled ||
2805 propdata->sstenabled =
FALSE;
2817 assert( propdata->nperms > 0 );
2818 assert( propdata->npermvars > 0 );
2825#ifdef SCIP_OUTPUT_COMPONENT
2830 if ( propdata->ofenabled || ( propdata->symconsenabled && propdata->detectorbitopes )
2831 || propdata->detectsubgroups || propdata->sstenabled )
2834 propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
2835 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
2838#ifdef SCIP_OUTPUT_COMPONENT
2843 if ( propdata->ofenabled )
2850 for (v = 0; v < propdata->npermvars; ++v)
2853 for (
p = 0;
p < propdata->nperms; ++
p)
2856 propdata->permstrans[v][
p] = propdata->perms[
p][v];
2858 propdata->permstrans[v][
p] = v;
2864 for (v = 0; v < propdata->nperms; ++v)
2865 propdata->inactiveperms[v] =
FALSE;
2879 assert( propdata->nmovedpermvars == -1 );
2880 propdata->nmovedpermvars = 0;
2881 for (v = 0; v < propdata->npermvars; ++v)
2885 propdata->bg0[v] =
FALSE;
2886 propdata->bg1[v] =
FALSE;
2887 propdata->permvarsevents[v] = -1;
2893 propdata->nmovedpermvars += 1;
2896 ++propdata->nmovedbinpermvars;
2898 ++propdata->nmovedintpermvars;
2900 ++propdata->nmovedimplintpermvars;
2902 ++propdata->nmovedcontpermvars;
2911 propdata->eventhdlr, (
SCIP_EVENTDATA*) propdata, &propdata->permvarsevents[v]) );
2914 assert( propdata->nbg1 == 0 );
2918 if ( (propdata->sstenabled || propdata->detectsubgroups) && ! propdata->ofenabled )
2925 for (v = 0; v < propdata->npermvars; ++v)
2928 for (
p = 0;
p < propdata->nperms; ++
p)
2929 propdata->permstrans[v][
p] = propdata->perms[
p][v];
2937 for (v = 0; v < propdata->npermvars; ++v)
2947 for (
j = 0;
j < propdata->npermvars; ++
j)
2957 if ( propdata->binvaraffected )
2959 for (
j = 0;
j < propdata->nbinpermvars; ++
j)
2963 if ( propdata->compressed )
2969 for (
p = 0;
p < propdata->nperms; ++
p)
2971 if ( propdata->perms[
p][
j] !=
j )
2987 propdata->npermvars - propdata->nbinpermvars) );
2988 for (
j = propdata->nbinpermvars, cnt = 0;
j < propdata->npermvars; ++
j, ++cnt)
2992 propdata->nonbinpermvarcaptured[cnt] =
FALSE;
2997 propdata->nonbinpermvarcaptured[cnt] =
TRUE;
2999 if ( propdata->compressed )
3005 for (
p = 0;
p < propdata->nperms; ++
p)
3007 if ( propdata->perms[
p][
j] !=
j )
3018 if ( ! propdata->symconsenabled && ! propdata->sstenabled )
3020 for (
p = 0;
p < propdata->nperms; ++
p)
3107 for (
j = 0;
j < npermvars; ++
j)
3158 SCIP_Bool infeasible =
FALSE;
3194 SCIP_Bool infeasible =
FALSE;
3245 int* componentbegins;
3258 assert( propdata->computedsymmetry );
3259 assert( propdata->nperms > 0 );
3261 assert( propdata->npermvars > 0 );
3262 assert( propdata->ncomponents > 0 );
3266 perms = propdata->perms;
3267 npermvars = propdata->npermvars;
3269 componentbegins = propdata->componentbegins;
3288 if ( propdata->preferlessrows )
3292 --(*ntwocycleperms);
3294 else if ( ! propdata->preferlessrows )
3335 int* componentbegins;
3359 assert( propdata->computedsymmetry );
3360 assert( propdata->nperms > 0 );
3362 assert( propdata->npermvars > 0 );
3363 assert( propdata->ncomponents > 0 );
3368 perms = propdata->perms;
3369 npermvars = propdata->npermvars;
3371 componentbegins = propdata->componentbegins;
3380 for (
k = 0;
k < npermvars; ++
k)
3393 for (
k = 0;
k < npermvars; ++
k)
3443 if (
k < npermvars )
3466 for (
k = 0;
k < npermvars; ++
k)
3514 for (
j = 0;
j < npermvars; ++
j)
3523 (*graphcomponents)[
j] =
j;
3536 (*graphcompbegins)[0] = 0;
3537 (*compcolorbegins)[0] = 0;
3540 for (
j = 1;
j < npermvars; ++
j)
3545 idx1 = (*graphcomponents)[
j];
3546 idx2 = (*graphcomponents)[
j-1];
3567 (*graphcompbegins)[
nextcomp] = npermvars;
3596 SCIP_Bool mayinteract,
3608 SCIP_Bool infeasible =
FALSE;
3635 for (
k = 0;
k < nrows; ++
k)
3642 for (
k = 0;
k < ncols; ++
k)
3661 for (
l = 0;
l < ncols; ++
l)
3696 for (
k = nrows - 1;
k >= 0; --
k)
3744 for (
l = 0;
l < ncols; ++
l)
3758 for (
k = 0;
k < nrows; ++
k)
3781 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3782 ++propdata->norbitopes;
3784 for (
k = nrows - 1;
k >= 0; --
k)
3789 for (
k = nrows - 1;
k >= 0; --
k)
3850 SCIP_Real vals[2] = {1, -1};
3866#ifdef SCIP_MORE_DEBUG
3872 if ( propdata->ngenlinconss >= propdata->genlinconsssize )
3881 propdata->genlinconsssize =
newsize;
3884 propdata->genlinconss[propdata->ngenlinconss] = cons;
3885 ++propdata->ngenlinconss;
3913 SCIP_Real vals[2] = {1, -1};
3916 int orbitsize[2] = {1, 1};
4006 propdata->permstrans, propdata->components, propdata->componentbegins,
4036 *naddedconss = orbitsize[
activeorb] - 1;
4054#ifdef SCIP_MORE_DEBUG
4060 if ( propdata->ngenlinconss >= propdata->genlinconsssize )
4069 propdata->genlinconsssize =
newsize;
4072 propdata->genlinconss[propdata->ngenlinconss] = cons;
4073 ++propdata->ngenlinconss;
4090 (*lexorder)[(*nvarsorder)++] =
varidx;
4175 for (
i = 0;
i < npermvars; ++
i)
4180 for (
i = 0;
i < npermvars; ++
i)
4185 for (
l = 0;
l < nleaders; ++
l)
4202 for (
i = 0;
i < npermvars; ++
i)
4206 for (
p = 0;
p < nperms; ++
p)
4208 for (
i = 0;
i < npermvars; ++
i)
4324 assert( propdata->computedsymmetry );
4327 assert( propdata->ncomponents > 0 );
4328 assert( propdata->nperms >= 0 );
4331 if ( propdata->nperms == 0 )
4338 assert( propdata->nperms > 0 );
4340 assert( propdata->npermvars > 0 );
4348 for (
i = 0;
i < propdata->nperms; ++
i)
4355 for (
i = 0;
i < propdata->npermvars; ++
i)
4357 if ( propdata->vartocomponent[
i] >= 0 )
4361 SCIPdebugMsg(
scip,
"starting subgroup detection routine for %d components\n", propdata->ncomponents);
4364 for (
i = 0;
i < propdata->ncomponents; ++
i)
4389 if ( propdata->componentblocked[
i] )
4391 SCIPdebugMsg(
scip,
"component %d has already been handled and will be skipped\n",
i);
4395 npermsincomp = propdata->componentbegins[
i + 1] - propdata->componentbegins[
i];
4408#ifdef SCIP_MORE_DEBUG
4415 for (
p = propdata->componentbegins[
i];
p < propdata->componentbegins[
i+1]; ++
p)
4417 perm = propdata->components[
p];
4419 for (
k = 0;
k < propdata->npermvars; ++
k)
4424 for (
k = 0;
k < propdata->npermvars; ++
k)
4429 j = propdata->perms[perm][
k];
4441 j = propdata->perms[perm][
j];
4480 SCIPdebugMsg(
scip,
" -> skipping component, since less no permutation was used\n");
4490 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
4522 propdata->permvars, propdata->npermvars,
FALSE,
4527 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4528 ++propdata->nsymresacks;
4530 if ( ! propdata->componentblocked[
i] )
4533 ++propdata->ncompblocked;
4648 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
4661 if ( ! propdata->componentblocked[
i] )
4664 ++propdata->ncompblocked;
4680 if( propdata->addweaksbcs )
4689 SCIPdebugMsg(
scip,
" choosing component %d with %d variables and adding strong SBCs\n",
4700 if ( ! propdata->componentblocked[
i] )
4703 ++propdata->ncompblocked;
4715 if ( propdata->addweaksbcs )
4744 SCIPdebugMsg(
scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4773 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4774 ++propdata->nsymresacks;
4776 if ( ! propdata->componentblocked[
i] )
4779 ++propdata->ncompblocked;
4782 SCIPdebugMsg(
scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n",
k,
i);
4799 SCIPdebugMsg(
scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4807 for (
i = propdata->nperms - 1;
i >= 0; --
i)
4854 for (
i = 0;
i < nrows; ++
i)
4860 for (
j = 0;
j < ncols; ++
j)
4864 if ( idx <
idcs[
i] )
4880 for (
j = 0;
j < ncols; ++
j)
4891 for (
i = 1;
i < nrows; ++
i)
4893 for (
j = 0;
j < ncols; ++
j)
4895 for (
j = 0;
j < ncols; ++
j)
4913 int* componentbegins,
4926 assert( ncomponents > 0 );
4927 assert( propdata->nperms >= 0 );
4930 if ( propdata->nperms == 0 )
4933 assert( propdata->nperms > 0 );
4935 assert( propdata->nbinpermvars >= 0 );
4936 assert( propdata->npermvars >= 0 );
4940 if ( propdata->nbinpermvars == 0 )
4942 assert( ! propdata->binvaraffected );
4946 perms = propdata->perms;
4947 npermvars = propdata->npermvars;
4948 permvars = propdata->permvars;
4951 for (
i = 0;
i < ncomponents; ++
i)
4969 assert( ! propdata->componentblocked[
i] );
4974 for (
j = componentbegins[
i];
j < componentbegins[
i + 1]; ++
j)
5083 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5084 ++propdata->norbitopes;
5169 for (
j = 0;
j < norbits; ++
j)
5174 orbitsize = orbitbegins[
j + 1] - orbitbegins[
j];
5175 assert( orbitsize >= 0 );
5177 for (
i = orbitbegins[
j];
i < orbitbegins[
j + 1]; ++
i)
5187 var = permvars[pos];
5191 var = permvars[orbits[
i]];
5206 nodedata->posinorbit = posinorbit++;
5216 int nconflictinorbit = 0;
5246 nodedata->nconflictinorbit = nconflictinorbit;
5294 SCIPdebugMsg(
scip,
"Could not find setppc conshdlr --> construction of conflict graph aborted.\n");
5303 SCIPdebugMsg(
scip,
"No setppc constraints present --> construction of conflict graph aborted.\n");
5375 SCIPdebugMsg(
scip,
"Construction of conflict graph terminated; %d conflicts detected.\n", nedges);
5424 int* componentbegins,
5430 SCIP_Bool conssaddlp;
5445 assert( propdata->npermvars >= 0 );
5446 assert( propdata->nbinpermvars >= 0 );
5449 if ( propdata->nbinpermvars == 0 )
5451 assert( propdata->binvaraffected == 0 );
5455 perms = propdata->perms;
5456 nperms = propdata->nperms;
5457 permvars = propdata->permvars;
5458 npermvars = propdata->npermvars;
5459 conssaddlp = propdata->conssaddlp;
5466 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
5469 for (
p = 0;
p < nperms; ++
p)
5475 for (
i = 0;
i < npermvars; ++
i)
5479 propdata->leaders, propdata->nleaders) );
5483 if ( ncomponents == -1 )
5485 assert( ! propdata->ofenabled );
5486 assert( ! propdata->detectorbitopes );
5487 assert( ! propdata->sstenabled );
5490 for (
p = 0;
p < propdata->nperms; ++
p)
5503 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5504 ++propdata->nsymresacks;
5511 for (
i = 0;
i < ncomponents; ++
i)
5527 for (
p = componentbegins[
i];
p < componentbegins[
i + 1]; ++
p)
5538 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
5556 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5557 ++propdata->nsymresacks;
5563 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
5569 for (
p = nperms - 1;
p >= 0; --
p)
5607 SCIP_Bool addcuts =
FALSE;
5625 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
5628 if ( propdata->sstaddcuts )
5633 addcuts = propdata->addconflictcuts;
5641 if ( propdata->nsstconss == 0 )
5644 assert( propdata->maxnsstconss == 0 );
5645 propdata->maxnsstconss = 2 * ncuts;
5648 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
5654 propdata->maxnsstconss,
newsize) );
5655 propdata->maxnsstconss =
newsize;
5659 if ( propdata->nleaders == 0 )
5661 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
5664 assert( propdata->nleaders < propdata->maxnleaders );
5671 propdata->leaders[propdata->nleaders++] = orbits[
posleader];
5673 for (
i = 0,
poscur = orbitbegins[orbitidx];
i < orbitsize; ++
i, ++
poscur)
5683 for (
j = 0;
j < propdata->nleaders - 1; ++
j)
5724 propdata->sstconss[propdata->nsstconss++] = cons;
5734 propdata->sstconss[propdata->nsstconss++] = cons;
5811 for (
i = 0;
i < norbits; ++
i)
5826 int cnt = orbitbegins[
i];
5832 while (
varidx == -1 && cnt < orbitbegins[
i + 1]);
5836 int cnt = orbitbegins[
i + 1] - 1;
5842 while (
varidx == -1 && cnt >= orbitbegins[
i]);
5853 if (
nodedata->nconflictinorbit > 0 )
5867 *
leaderidx = orbitbegins[
i + 1] - orbitbegins[
i] - 1;
5883 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
5891 for (
i = 0;
i < orbitsize; ++
i)
5897 var = permvars[orbits[orbitbegins[*orbitidx] +
i]];
5958 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
5963 for (
i = 0;
i < orbitsize; ++
i)
5969 var = permvars[orbits[orbitbegins[*orbitidx] +
i]];
6009 int nmovedbinpermvars;
6010 int nmovedintpermvars;
6011 int nmovedimplintpermvars;
6012 int nmovedcontpermvars;
6019 int* componentbegins;
6020 int* vartocomponent;
6022 unsigned* componentblocked;
6047 permvars = propdata->permvars;
6048 npermvars = propdata->npermvars;
6049 permvarmap = propdata->permvarmap;
6050 permstrans = propdata->permstrans;
6051 nperms = propdata->nperms;
6053 componentbegins = propdata->componentbegins;
6054 componentblocked = propdata->componentblocked;
6055 vartocomponent = propdata->vartocomponent;
6056 ncomponents = propdata->ncomponents;
6057 nmovedpermvars = propdata->nmovedpermvars;
6058 nmovedbinpermvars = propdata->nmovedbinpermvars;
6059 nmovedintpermvars = propdata->nmovedintpermvars;
6060 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
6061 nmovedcontpermvars = propdata->nmovedcontpermvars;
6071 assert( ncomponents > 0 );
6072 assert( nmovedpermvars > 0 || ! propdata->ofenabled );
6073 assert( nmovedbinpermvars > 0 || ! propdata->ofenabled );
6081 if ( nmovedpermvars == -1 )
6085 for (v = 0; v < npermvars; ++v)
6087 for (
p = 0;
p < nperms; ++
p)
6089 if ( permstrans[v][
p] != v )
6096 ++nmovedbinpermvars;
6099 ++nmovedintpermvars;
6102 ++nmovedimplintpermvars;
6106 ++nmovedcontpermvars;
6112 propdata->nmovedbinpermvars = nmovedbinpermvars;
6113 propdata->nmovedintpermvars = nmovedintpermvars;
6114 propdata->nmovedimplintpermvars = nmovedimplintpermvars;
6115 propdata->nmovedcontpermvars = nmovedcontpermvars;
6168 for (v = 0; v <
nvars; ++v)
6175 SCIPdebugMsg(
scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
6178 if ( nchgbds !=
NULL )
6182 for (
p = 0;
p < nperms; ++
p)
6183 inactiveperms[
p] =
TRUE;
6186 for (
c = 0;
c < ncomponents; ++
c)
6190 for (
c = 0;
c < ncomponents; ++
c)
6194 if ( componentblocked[
c] )
6197 for (
p = componentbegins[
c];
p < componentbegins[
c + 1]; ++
p)
6208 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
6209 componentblocked, ncomponents, nmovedpermvars) );
6214 for (
p = 0;
p < norbits; ++
p)
6233 varmap, orbits, orbitbegins, norbits) );
6250 permvars, npermvars, orbits, orbitbegins, norbits, propdata->sstleaderrule, propdata->ssttiebreakrule,
selectedtype,
6256 assert( 0 <= orbitidx && orbitidx < norbits );
6266 if ( nchgbds !=
NULL )
6271 for (
p = 0;
p < nperms; ++
p)
6273 if ( inactiveperms[
p] )
6278 inactiveperms[
p] =
TRUE;
6284 for (
p = componentbegins[
c];
p < componentbegins[
c + 1]; ++
p)
6289 for (
c = 0;
c < ncomponents; ++
c)
6320 SCIP_Bool* earlyterm
6330 assert( propdata->symconsenabled || propdata->sstenabled );
6333 if ( propdata->triedaddconss )
6335 assert( propdata->nperms > 0 );
6337 if ( earlyterm !=
NULL )
6367 propdata->ofenabled =
FALSE;
6368 propdata->sstenabled =
FALSE;
6377 assert( propdata->binvaraffected || ! propdata->ofenabled || ! propdata->symconsenabled );
6379 if ( propdata->nperms <= 0 || (! propdata->symconsenabled && ! propdata->sstenabled) )
6382 if ( ! propdata->binvaraffected )
6384 SCIPdebugMsg(
scip,
"Symmetry propagator: problem is linear and no symmetry on binary variables has been found, turning symretope constraints off.\n");
6385 propdata->symconsenabled =
FALSE;
6387 assert( propdata->nperms > 0 );
6390 propdata->triedaddconss =
TRUE;
6392 if ( propdata->symconsenabled )
6396 if ( propdata->detectorbitopes )
6403 if ( propdata->ncomponents == propdata->norbitopes )
6404 propdata->ofenabled =
FALSE;
6409 if ( propdata->ngenorbconss == 0 )
6416 if ( propdata->ncompblocked < propdata->ncomponents && propdata->detectsubgroups && propdata->symconsenabled )
6419 propdata->genlinconsssize = propdata->nperms;
6425 if ( propdata->sstenabled )
6435 if ( ! propdata->ofenabled )
6438 if ( propdata->nperms < 1 || ! propdata->binvaraffected )
6441 if ( propdata->addsymresacks )
6447 if ( propdata->ngenorbconss == 0 )
6476 SCIP_Bool* infeasible,
6481 SCIP_Bool tightened;
6492 assert( orbitbegins[0] == 0 );
6494 *infeasible =
FALSE;
6499 for (
i = 0;
i < norbits; ++
i)
6507 assert( orbitbegins[
i+1] - orbitbegins[
i] >= 2 );
6510 for (
j = orbitbegins[
i];
j < orbitbegins[
i+1]; ++
j)
6512 assert( 0 <= orbits[
j] && orbits[
j] < npermvars );
6513 var = permvars[orbits[
j]];
6546 for (
j = orbitbegins[
i];
j < orbitbegins[
i+1]; ++
j)
6548 assert( 0 <= orbits[
j] && orbits[
j] < npermvars );
6549 var = permvars[orbits[
j]];
6574 for (
j = orbitbegins[
i];
j < orbitbegins[
i+1]; ++
j)
6576 assert( 0 <= orbits[
j] && orbits[
j] < npermvars );
6577 var = permvars[orbits[
j]];
6646 if ( domchg !=
NULL )
6650 for (
i = 0;
i < nboundchgs; ++
i)
6702 SCIP_Bool* infeasible,
6713 int* componentbegins;
6714 int* vartocomponent;
6733 assert( propdata->ofenabled );
6737 *infeasible =
FALSE;
6752 nperms = propdata->nperms;
6757 assert( propdata->npermvars > 0 );
6764 assert( propdata->ncomponents > 0 );
6766 permvars = propdata->permvars;
6767 npermvars = propdata->npermvars;
6768 nbinpermvars = propdata->nbinpermvars;
6769 permstrans = propdata->permstrans;
6770 inactiveperms = propdata->inactiveperms;
6772 componentbegins = propdata->componentbegins;
6773 vartocomponent = propdata->vartocomponent;
6774 ncomponents = propdata->ncomponents;
6779 assert( propdata->nbg1 >= 0 );
6780 assert( propdata->nbg1 <= npermvars );
6782 bg1 = propdata->bg1;
6783 bg1list = propdata->bg1list;
6784 nbg1 = propdata->nbg1;
6788 assert( nbg1 >= propdata->nbg1 );
6792 for (
p = 0;
p < nperms; ++
p)
6793 propdata->inactiveperms[
p] =
FALSE;
6798 assert( propdata->nbg0 >= 0 );
6799 assert( propdata->nbg0 <= npermvars );
6801 bg0 = propdata->bg0;
6802 bg0list = propdata->bg0list;
6803 nbg0 = propdata->nbg0;
6811 assert( 0 <= v && v < npermvars );
6831 if ( inactiveperms[perm] )
6857 inactiveperms[perm] =
TRUE;
6870 assert( 0 <= v && v < npermvars );
6890 if ( inactiveperms[perm] )
6916 inactiveperms[perm] =
TRUE;
6925 for (
j = propdata->nbg1;
j < nbg1; ++
j)
6936 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
6946 propdata->nfixedzero += nfixedzero;
6947 propdata->nfixedone += nfixedone;
6948 *
nprop = nfixedzero + nfixedone;
6950 SCIPdebugMsg(
scip,
"Orbital fixings: %d 0s, %d 1s.\n", nfixedzero, nfixedone);
6981 if ( propdata->usesymmetry < 0 )
6988 if ( (propdata->symconsenabled || propdata->sstenabled) && propdata->addconsstiming == 0 )
6990 SCIPdebugMsg(
scip,
"Try to add symmetry handling constraints before presolving.");
6994 else if ( propdata->ofenabled && propdata->ofsymcomptiming == 0 )
7007 assert( propdata->binvaraffected || ! propdata->ofenabled );
7028 assert( propdata->usesymmetry >= 0 );
7049 assert( propdata->binvaraffected || ! propdata->ofenabled );
7072 assert( propdata->usesymmetry >= 0 );
7075 if ( propdata->symconsenabled || propdata->sstenabled )
7079 SCIP_Bool earlyterm =
FALSE;
7090 noldngenconns = propdata->ngenorbconss + propdata->nsstconss + propdata->ngenlinconss;
7106 if ( propdata->ngenorbconss > 0 || propdata->ngenlinconss > 0 || propdata->nsstconss > 0 )
7109 assert( propdata->nperms > 0 );
7110 assert( propdata->triedaddconss );
7115 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss -
noldngenconns;
7116 SCIPdebugMsg(
scip,
"Added symmetry breaking constraints: %d.\n", *naddconss);
7119 for (
i = 0;
i < propdata->ngenorbconss; ++
i)
7123 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7133 for (
i = 0;
i < propdata->ngenlinconss; ++
i)
7137 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7147 propdata->ngenorbconss + propdata->ngenlinconss);
7149 for (
i = 0;
i < propdata->nsstconss; ++
i)
7153 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides,
result) );
7162 SCIPdebugMsg(
scip,
"Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
7171 SCIP_Bool infeasible;
7185 propdata->offoundreduction =
TRUE;
7187 else if (
nprop > 0 )
7190 *nfixedvars +=
nprop;
7191 propdata->offoundreduction =
TRUE;
7205 assert( propdata->binvaraffected || ! propdata->ofenabled );
7217 SCIP_Bool infeasible =
FALSE;
7218 SCIP_Longint nodenumber;
7243 if ( propdata->usesymmetry < 0 )
7250 if ( ! propdata->ofenabled )
7254 if ( propdata->nperms == 0 )
7259 if ( nodenumber == propdata->nodenumber )
7261 propdata->nodenumber = nodenumber;
7273 propdata->offoundreduction =
TRUE;
7275 else if (
nprop > 0 )
7278 propdata->offoundreduction =
TRUE;
7303 propdata->usesymmetry = -1;
7304 propdata->symconsenabled =
FALSE;
7305 propdata->triedaddconss =
FALSE;
7306 propdata->nsymresacks = 0;
7307 propdata->norbitopes = 0;
7308 propdata->ofenabled =
FALSE;
7309 propdata->sstenabled =
FALSE;
7310 propdata->lastrestart = 0;
7311 propdata->nfixedzero = 0;
7312 propdata->nfixedone = 0;
7313 propdata->nodenumber = -1;
7314 propdata->offoundreduction =
FALSE;
7376 propdata->npermvars = 0;
7377 propdata->nbinpermvars = 0;
7378 propdata->permvars =
NULL;
7380 propdata->permvarsobj =
NULL;
7382 propdata->nperms = -1;
7383 propdata->nmaxperms = 0;
7384 propdata->perms =
NULL;
7385 propdata->permstrans =
NULL;
7386 propdata->permvarmap =
NULL;
7387 propdata->nonbinpermvarcaptured =
NULL;
7389 propdata->ncomponents = -1;
7390 propdata->ncompblocked = 0;
7391 propdata->components =
NULL;
7392 propdata->componentbegins =
NULL;
7393 propdata->vartocomponent =
NULL;
7394 propdata->componentblocked =
NULL;
7396 propdata->log10groupsize = -1.0;
7397 propdata->nmovedvars = -1;
7398 propdata->binvaraffected =
FALSE;
7399 propdata->computedsymmetry =
FALSE;
7400 propdata->conshdlr_nonlinear =
NULL;
7402 propdata->usesymmetry = -1;
7403 propdata->symconsenabled =
FALSE;
7404 propdata->triedaddconss =
FALSE;
7405 propdata->genorbconss =
NULL;
7406 propdata->genlinconss =
NULL;
7407 propdata->ngenorbconss = 0;
7408 propdata->ngenlinconss = 0;
7409 propdata->genlinconsssize = 0;
7410 propdata->nsymresacks = 0;
7411 propdata->norbitopes = 0;
7412 propdata->isnonlinvar =
NULL;
7414 propdata->ofenabled =
FALSE;
7415 propdata->bg0 =
NULL;
7416 propdata->bg0list =
NULL;
7418 propdata->bg1 =
NULL;
7419 propdata->bg1list =
NULL;
7421 propdata->permvarsevents =
NULL;
7422 propdata->inactiveperms =
NULL;
7423 propdata->nmovedpermvars = -1;
7424 propdata->nmovedbinpermvars = 0;
7425 propdata->nmovedintpermvars = 0;
7426 propdata->nmovedimplintpermvars = 0;
7427 propdata->nmovedcontpermvars = 0;
7428 propdata->lastrestart = 0;
7429 propdata->nfixedzero = 0;
7430 propdata->nfixedone = 0;
7431 propdata->nodenumber = -1;
7432 propdata->offoundreduction =
FALSE;
7434 propdata->sstenabled =
FALSE;
7435 propdata->sstconss =
NULL;
7436 propdata->nsstconss = 0;
7437 propdata->maxnsstconss = 0;
7438 propdata->leaders =
NULL;
7439 propdata->nleaders = 0;
7440 propdata->maxnleaders = 0;
7443 propdata->eventhdlr =
NULL;
7462 tabledata->propdata = propdata;
7469 "propagating/" PROP_NAME "/maxgenerators",
7470 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
7474 "propagating/" PROP_NAME "/checksymmetries",
7475 "Should all symmetries be checked after computation?",
7479 "propagating/" PROP_NAME "/displaynorbitvars",
7480 "Should the number of variables affected by some symmetry be displayed?",
7484 "propagating/" PROP_NAME "/doubleequations",
7485 "Double equations to positive/negative version?",
7491 "Should the symmetry breaking constraints be added to the LP?",
7495 "propagating/" PROP_NAME "/addsymresacks",
7496 "Add inequalities for symresacks for each generator?",
7500 "propagating/" PROP_NAME "/detectorbitopes",
7501 "Should we check whether the components of the symmetry group can be handled by orbitopes?",
7505 "propagating/" PROP_NAME "/detectsubgroups",
7506 "Should we try to detect symmetric subgroups of the symmetry group on binary variables?",
7510 "propagating/" PROP_NAME "/addweaksbcs",
7511 "Should we add weak SBCs for enclosing orbit of symmetric subgroups?",
7515 "propagating/" PROP_NAME "/addconsstiming",
7516 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
7521 "propagating/" PROP_NAME "/ofsymcomptiming",
7522 "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
7526 "propagating/" PROP_NAME "/performpresolving",
7527 "run orbital fixing during presolving?",
7531 "propagating/" PROP_NAME "/recomputerestart",
7532 "recompute symmetries after a restart has occured? (0 = never)",
7536 "propagating/" PROP_NAME "/compresssymmetries",
7537 "Should non-affected variables be removed from permutation to save memory?",
7541 "propagating/" PROP_NAME "/compressthreshold",
7542 "Compression is used if percentage of moved vars is at most the threshold.",
7546 "propagating/" PROP_NAME "/usecolumnsparsity",
7547 "Should the number of conss a variable is contained in be exploited in symmetry detection?",
7551 "propagating/" PROP_NAME "/maxnconsssubgroup",
7552 "maximum number of constraints up to which subgroup structures are detected",
7556 "propagating/" PROP_NAME "/usedynamicprop",
7557 "whether dynamic propagation should be used for full orbitopes",
7561 "propagating/" PROP_NAME "/addstrongsbcs",
7562 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
7566 "propagating/" PROP_NAME "/ssttiebreakrule",
7567 "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)",
7571 "propagating/" PROP_NAME "/sstleaderrule",
7572 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit; 3: var having most conflicting vars in problem)",
7576 "propagating/" PROP_NAME "/sstleadervartype",
7577 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
7578 "if multiple types are allowed, take the one with most affected vars",
7582 "propagating/" PROP_NAME "/addconflictcuts",
7583 "Should Schreier Sims constraints be added if we use a conflict based rule?",
7588 "Should Schreier Sims constraints be added?",
7592 "propagating/" PROP_NAME "/sstmixedcomponents",
7593 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
7597 "propagating/" PROP_NAME "/symfixnonbinaryvars",
7598 "Whether all non-binary variables shall be not affected by symmetries if OF is active?",
7602 "propagating/" PROP_NAME "/onlybinarysymmetry",
7603 "Is only symmetry on binary variables used?",
7607 "propagating/" PROP_NAME "/preferlessrows",
7608 "Shall orbitopes with less rows be preferred in detection?",
7634 SCIP_Real* log10groupsize,
7635 SCIP_Bool* binvaraffected,
7637 int** componentbegins,
7638 int** vartocomponent,
7665 *npermvars = propdata->npermvars;
7666 *permvars = propdata->permvars;
7668 if ( permvarmap !=
NULL )
7669 *permvarmap = propdata->permvarmap;
7671 *nperms = propdata->nperms;
7672 if ( perms !=
NULL )
7674 *perms = propdata->perms;
7678 if ( permstrans !=
NULL )
7680 *permstrans = propdata->permstrans;
7681 assert( *permstrans !=
NULL || *nperms <= 0 );
7684 if ( log10groupsize !=
NULL )
7685 *log10groupsize = propdata->log10groupsize;
7687 if ( binvaraffected !=
NULL )
7688 *binvaraffected = propdata->binvaraffected;
7693 if ( componentbegins !=
NULL )
7694 *componentbegins = propdata->componentbegins;
7696 if ( vartocomponent )
7697 *vartocomponent = propdata->vartocomponent;
7700 *ncomponents = propdata->ncomponents;
7722 return propdata->ofenabled;
7742 if ( propdata->nperms < 0 )
7745 return propdata->nperms;
interface for symmetry computations
const char * SYMsymmetryGetName(void)
const char * SYMsymmetryGetAddName(void)
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
const char * SYMsymmetryGetDesc(void)
const char * SYMsymmetryGetAddDesc(void)
Constraint handler for AND constraints, .
constraint handler for bound disjunction constraints
struct SCIP_NodeData SCIP_NODEDATA
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 symresack constraints
Constraint handler for variable bound constraints .
Constraint handler for XOR constraints, .
static const NodeData nodedata[]
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
SCIP_VAR ** SCIPgetVarsOr(SCIP *scip, SCIP_CONS *cons)
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 SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsOr(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsXor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetIntVarXor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
SCIP_Real SCIPgetRhsNonlinear(SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(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_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPgetRhsXor(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsXor(SCIP *scip, SCIP_CONS *cons)
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_Real SCIPgetLhsNonlinear(SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
@ SCIP_SETPPCTYPE_COVERING
@ SCIP_SETPPCTYPE_PACKING
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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_Bool global, SCIP_Bool *valid)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
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 SCIPgetNFixedVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
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)
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
#define SCIPhashFour(a, b, c, d)
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
static INLINE uint32_t SCIPrealHashCode(double x)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
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_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 SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_Bool SCIPconsIsConflict(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
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_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
SCIP_RETCODE SCIPsimplifyExpr(SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
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 SCIPduplicateBufferArray(scip, ptr, source, num)
#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)
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
int SCIPnodeGetDepth(SCIP_NODE *node)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Bool SCIPinProbing(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)
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)
int SCIPgetNActiveConss(SCIP *scip)
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, 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 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 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 SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
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)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
void SCIPsortIntIntPtr(int *intarray1, int *intarray2, void **ptrarray, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntPtr(int *intarray, void **ptrarray, 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))
static const SCIP_Real scalars[]
internal miscellaneous methods
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
#define PROP_PRESOL_MAXROUNDS
#define PROP_PRESOLTIMING
#define DEFAULT_CONSSADDLP
SCIP_Bool SCIPisOrbitalfixingEnabled(SCIP *scip)
#define DEFAULT_MAXGENERATORS
static SCIP_Bool isLeadervartypeCompatible(SCIP_VAR *var, int leadervartype)
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
#define DEFAULT_DETECTSUBGROUPS
#define DEFAULT_SSTLEADERRULE
#define DEFAULT_PREFERLESSROWS
#define ISSSTINTACTIVE(x)
#define DEFAULT_ADDWEAKSBCS
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
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)
#define DEFAULT_SSTLEADERVARTYPE
#define TABLE_EARLIEST_ORBITALFIXING
#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 selectOrbitLeaderSSTConss(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_HASHMAP *varmap, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool useconflictgraph, SCIP_Bool *success)
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
#define DEFAULT_ONLYBINARYSYMMETRY
static SCIP_RETCODE createConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *permvarmap, SCIP_Bool *success)
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
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
#define DEFAULT_ADDCONFLICTCUTS
#define ISSSTBINACTIVE(x)
static SCIP_RETCODE performOrbitalFixing(SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone)
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
static SCIP_RETCODE SCIPsortOrbitope(SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols)
#define ISSSTIMPLINTACTIVE(x)
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, SCIP_CONSHDLR *conshdlr_nonlinear, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool **isnonlinvar, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *symcodetime, SCIP_Bool *success)
#define DEFAULT_COMPRESSTHRESHOLD
static SCIP_RETCODE addSSTConssOrbitAndUpdateSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds, SCIP_Bool useconflictgraph)
static SCIP_RETCODE updateSymInfoConflictGraphSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_VAR **permvars, int npermvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *varmap, int *orbits, int *orbitbegins, int norbits)
#define DEFAULT_DETECTORBITOPES
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *bg1, int *bg1list, int *nbg1)
#define DEFAULT_ADDCONSSTIMING
#define DEFAULT_SSTADDCUTS
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
#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 int getNSymhandableConss(SCIP *scip, SCIP_CONSHDLR *conshdlr_nonlinear)
#define DEFAULT_USEDYNAMICPROP
#define DEFAULT_RECOMPUTERESTART
#define TABLE_DESC_ORBITALFIXING
static SCIP_Bool hasNonlinearConstraints(SCIP_PROPDATA *propdata)
#define EVENTHDLR_SYMMETRY_NAME
#define DEFAULT_MAXNCONSSSUBGROUP
#define TABLE_POSITION_ORBITALFIXING
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents)
static SCIP_RETCODE addStrongSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
static SCIP_RETCODE collectCoefficients(SCIP *scip, SCIP_Bool doubleequations, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata, int *nconssforvar)
#define ISORBITALFIXINGACTIVE(x)
#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)
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds)
#define TABLE_NAME_ORBITALFIXING
int SCIPgetSymmetryNGenerators(SCIP *scip)
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
#define DEFAULT_SYMFIXNONBINARYVARS
#define DEFAULT_OFSYMCOMPTIMING
static SCIP_RETCODE tryAddSymmetryHandlingConss(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
static SCIP_RETCODE setSymmetryData(SCIP *scip, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
static SCIP_RETCODE setSymmetryMethodEnabledValues(SCIP_PROPDATA *propdata)
#define ISSSTCONTACTIVE(x)
#define DEFAULT_DISPLAYNORBITVARS
#define EVENTHDLR_SYMMETRY_DESC
#define PROP_PRESOL_PRIORITY
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
#define DEFAULT_USECOLUMNSPARSITY
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes)
propagator for symmetry handling
public functions to work with algebraic expressions
public methods for data structures
methods for handling symmetries
#define SCIP_EVENTTYPE_GUBCHANGED
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_GLBCHANGED
#define SCIP_EXPRITER_ENTEREXPR
enum SCIP_BoundType SCIP_BOUNDTYPE
#define SCIP_DECL_HASHKEYEQ(x)
#define SCIP_DECL_SORTINDCOMP(x)
#define SCIP_DECL_HASHGETKEY(x)
#define SCIP_DECL_HASHKEYVAL(x)
#define SCIP_DECL_PROPEXITPRE(x)
#define SCIP_DECL_PROPFREE(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_STAGE_INITPRESOLVE
#define SYM_COMPUTETIMING_DURINGPRESOL
#define SYM_HANDLETYPE_ORBITALFIXING
@ SCIP_LEADERRULE_MAXCONFLICTS
@ SCIP_LEADERRULE_LASTINORBIT
@ SCIP_LEADERRULE_MAXCONFLICTSINORBIT
@ SCIP_LEADERRULE_FIRSTINORBIT
@ SCIP_LEADERTIEBREAKRULE_MAXORBIT
@ SCIP_LEADERTIEBREAKRULE_MINORBIT
@ SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT
enum SYM_Rhssense SYM_RHSSENSE
#define SYM_HANDLETYPE_SYMBREAK
#define SYM_COMPUTETIMING_AFTERPRESOL
#define SYM_HANDLETYPE_SST
@ SYM_SENSE_BOUNDIS_TYPE_2
@ SYM_SENSE_BOUNDIS_TYPE_1
#define SCIP_DECL_TABLEFREE(x)
struct SCIP_TableData SCIP_TABLEDATA
#define SCIP_DECL_TABLEOUTPUT(x)
#define SCIP_PROPTIMING_ALWAYS
@ SCIP_VARTYPE_CONTINUOUS
@ SCIP_BOUNDCHGTYPE_BRANCHING
enum SCIP_Vartype SCIP_VARTYPE