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;
243 int* componentbegins;
247 unsigned* componentblocked;
289 int maxnconsssubgroup;
294 int recomputerestart;
304 int sstleadervartype;
320 struct SCIP_ConflictData
325 int nconflictinorbit;
332 typedef struct SCIP_ConflictData SCIP_CONFLICTDATA;
342 else if ( elem1 > elem2 )
363 assert( arr1 !=
NULL || narr1 == 0 );
364 assert( narr1 >= 0 );
365 assert( arr2 !=
NULL || narr2 == 0 );
366 assert( narr2 >= 0 );
367 assert( compfunc !=
NULL );
380 cmp = compfunc(arr1[it1], arr2[it2]);
386 if ( ++it1 >= narr1 )
395 if ( ++it2 >= narr2 )
408 assert( it1 >= narr1 || it2 >= narr2 );
433 assert( scip !=
NULL );
434 assert( perm !=
NULL );
435 assert( 0 <= baseidx );
438 assert( covered !=
NULL );
441 if ( perm[baseidx] == baseidx || covered[baseidx] )
444 varidx = baseidx >= nvars ? baseidx - nvars : baseidx;
448 covered[baseidx] =
TRUE;
449 while ( j != baseidx )
452 varidx = j >= nvars ? j - nvars : j;
477 assert( scip !=
NULL );
478 assert( propdata !=
NULL );
479 assert( propdata->nperms > 0 );
480 assert( propdata->permvars !=
NULL );
481 assert( propdata->npermvars > 0 );
484 npermvars = propdata->npermvars;
488 SCIPinfoMessage(scip,
NULL,
"Display permutations as signed permutations (allowing translations)\n");
492 for (p = 0; p < propdata->nperms; ++p)
495 perm = propdata->perms[p];
497 for (i = 0; i < permlen; ++i)
502 for (i = 0; i < permlen; ++i)
528 assert( scip !=
NULL );
529 assert( propdata !=
NULL );
530 assert( propdata->nperms > 0 );
531 assert( propdata->permvars !=
NULL );
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] )
547 SCIPinfoMessage(scip,
NULL,
" Symmetries are displayed as signed permutations (allowing translations).\n");
551 comppermlen = propdata->componenthassignedperm[c] ? 2 * npermvars : npermvars;
553 for (p = propdata->componentbegins[c], cnt = 0; p < propdata->componentbegins[c + 1]; ++p, ++cnt)
556 perm = propdata->perms[propdata->components[p]];
558 for (i = 0; i < comppermlen; ++i)
563 for (i = 0; i < comppermlen; ++i)
583 assert( propdata !=
NULL );
585 if ( propdata->nperms == -1 )
587 SCIPinfoMessage(scip,
NULL,
"Cannot display symmetries. Symmetries have not been computed yet.\n");
589 else if ( propdata->nperms == 0 )
593 else if ( propdata->ncomponents < 0 )
614 struct SCIP_TableData
629 assert( scip !=
NULL );
630 assert( table !=
NULL );
633 assert( tabledata !=
NULL );
634 assert( tabledata->propdata !=
NULL );
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 )
675 assert( tabledata !=
NULL );
779 if ( G1->
lhs[perm1] < G2->
lhs[perm2] )
781 if ( G1->
lhs[perm1] > G2->
lhs[perm2] )
784 if ( G1->
rhs[perm1] < G2->
rhs[perm2] )
786 if ( G1->
rhs[perm1] > G2->
rhs[perm2] )
851 assert( propdata->permvarmap ==
NULL );
852 assert( propdata->genorbconss ==
NULL );
853 assert( propdata->genlinconss ==
NULL );
854 assert( propdata->ngenlinconss == 0 );
855 assert( propdata->ngenorbconss == 0 );
856 assert( propdata->genorbconsssize == 0 );
857 assert( propdata->genlinconsssize == 0 );
858 assert( propdata->sstconss ==
NULL );
859 assert( propdata->leaders ==
NULL );
861 assert( propdata->permvardomaincenter ==
NULL );
862 assert( propdata->permvars ==
NULL );
863 assert( propdata->perms ==
NULL );
864 assert( propdata->permstrans ==
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 );
875 assert( propdata->binvaraffected ==
FALSE );
876 assert( propdata->isnonlinvar ==
NULL );
878 assert( propdata->componenthassignedperm ==
NULL );
879 assert( propdata->componentblocked ==
NULL );
880 assert( propdata->componentbegins ==
NULL );
881 assert( propdata->components ==
NULL );
882 assert( propdata->ncomponents == -1 );
883 assert( propdata->ncompblocked == 0 );
897 assert( scip !=
NULL );
898 assert( propdata !=
NULL );
901 if ( propdata->orbitalreddata !=
NULL )
905 if ( propdata->orbitopalreddata !=
NULL )
909 if ( propdata->lexreddata !=
NULL )
927 assert( scip !=
NULL );
928 assert( propdata !=
NULL );
932 if ( propdata->permvarmap !=
NULL )
938 for (i = 0; i < propdata->npermvars; ++i)
940 assert( propdata->permvars[i] !=
NULL );
945 if ( propdata->permstrans !=
NULL )
947 assert( propdata->nperms > 0 );
948 assert( propdata->permvars !=
NULL );
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)
983 assert( propdata->genlinconss[i] !=
NULL );
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)
1000 assert( propdata->sstconss[i] !=
NULL );
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 );
1025 assert( propdata->vartocomponent !=
NULL );
1026 assert( propdata->componentbegins !=
NULL );
1027 assert( propdata->components !=
NULL );
1035 propdata->ncomponents = -1;
1036 propdata->ncompblocked = 0;
1040 if ( propdata->nperms > 0 )
1044 assert( propdata->permvars !=
NULL );
1047 permlen = 2 * propdata->npermvars;
1049 permlen = propdata->npermvars;
1054 if ( propdata->perms !=
NULL )
1056 for (i = 0; i < propdata->nperms; ++i)
1065 propdata->npermvars = 0;
1066 propdata->nbinpermvars = 0;
1067 propdata->nperms = -1;
1068 propdata->nmaxperms = 0;
1069 propdata->nmovedpermvars = -1;
1070 propdata->nmovedbinpermvars = 0;
1071 propdata->nmovedintpermvars = 0;
1072 propdata->nmovedimplintpermvars = 0;
1073 propdata->nmovedcontpermvars = 0;
1074 propdata->nmovedvars = -1;
1075 propdata->log10groupsize = -1.0;
1076 propdata->binvaraffected =
FALSE;
1077 propdata->isnonlinvar =
NULL;
1079 propdata->nperms = -1;
1083 propdata->computedsymmetry =
FALSE;
1084 propdata->compressed =
FALSE;
1095 int* consarrsizeptr,
1101 assert( scip !=
NULL );
1102 assert( consarrptr !=
NULL );
1103 assert( consarrsizeptr !=
NULL );
1104 assert( consarrsizereq > 0 );
1105 assert( *consarrsizeptr >= 0 );
1106 assert( (*consarrsizeptr == 0) == (*consarrptr ==
NULL) );
1109 if ( consarrsizereq <= *consarrsizeptr )
1114 assert( newsize > *consarrsizeptr );
1117 if ( *consarrptr ==
NULL )
1126 *consarrsizeptr = newsize;
1157 assert( scip !=
NULL );
1158 assert( vars !=
NULL );
1159 assert( nvars > 0 );
1160 assert( permvars !=
NULL );
1161 assert( npermvars !=
NULL );
1162 assert( nbinpermvars !=
NULL );
1163 assert( perms !=
NULL );
1164 assert( nperms > 0 );
1165 assert( binvaraffected !=
NULL );
1166 assert(
SCIPisGE(scip, compressthreshold, 0.0) );
1167 assert(
SCIPisLE(scip, compressthreshold, 1.0) );
1168 assert( compressed !=
NULL );
1173 *nbinpermvars = nbinvars;
1174 *binvaraffected =
FALSE;
1175 *compressed =
FALSE;
1181 int* labelmovedvars;
1182 int* labeltopermvaridx;
1183 int nbinvarsaffected = 0;
1185 assert( nmovedvars !=
NULL );
1192 for (i = 0; i < nvars; ++i)
1194 labelmovedvars[i] = -1;
1196 for (p = 0; p < nperms; ++p)
1198 if ( perms[p][i] != i )
1200 labeltopermvaridx[*nmovedvars] = i;
1201 labelmovedvars[i] = (*nmovedvars)++;
1210 if ( nbinvarsaffected > 0 )
1211 *binvaraffected =
TRUE;
1215 if ( *nmovedvars > 0 &&
SCIPisLE(scip, percentagemovedvars, compressthreshold) )
1218 for (p = 0; p < nperms; ++p)
1221 for (i = 0; i < *nmovedvars; ++i)
1223 assert( i <= labeltopermvaridx[i] );
1224 if ( perms[p][labeltopermvaridx[i]] >= nvars )
1230 imgvaridx = perms[p][labeltopermvaridx[i]] - nvars;
1231 perms[p][i] = labelmovedvars[imgvaridx] + *nmovedvars;
1233 assert( 0 <= perms[p][i] && perms[p][i] < 2 * (*nmovedvars) );
1236 perms[p][i] = labelmovedvars[perms[p][labeltopermvaridx[i]]];
1251 for (i = 0; i < *nmovedvars; ++i)
1253 (*permvars)[i] = vars[labeltopermvaridx[i]];
1255 *npermvars = *nmovedvars;
1256 *nbinpermvars = nbinvarsaffected;
1267 for (i = 0; i < nbinvars; ++i)
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);
1301 assert( conshdlr !=
NULL );
1326 assert( conshdlrs !=
NULL );
1329 for (c = 0; c < nconshdlrs; ++c)
1331 conshdlr = conshdlrs[c];
1332 assert( conshdlr !=
NULL );
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",
1386 SCIPwarningMessage(scip,
"Expression handler %s does not implement the EXPRGETSYMDATA callback.\n" 1387 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n" 1413 assert( scip !=
NULL );
1414 assert( nopnodes !=
NULL );
1415 assert( nvalnodes !=
NULL );
1416 assert( nconsnodes !=
NULL );
1417 assert( nedges !=
NULL );
1422 assert( conss !=
NULL || nconss == 0 );
1424 *nconsnodes = nconss;
1429 for (c = 0; c < nconss; ++c)
1457 depth = (int) log2((
double) num);
1458 expval = (int) exp2((
double) (depth + 1));
1459 numnodes =
MIN(expval, 100);
1461 *nopnodes += numnodes;
1462 *nvalnodes +=
MAX((
int) 0.1 * numnodes, 1);
1477 *nopnodes += num - 1;
1486 if ( nvars <= 100000 )
1487 *nedges = 100 * nvars;
1488 else if ( nvars <= 1000000 )
1489 *nedges = 32 * nvars;
1490 else if ( nvars <= 16700000 )
1491 *nedges = 16 * nvars;
1493 *nedges = INT_MAX / 10;
1521 #ifdef SCIP_DISPLAY_SYM_CHECK 1526 assert( scip !=
NULL );
1527 assert( perms !=
NULL );
1528 assert( nperms > 0 );
1529 assert( npermvars > 0 );
1534 assert( conss !=
NULL );
1538 assert( nsymvars == npermvars );
1542 for (c = 0; c < nconss; ++c)
1564 for (c = 0; c < nconss; ++c)
1569 SCIPsort(graphperm, SYMsortSymgraphs, graphs, nconss);
1572 for (c = 1; c < nconss; ++c)
1574 if (
compareSymgraphs(scip, graphs[graphperm[c]], graphs[graphperm[c-1]]) != 0 )
1575 groupbegins[ngroups++] = c;
1577 groupbegins[ngroups] = nconss;
1580 for (c = 0; c < nconss; ++c)
1585 #ifdef SCIP_DISPLAY_SYM_CHECK 1591 for (p = 0; p < nperms; ++p)
1596 #ifdef SCIP_DISPLAY_SYM_CHECK 1600 for (i = 0; i < permlen; ++i)
1605 for (i = 0; i < permlen; ++i)
1607 SCIPinfoMessage(scip,
NULL,
"Check whether every constraint has a symmetric counterpart.\n");
1611 for (g = 0; g < ngroups; ++g)
1613 for (c = groupbegins[g]; c < groupbegins[g+1]; ++c)
1615 #ifdef SCIP_DISPLAY_SYM_CHECK 1626 #ifdef SCIP_DISPLAY_SYM_CHECK 1635 for (d = groupbegins[g]; d < groupbegins[g+1] && ! found; ++d)
1639 #ifdef SCIP_DISPLAY_SYM_CHECK 1640 SCIPinfoMessage(scip,
NULL,
"\tconstraint is %ssymmetric to constraint %d\n\t", !found ?
"not " :
"", d);
1650 #ifdef SCIP_DISPLAY_SYM_CHECK 1660 #ifdef SCIP_DISPLAY_SYM_CHECK 1667 for (c = nconss - 1; c >= 0; --c)
1712 assert( scip !=
NULL );
1713 assert( permvars !=
NULL );
1714 assert( npermvars !=
NULL );
1715 assert( nbinpermvars !=
NULL );
1716 assert( perms !=
NULL );
1717 assert( nperms !=
NULL );
1718 assert( nmaxperms !=
NULL );
1719 assert( nmovedvars !=
NULL );
1720 assert( binvaraffected !=
NULL );
1721 assert( compressed !=
NULL );
1722 assert( log10groupsize !=
NULL );
1723 assert( symcodetime !=
NULL );
1724 assert( success !=
NULL );
1734 *binvaraffected =
FALSE;
1735 *compressed =
FALSE;
1736 *log10groupsize = 0;
1748 assert( conss !=
NULL || nconss == 0 );
1762 nopnodes, nvalnodes, nconsnodes, nedges) );
1765 for (c = 0; c < nconss && *success; ++c)
1800 perms, log10groupsize, symcodetime) );
1802 if ( checksymmetries && *nperms > 0 )
1817 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1818 compresssymmetries, compressthreshold, compressed) );
1838 assert( symmetry !=
NULL );
1839 assert( vars !=
NULL );
1840 assert( nvars > 0 );
1842 for (v = 0; v < nvars; ++v)
1845 if ( symmetry[v] >= nvars )
1872 int* componentbegins;
1877 assert( scip !=
NULL );
1878 assert( propdata !=
NULL );
1879 assert( propdata->ncomponents > 0 );
1880 assert( propdata->components !=
NULL );
1881 assert( propdata->componentbegins !=
NULL );
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;
1916 assert( scip !=
NULL );
1917 assert( propdata !=
NULL );
1920 assert( propdata->nperms >= 0 );
1923 if ( propdata->ncomponents >= 0 )
1927 assert( propdata->ncomponents == -1 );
1928 assert( propdata->components ==
NULL );
1929 assert( propdata->componentbegins ==
NULL );
1930 assert( propdata->vartocomponent ==
NULL );
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 1944 assert( propdata->components !=
NULL );
1945 assert( propdata->componentbegins !=
NULL );
1946 assert( propdata->ncomponents > 0 );
1950 assert( propdata->componenthassignedperm !=
NULL );
1965 assert( scip !=
NULL );
1966 assert( propdata !=
NULL );
1969 assert( propdata->nperms >= 0 );
1972 if ( propdata->permvarmap !=
NULL )
1979 for (v = 0; v < propdata->npermvars; ++v)
1998 assert( scip !=
NULL );
1999 assert( propdata !=
NULL );
2002 assert( propdata->nperms >= 0 );
2005 if ( propdata->permstrans !=
NULL )
2009 assert( 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];
2032 assert( scip !=
NULL );
2033 assert( propdata !=
NULL );
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;
2148 assert( scip !=
NULL );
2149 assert( propdata !=
NULL );
2150 assert( propdata->usesymmetry >= 0 );
2164 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2192 if ( ! (type & symspecrequire) )
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 );
2212 assert( propdata->permvars ==
NULL );
2213 assert( propdata->nperms < 0 );
2214 assert( propdata->nmaxperms == 0 );
2215 assert( propdata->perms ==
NULL );
2219 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2226 (symspecrequirefixed & (
int)
SYM_SPEC_REAL) != 0 ?
'+' :
'-');
2229 if ( symspecrequire & symspecrequirefixed )
2233 maxgenerators = propdata->maxgenerators;
2238 propdata->compresssymmetries, propdata->compressthreshold,
2239 maxgenerators, symspecrequirefixed, propdata->checksymmetries, &propdata->permvars,
2240 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2241 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2242 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2243 &propdata->log10groupsize, &symcodetime, &successful) );
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)
2332 int** orbitopevaridx,
2346 int ntestedperms = 0;
2350 assert( scip !=
NULL );
2351 assert( permvars !=
NULL );
2352 assert( perms !=
NULL );
2353 assert( activeperms !=
NULL );
2354 assert( orbitopevaridx !=
NULL );
2355 assert( columnorder !=
NULL );
2356 assert( nusedelems !=
NULL );
2357 assert( isorbitope !=
NULL );
2358 assert( nactiveperms > 0 );
2359 assert( ntwocycles > 0 );
2360 assert( npermvars > 0 );
2361 assert( activevars ==
NULL || (0 <= nactiveperms && nactiveperms < npermvars) );
2364 if ( nusedcols !=
NULL )
2373 while ( ! foundperm )
2377 assert( ntestedperms < nactiveperms );
2379 permidx = activeperms[ntestedperms];
2381 for (j = 0; j < npermvars; ++j)
2383 if ( activevars !=
NULL && ! activevars[j] )
2386 assert( activevars ==
NULL || activevars[perms[permidx][j]] );
2389 if ( perms[permidx][j] > j )
2394 rowisbinary[row] =
TRUE;
2396 orbitopevaridx[row][0] = j;
2397 orbitopevaridx[row++][1] = perms[permidx][j];
2399 ++(nusedelems[perms[permidx][j]]);
2404 if ( row == ntwocycles )
2412 if ( row != ntwocycles )
2414 *isorbitope =
FALSE;
2419 usedperm[ntestedperms - 1] =
TRUE;
2429 for (j = ntestedperms; j < nactiveperms; ++j)
2434 if ( nusedperms == nactiveperms )
2441 perms[activeperms[j]],
TRUE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2445 *isorbitope =
FALSE;
2452 coltoextend = nfilledcols;
2453 columnorder[nfilledcols++] = -1;
2458 if ( ! *isorbitope )
2465 for (j = ntestedperms; j < nactiveperms; ++j)
2470 if ( nusedperms == nactiveperms )
2477 perms[activeperms[j]],
FALSE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2481 *isorbitope =
FALSE;
2488 coltoextend = nfilledcols;
2489 columnorder[nfilledcols] = 1;
2495 if ( activevars ==
NULL && nusedperms < nactiveperms )
2496 *isorbitope =
FALSE;
2498 if ( nusedcols !=
NULL )
2499 *nusedcols = nfilledcols;
2500 assert( ! *isorbitope || activevars ==
NULL || nusedperms < nfilledcols );
2519 int* componentbegins;
2525 assert( scip !=
NULL );
2526 assert( propdata !=
NULL );
2527 assert( compidx >= 0 );
2528 assert( compidx < propdata->ncomponents );
2529 assert( genorder !=
NULL );
2530 assert( *genorder !=
NULL );
2531 assert( ntwocycleperms !=
NULL );
2532 assert( propdata->computedsymmetry );
2533 assert( propdata->nperms > 0 );
2534 assert( propdata->perms !=
NULL );
2535 assert( propdata->npermvars > 0 );
2536 assert( propdata->ncomponents > 0 );
2537 assert( propdata->components !=
NULL );
2538 assert( propdata->componentbegins !=
NULL );
2540 perms = propdata->perms;
2541 npermvars = propdata->npermvars;
2543 componentbegins = propdata->componentbegins;
2544 npermsincomp = componentbegins[compidx + 1] - componentbegins[compidx];
2545 *ntwocycleperms = npermsincomp;
2549 for (i = 0; i < npermsincomp; ++i)
2554 perm = perms[
components[componentbegins[compidx] + i]];
2559 if ( ntwocycles[i] == 0 )
2562 if ( propdata->preferlessrows )
2563 ntwocycles[i] = npermvars;
2566 --(*ntwocycleperms);
2568 else if ( ! propdata->preferlessrows )
2569 ntwocycles[i] = - ntwocycles[i];
2593 int** graphcomponents,
2594 int** graphcompbegins,
2595 int** compcolorbegins,
2596 int* ngraphcomponents,
2609 int* componentbegins;
2610 int* componentslastperm;
2618 assert( scip !=
NULL );
2619 assert( propdata !=
NULL );
2620 assert( graphcomponents !=
NULL );
2621 assert( graphcompbegins !=
NULL );
2622 assert( compcolorbegins !=
NULL );
2623 assert( ngraphcomponents !=
NULL );
2624 assert( ncompcolors !=
NULL );
2625 assert( genorder !=
NULL );
2626 assert( usedperms !=
NULL );
2627 assert( nusedperms !=
NULL );
2628 assert( usedpermssize > 0 );
2629 assert( permused !=
NULL );
2630 assert( ntwocycleperms >= 0 );
2631 assert( compidx >= 0 );
2632 assert( compidx < propdata->ncomponents );
2633 assert( propdata->computedsymmetry );
2634 assert( propdata->nperms > 0 );
2635 assert( propdata->perms !=
NULL );
2636 assert( propdata->npermvars > 0 );
2637 assert( propdata->ncomponents > 0 );
2638 assert( propdata->components !=
NULL );
2639 assert( propdata->componentbegins !=
NULL );
2640 assert( ! propdata->componentblocked[compidx] );
2642 perms = propdata->perms;
2643 npermvars = propdata->npermvars;
2645 componentbegins = propdata->componentbegins;
2648 assert( ntwocycleperms <= componentbegins[compidx + 1] - componentbegins[compidx] );
2654 for (k = 0; k < npermvars; ++k)
2655 componentslastperm[k] = -1;
2657 for (j = 0; j < ntwocycleperms; ++j)
2660 int firstcolor = -1;
2663 perm = perms[
components[componentbegins[compidx] + genorder[j]]];
2664 assert( perm !=
NULL );
2667 for (k = 0; k < npermvars; ++k)
2676 assert( perm[img] == k );
2684 if ( comp1 == comp2 )
2687 if ( firstcolor < 0 )
2692 componentslastperm[comp1] = j;
2699 if ( componentslastperm[comp1] == j || componentslastperm[comp2] == j )
2706 if ( color1 == color2 )
2709 componentslastperm[comp1] = j;
2710 componentslastperm[comp2] = j;
2712 if ( firstcolor < 0 )
2713 firstcolor = color1;
2717 if ( k < npermvars )
2721 if ( firstcolor == -1 )
2725 if ( *nusedperms >= usedpermssize )
2728 assert( newsize > usedpermssize );
2732 usedpermssize = newsize;
2735 (*usedperms)[*nusedperms] =
components[componentbegins[compidx] + genorder[j]];
2737 permused[genorder[j]] =
TRUE;
2740 for (k = 0; k < npermvars; ++k)
2749 assert( perm[img] == k );
2758 if ( comp1 == comp2 )
2764 if ( color1 != color2 )
2788 for (j = 0; j < npermvars; ++j)
2797 (*graphcomponents)[j] = j;
2801 SCIPsort(*graphcomponents, SYMsortGraphCompVars, (
void*) &graphcompvartype, npermvars);
2810 (*graphcompbegins)[0] = 0;
2811 (*compcolorbegins)[0] = 0;
2814 for (j = 1; j < npermvars; ++j)
2819 idx1 = (*graphcomponents)[j];
2820 idx2 = (*graphcomponents)[j-1];
2822 assert( graphcompvartype.
colors[idx1] >= graphcompvartype.
colors[idx2] );
2826 (*graphcompbegins)[nextcomp] = j;
2828 if ( graphcompvartype.
colors[idx1] > graphcompvartype.
colors[idx2] )
2830 (*compcolorbegins)[nextcolor] = nextcomp;
2837 assert( nextcomp == *ngraphcomponents );
2838 assert( nextcolor == *ncompcolors );
2840 (*compcolorbegins)[nextcolor] = *ngraphcomponents;
2841 (*graphcompbegins)[nextcomp] = npermvars;
2859 int* compcolorbegins,
2860 int* graphcompbegins,
2861 int* graphcomponents,
2866 int* compidxfirstrow,
2869 int* maxnvarslexorder,
2877 int** orbitopevaridx;
2884 int nactivevars = 0;
2889 assert( scip !=
NULL );
2890 assert( propdata !=
NULL );
2891 assert( usedperms !=
NULL );
2892 assert( compcolorbegins !=
NULL );
2893 assert( graphcompbegins !=
NULL );
2894 assert( graphcomponents !=
NULL );
2895 assert( nusedperms > 0 );
2896 assert( nrows > 0 );
2897 assert( ncols > 0 );
2898 assert( lexorder !=
NULL );
2899 assert( nvarslexorder !=
NULL );
2900 assert( maxnvarslexorder !=
NULL );
2909 for (k = 0; k < nrows; ++k)
2916 for (k = 0; k < ncols; ++k)
2917 columnorder[k] = ncols + 1;
2923 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1]; ++k)
2929 compstart = graphcompbegins[k];
2930 firstvar = propdata->permvars[graphcomponents[compstart]];
2935 for (l = 0; l < ncols; ++l)
2939 varidx = graphcomponents[compstart + l];
2940 assert( ! activevars[varidx] );
2942 activevars[varidx] =
TRUE;
2948 assert( nactivevars == nrows * ncols );
2960 propdata->perms, usedperms, nrows, nusedperms, orbitopevaridx, columnorder,
2961 nusedelems, &ngencols,
NULL, &isorbitope, activevars) );
2970 for (k = nrows - 1; k >= 0; --k)
2990 if ( firstvaridx !=
NULL )
2992 if ( columnorder[ngencols-1] > -1 )
2993 *firstvaridx = orbitopevaridx[0][ngencols-1];
2995 *firstvaridx = orbitopevaridx[0][1];
2999 if ( compidxfirstrow !=
NULL && firstvaridx !=
NULL )
3001 *compidxfirstrow = -1;
3003 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3009 compstart = graphcompbegins[k];
3010 firstvar = propdata->permvars[graphcomponents[compstart]];
3018 for (l = 0; l < ncols; ++l)
3020 if ( graphcomponents[compstart + l] == *firstvaridx )
3022 *compidxfirstrow = k;
3027 assert( *compidxfirstrow > -1 );
3032 for (k = 0; k < nrows; ++k)
3039 propdata->permvars, propdata->npermvars, orbitopevaridx, columnorder,
3040 nusedelems,
NULL, &infeasible,
TRUE, lexorder, nvarslexorder, maxnvarslexorder) );
3042 assert( ! infeasible );
3043 assert( firstvaridx ==
NULL || propdata->permvars[*firstvaridx] == orbitopevarmatrix[0][0] );
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)
3078 int* graphcompbegins,
3079 int* graphcomponents,
3089 assert( scip !=
NULL );
3090 assert( propdata !=
NULL );
3091 assert( graphcompbegins !=
NULL );
3092 assert( graphcomponents !=
NULL );
3093 assert( graphcompidx >= 0 );
3094 assert( ! storelexorder || lexorder !=
NULL );
3095 assert( ! storelexorder || nvarsorder !=
NULL );
3096 assert( ! storelexorder || maxnvarsorder !=
NULL );
3099 if ( storelexorder )
3101 if ( *maxnvarsorder == 0 )
3103 *maxnvarsorder = graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3110 assert( *nvarsorder == *maxnvarsorder );
3112 *maxnvarsorder += graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3117 (*lexorder)[*nvarsorder++] = graphcomponents[graphcompbegins[graphcompidx]];
3121 for (k = graphcompbegins[graphcompidx]+1; k < graphcompbegins[graphcompidx+1]; ++k)
3128 vars[0] = propdata->permvars[graphcomponents[k-1]];
3129 vars[1] = propdata->permvars[graphcomponents[k]];
3131 if ( storelexorder )
3132 (*lexorder)[*nvarsorder++] = graphcomponents[k];
3142 #ifdef SCIP_MORE_DEBUG 3149 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3150 propdata->genlinconss[propdata->ngenlinconss] = cons;
3151 ++propdata->ngenlinconss;
3162 int* compcolorbegins,
3163 int* graphcompbegins,
3164 int* graphcomponents,
3166 int* chosencomppercolor,
3167 int* firstvaridxpercolor,
3182 int orbitsize[2] = {1, 1};
3184 int chosencolor = -1;
3188 assert( scip !=
NULL );
3189 assert( propdata !=
NULL );
3190 assert( compcolorbegins !=
NULL );
3191 assert( graphcompbegins !=
NULL );
3192 assert( graphcomponents !=
NULL );
3193 assert( firstvaridxpercolor !=
NULL );
3194 assert( chosencomppercolor !=
NULL );
3195 assert( naddedconss !=
NULL );
3196 assert( symgrpcompidx >= 0 );
3197 assert( symgrpcompidx < propdata->ncomponents );
3198 assert( ! storelexorder || lexorder !=
NULL );
3199 assert( ! storelexorder || nvarsorder !=
NULL );
3200 assert( ! storelexorder || maxnvarsorder !=
NULL );
3210 if ( lexorder ==
NULL || *lexorder ==
NULL )
3213 varsinlexorder =
NULL;
3217 assert( *maxnvarsorder >= 0 );
3218 assert( *nvarsorder >= 0 );
3222 for (k = 0; k < *nvarsorder; ++k)
3226 assert((*lexorder)[k] >= 0);
3234 if ( ncompcolors > 0 )
3238 for (j = 0; j < ncompcolors; ++j)
3245 if ( chosencomppercolor[j] < 0 )
3248 assert( firstvaridxpercolor[j] >= 0 );
3250 graphcomp = chosencomppercolor[j];
3251 graphcompsize = graphcompbegins[graphcomp+1] - graphcompbegins[graphcomp];
3252 varidx = firstvaridxpercolor[j];
3253 assert(varidx >= 0);
3257 if ( varfound[varidx] || graphcompsize == propdata->npermvars )
3261 if ( varsinlexorder !=
NULL 3263 && lexorder !=
NULL && *lexorder !=
NULL && *maxnvarsorder > 0 && *nvarsorder > 0
3264 && (*lexorder)[0] != varidx )
3268 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3270 assert( 0 <= graphcomponents[k] && graphcomponents[k] < propdata->npermvars );
3272 usedvars[graphcomponents[k]] =
TRUE;
3276 propdata->permstrans, propdata->components, propdata->componentbegins,
3277 usedvars, varfound, varidx, symgrpcompidx,
3278 orbit[activeorb], &orbitsize[activeorb]) );
3280 assert( orbit[activeorb][0] == varidx );
3282 if ( orbitsize[activeorb] > orbitsize[1 - activeorb] )
3285 activeorb = 1 - activeorb;
3290 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3291 usedvars[graphcomponents[k]] =
FALSE;
3295 if ( chosencolor > -1 )
3298 activeorb = 1 - activeorb;
3300 assert( orbit[activeorb][0] == firstvaridxpercolor[chosencolor] );
3301 vars[0] = propdata->permvars[orbit[activeorb][0]];
3303 assert( chosencolor > -1 );
3304 SCIPdebugMsg(scip,
" adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3306 *naddedconss = orbitsize[activeorb] - 1;
3309 for (j = 1; j < orbitsize[activeorb]; ++j)
3314 vars[1] = propdata->permvars[orbit[activeorb][j]];
3324 #ifdef SCIP_MORE_DEBUG 3331 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3332 propdata->genlinconss[propdata->ngenlinconss] = cons;
3333 ++propdata->ngenlinconss;
3337 if ( storelexorder )
3341 varidx = orbit[activeorb][0];
3342 assert(varidx >= 0);
3344 if ( *maxnvarsorder == 0 )
3350 (*lexorder)[(*nvarsorder)++] = varidx;
3354 assert( *nvarsorder == *maxnvarsorder );
3355 assert( varsinlexorder !=
NULL );
3356 assert( lexorder !=
NULL );
3357 assert( *lexorder !=
NULL );
3360 if ( varidx == (*lexorder)[0] )
3377 for (k = *maxnvarsorder - 1; k >= 1; --k)
3378 (*lexorder)[k] = (*lexorder)[k - 1];
3380 (*lexorder)[0] = varidx;
3386 SCIPdebugMsg(scip,
" no further weak sbcs are valid\n");
3390 if ( varsinlexorder !=
NULL )
3404 int** modifiedperms,
3423 assert( scip !=
NULL );
3424 assert( origperms !=
NULL );
3425 assert( modifiedperms !=
NULL );
3426 assert( nperms > 0 );
3427 assert( origpermvars !=
NULL );
3428 assert( modifiedpermvars !=
NULL );
3429 assert( npermvars > 0 );
3430 assert( leaders !=
NULL );
3431 assert( nleaders > 0 );
3435 for (i = 0; i < npermvars; ++i)
3440 for (i = 0; i < npermvars; ++i)
3441 posinpermvar[i] = i;
3445 for (l = 0; l < nleaders; ++l)
3447 leader = leaders[l];
3448 curposleader = posinpermvar[leader];
3449 varidx = permvaridx[curposleader];
3450 lidx = permvaridx[l];
3453 permvaridx[curposleader] = lidx;
3454 permvaridx[l] = varidx;
3457 posinpermvar[lidx] = curposleader;
3458 posinpermvar[leader] = l;
3462 for (i = 0; i < npermvars; ++i)
3463 modifiedpermvars[i] = origpermvars[permvaridx[i]];
3466 for (p = 0; p < nperms; ++p)
3468 for (i = 0; i < npermvars; ++i)
3469 modifiedperms[p][i] = posinpermvar[origperms[p][permvaridx[i]]];
3485 int* graphcomponents,
3486 int* graphcompbegins,
3487 int* compcolorbegins,
3497 assert( graphcompbegins !=
NULL );
3498 assert( compcolorbegins !=
NULL );
3499 assert( ncompcolors >= 0 );
3500 assert( symcompsize > 0 );
3502 for (j = 0; j < ncompcolors; ++j)
3505 int largestcompsize = 0;
3510 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3514 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3518 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3521 if ( largestcompsize < 1 )
3526 largestcompsize = compsize;
3528 else if ( compsize != largestcompsize )
3531 firstvar = permvars[graphcomponents[graphcompbegins[k]]];
3539 if ( k == compcolorbegins[j+1] )
3545 ncols = graphcompbegins[compcolorbegins[j] + 1] - graphcompbegins[compcolorbegins[j]];
3547 threshold = 0.7 * (
SCIP_Real) symcompsize;
3550 if ( nbinrows <= 2 * ncols || (nbinrows <= 8 * ncols && nbinrows < 100) )
3551 multorbitopecriterion =
TRUE;
3552 else if ( nbinrows <= 3 * ncols || (
SCIP_Real) nbinrows * ncols >= threshold )
3553 oneorbitopecriterion =
TRUE;
3557 if ( (norbitopes == 1 && oneorbitopecriterion) || (norbitopes >= 2 && multorbitopecriterion) )
3576 int nstrongsbcs = 0;
3579 int** modifiedperms;
3581 int* nvarsincomponent;
3583 int* graphcomponents;
3584 int* graphcompbegins;
3585 int* compcolorbegins;
3586 int* chosencomppercolor =
NULL;
3587 int* firstvaridxpercolor =
NULL;
3590 int ngraphcomponents;
3595 int ntrivialcolors = 0;
3597 int* lexorder =
NULL;
3598 int nvarslexorder = 0;
3599 int maxnvarslexorder = 0;
3603 int norbitopesincomp;
3605 assert( scip !=
NULL );
3606 assert( propdata !=
NULL );
3607 assert( propdata->computedsymmetry );
3608 assert( propdata->nperms >= 0 );
3609 assert( 0 <= cidx && cidx < propdata->ncomponents );
3610 assert( propdata->components !=
NULL );
3611 assert( propdata->componentbegins !=
NULL );
3614 if ( propdata->nperms == 0 || propdata->componentblocked[cidx] )
3621 assert( propdata->nperms > 0 );
3622 assert( propdata->perms !=
NULL );
3623 assert( propdata->npermvars > 0 );
3624 assert( propdata->permvars !=
NULL );
3631 for (p = 0; p < propdata->nperms; ++p)
3638 for (p = 0; p < propdata->npermvars; ++p)
3640 if ( propdata->vartocomponent[p] >= 0 )
3641 ++nvarsincomponent[propdata->vartocomponent[p]];
3644 SCIPdebugMsg(scip,
"starting subgroup detection routine for component %d\n", cidx);
3646 npermsincomp = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
3649 for (j = 0; j < npermsincomp; ++j)
3654 assert( ntwocycleperms >= 0 );
3655 assert( ntwocycleperms <= npermsincomp );
3657 SCIPdebugMsg(scip,
"component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
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];
3702 if ( ntwocycleperms < 2 )
3708 usedpermssize = ntwocycleperms / 2;
3713 &graphcomponents, &graphcompbegins, &compcolorbegins, &ngraphcomponents,
3714 &ncompcolors, &usedperms, &nusedperms, usedpermssize, permused) );
3716 SCIPdebugMsg(scip,
" created subgroup detection graph using %d of the permutations\n", nusedperms);
3718 if ( nusedperms == npermsincomp )
3719 allpermsused =
TRUE;
3721 assert( graphcomponents !=
NULL );
3722 assert( graphcompbegins !=
NULL );
3723 assert( compcolorbegins !=
NULL );
3724 assert( ngraphcomponents > 0 );
3725 assert( ncompcolors > 0 );
3726 assert( nusedperms <= ntwocycleperms );
3727 assert( ncompcolors < propdata->npermvars );
3729 if ( nusedperms == 0 )
3731 SCIPdebugMsg(scip,
" -> skipping component, since less no permutation was used\n");
3739 SCIPdebugMsg(scip,
" number of different colors in the graph: %d\n", ncompcolors);
3741 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3750 for (j = 0; j < ncompcolors; ++j)
3752 chosencomppercolor[j] = -1;
3753 firstvaridxpercolor[j] = -1;
3757 norbitopesincomp =
getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3758 ncompcolors, nvarsincomponent[cidx]);
3761 if ( norbitopesincomp == 1 )
3765 for (k = 0; k < npermsincomp; ++k)
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;
3790 SCIPdebugMsg(scip,
" add symresack for permutation %d of component %d\n", k, cidx);
3796 for (j = 0; j < ncompcolors; ++j)
3798 int nbinarycomps = 0;
3799 int largestcolorcomp = -1;
3800 int largestcompsize = 0;
3812 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3814 if( chosencomppercolor !=
NULL )
3815 chosencomppercolor[j] = -1;
3821 SCIPdebugMsg(scip,
" color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
3822 graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]]);
3825 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3830 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3833 if ( largestcompsize < 1 )
3841 largestcompsize = compsize;
3842 largestcolorcomp = k;
3844 else if ( compsize != largestcompsize )
3851 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3859 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3863 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3870 contaffected =
TRUE;
3873 SCIPdebugMsg(scip,
" affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
3877 useorbitope =
FALSE;
3878 if ( norbitopesincomp > 0 && nbinarycomps > 0 )
3881 if ( isorbitope && useorbitope )
3886 SCIPdebugMsg(scip,
" detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
3888 assert( nbinarycomps > 0 );
3889 assert( largestcompsize > 2 );
3897 graphcompbegins, graphcomponents, j, nbinarycomps, largestcompsize, &firstvaridx, &chosencomp,
3898 &lexorder, &nvarslexorder, &maxnvarslexorder, allpermsused, &orbitopeadded) );
3900 if ( orbitopeadded )
3902 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3904 assert( chosencomppercolor !=
NULL );
3905 assert( firstvaridxpercolor !=
NULL );
3908 assert( compcolorbegins[j] <= chosencomp && chosencomp < compcolorbegins[j+1] );
3909 assert( 0 <= firstvaridx && firstvaridx < propdata->npermvars );
3911 chosencomppercolor[j] = chosencomp;
3912 firstvaridxpercolor[j] = firstvaridx;
3915 if ( ! propdata->componentblocked[cidx] )
3918 ++propdata->ncompblocked;
3928 if ( propdata->addstrongsbcs && ! orbitopeadded )
3930 assert( largestcolorcomp >= 0 );
3931 assert( largestcolorcomp < ngraphcomponents );
3932 assert( largestcompsize > 0 );
3934 if( propdata->addweaksbcs )
3936 assert( chosencomppercolor !=
NULL );
3937 assert( firstvaridxpercolor !=
NULL );
3939 chosencomppercolor[j] = largestcolorcomp;
3940 firstvaridxpercolor[j] = graphcomponents[graphcompbegins[largestcolorcomp]];
3943 SCIPdebugMsg(scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3944 largestcolorcomp, graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp]);
3948 propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3951 if ( !
SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
3952 handlednonbinarysymmetry =
TRUE;
3954 if ( ! propdata->componentblocked[cidx] )
3957 ++propdata->ncompblocked;
3961 nstrongsbcs += graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp] - 1;
3964 else if ( ! orbitopeadded )
3966 SCIPdebugMsg(scip,
" no useable orbitope found and no SBCs added\n");
3969 if ( propdata->addweaksbcs )
3971 assert( chosencomppercolor !=
NULL );
3972 chosencomppercolor[j] = -1;
3977 SCIPdebugMsg(scip,
" skipped %d trivial colors\n", ntrivialcolors);
3980 if ( propdata->addweaksbcs && propdata->componentblocked[cidx] && nusedperms < npermsincomp )
3984 assert( firstvaridxpercolor !=
NULL );
3985 assert( chosencomppercolor !=
NULL );
3988 graphcomponents, ncompcolors, chosencomppercolor, firstvaridxpercolor,
3989 cidx, &naddedconss, propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3991 assert( naddedconss < propdata->npermvars );
3994 nweaksbcs += naddedconss;
3998 SCIPdebugMsg(scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4003 if ( nvarslexorder > 0 && propdata->addsymresacks && ! handlednonbinarysymmetry )
4008 propdata->permvars, modifiedpermvars, propdata->npermvars, lexorder, nvarslexorder) );
4010 for (k = 0; k < npermsincomp; ++k)
4022 symresackperm = modifiedperms[propdata->components[propdata->componentbegins[cidx] + k]];
4023 for (j = 0; j < propdata->nperms && !actsonbinary; ++j)
4026 actsonbinary =
TRUE;
4029 if ( ! actsonbinary )
4035 symresackperm, modifiedpermvars, propdata->npermvars,
FALSE,
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);
4068 SCIPdebugMsg(scip,
"total number of added strong sbcs: %d\n", nstrongsbcs);
4069 SCIPdebugMsg(scip,
"total number of added weak sbcs: %d\n", nweaksbcs);
4076 for (p = propdata->nperms - 1; p >= 0; --p)
4096 SCIP_CONFLICTDATA* varconflicts,
4110 assert( scip !=
NULL );
4111 assert( varconflicts !=
NULL );
4112 assert( conflictvars !=
NULL );
4113 assert( nconflictvars > 0 );
4114 assert( orbits !=
NULL );
4115 assert( orbitbegins !=
NULL );
4116 assert( norbits >= 0 );
4119 for (i = 0; i < nconflictvars; ++i)
4122 varconflicts[i].orbitidx = -1;
4123 varconflicts[i].nconflictinorbit = 0;
4124 varconflicts[i].orbitsize = -1;
4125 varconflicts[i].posinorbit = -1;
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)
4143 assert( pos < nconflictvars );
4144 assert( varconflicts[pos].var == conflictvars[pos] );
4146 varconflicts[pos].orbitidx =
r;
4147 varconflicts[pos].nconflictinorbit = 0;
4148 varconflicts[pos].orbitsize = orbitsize;
4149 varconflicts[pos].posinorbit = posinorbit++;
4159 for (i = orbitbegins[
r]; i < orbitbegins[
r + 1]; ++i)
4162 assert( varconflicts[ii].orbitidx ==
r );
4165 if ( ! varconflicts[ii].
active )
4168 for (j = i + 1; j < orbitbegins[
r + 1]; ++j)
4171 assert( varconflicts[jj].orbitidx ==
r );
4174 if ( ! varconflicts[jj].active )
4184 varconflicts[ii].ncliques, (
void**)varconflicts[jj].cliques, varconflicts[jj].ncliques,
4185 sortByPointerValue) )
4188 ++varconflicts[ii].nconflictinorbit;
4189 ++varconflicts[jj].nconflictinorbit;
4209 SCIP_CONFLICTDATA** varconflicts,
4226 int varncliques = 0;
4229 assert( scip !=
NULL );
4230 assert( varconflicts !=
NULL );
4231 assert( conflictvars !=
NULL );
4232 assert( nconflictvars > 0 );
4235 *varconflicts =
NULL;
4241 if ( ncliques == 0 )
4243 SCIPdebugMsg(scip,
"No cliques present --> construction of conflict structure aborted.\n");
4248 SCIPdebugMsg(scip,
"Construction of conflict structure:\n");
4250 for (i = 0; i < nconflictvars; ++i)
4252 (*varconflicts)[i].ncliques = 0;
4253 (*varconflicts)[i].active =
TRUE;
4254 (*varconflicts)[i].var = conflictvars[i];
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];
4273 assert( clique !=
NULL );
4277 assert( cliquevars !=
NULL );
4278 assert( ncliquevars > 0 );
4284 for (i = 0; i < ncliquevars; ++i)
4289 if ( node == INT_MAX )
4291 assert( node >= 0 );
4292 assert( node < nconflictvars );
4294 assert( (*varconflicts)[node].var == cliquevars[i] );
4295 (*varconflicts)[node].active =
TRUE;
4296 (*varconflicts)[node].ncliques++;
4301 for (i = 0; i < nconflictvars; ++i)
4303 assert( (*varconflicts)[i].ncliques >= 0 );
4304 assert( (*varconflicts)[i].cliques ==
NULL );
4305 if ( (*varconflicts)[i].ncliques > 0 )
4313 for (c = 0; c < ncliques; ++c)
4315 clique = cliques[c];
4316 assert( clique !=
NULL );
4320 assert( cliquevars !=
NULL );
4321 assert( ncliquevars > 0 );
4327 for (i = 0; i < ncliquevars; ++i)
4332 if ( node == INT_MAX )
4335 assert( node >= 0 );
4336 assert( node < nconflictvars );
4337 assert( (*varconflicts)[node].var == cliquevars[i] );
4340 assert( tmpncliques[node] < (*varconflicts)[node].ncliques );
4341 assert( (*varconflicts)[node].cliques !=
NULL );
4342 (*varconflicts)[node].cliques[tmpncliques[node]++] = clique;
4351 for (i = 0; i < nconflictvars; ++i)
4353 SCIPsortPtr((
void**)(*varconflicts)[i].cliques, sortByPointerValue, (*varconflicts)[i].ncliques);
4357 for (i = 0; i < nconflictvars; ++i)
4359 assert( tmpncliques[i] == (*varconflicts)[i].ncliques );
4366 SCIPdebugMsg(scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4377 SCIP_CONFLICTDATA** varconflicts,
4384 assert( scip !=
NULL );
4385 assert( varconflicts !=
NULL );
4386 assert( *varconflicts !=
NULL );
4387 assert( nvars >= 0 );
4389 for (i = nvars - 1; i >= 0; --i)
4391 n = (*varconflicts)[i].ncliques;
4409 int* componentbegins;
4412 int** modifiedperms =
NULL;
4415 int nsymresackcons = 0;
4421 assert( scip !=
NULL );
4422 assert( propdata !=
NULL );
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;
4441 assert( nperms <= 0 || perms !=
NULL );
4442 assert( permvars !=
NULL );
4443 assert( npermvars > 0 );
4445 assert( componentbegins !=
NULL );
4446 assert( 0 <= cidx && cidx < propdata->ncomponents );
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)
4475 modifiedpermvars[i] = permvars[i];
4478 propdata->leaders, propdata->nleaders) );
4482 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
4493 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4496 assert( modifiedperms !=
NULL );
4497 assert( modifiedpermvars !=
NULL );
4512 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4513 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4514 ++propdata->nsymresacks;
4518 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4520 assert( modifiedperms !=
NULL );
4521 assert( modifiedpermvars !=
NULL );
4524 for (p = nperms - 1; p >= 0; --p)
4531 SCIPdebugMsg(scip,
"Added %d symresack constraints.\n", nsymresackcons);
4541 SCIP_CONFLICTDATA* varconflicts,
4549 int norbitvarinconflict,
4567 assert( scip !=
NULL );
4568 assert( propdata !=
NULL );
4569 assert( permvars !=
NULL );
4570 assert( orbits !=
NULL );
4571 assert( orbitbegins !=
NULL );
4572 assert( orbitidx >= 0 );
4573 assert( orbitleaderidx >= 0 );
4574 assert( orbitvarinconflict !=
NULL || varconflicts ==
NULL );
4575 assert( norbitvarinconflict >= 0 );
4576 assert( nchgbds !=
NULL );
4578 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4581 if ( propdata->sstaddcuts )
4585 addcuts = propdata->addconflictcuts;
4588 ncuts = orbitsize - norbitvarinconflict - 1;
4593 if ( propdata->nsstconss == 0 )
4595 assert( propdata->sstconss ==
NULL );
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 );
4619 posleader = orbitbegins[orbitidx] + orbitleaderidx;
4620 vars[0] = permvars[orbits[posleader]];
4623 propdata->leaders[propdata->nleaders++] = orbits[posleader];
4625 for (i = 0, poscur = orbitbegins[orbitidx]; i < orbitsize; ++i, ++poscur)
4627 if ( i == orbitleaderidx )
4629 assert( orbitvarinconflict ==
NULL || ! orbitvarinconflict[i] );
4633 vars[1] = permvars[orbits[poscur]];
4635 for (j = 0; j < propdata->nleaders - 1; ++j)
4637 assert( propdata->leaders[j] != orbits[poscur] );
4642 if ( varconflicts !=
NULL )
4644 if ( orbitvarinconflict[i] )
4648 assert( varconflicts !=
NULL );
4657 assert( varconflicts[orbits[poscur]].
active );
4658 varconflicts[orbits[poscur]].active =
FALSE;
4662 orbitvarinconflict[i] =
FALSE;
4671 propdata->sstconss[propdata->nsstconss++] = cons;
4681 propdata->sstconss[propdata->nsstconss++] = cons;
4693 SCIP_CONFLICTDATA* varconflicts,
4705 int* norbitvarinconflict,
4711 int curcriterion = INT_MIN;
4716 assert( scip !=
NULL );
4717 assert( conflictvars !=
NULL );
4718 assert( nconflictvars > 0 );
4719 assert( orbits !=
NULL );
4720 assert( orbitbegins !=
NULL );
4721 assert( norbits > 0 );
4722 assert( orbitidx !=
NULL );
4723 assert( leaderidx !=
NULL );
4724 assert( orbitvarinconflict !=
NULL || varconflicts ==
NULL );
4725 assert( norbitvarinconflict !=
NULL );
4726 assert( success !=
NULL );
4730 *norbitvarinconflict = 0;
4741 orbitcriterion = INT_MIN;
4744 for (i = 0; i < norbits; ++i)
4748 if (
SCIPvarGetType(conflictvars[orbits[orbitbegins[i]]]) != leadervartype )
4752 curcriterion = orbitbegins[i] - orbitbegins[i + 1];
4754 curcriterion = orbitbegins[i + 1] - orbitbegins[i];
4764 cnt = orbitbegins[i];
4768 varidx = orbits[cnt++];
4776 cnt = orbitbegins[i + 1] - 1;
4780 varidx = orbits[cnt--];
4789 assert( varconflicts[varidx].orbitidx == i );
4791 curcriterion = varconflicts[varidx].nconflictinorbit;
4795 if ( curcriterion > orbitcriterion )
4797 orbitcriterion = curcriterion;
4804 *leaderidx = orbitbegins[i + 1] - orbitbegins[i] - 1;
4809 if ( *success && varconflicts !=
NULL )
4811 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4812 assert( leader < nconflictvars );
4815 && varconflicts[leader].ncliques > 0 )
4822 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4823 assert( varconflicts !=
NULL );
4824 assert( leader >= 0 && leader < nconflictvars );
4826 assert( orbitvarinconflict !=
NULL );
4828 for (i = 0; i < orbitsize; ++i)
4831 if ( i == *leaderidx )
4835 varmapid = orbits[orbitbegins[*orbitidx] + i];
4838 if ( ! varconflicts[varmapid].
active )
4843 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4844 varconflicts[varmapid].ncliques, sortByPointerValue) )
4847 orbitvarinconflict[i] =
TRUE;
4848 ++(*norbitvarinconflict);
4860 assert( varconflicts !=
NULL );
4865 for (i = 0; i < nconflictvars; ++i)
4873 if ( varconflicts[i].orbitidx == -1 )
4876 curcriterion = varconflicts[i].nconflictinorbit;
4878 if ( curcriterion > orbitcriterion )
4880 orbitcriterion = curcriterion;
4881 *orbitidx = varconflicts[i].orbitidx;
4882 *leaderidx = varconflicts[i].posinorbit;
4888 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4889 assert( leader < nconflictvars );
4890 assert( norbitvarinconflict !=
NULL );
4892 if ( *success && varconflicts[leader].ncliques > 0 )
4897 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4898 assert( varconflicts !=
NULL );
4899 assert( leader >= 0 && leader < nconflictvars );
4901 assert( orbitvarinconflict !=
NULL );
4903 for (i = 0; i < orbitsize; ++i)
4906 if ( i == *leaderidx )
4910 varmapid = orbits[orbitbegins[*orbitidx] + i];
4912 if ( ! varconflicts[varmapid].
active )
4917 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4918 varconflicts[varmapid].ncliques, sortByPointerValue) )
4921 orbitvarinconflict[i] =
TRUE;
4922 ++(*norbitvarinconflict);
4942 SCIP_CONFLICTDATA* varconflicts =
NULL;
4948 int nmovedbinpermvars;
4949 int nmovedintpermvars;
4950 int nmovedimplintpermvars;
4951 int nmovedcontpermvars;
4958 int* componentbegins;
4959 int* vartocomponent;
4961 unsigned* componentblocked;
4966 int norbitvarinconflict;
4974 int nvarsselectedtype;
4977 int norbitleadercomponent;
4986 assert( scip !=
NULL );
4987 assert( propdata !=
NULL );
4988 assert( propdata->computedsymmetry );
4990 permvars = propdata->permvars;
4991 npermvars = propdata->npermvars;
4992 nperms = propdata->nperms;
4993 assert( permvars !=
NULL );
4994 assert( npermvars > 0 );
4995 assert( nperms > 0 );
4998 permvarmap = propdata->permvarmap;
4999 assert( permvarmap !=
NULL );
5002 permstrans = propdata->permstrans;
5003 assert( permstrans !=
NULL );
5006 componentbegins = propdata->componentbegins;
5007 componentblocked = propdata->componentblocked;
5008 vartocomponent = propdata->vartocomponent;
5009 ncomponents = propdata->ncomponents;
5012 assert( componentbegins !=
NULL );
5013 assert( vartocomponent !=
NULL );
5014 assert( componentblocked !=
NULL );
5015 assert( ncomponents > 0 );
5016 assert( 0 <= cidx && cidx < ncomponents );
5019 if ( componentblocked[cidx] )
5023 if ( propdata->componenthassignedperm[cidx] )
5026 leaderrule = propdata->sstleaderrule;
5027 tiebreakrule = propdata->ssttiebreakrule;
5028 leadervartype = propdata->sstleadervartype;
5029 mixedcomponents = propdata->sstmixedcomponents;
5033 nmovedpermvars = propdata->nmovedpermvars;
5034 nmovedbinpermvars = propdata->nmovedbinpermvars;
5035 nmovedintpermvars = propdata->nmovedintpermvars;
5036 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5037 nmovedcontpermvars = propdata->nmovedcontpermvars;
5038 assert( nmovedpermvars > 0 );
5041 nvarsselectedtype = 0;
5042 if (
ISSSTBINACTIVE(leadervartype) && nmovedbinpermvars > nvarsselectedtype )
5045 nvarsselectedtype = nmovedbinpermvars;
5048 if (
ISSSTINTACTIVE(leadervartype) && nmovedintpermvars > nvarsselectedtype )
5051 nvarsselectedtype = nmovedintpermvars;
5054 if (
ISSSTIMPLINTACTIVE(leadervartype) && nmovedimplintpermvars > nvarsselectedtype )
5057 nvarsselectedtype = nmovedimplintpermvars;
5060 if (
ISSSTCONTACTIVE(leadervartype) && nmovedcontpermvars > nvarsselectedtype )
5063 nvarsselectedtype = nmovedcontpermvars;
5067 if ( nvarsselectedtype == 0 )
5071 if ( onlywithcontvars )
5073 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
5075 perm = propdata->perms[p];
5076 for (i = 0; i < propdata->npermvars; ++i)
5098 conflictgraphcreated = varconflicts !=
NULL;
5106 if ( conflictgraphcreated )
5111 SCIPdebugMsg(scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5112 SCIPdebugMsg(scip,
"orbitidx\tleaderidx\torbitsize\n");
5114 if ( nchgbds !=
NULL )
5118 for (c = 0; c < ncomponents; ++c)
5120 for (p = componentbegins[c]; p < componentbegins[c + 1]; ++p)
5125 inactiveperms[components[p]] =
TRUE;
5128 ninactiveperms = nperms - componentbegins[cidx + 1] + componentbegins[cidx];
5131 norbitleadercomponent = 0;
5132 while ( ninactiveperms < nperms )
5138 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5139 componentblocked, ncomponents, nmovedpermvars) );
5142 if ( ! mixedcomponents )
5144 for (p = 0; p < norbits; ++p)
5147 if (
SCIPvarGetType(permvars[orbits[orbitbegins[p]]]) != selectedtype )
5159 if ( conflictgraphcreated )
5177 norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype, &orbitidx, &orbitleaderidx,
5178 orbitvarinconflict, &norbitvarinconflict, &success) );
5183 assert( 0 <= orbitidx && orbitidx < norbits );
5184 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5185 SCIPdebugMsg(scip,
"%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5189 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5191 ++norbitleadercomponent;
5193 if ( nchgbds !=
NULL )
5194 *nchgbds += nchanges;
5197 posleader = orbits[orbitbegins[orbitidx] + orbitleaderidx];
5198 for (p = 0; p < nperms; ++p)
5200 if ( inactiveperms[p] )
5203 if ( permstrans[posleader][p] != posleader )
5205 inactiveperms[p] =
TRUE;
5212 if ( norbitleadercomponent > 0 )
5215 if ( conflictgraphcreated )
5221 if ( varconflicts !=
NULL )
5254 assert( scip !=
NULL );
5255 assert( propdata !=
NULL );
5256 assert( propdata->usedynamicprop );
5257 assert( varidxmatrix !=
NULL );
5258 assert( nrows > 0 );
5259 assert( ncols > 0 );
5260 assert( success !=
NULL );
5274 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5275 for (i = 0; i < ncols - 1; ++i)
5279 consvars[0] = propdata->permvars[varidxmatrix[0][i]];
5280 consvars[1] = propdata->permvars[varidxmatrix[0][i + 1]];
5286 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5294 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5299 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5302 propdata->permvars, propdata->npermvars, orbisackperm, (
SYM_SYMTYPE) propdata->symtype,
5303 propdata->permvardomaincenter,
TRUE, success) );
5310 for (i = 0; i < nrows; ++i)
5313 for (j = 0; j < ncols; ++j)
5314 varmatrix[i][j] = propdata->permvars[varidxmatrix[i][j]];
5321 ispporbitope = npprows >= 3;
5330 assert( pprows !=
NULL );
5335 for (i = 0; i < nrows; ++i)
5339 assert( r < npprows );
5340 ppvarsarrayonlypprows[r++] = varmatrix[i];
5343 assert( r == npprows );
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)
5377 orbitopevarmatrix[pos++] = varmatrix[i][j];
5386 orbitopevarmatrix, nrows, ncols, success) );
5394 for (i = nrows - 1; i >= 0; --i)
5409 int** componentperms,
5428 int** pporbisackperms;
5429 int npporbisackperms;
5433 int* npermvarssetppcconss;
5434 int* maxnpermvarssetppcconss;
5438 assert( scip !=
NULL );
5439 assert( propdata !=
NULL );
5440 assert( componentperms !=
NULL );
5441 assert( componentsize > 0 );
5442 assert( success !=
NULL );
5448 if ( hassignedperm )
5452 if ( setppcconshdlr ==
NULL )
5456 if ( nsetppcconss == 0 )
5460 assert( setppcconss !=
NULL );
5467 for (c = 0; c < nsetppcconss; ++c)
5469 cons = setppcconss[c];
5475 setppconsssort[nsetppconss++] = cons;
5477 SCIPsortPtr((
void**) setppconsssort, sortByPointerValue, nsetppcconss);
5485 for (c = 0; c < nsetppconss; ++c)
5488 assert( c < nsetppconss );
5489 cons = setppconsssort[c];
5490 assert( cons !=
NULL );
5495 for (i = 0; i < nsetppcvars; ++i)
5497 var = setppcvars[i];
5498 assert( var !=
NULL );
5500 assert( varid == INT_MAX || varid < propdata->npermvars );
5501 assert( varid >= 0 );
5502 if ( varid < propdata->npermvars )
5505 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5506 assert( npermvarssetppcconss[varid] < maxnpermvarssetppcconss[varid] );
5507 permvarssetppcconss[varid][npermvarssetppcconss[varid]++] = cons;
5515 npporbisackperms = 0;
5516 for (p = 0; p < componentsize; ++p)
5518 perm = componentperms[p];
5522 for (i = 0; i < propdata->npermvars; ++i)
5541 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) )
5550 if ( ntwocycles > 0 )
5552 pporbisackperms[npporbisackperms++] = perm;
5553 if ( ntwocycles > maxntwocycles )
5554 maxntwocycles = ntwocycles;
5562 if ( npporbisackperms * 2 >= componentsize )
5570 assert( npporbisackperms > 0 );
5571 assert( maxntwocycles > 0 );
5576 for (i = 0; i < maxntwocycles; ++i)
5577 ppvarsmatrix[i] = &(ppvarsblock[2 * i]);
5580 for (p = 0; p < npporbisackperms; ++p)
5582 perm = pporbisackperms[p];
5586 for (i = 0; i < propdata->npermvars; ++i)
5597 assert( perm[j] == i );
5599 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) );
5601 assert( nrows < maxntwocycles );
5602 row = ppvarsmatrix[nrows++];
5603 row[0] = propdata->permvars[i];
5604 row[1] = propdata->permvars[j];
5605 assert( row[0] != row[1] );
5607 assert( nrows > 0 );
5616 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5620 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5634 for (varid = 0; varid < propdata->npermvars; ++varid)
5636 assert( (permvarssetppcconss[varid] ==
NULL) == (maxnpermvarssetppcconss[varid] == 0) );
5637 assert( npermvarssetppcconss[varid] >= 0 );
5638 assert( maxnpermvarssetppcconss[varid] >= 0 );
5639 assert( npermvarssetppcconss[varid] <= maxnpermvarssetppcconss[varid] );
5640 if ( npermvarssetppcconss[varid] == 0 )
5643 permvarssetppcconss[varid] =
NULL;
5644 npermvarssetppcconss[varid] = 0;
5645 maxnpermvarssetppcconss[varid] = 0;
5665 int** componentperms;
5673 assert( scip !=
NULL );
5674 assert( propdata !=
NULL );
5678 && propdata->usedynamicprop
5679 && propdata->addsymresacks
5681 assert( propdata->nperms > 0 );
5682 assert( 0 <= cidx && cidx < propdata->ncomponents );
5683 assert( propdata->componentblocked !=
NULL );
5686 if ( propdata->componentblocked[cidx] )
5691 checklexred =
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5692 assert( checkorbired || checklexred );
5695 assert( propdata->nmovedpermvars );
5698 componentsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
5700 for (p = 0; p < componentsize; ++p)
5701 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
5710 checkpporbisack =
SCIPgetParam(scip,
"constraints/orbisack/checkpporbisack");
5714 componentperms, componentsize, propdata->componenthassignedperm[cidx], &success) );
5719 goto FINISHCOMPONENT;
5724 if ( checkorbired && !propdata->componenthassignedperm[cidx] )
5727 propdata->permvars, propdata->npermvars, componentperms, componentsize, &success) );
5736 for (p = 0; p < componentsize; ++p)
5738 assert( componentperms[p] !=
NULL );
5740 propdata->permvars, propdata->npermvars, componentperms[p],
5741 (
SYM_SYMTYPE) propdata->symtype, propdata->permvardomaincenter,
TRUE, &success) );
5749 if ( propdata->componentblocked[cidx] )
5750 ++propdata->ncompblocked;
5765 int ncomponentshandled;
5768 assert( scip !=
NULL );
5769 assert( propdata !=
NULL );
5772 if ( propdata->orbitopalreddata )
5776 if ( propdata->orbitalreddata )
5780 if ( propdata->lexreddata )
5784 if ( propdata->ncomponents >= 0 )
5791 ncomponentshandled = 0;
5792 for (i = 0; i < propdata->ncomponents; ++i)
5794 if ( propdata->componentblocked[i] )
5795 ++ncomponentshandled;
5797 assert( propdata->ncompblocked <= ncomponentshandled );
5798 assert( ncomponentshandled <= propdata->ncomponents );
5800 ncomponentshandled, propdata->ncomponents);
5818 assert( scip !=
NULL );
5819 assert( propdata !=
NULL );
5820 assert( varidxmatrix !=
NULL );
5821 assert( nrows > 0 );
5822 assert( ncols > 0 );
5823 assert( success !=
NULL );
5828 if ( propdata->usedynamicprop )
5833 else if ( propdata->binvaraffected )
5845 for (i = 0; i < nrows; ++i)
5852 for (j = 0; j < ncols; ++j)
5855 orbitopematrix[nbinrows][j] = propdata->permvars[varidxmatrix[i][j]];
5870 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5871 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5872 ++propdata->norbitopes;
5877 for (i = nbinrows - 1; i >= 0; --i)
5916 assert( scip !=
NULL );
5917 assert( propdata !=
NULL );
5918 assert( varidxmatrix !=
NULL );
5919 assert( nrows > 0 );
5920 assert( ncols > 0 );
5921 assert( rowsbegin !=
NULL );
5922 assert( colsbegin !=
NULL );
5923 assert( nrowblocks > 0 );
5924 assert( ncolblocks > 0 );
5925 assert( success !=
NULL );
5929 &propdata->genorbconsssize, propdata->ngenorbconss + nrowblocks + ncolblocks) );
5931 maxdim =
MAX(nrows, ncols);
5933 for (i = 0; i < maxdim; ++i)
5939 for (p = 0; p < ncolblocks; ++p)
5942 for (i = 0; i < nrows; ++i)
5945 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[i][colsbegin[p]]]) )
5948 for (col = 0, j = colsbegin[p]; j < colsbegin[p + 1]; ++j, ++col)
5951 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[i][j]];
5963 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5969 for (p = 0; p < nrowblocks; ++p)
5972 for (i = 0; i < ncols; ++i)
5975 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[rowsbegin[p]][i]]) )
5978 for (col = 0, j = rowsbegin[p]; j < rowsbegin[p + 1]; ++j, ++col)
5981 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[j][i]];
5993 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5998 for (i = maxdim - 1; i >= 0; --i)
6016 int** lexmatrix =
NULL;
6017 int* lexrowsbegin =
NULL;
6018 int* lexcolsbegin =
NULL;
6030 assert( scip !=
NULL );
6031 assert( propdata !=
NULL );
6032 assert( 0 <= cidx && cidx < propdata->ncomponents );
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]];
6053 &success, &isorbitope, &lexmatrix, &nrows, &ncols,
6054 &lexrowsbegin, &lexcolsbegin, &nrowmatrices, &ncolmatrices) );
6061 assert( lexmatrix !=
NULL );
6062 assert( nrows > 0 );
6063 assert( ncols > 0 );
6074 for (i = 0; i < nrows && !hasbinaryvar; ++i)
6076 for (p = 0; p < ncols; ++p)
6080 hasbinaryvar =
TRUE;
6089 lexrowsbegin, lexcolsbegin, nrowmatrices, ncolmatrices, &success) );
6096 for (i = nrows - 1; i >= 0; --i)