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;
305 int sstleadervartype;
321 struct SCIP_ConflictData
326 int nconflictinorbit;
333 typedef struct SCIP_ConflictData SCIP_CONFLICTDATA;
343 else if ( elem1 > elem2 )
364 assert( arr1 !=
NULL || narr1 == 0 );
365 assert( narr1 >= 0 );
366 assert( arr2 !=
NULL || narr2 == 0 );
367 assert( narr2 >= 0 );
368 assert( compfunc !=
NULL );
381 cmp = compfunc(arr1[it1], arr2[it2]);
387 if ( ++it1 >= narr1 )
396 if ( ++it2 >= narr2 )
409 assert( it1 >= narr1 || it2 >= narr2 );
434 assert( scip !=
NULL );
435 assert( perm !=
NULL );
436 assert( 0 <= baseidx );
439 assert( covered !=
NULL );
442 if ( perm[baseidx] == baseidx || covered[baseidx] )
445 varidx = baseidx >= nvars ? baseidx - nvars : baseidx;
449 covered[baseidx] =
TRUE;
450 while ( j != baseidx )
453 varidx = j >= nvars ? j - nvars : j;
478 assert( scip !=
NULL );
479 assert( propdata !=
NULL );
480 assert( propdata->nperms > 0 );
481 assert( propdata->permvars !=
NULL );
482 assert( propdata->npermvars > 0 );
485 npermvars = propdata->npermvars;
489 SCIPinfoMessage(scip,
NULL,
"Display permutations as signed permutations (allowing translations)\n");
493 for (p = 0; p < propdata->nperms; ++p)
496 perm = propdata->perms[p];
498 for (i = 0; i < permlen; ++i)
503 for (i = 0; i < permlen; ++i)
529 assert( scip !=
NULL );
530 assert( propdata !=
NULL );
531 assert( propdata->nperms > 0 );
532 assert( propdata->permvars !=
NULL );
533 assert( propdata->npermvars > 0 );
534 assert( propdata->ncomponents > 0 );
537 npermvars = propdata->npermvars;
542 for (c = 0; c < propdata->ncomponents; ++c)
547 if ( propdata->componenthassignedperm[c] )
548 SCIPinfoMessage(scip,
NULL,
" Symmetries are displayed as signed permutations (allowing translations).\n");
552 comppermlen = propdata->componenthassignedperm[c] ? 2 * npermvars : npermvars;
554 for (p = propdata->componentbegins[c], cnt = 0; p < propdata->componentbegins[c + 1]; ++p, ++cnt)
557 perm = propdata->perms[propdata->components[p]];
559 for (i = 0; i < comppermlen; ++i)
564 for (i = 0; i < comppermlen; ++i)
584 assert( propdata !=
NULL );
586 if ( propdata->nperms == -1 )
588 SCIPinfoMessage(scip,
NULL,
"Cannot display symmetries. Symmetries have not been computed yet.\n");
590 else if ( propdata->nperms == 0 )
594 else if ( propdata->ncomponents < 0 )
615 struct SCIP_TableData
630 assert( scip !=
NULL );
631 assert( table !=
NULL );
634 assert( tabledata !=
NULL );
635 assert( tabledata->propdata !=
NULL );
637 if ( tabledata->propdata->orbitopalreddata || tabledata->propdata->orbitalreddata
638 || tabledata->propdata->lexreddata )
641 if ( tabledata->propdata->orbitopalreddata )
645 " %10d cutoffs\n", nred, ncutoff);
647 if ( tabledata->propdata->orbitalreddata )
651 " %10d cutoffs\n", nred, ncutoff);
653 if ( tabledata->propdata->lexreddata )
657 " %10d cutoffs\n", nred, ncutoff);
659 if ( tabledata->propdata->shadowtreeeventhdlr )
676 assert( tabledata !=
NULL );
780 if ( G1->
lhs[perm1] < G2->
lhs[perm2] )
782 if ( G1->
lhs[perm1] > G2->
lhs[perm2] )
785 if ( G1->
rhs[perm1] < G2->
rhs[perm2] )
787 if ( G1->
rhs[perm1] > G2->
rhs[perm2] )
852 assert( propdata->permvarmap ==
NULL );
853 assert( propdata->genorbconss ==
NULL );
854 assert( propdata->genlinconss ==
NULL );
855 assert( propdata->ngenlinconss == 0 );
856 assert( propdata->ngenorbconss == 0 );
857 assert( propdata->genorbconsssize == 0 );
858 assert( propdata->genlinconsssize == 0 );
859 assert( propdata->sstconss ==
NULL );
860 assert( propdata->leaders ==
NULL );
862 assert( propdata->permvardomaincenter ==
NULL );
863 assert( propdata->permvars ==
NULL );
864 assert( propdata->perms ==
NULL );
865 assert( propdata->permstrans ==
NULL );
866 assert( propdata->npermvars == 0 );
867 assert( propdata->nbinpermvars == 0 );
868 assert( propdata->nperms == -1 || propdata->nperms == 0 );
869 assert( propdata->nmaxperms == 0 );
870 assert( propdata->nmovedpermvars == -1 );
871 assert( propdata->nmovedbinpermvars == 0 );
872 assert( propdata->nmovedintpermvars == 0 );
873 assert( propdata->nmovedimplintpermvars == 0 );
874 assert( propdata->nmovedcontpermvars == 0 );
875 assert( propdata->nmovedvars == -1 );
876 assert( propdata->binvaraffected ==
FALSE );
877 assert( propdata->isnonlinvar ==
NULL );
879 assert( propdata->componenthassignedperm ==
NULL );
880 assert( propdata->componentblocked ==
NULL );
881 assert( propdata->componentbegins ==
NULL );
882 assert( propdata->components ==
NULL );
883 assert( propdata->ncomponents == -1 );
884 assert( propdata->ncompblocked == 0 );
898 assert( scip !=
NULL );
899 assert( propdata !=
NULL );
902 if ( propdata->orbitalreddata !=
NULL )
906 if ( propdata->orbitopalreddata !=
NULL )
910 if ( propdata->lexreddata !=
NULL )
928 assert( scip !=
NULL );
929 assert( propdata !=
NULL );
933 if ( propdata->permvarmap !=
NULL )
939 for (i = 0; i < propdata->npermvars; ++i)
941 assert( propdata->permvars[i] !=
NULL );
946 if ( propdata->permstrans !=
NULL )
948 assert( propdata->nperms > 0 );
949 assert( propdata->permvars !=
NULL );
950 assert( propdata->npermvars > 0 );
951 assert( propdata->nmaxperms > 0 );
953 for (i = 0; i < propdata->npermvars; ++i)
961 if ( propdata->genorbconss !=
NULL )
963 assert( propdata->ngenorbconss > 0 );
966 while ( propdata->ngenorbconss > 0 )
968 assert( propdata->genorbconss[propdata->ngenorbconss - 1] !=
NULL );
971 assert( propdata->ngenorbconss == 0 );
975 propdata->genorbconsssize = 0;
979 if ( propdata->genlinconss !=
NULL )
982 for (i = 0; i < propdata->ngenlinconss; ++i)
984 assert( propdata->genlinconss[i] !=
NULL );
990 propdata->ngenlinconss = 0;
991 propdata->genlinconsssize = 0;
994 if ( propdata->sstconss !=
NULL )
996 assert( propdata->nsstconss > 0 );
999 for (i = 0; i < propdata->nsstconss; ++i)
1001 assert( propdata->sstconss[i] !=
NULL );
1007 propdata->sstconss =
NULL;
1008 propdata->nsstconss = 0;
1009 propdata->maxnsstconss = 0;
1012 if ( propdata->leaders !=
NULL )
1014 assert( propdata->maxnleaders > 0 );
1017 propdata->maxnleaders = 0;
1018 propdata->leaders =
NULL;
1019 propdata->nleaders = 0;
1023 if ( propdata->ncomponents > 0 )
1025 assert( propdata->componentblocked !=
NULL );
1026 assert( propdata->vartocomponent !=
NULL );
1027 assert( propdata->componentbegins !=
NULL );
1028 assert( propdata->components !=
NULL );
1036 propdata->ncomponents = -1;
1037 propdata->ncompblocked = 0;
1041 if ( propdata->nperms > 0 )
1045 assert( propdata->permvars !=
NULL );
1048 permlen = 2 * propdata->npermvars;
1050 permlen = propdata->npermvars;
1055 if ( propdata->perms !=
NULL )
1057 for (i = 0; i < propdata->nperms; ++i)
1066 propdata->npermvars = 0;
1067 propdata->nbinpermvars = 0;
1068 propdata->nperms = -1;
1069 propdata->nmaxperms = 0;
1070 propdata->nmovedpermvars = -1;
1071 propdata->nmovedbinpermvars = 0;
1072 propdata->nmovedintpermvars = 0;
1073 propdata->nmovedimplintpermvars = 0;
1074 propdata->nmovedcontpermvars = 0;
1075 propdata->nmovedvars = -1;
1076 propdata->log10groupsize = -1.0;
1077 propdata->binvaraffected =
FALSE;
1078 propdata->isnonlinvar =
NULL;
1080 propdata->nperms = -1;
1084 propdata->computedsymmetry =
FALSE;
1085 propdata->compressed =
FALSE;
1096 int* consarrsizeptr,
1102 assert( scip !=
NULL );
1103 assert( consarrptr !=
NULL );
1104 assert( consarrsizeptr !=
NULL );
1105 assert( consarrsizereq > 0 );
1106 assert( *consarrsizeptr >= 0 );
1107 assert( (*consarrsizeptr == 0) == (*consarrptr ==
NULL) );
1110 if ( consarrsizereq <= *consarrsizeptr )
1115 assert( newsize > *consarrsizeptr );
1118 if ( *consarrptr ==
NULL )
1127 *consarrsizeptr = newsize;
1158 assert( scip !=
NULL );
1159 assert( vars !=
NULL );
1160 assert( nvars > 0 );
1161 assert( permvars !=
NULL );
1162 assert( npermvars !=
NULL );
1163 assert( nbinpermvars !=
NULL );
1164 assert( perms !=
NULL );
1165 assert( nperms > 0 );
1166 assert( binvaraffected !=
NULL );
1167 assert(
SCIPisGE(scip, compressthreshold, 0.0) );
1168 assert(
SCIPisLE(scip, compressthreshold, 1.0) );
1169 assert( compressed !=
NULL );
1174 *nbinpermvars = nbinvars;
1175 *binvaraffected =
FALSE;
1176 *compressed =
FALSE;
1182 int* labelmovedvars;
1183 int* labeltopermvaridx;
1184 int nbinvarsaffected = 0;
1186 assert( nmovedvars !=
NULL );
1193 for (i = 0; i < nvars; ++i)
1195 labelmovedvars[i] = -1;
1197 for (p = 0; p < nperms; ++p)
1199 if ( perms[p][i] != i )
1201 labeltopermvaridx[*nmovedvars] = i;
1202 labelmovedvars[i] = (*nmovedvars)++;
1211 if ( nbinvarsaffected > 0 )
1212 *binvaraffected =
TRUE;
1216 if ( *nmovedvars > 0 &&
SCIPisLE(scip, percentagemovedvars, compressthreshold) )
1219 for (p = 0; p < nperms; ++p)
1222 for (i = 0; i < *nmovedvars; ++i)
1224 assert( i <= labeltopermvaridx[i] );
1225 if ( perms[p][labeltopermvaridx[i]] >= nvars )
1231 imgvaridx = perms[p][labeltopermvaridx[i]] - nvars;
1232 perms[p][i] = labelmovedvars[imgvaridx] + *nmovedvars;
1234 assert( 0 <= perms[p][i] && perms[p][i] < 2 * (*nmovedvars) );
1237 perms[p][i] = labelmovedvars[perms[p][labeltopermvaridx[i]]];
1252 for (i = 0; i < *nmovedvars; ++i)
1254 (*permvars)[i] = vars[labeltopermvaridx[i]];
1256 *npermvars = *nmovedvars;
1257 *nbinpermvars = nbinvarsaffected;
1268 for (i = 0; i < nbinvars; ++i)
1270 for (p = 0; p < nperms && ! *binvaraffected; ++p)
1272 if ( perms[p][i] != i )
1275 *binvaraffected =
TRUE;
1284 for (i = 0; i < *npermvars; ++i)
1289 (*permvardomaincenter)[i] = 0.5 * (ub + lb);
1302 assert( conshdlr !=
NULL );
1327 assert( conshdlrs !=
NULL );
1330 for (c = 0; c < nconshdlrs; ++c)
1332 conshdlr = conshdlrs[c];
1333 assert( conshdlr !=
NULL );
1345 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n" 1346 " If symmetries shall be detected, implement the %s callback.\n",
1387 SCIPwarningMessage(scip,
"Expression handler %s does not implement the EXPRGETSYMDATA callback.\n" 1388 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n" 1414 assert( scip !=
NULL );
1415 assert( nopnodes !=
NULL );
1416 assert( nvalnodes !=
NULL );
1417 assert( nconsnodes !=
NULL );
1418 assert( nedges !=
NULL );
1423 assert( conss !=
NULL || nconss == 0 );
1425 *nconsnodes = nconss;
1430 for (c = 0; c < nconss; ++c)
1458 depth = (int) log2((
double) num);
1459 expval = (int) exp2((
double) (depth + 1));
1460 numnodes =
MIN(expval, 100);
1462 *nopnodes += numnodes;
1463 *nvalnodes +=
MAX((
int) 0.1 * numnodes, 1);
1478 *nopnodes += num - 1;
1487 if ( nvars <= 100000 )
1488 *nedges = 100 * nvars;
1489 else if ( nvars <= 1000000 )
1490 *nedges = 32 * nvars;
1491 else if ( nvars <= 16700000 )
1492 *nedges = 16 * nvars;
1494 *nedges = INT_MAX / 10;
1522 #ifdef SCIP_DISPLAY_SYM_CHECK 1527 assert( scip !=
NULL );
1528 assert( perms !=
NULL );
1529 assert( nperms > 0 );
1530 assert( npermvars > 0 );
1535 assert( conss !=
NULL );
1539 assert( nsymvars == npermvars );
1543 for (c = 0; c < nconss; ++c)
1565 for (c = 0; c < nconss; ++c)
1570 SCIPsort(graphperm, SYMsortSymgraphs, graphs, nconss);
1573 for (c = 1; c < nconss; ++c)
1575 if (
compareSymgraphs(scip, graphs[graphperm[c]], graphs[graphperm[c-1]]) != 0 )
1576 groupbegins[ngroups++] = c;
1578 groupbegins[ngroups] = nconss;
1581 for (c = 0; c < nconss; ++c)
1586 #ifdef SCIP_DISPLAY_SYM_CHECK 1592 for (p = 0; p < nperms; ++p)
1597 #ifdef SCIP_DISPLAY_SYM_CHECK 1601 for (i = 0; i < permlen; ++i)
1606 for (i = 0; i < permlen; ++i)
1608 SCIPinfoMessage(scip,
NULL,
"Check whether every constraint has a symmetric counterpart.\n");
1612 for (g = 0; g < ngroups; ++g)
1614 for (c = groupbegins[g]; c < groupbegins[g+1]; ++c)
1616 #ifdef SCIP_DISPLAY_SYM_CHECK 1627 #ifdef SCIP_DISPLAY_SYM_CHECK 1636 for (d = groupbegins[g]; d < groupbegins[g+1] && ! found; ++d)
1640 #ifdef SCIP_DISPLAY_SYM_CHECK 1641 SCIPinfoMessage(scip,
NULL,
"\tconstraint is %ssymmetric to constraint %d\n\t", !found ?
"not " :
"", d);
1651 #ifdef SCIP_DISPLAY_SYM_CHECK 1661 #ifdef SCIP_DISPLAY_SYM_CHECK 1668 for (c = nconss - 1; c >= 0; --c)
1713 assert( scip !=
NULL );
1714 assert( permvars !=
NULL );
1715 assert( npermvars !=
NULL );
1716 assert( nbinpermvars !=
NULL );
1717 assert( perms !=
NULL );
1718 assert( nperms !=
NULL );
1719 assert( nmaxperms !=
NULL );
1720 assert( nmovedvars !=
NULL );
1721 assert( binvaraffected !=
NULL );
1722 assert( compressed !=
NULL );
1723 assert( log10groupsize !=
NULL );
1724 assert( symcodetime !=
NULL );
1725 assert( success !=
NULL );
1735 *binvaraffected =
FALSE;
1736 *compressed =
FALSE;
1737 *log10groupsize = 0;
1747 assert( conss !=
NULL );
1763 nopnodes, nvalnodes, nconsnodes, nedges) );
1766 for (c = 0; c < nconss && *success; ++c)
1801 perms, log10groupsize, symcodetime) );
1803 if ( checksymmetries && *nperms > 0 )
1818 permvardomaincenter, *perms, *nperms, nmovedvars, binvaraffected,
1819 compresssymmetries, compressthreshold, compressed) );
1839 assert( symmetry !=
NULL );
1840 assert( vars !=
NULL );
1841 assert( nvars > 0 );
1843 for (v = 0; v < nvars; ++v)
1846 if ( symmetry[v] >= nvars )
1873 int* componentbegins;
1878 assert( scip !=
NULL );
1879 assert( propdata !=
NULL );
1880 assert( propdata->ncomponents > 0 );
1881 assert( propdata->components !=
NULL );
1882 assert( propdata->componentbegins !=
NULL );
1885 componentbegins = propdata->componentbegins;
1886 ncomponents = propdata->ncomponents;
1895 for (c = 0; c < ncomponents; ++c)
1897 for (i = componentbegins[c]; i < componentbegins[c + 1]; ++i)
1901 propdata->componenthassignedperm[c] =
TRUE;
1917 assert( scip !=
NULL );
1918 assert( propdata !=
NULL );
1921 assert( propdata->nperms >= 0 );
1924 if ( propdata->ncomponents >= 0 )
1928 assert( propdata->ncomponents == -1 );
1929 assert( propdata->components ==
NULL );
1930 assert( propdata->componentbegins ==
NULL );
1931 assert( propdata->vartocomponent ==
NULL );
1933 #ifdef SCIP_OUTPUT_COMPONENT 1938 propdata->permvars, propdata->npermvars,
FALSE, &propdata->components, &propdata->componentbegins,
1939 &propdata->vartocomponent, &propdata->componentblocked, &propdata->ncomponents) );
1941 #ifdef SCIP_OUTPUT_COMPONENT 1945 assert( propdata->components !=
NULL );
1946 assert( propdata->componentbegins !=
NULL );
1947 assert( propdata->ncomponents > 0 );
1951 assert( propdata->componenthassignedperm !=
NULL );
1966 assert( scip !=
NULL );
1967 assert( propdata !=
NULL );
1970 assert( propdata->nperms >= 0 );
1973 if ( propdata->permvarmap !=
NULL )
1980 for (v = 0; v < propdata->npermvars; ++v)
1999 assert( scip !=
NULL );
2000 assert( propdata !=
NULL );
2003 assert( propdata->nperms >= 0 );
2006 if ( propdata->permstrans !=
NULL )
2010 assert( propdata->permstrans ==
NULL );
2012 for (v = 0; v < propdata->npermvars; ++v)
2015 for (p = 0; p < propdata->nperms; ++p)
2016 propdata->permstrans[v][p] = propdata->perms[p][v];
2033 assert( scip !=
NULL );
2034 assert( propdata !=
NULL );
2037 assert( propdata->nperms >= 0 );
2040 if ( propdata->nmovedpermvars >= 0 )
2042 assert( propdata->nmovedpermvars == -1 );
2044 propdata->nmovedpermvars = 0;
2045 propdata->nmovedbinpermvars = 0;
2046 propdata->nmovedintpermvars = 0;
2047 propdata->nmovedimplintpermvars = 0;
2048 propdata->nmovedcontpermvars = 0;
2050 for (p = 0; p < propdata->nperms; ++p)
2052 for (v = 0; v < propdata->npermvars; ++v)
2054 if ( propdata->perms[p][v] != v )
2056 ++propdata->nmovedpermvars;
2061 ++propdata->nmovedbinpermvars;
2064 ++propdata->nmovedintpermvars;
2067 ++propdata->nmovedimplintpermvars;
2070 ++propdata->nmovedcontpermvars;
2092 if ( propdata->enforcecomputesymmetry )
2145 unsigned int type = 0;
2149 assert( scip !=
NULL );
2150 assert( propdata !=
NULL );
2151 assert( propdata->usesymmetry >= 0 );
2165 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2193 if ( ! (type & symspecrequire) )
2196 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2209 if ( propdata->computedsymmetry )
2212 assert( propdata->npermvars == 0 );
2213 assert( propdata->permvars ==
NULL );
2214 assert( propdata->nperms < 0 );
2215 assert( propdata->nmaxperms == 0 );
2216 assert( propdata->perms ==
NULL );
2220 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2227 (symspecrequirefixed & (
int)
SYM_SPEC_REAL) != 0 ?
'+' :
'-');
2230 if ( symspecrequire & symspecrequirefixed )
2234 maxgenerators = propdata->maxgenerators;
2239 propdata->compresssymmetries, propdata->compressthreshold,
2240 maxgenerators, symspecrequirefixed, propdata->checksymmetries, &propdata->permvars,
2241 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvardomaincenter,
2242 &propdata->perms, &propdata->nperms, &propdata->nmaxperms,
2243 &propdata->nmovedvars, &propdata->binvaraffected, &propdata->compressed,
2244 &propdata->log10groupsize, &symcodetime, &successful) );
2247 propdata->computedsymmetry =
TRUE;
2262 if ( propdata->nperms == 0 )
2269 assert( propdata->nperms > 0 );
2270 assert( propdata->npermvars > 0 );
2277 if ( maxgenerators == 0 )
2285 if ( propdata->displaynorbitvars )
2287 if ( propdata->nmovedvars == -1 )
2290 propdata->npermvars, &(propdata->nmovedvars)) );
2297 for (i = 0; i < propdata->npermvars; ++i)
2333 int** orbitopevaridx,
2347 int ntestedperms = 0;
2351 assert( scip !=
NULL );
2352 assert( permvars !=
NULL );
2353 assert( perms !=
NULL );
2354 assert( activeperms !=
NULL );
2355 assert( orbitopevaridx !=
NULL );
2356 assert( columnorder !=
NULL );
2357 assert( nusedelems !=
NULL );
2358 assert( isorbitope !=
NULL );
2359 assert( nactiveperms > 0 );
2360 assert( ntwocycles > 0 );
2361 assert( npermvars > 0 );
2362 assert( activevars ==
NULL || (0 <= nactiveperms && nactiveperms < npermvars) );
2365 if ( nusedcols !=
NULL )
2374 while ( ! foundperm )
2378 assert( ntestedperms < nactiveperms );
2380 permidx = activeperms[ntestedperms];
2382 for (j = 0; j < npermvars; ++j)
2384 if ( activevars !=
NULL && ! activevars[j] )
2387 assert( activevars ==
NULL || activevars[perms[permidx][j]] );
2390 if ( perms[permidx][j] > j )
2395 rowisbinary[row] =
TRUE;
2397 orbitopevaridx[row][0] = j;
2398 orbitopevaridx[row++][1] = perms[permidx][j];
2400 ++(nusedelems[perms[permidx][j]]);
2405 if ( row == ntwocycles )
2413 if ( row != ntwocycles )
2415 *isorbitope =
FALSE;
2420 usedperm[ntestedperms - 1] =
TRUE;
2430 for (j = ntestedperms; j < nactiveperms; ++j)
2435 if ( nusedperms == nactiveperms )
2442 perms[activeperms[j]],
TRUE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2446 *isorbitope =
FALSE;
2453 coltoextend = nfilledcols;
2454 columnorder[nfilledcols++] = -1;
2459 if ( ! *isorbitope )
2466 for (j = ntestedperms; j < nactiveperms; ++j)
2471 if ( nusedperms == nactiveperms )
2478 perms[activeperms[j]],
FALSE, &nusedelems, permvars,
NULL, &success, &infeasible) );
2482 *isorbitope =
FALSE;
2489 coltoextend = nfilledcols;
2490 columnorder[nfilledcols] = 1;
2496 if ( activevars ==
NULL && nusedperms < nactiveperms )
2497 *isorbitope =
FALSE;
2499 if ( nusedcols !=
NULL )
2500 *nusedcols = nfilledcols;
2501 assert( ! *isorbitope || activevars ==
NULL || nusedperms < nfilledcols );
2520 int* componentbegins;
2526 assert( scip !=
NULL );
2527 assert( propdata !=
NULL );
2528 assert( compidx >= 0 );
2529 assert( compidx < propdata->ncomponents );
2530 assert( genorder !=
NULL );
2531 assert( *genorder !=
NULL );
2532 assert( ntwocycleperms !=
NULL );
2533 assert( propdata->computedsymmetry );
2534 assert( propdata->nperms > 0 );
2535 assert( propdata->perms !=
NULL );
2536 assert( propdata->npermvars > 0 );
2537 assert( propdata->ncomponents > 0 );
2538 assert( propdata->components !=
NULL );
2539 assert( propdata->componentbegins !=
NULL );
2541 perms = propdata->perms;
2542 npermvars = propdata->npermvars;
2544 componentbegins = propdata->componentbegins;
2545 npermsincomp = componentbegins[compidx + 1] - componentbegins[compidx];
2546 *ntwocycleperms = npermsincomp;
2550 for (i = 0; i < npermsincomp; ++i)
2555 perm = perms[
components[componentbegins[compidx] + i]];
2560 if ( ntwocycles[i] == 0 )
2563 if ( propdata->preferlessrows )
2564 ntwocycles[i] = npermvars;
2567 --(*ntwocycleperms);
2569 else if ( ! propdata->preferlessrows )
2570 ntwocycles[i] = - ntwocycles[i];
2594 int** graphcomponents,
2595 int** graphcompbegins,
2596 int** compcolorbegins,
2597 int* ngraphcomponents,
2610 int* componentbegins;
2611 int* componentslastperm;
2619 assert( scip !=
NULL );
2620 assert( propdata !=
NULL );
2621 assert( graphcomponents !=
NULL );
2622 assert( graphcompbegins !=
NULL );
2623 assert( compcolorbegins !=
NULL );
2624 assert( ngraphcomponents !=
NULL );
2625 assert( ncompcolors !=
NULL );
2626 assert( genorder !=
NULL );
2627 assert( usedperms !=
NULL );
2628 assert( nusedperms !=
NULL );
2629 assert( usedpermssize > 0 );
2630 assert( permused !=
NULL );
2631 assert( ntwocycleperms >= 0 );
2632 assert( compidx >= 0 );
2633 assert( compidx < propdata->ncomponents );
2634 assert( propdata->computedsymmetry );
2635 assert( propdata->nperms > 0 );
2636 assert( propdata->perms !=
NULL );
2637 assert( propdata->npermvars > 0 );
2638 assert( propdata->ncomponents > 0 );
2639 assert( propdata->components !=
NULL );
2640 assert( propdata->componentbegins !=
NULL );
2641 assert( ! propdata->componentblocked[compidx] );
2643 perms = propdata->perms;
2644 npermvars = propdata->npermvars;
2646 componentbegins = propdata->componentbegins;
2649 assert( ntwocycleperms <= componentbegins[compidx + 1] - componentbegins[compidx] );
2655 for (k = 0; k < npermvars; ++k)
2656 componentslastperm[k] = -1;
2658 for (j = 0; j < ntwocycleperms; ++j)
2661 int firstcolor = -1;
2664 perm = perms[
components[componentbegins[compidx] + genorder[j]]];
2665 assert( perm !=
NULL );
2668 for (k = 0; k < npermvars; ++k)
2677 assert( perm[img] == k );
2685 if ( comp1 == comp2 )
2688 if ( firstcolor < 0 )
2693 componentslastperm[comp1] = j;
2700 if ( componentslastperm[comp1] == j || componentslastperm[comp2] == j )
2707 if ( color1 == color2 )
2710 componentslastperm[comp1] = j;
2711 componentslastperm[comp2] = j;
2713 if ( firstcolor < 0 )
2714 firstcolor = color1;
2718 if ( k < npermvars )
2722 if ( firstcolor == -1 )
2726 if ( *nusedperms >= usedpermssize )
2729 assert( newsize > usedpermssize );
2733 usedpermssize = newsize;
2736 (*usedperms)[*nusedperms] =
components[componentbegins[compidx] + genorder[j]];
2738 permused[genorder[j]] =
TRUE;
2741 for (k = 0; k < npermvars; ++k)
2750 assert( perm[img] == k );
2759 if ( comp1 == comp2 )
2765 if ( color1 != color2 )
2789 for (j = 0; j < npermvars; ++j)
2798 (*graphcomponents)[j] = j;
2802 SCIPsort(*graphcomponents, SYMsortGraphCompVars, (
void*) &graphcompvartype, npermvars);
2811 (*graphcompbegins)[0] = 0;
2812 (*compcolorbegins)[0] = 0;
2815 for (j = 1; j < npermvars; ++j)
2820 idx1 = (*graphcomponents)[j];
2821 idx2 = (*graphcomponents)[j-1];
2823 assert( graphcompvartype.
colors[idx1] >= graphcompvartype.
colors[idx2] );
2827 (*graphcompbegins)[nextcomp] = j;
2829 if ( graphcompvartype.
colors[idx1] > graphcompvartype.
colors[idx2] )
2831 (*compcolorbegins)[nextcolor] = nextcomp;
2838 assert( nextcomp == *ngraphcomponents );
2839 assert( nextcolor == *ncompcolors );
2841 (*compcolorbegins)[nextcolor] = *ngraphcomponents;
2842 (*graphcompbegins)[nextcomp] = npermvars;
2860 int* compcolorbegins,
2861 int* graphcompbegins,
2862 int* graphcomponents,
2867 int* compidxfirstrow,
2870 int* maxnvarslexorder,
2878 int** orbitopevaridx;
2885 int nactivevars = 0;
2890 assert( scip !=
NULL );
2891 assert( propdata !=
NULL );
2892 assert( usedperms !=
NULL );
2893 assert( compcolorbegins !=
NULL );
2894 assert( graphcompbegins !=
NULL );
2895 assert( graphcomponents !=
NULL );
2896 assert( nusedperms > 0 );
2897 assert( nrows > 0 );
2898 assert( ncols > 0 );
2899 assert( lexorder !=
NULL );
2900 assert( nvarslexorder !=
NULL );
2901 assert( maxnvarslexorder !=
NULL );
2910 for (k = 0; k < nrows; ++k)
2917 for (k = 0; k < ncols; ++k)
2918 columnorder[k] = ncols + 1;
2924 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1]; ++k)
2930 compstart = graphcompbegins[k];
2931 firstvar = propdata->permvars[graphcomponents[compstart]];
2936 for (l = 0; l < ncols; ++l)
2940 varidx = graphcomponents[compstart + l];
2941 assert( ! activevars[varidx] );
2943 activevars[varidx] =
TRUE;
2949 assert( nactivevars == nrows * ncols );
2961 propdata->perms, usedperms, nrows, nusedperms, orbitopevaridx, columnorder,
2962 nusedelems, &ngencols,
NULL, &isorbitope, activevars) );
2971 for (k = nrows - 1; k >= 0; --k)
2991 if ( firstvaridx !=
NULL )
2993 if ( columnorder[ngencols-1] > -1 )
2994 *firstvaridx = orbitopevaridx[0][ngencols-1];
2996 *firstvaridx = orbitopevaridx[0][1];
3000 if ( compidxfirstrow !=
NULL && firstvaridx !=
NULL )
3002 *compidxfirstrow = -1;
3004 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3010 compstart = graphcompbegins[k];
3011 firstvar = propdata->permvars[graphcomponents[compstart]];
3019 for (l = 0; l < ncols; ++l)
3021 if ( graphcomponents[compstart + l] == *firstvaridx )
3023 *compidxfirstrow = k;
3028 assert( *compidxfirstrow > -1 );
3033 for (k = 0; k < nrows; ++k)
3040 propdata->permvars, propdata->npermvars, orbitopevaridx, columnorder,
3041 nusedelems,
NULL, &infeasible,
TRUE, lexorder, nvarslexorder, maxnvarslexorder) );
3043 assert( ! infeasible );
3044 assert( firstvaridx ==
NULL || propdata->permvars[*firstvaridx] == orbitopevarmatrix[0][0] );
3057 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3058 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3059 ++propdata->norbitopes;
3061 for (k = nrows - 1; k >= 0; --k)
3066 for (k = nrows - 1; k >= 0; --k)
3079 int* graphcompbegins,
3080 int* graphcomponents,
3090 assert( scip !=
NULL );
3091 assert( propdata !=
NULL );
3092 assert( graphcompbegins !=
NULL );
3093 assert( graphcomponents !=
NULL );
3094 assert( graphcompidx >= 0 );
3095 assert( ! storelexorder || lexorder !=
NULL );
3096 assert( ! storelexorder || nvarsorder !=
NULL );
3097 assert( ! storelexorder || maxnvarsorder !=
NULL );
3100 if ( storelexorder )
3102 if ( *maxnvarsorder == 0 )
3104 *maxnvarsorder = graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3111 assert( *nvarsorder == *maxnvarsorder );
3113 *maxnvarsorder += graphcompbegins[graphcompidx + 1] - graphcompbegins[graphcompidx + 1];
3118 (*lexorder)[*nvarsorder++] = graphcomponents[graphcompbegins[graphcompidx]];
3122 for (k = graphcompbegins[graphcompidx]+1; k < graphcompbegins[graphcompidx+1]; ++k)
3129 vars[0] = propdata->permvars[graphcomponents[k-1]];
3130 vars[1] = propdata->permvars[graphcomponents[k]];
3132 if ( storelexorder )
3133 (*lexorder)[*nvarsorder++] = graphcomponents[k];
3143 #ifdef SCIP_MORE_DEBUG 3150 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3151 propdata->genlinconss[propdata->ngenlinconss] = cons;
3152 ++propdata->ngenlinconss;
3163 int* compcolorbegins,
3164 int* graphcompbegins,
3165 int* graphcomponents,
3167 int* chosencomppercolor,
3168 int* firstvaridxpercolor,
3183 int orbitsize[2] = {1, 1};
3185 int chosencolor = -1;
3189 assert( scip !=
NULL );
3190 assert( propdata !=
NULL );
3191 assert( compcolorbegins !=
NULL );
3192 assert( graphcompbegins !=
NULL );
3193 assert( graphcomponents !=
NULL );
3194 assert( firstvaridxpercolor !=
NULL );
3195 assert( chosencomppercolor !=
NULL );
3196 assert( naddedconss !=
NULL );
3197 assert( symgrpcompidx >= 0 );
3198 assert( symgrpcompidx < propdata->ncomponents );
3199 assert( ! storelexorder || lexorder !=
NULL );
3200 assert( ! storelexorder || nvarsorder !=
NULL );
3201 assert( ! storelexorder || maxnvarsorder !=
NULL );
3211 if ( lexorder ==
NULL || *lexorder ==
NULL )
3214 varsinlexorder =
NULL;
3218 assert( *maxnvarsorder >= 0 );
3219 assert( *nvarsorder >= 0 );
3223 for (k = 0; k < *nvarsorder; ++k)
3227 assert((*lexorder)[k] >= 0);
3235 if ( ncompcolors > 0 )
3239 for (j = 0; j < ncompcolors; ++j)
3246 if ( chosencomppercolor[j] < 0 )
3249 assert( firstvaridxpercolor[j] >= 0 );
3251 graphcomp = chosencomppercolor[j];
3252 graphcompsize = graphcompbegins[graphcomp+1] - graphcompbegins[graphcomp];
3253 varidx = firstvaridxpercolor[j];
3254 assert(varidx >= 0);
3258 if ( varfound[varidx] || graphcompsize == propdata->npermvars )
3262 if ( varsinlexorder !=
NULL 3264 && lexorder !=
NULL && *lexorder !=
NULL && *maxnvarsorder > 0 && *nvarsorder > 0
3265 && (*lexorder)[0] != varidx )
3269 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3271 assert( 0 <= graphcomponents[k] && graphcomponents[k] < propdata->npermvars );
3273 usedvars[graphcomponents[k]] =
TRUE;
3277 propdata->permstrans, propdata->components, propdata->componentbegins,
3278 usedvars, varfound, varidx, symgrpcompidx,
3279 orbit[activeorb], &orbitsize[activeorb]) );
3281 assert( orbit[activeorb][0] == varidx );
3283 if ( orbitsize[activeorb] > orbitsize[1 - activeorb] )
3286 activeorb = 1 - activeorb;
3291 for (k = graphcompbegins[graphcomp]; k < graphcompbegins[graphcomp+1]; ++k)
3292 usedvars[graphcomponents[k]] =
FALSE;
3296 if ( chosencolor > -1 )
3299 activeorb = 1 - activeorb;
3301 assert( orbit[activeorb][0] == firstvaridxpercolor[chosencolor] );
3302 vars[0] = propdata->permvars[orbit[activeorb][0]];
3304 assert( chosencolor > -1 );
3305 SCIPdebugMsg(scip,
" adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3307 *naddedconss = orbitsize[activeorb] - 1;
3310 for (j = 1; j < orbitsize[activeorb]; ++j)
3315 vars[1] = propdata->permvars[orbit[activeorb][j]];
3325 #ifdef SCIP_MORE_DEBUG 3332 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
3333 propdata->genlinconss[propdata->ngenlinconss] = cons;
3334 ++propdata->ngenlinconss;
3338 if ( storelexorder )
3342 varidx = orbit[activeorb][0];
3343 assert(varidx >= 0);
3345 if ( *maxnvarsorder == 0 )
3351 (*lexorder)[(*nvarsorder)++] = varidx;
3355 assert( *nvarsorder == *maxnvarsorder );
3356 assert( varsinlexorder !=
NULL );
3357 assert( lexorder !=
NULL );
3358 assert( *lexorder !=
NULL );
3361 if ( varidx == (*lexorder)[0] )
3378 for (k = *maxnvarsorder - 1; k >= 1; --k)
3379 (*lexorder)[k] = (*lexorder)[k - 1];
3381 (*lexorder)[0] = varidx;
3387 SCIPdebugMsg(scip,
" no further weak sbcs are valid\n");
3391 if ( varsinlexorder !=
NULL )
3405 int** modifiedperms,
3424 assert( scip !=
NULL );
3425 assert( origperms !=
NULL );
3426 assert( modifiedperms !=
NULL );
3427 assert( nperms > 0 );
3428 assert( origpermvars !=
NULL );
3429 assert( modifiedpermvars !=
NULL );
3430 assert( npermvars > 0 );
3431 assert( leaders !=
NULL );
3432 assert( nleaders > 0 );
3436 for (i = 0; i < npermvars; ++i)
3441 for (i = 0; i < npermvars; ++i)
3442 posinpermvar[i] = i;
3446 for (l = 0; l < nleaders; ++l)
3448 leader = leaders[l];
3449 curposleader = posinpermvar[leader];
3450 varidx = permvaridx[curposleader];
3451 lidx = permvaridx[l];
3454 permvaridx[curposleader] = lidx;
3455 permvaridx[l] = varidx;
3458 posinpermvar[lidx] = curposleader;
3459 posinpermvar[leader] = l;
3463 for (i = 0; i < npermvars; ++i)
3464 modifiedpermvars[i] = origpermvars[permvaridx[i]];
3467 for (p = 0; p < nperms; ++p)
3469 for (i = 0; i < npermvars; ++i)
3470 modifiedperms[p][i] = posinpermvar[origperms[p][permvaridx[i]]];
3486 int* graphcomponents,
3487 int* graphcompbegins,
3488 int* compcolorbegins,
3498 assert( graphcompbegins !=
NULL );
3499 assert( compcolorbegins !=
NULL );
3500 assert( ncompcolors >= 0 );
3501 assert( symcompsize > 0 );
3503 for (j = 0; j < ncompcolors; ++j)
3506 int largestcompsize = 0;
3511 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3515 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3519 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3522 if ( largestcompsize < 1 )
3527 largestcompsize = compsize;
3529 else if ( compsize != largestcompsize )
3532 firstvar = permvars[graphcomponents[graphcompbegins[k]]];
3540 if ( k == compcolorbegins[j+1] )
3546 ncols = graphcompbegins[compcolorbegins[j] + 1] - graphcompbegins[compcolorbegins[j]];
3548 threshold = 0.7 * (
SCIP_Real) symcompsize;
3551 if ( nbinrows <= 2 * ncols || (nbinrows <= 8 * ncols && nbinrows < 100) )
3552 multorbitopecriterion =
TRUE;
3553 else if ( nbinrows <= 3 * ncols || (
SCIP_Real) nbinrows * ncols >= threshold )
3554 oneorbitopecriterion =
TRUE;
3558 if ( (norbitopes == 1 && oneorbitopecriterion) || (norbitopes >= 2 && multorbitopecriterion) )
3577 int nstrongsbcs = 0;
3580 int** modifiedperms;
3582 int* nvarsincomponent;
3584 int* graphcomponents;
3585 int* graphcompbegins;
3586 int* compcolorbegins;
3587 int* chosencomppercolor =
NULL;
3588 int* firstvaridxpercolor =
NULL;
3591 int ngraphcomponents;
3596 int ntrivialcolors = 0;
3598 int* lexorder =
NULL;
3599 int nvarslexorder = 0;
3600 int maxnvarslexorder = 0;
3604 int norbitopesincomp;
3606 assert( scip !=
NULL );
3607 assert( propdata !=
NULL );
3608 assert( propdata->computedsymmetry );
3609 assert( propdata->nperms >= 0 );
3610 assert( 0 <= cidx && cidx < propdata->ncomponents );
3611 assert( propdata->components !=
NULL );
3612 assert( propdata->componentbegins !=
NULL );
3615 if ( propdata->nperms == 0 || propdata->componentblocked[cidx] )
3622 assert( propdata->nperms > 0 );
3623 assert( propdata->perms !=
NULL );
3624 assert( propdata->npermvars > 0 );
3625 assert( propdata->permvars !=
NULL );
3632 for (p = 0; p < propdata->nperms; ++p)
3639 for (p = 0; p < propdata->npermvars; ++p)
3641 if ( propdata->vartocomponent[p] >= 0 )
3642 ++nvarsincomponent[propdata->vartocomponent[p]];
3645 SCIPdebugMsg(scip,
"starting subgroup detection routine for component %d\n", cidx);
3647 npermsincomp = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
3650 for (j = 0; j < npermsincomp; ++j)
3655 assert( ntwocycleperms >= 0 );
3656 assert( ntwocycleperms <= npermsincomp );
3658 SCIPdebugMsg(scip,
"component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
3660 #ifdef SCIP_MORE_DEBUG 3667 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx+1]; ++p)
3669 perm = propdata->components[p];
3671 for (k = 0; k < propdata->npermvars; ++k)
3676 for (k = 0; k < propdata->npermvars; ++k)
3681 j = propdata->perms[perm][k];
3693 j = propdata->perms[perm][j];
3703 if ( ntwocycleperms < 2 )
3709 usedpermssize = ntwocycleperms / 2;
3714 &graphcomponents, &graphcompbegins, &compcolorbegins, &ngraphcomponents,
3715 &ncompcolors, &usedperms, &nusedperms, usedpermssize, permused) );
3717 SCIPdebugMsg(scip,
" created subgroup detection graph using %d of the permutations\n", nusedperms);
3719 if ( nusedperms == npermsincomp )
3720 allpermsused =
TRUE;
3722 assert( graphcomponents !=
NULL );
3723 assert( graphcompbegins !=
NULL );
3724 assert( compcolorbegins !=
NULL );
3725 assert( ngraphcomponents > 0 );
3726 assert( ncompcolors > 0 );
3727 assert( nusedperms <= ntwocycleperms );
3728 assert( ncompcolors < propdata->npermvars );
3730 if ( nusedperms == 0 )
3732 SCIPdebugMsg(scip,
" -> skipping component, since less no permutation was used\n");
3740 SCIPdebugMsg(scip,
" number of different colors in the graph: %d\n", ncompcolors);
3742 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3751 for (j = 0; j < ncompcolors; ++j)
3753 chosencomppercolor[j] = -1;
3754 firstvaridxpercolor[j] = -1;
3758 norbitopesincomp =
getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3759 ncompcolors, nvarsincomponent[cidx]);
3762 if ( norbitopesincomp == 1 )
3766 for (k = 0; k < npermsincomp; ++k)
3774 propdata->perms[propdata->components[propdata->componentbegins[cidx] + k]],
3775 propdata->permvars, propdata->npermvars,
FALSE,
3781 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
3782 propdata->genorbconss[propdata->ngenorbconss++] = cons;
3783 ++propdata->nsymresacks;
3785 if ( ! propdata->componentblocked[cidx] )
3788 ++propdata->ncompblocked;
3791 SCIPdebugMsg(scip,
" add symresack for permutation %d of component %d\n", k, cidx);
3797 for (j = 0; j < ncompcolors; ++j)
3799 int nbinarycomps = 0;
3800 int largestcolorcomp = -1;
3801 int largestcompsize = 0;
3813 if ( graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]] < 2 )
3815 if( chosencomppercolor !=
NULL )
3816 chosencomppercolor[j] = -1;
3822 SCIPdebugMsg(scip,
" color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
3823 graphcompbegins[compcolorbegins[j+1]] - graphcompbegins[compcolorbegins[j]]);
3826 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3831 compsize = graphcompbegins[k+1] - graphcompbegins[k];
3834 if ( largestcompsize < 1 )
3842 largestcompsize = compsize;
3843 largestcolorcomp = k;
3845 else if ( compsize != largestcompsize )
3852 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3860 for (k = compcolorbegins[j]; k < compcolorbegins[j+1]; ++k)
3864 firstvar = propdata->permvars[graphcomponents[graphcompbegins[k]]];
3871 contaffected =
TRUE;
3874 SCIPdebugMsg(scip,
" affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
3878 useorbitope =
FALSE;
3879 if ( norbitopesincomp > 0 && nbinarycomps > 0 )
3882 if ( isorbitope && useorbitope )
3887 SCIPdebugMsg(scip,
" detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
3889 assert( nbinarycomps > 0 );
3890 assert( largestcompsize > 2 );
3898 graphcompbegins, graphcomponents, j, nbinarycomps, largestcompsize, &firstvaridx, &chosencomp,
3899 &lexorder, &nvarslexorder, &maxnvarslexorder, allpermsused, &orbitopeadded) );
3901 if ( orbitopeadded )
3903 if ( propdata->addstrongsbcs || propdata->addweaksbcs )
3905 assert( chosencomppercolor !=
NULL );
3906 assert( firstvaridxpercolor !=
NULL );
3909 assert( compcolorbegins[j] <= chosencomp && chosencomp < compcolorbegins[j+1] );
3910 assert( 0 <= firstvaridx && firstvaridx < propdata->npermvars );
3912 chosencomppercolor[j] = chosencomp;
3913 firstvaridxpercolor[j] = firstvaridx;
3916 if ( ! propdata->componentblocked[cidx] )
3919 ++propdata->ncompblocked;
3929 if ( propdata->addstrongsbcs && ! orbitopeadded )
3931 assert( largestcolorcomp >= 0 );
3932 assert( largestcolorcomp < ngraphcomponents );
3933 assert( largestcompsize > 0 );
3935 if( propdata->addweaksbcs )
3937 assert( chosencomppercolor !=
NULL );
3938 assert( firstvaridxpercolor !=
NULL );
3940 chosencomppercolor[j] = largestcolorcomp;
3941 firstvaridxpercolor[j] = graphcomponents[graphcompbegins[largestcolorcomp]];
3944 SCIPdebugMsg(scip,
" choosing component %d with %d variables and adding strong SBCs\n",
3945 largestcolorcomp, graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp]);
3949 propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3952 if ( !
SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
3953 handlednonbinarysymmetry =
TRUE;
3955 if ( ! propdata->componentblocked[cidx] )
3958 ++propdata->ncompblocked;
3962 nstrongsbcs += graphcompbegins[largestcolorcomp+1] - graphcompbegins[largestcolorcomp] - 1;
3965 else if ( ! orbitopeadded )
3967 SCIPdebugMsg(scip,
" no useable orbitope found and no SBCs added\n");
3970 if ( propdata->addweaksbcs )
3972 assert( chosencomppercolor !=
NULL );
3973 chosencomppercolor[j] = -1;
3978 SCIPdebugMsg(scip,
" skipped %d trivial colors\n", ntrivialcolors);
3981 if ( propdata->addweaksbcs && propdata->componentblocked[cidx] && nusedperms < npermsincomp )
3985 assert( firstvaridxpercolor !=
NULL );
3986 assert( chosencomppercolor !=
NULL );
3989 graphcomponents, ncompcolors, chosencomppercolor, firstvaridxpercolor,
3990 cidx, &naddedconss, propdata->addsymresacks, &lexorder, &nvarslexorder, &maxnvarslexorder) );
3992 assert( naddedconss < propdata->npermvars );
3995 nweaksbcs += naddedconss;
3999 SCIPdebugMsg(scip,
" don't add weak sbcs because all generators were used or the settings forbid it\n");
4004 if ( nvarslexorder > 0 && propdata->addsymresacks && ! handlednonbinarysymmetry )
4009 propdata->permvars, modifiedpermvars, propdata->npermvars, lexorder, nvarslexorder) );
4011 for (k = 0; k < npermsincomp; ++k)
4023 symresackperm = modifiedperms[propdata->components[propdata->componentbegins[cidx] + k]];
4024 for (j = 0; j < propdata->nperms && !actsonbinary; ++j)
4027 actsonbinary =
TRUE;
4030 if ( ! actsonbinary )
4036 symresackperm, modifiedpermvars, propdata->npermvars,
FALSE,
4042 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4043 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4044 ++propdata->nsymresacks;
4046 if ( ! propdata->componentblocked[cidx] )
4049 ++propdata->ncompblocked;
4052 SCIPdebugMsg(scip,
" add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, cidx);
4068 SCIPdebugMsg(scip,
"total number of added (sub-)orbitopes: %d\n", norbitopes);
4069 SCIPdebugMsg(scip,
"total number of added strong sbcs: %d\n", nstrongsbcs);
4070 SCIPdebugMsg(scip,
"total number of added weak sbcs: %d\n", nweaksbcs);
4077 for (p = propdata->nperms - 1; p >= 0; --p)
4097 SCIP_CONFLICTDATA* varconflicts,
4111 assert( scip !=
NULL );
4112 assert( varconflicts !=
NULL );
4113 assert( conflictvars !=
NULL );
4114 assert( nconflictvars > 0 );
4115 assert( orbits !=
NULL );
4116 assert( orbitbegins !=
NULL );
4117 assert( norbits >= 0 );
4120 for (i = 0; i < nconflictvars; ++i)
4123 varconflicts[i].orbitidx = -1;
4124 varconflicts[i].nconflictinorbit = 0;
4125 varconflicts[i].orbitsize = -1;
4126 varconflicts[i].posinorbit = -1;
4130 for (
r = 0;
r < norbits; ++
r)
4135 orbitsize = orbitbegins[
r + 1] - orbitbegins[
r];
4136 assert( orbitsize >= 0 );
4138 for (i = orbitbegins[
r]; i < orbitbegins[
r + 1]; ++i)
4144 assert( pos < nconflictvars );
4145 assert( varconflicts[pos].var == conflictvars[pos] );
4147 varconflicts[pos].orbitidx =
r;
4148 varconflicts[pos].nconflictinorbit = 0;
4149 varconflicts[pos].orbitsize = orbitsize;
4150 varconflicts[pos].posinorbit = posinorbit++;
4160 for (i = orbitbegins[
r]; i < orbitbegins[
r + 1]; ++i)
4163 assert( varconflicts[ii].orbitidx ==
r );
4166 if ( ! varconflicts[ii].
active )
4169 for (j = i + 1; j < orbitbegins[
r + 1]; ++j)
4172 assert( varconflicts[jj].orbitidx ==
r );
4175 if ( ! varconflicts[jj].active )
4185 varconflicts[ii].ncliques, (
void**)varconflicts[jj].cliques, varconflicts[jj].ncliques,
4186 sortByPointerValue) )
4189 ++varconflicts[ii].nconflictinorbit;
4190 ++varconflicts[jj].nconflictinorbit;
4210 SCIP_CONFLICTDATA** varconflicts,
4227 int varncliques = 0;
4230 assert( scip !=
NULL );
4231 assert( varconflicts !=
NULL );
4232 assert( conflictvars !=
NULL );
4233 assert( nconflictvars > 0 );
4236 *varconflicts =
NULL;
4242 if ( ncliques == 0 )
4244 SCIPdebugMsg(scip,
"No cliques present --> construction of conflict structure aborted.\n");
4249 SCIPdebugMsg(scip,
"Construction of conflict structure:\n");
4251 for (i = 0; i < nconflictvars; ++i)
4253 (*varconflicts)[i].ncliques = 0;
4254 (*varconflicts)[i].active =
TRUE;
4255 (*varconflicts)[i].var = conflictvars[i];
4257 (*varconflicts)[i].cliques =
NULL;
4258 (*varconflicts)[i].orbitidx = -1;
4259 (*varconflicts)[i].nconflictinorbit = 0;
4260 (*varconflicts)[i].orbitsize = -1;
4261 (*varconflicts)[i].posinorbit = -1;
4271 for (c = 0; c < ncliques; ++c)
4273 clique = cliques[c];
4274 assert( clique !=
NULL );
4278 assert( cliquevars !=
NULL );
4279 assert( ncliquevars > 0 );
4285 for (i = 0; i < ncliquevars; ++i)
4290 if ( node == INT_MAX )
4292 assert( node >= 0 );
4293 assert( node < nconflictvars );
4295 assert( (*varconflicts)[node].var == cliquevars[i] );
4296 (*varconflicts)[node].active =
TRUE;
4297 (*varconflicts)[node].ncliques++;
4302 for (i = 0; i < nconflictvars; ++i)
4304 assert( (*varconflicts)[i].ncliques >= 0 );
4305 assert( (*varconflicts)[i].cliques ==
NULL );
4306 if ( (*varconflicts)[i].ncliques > 0 )
4314 for (c = 0; c < ncliques; ++c)
4316 clique = cliques[c];
4317 assert( clique !=
NULL );
4321 assert( cliquevars !=
NULL );
4322 assert( ncliquevars > 0 );
4328 for (i = 0; i < ncliquevars; ++i)
4333 if ( node == INT_MAX )
4336 assert( node >= 0 );
4337 assert( node < nconflictvars );
4338 assert( (*varconflicts)[node].var == cliquevars[i] );
4341 assert( tmpncliques[node] < (*varconflicts)[node].ncliques );
4342 assert( (*varconflicts)[node].cliques !=
NULL );
4343 (*varconflicts)[node].cliques[tmpncliques[node]++] = clique;
4352 for (i = 0; i < nconflictvars; ++i)
4354 SCIPsortPtr((
void**)(*varconflicts)[i].cliques, sortByPointerValue, (*varconflicts)[i].ncliques);
4358 for (i = 0; i < nconflictvars; ++i)
4360 assert( tmpncliques[i] == (*varconflicts)[i].ncliques );
4367 SCIPdebugMsg(scip,
"Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4378 SCIP_CONFLICTDATA** varconflicts,
4385 assert( scip !=
NULL );
4386 assert( varconflicts !=
NULL );
4387 assert( *varconflicts !=
NULL );
4388 assert( nvars >= 0 );
4390 for (i = nvars - 1; i >= 0; --i)
4392 n = (*varconflicts)[i].ncliques;
4410 int* componentbegins;
4413 int** modifiedperms =
NULL;
4416 int nsymresackcons = 0;
4422 assert( scip !=
NULL );
4423 assert( propdata !=
NULL );
4424 assert( propdata->npermvars >= 0 );
4425 assert( propdata->nbinpermvars >= 0 );
4428 if ( propdata->nbinpermvars == 0 )
4430 assert( propdata->binvaraffected == 0 );
4434 perms = propdata->perms;
4435 nperms = propdata->nperms;
4436 permvars = propdata->permvars;
4437 npermvars = propdata->npermvars;
4438 conssaddlp = propdata->conssaddlp;
4440 componentbegins = propdata->componentbegins;
4442 assert( nperms <= 0 || perms !=
NULL );
4443 assert( permvars !=
NULL );
4444 assert( npermvars > 0 );
4446 assert( componentbegins !=
NULL );
4447 assert( 0 <= cidx && cidx < propdata->ncomponents );
4462 if ( propdata->componenthassignedperm[cidx] )
4466 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4469 for (p = 0; p < nperms; ++p)
4475 for (i = 0; i < npermvars; ++i)
4476 modifiedpermvars[i] = permvars[i];
4479 propdata->leaders, propdata->nleaders) );
4483 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
4494 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4497 assert( modifiedperms !=
NULL );
4498 assert( modifiedpermvars !=
NULL );
4513 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
4514 propdata->genorbconss[propdata->ngenorbconss++] = cons;
4515 ++propdata->nsymresacks;
4519 if ( propdata->nleaders > 0 &&
ISSSTBINACTIVE(propdata->sstleadervartype) )
4521 assert( modifiedperms !=
NULL );
4522 assert( modifiedpermvars !=
NULL );
4525 for (p = nperms - 1; p >= 0; --p)
4532 SCIPdebugMsg(scip,
"Added %d symresack constraints.\n", nsymresackcons);
4542 SCIP_CONFLICTDATA* varconflicts,
4550 int norbitvarinconflict,
4568 assert( scip !=
NULL );
4569 assert( propdata !=
NULL );
4570 assert( permvars !=
NULL );
4571 assert( orbits !=
NULL );
4572 assert( orbitbegins !=
NULL );
4573 assert( orbitidx >= 0 );
4574 assert( orbitleaderidx >= 0 );
4575 assert( orbitvarinconflict !=
NULL || varconflicts ==
NULL );
4576 assert( norbitvarinconflict >= 0 );
4577 assert( nchgbds !=
NULL );
4579 orbitsize = orbitbegins[orbitidx + 1] - orbitbegins[orbitidx];
4582 if ( propdata->sstaddcuts )
4586 addcuts = propdata->addconflictcuts;
4589 ncuts = orbitsize - norbitvarinconflict - 1;
4594 if ( propdata->nsstconss == 0 )
4596 assert( propdata->sstconss ==
NULL );
4597 assert( propdata->maxnsstconss == 0 );
4598 propdata->maxnsstconss = 2 * ncuts;
4601 else if ( propdata->nsstconss + ncuts > propdata->maxnsstconss )
4607 propdata->maxnsstconss, newsize) );
4608 propdata->maxnsstconss = newsize;
4612 if ( propdata->nleaders == 0 )
4614 propdata->maxnleaders =
MIN(propdata->nperms, propdata->npermvars);
4617 assert( propdata->nleaders < propdata->maxnleaders );
4620 posleader = orbitbegins[orbitidx] + orbitleaderidx;
4621 vars[0] = permvars[orbits[posleader]];
4624 propdata->leaders[propdata->nleaders++] = orbits[posleader];
4626 for (i = 0, poscur = orbitbegins[orbitidx]; i < orbitsize; ++i, ++poscur)
4628 if ( i == orbitleaderidx )
4630 assert( orbitvarinconflict ==
NULL || ! orbitvarinconflict[i] );
4634 vars[1] = permvars[orbits[poscur]];
4636 for (j = 0; j < propdata->nleaders - 1; ++j)
4638 assert( propdata->leaders[j] != orbits[poscur] );
4643 if ( varconflicts !=
NULL )
4645 if ( orbitvarinconflict[i] )
4649 assert( varconflicts !=
NULL );
4658 assert( varconflicts[orbits[poscur]].
active );
4659 varconflicts[orbits[poscur]].active =
FALSE;
4663 orbitvarinconflict[i] =
FALSE;
4672 propdata->sstconss[propdata->nsstconss++] = cons;
4682 propdata->sstconss[propdata->nsstconss++] = cons;
4694 SCIP_CONFLICTDATA* varconflicts,
4706 int* norbitvarinconflict,
4712 int curcriterion = INT_MIN;
4717 assert( scip !=
NULL );
4718 assert( conflictvars !=
NULL );
4719 assert( nconflictvars > 0 );
4720 assert( orbits !=
NULL );
4721 assert( orbitbegins !=
NULL );
4722 assert( norbits > 0 );
4723 assert( orbitidx !=
NULL );
4724 assert( leaderidx !=
NULL );
4725 assert( orbitvarinconflict !=
NULL || varconflicts ==
NULL );
4726 assert( norbitvarinconflict !=
NULL );
4727 assert( success !=
NULL );
4731 *norbitvarinconflict = 0;
4742 orbitcriterion = INT_MIN;
4745 for (i = 0; i < norbits; ++i)
4749 if (
SCIPvarGetType(conflictvars[orbits[orbitbegins[i]]]) != leadervartype )
4753 curcriterion = orbitbegins[i] - orbitbegins[i + 1];
4755 curcriterion = orbitbegins[i + 1] - orbitbegins[i];
4765 cnt = orbitbegins[i];
4769 varidx = orbits[cnt++];
4777 cnt = orbitbegins[i + 1] - 1;
4781 varidx = orbits[cnt--];
4790 assert( varconflicts[varidx].orbitidx == i );
4792 curcriterion = varconflicts[varidx].nconflictinorbit;
4796 if ( curcriterion > orbitcriterion )
4798 orbitcriterion = curcriterion;
4805 *leaderidx = orbitbegins[i + 1] - orbitbegins[i] - 1;
4810 if ( *success && varconflicts !=
NULL )
4812 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4813 assert( leader < nconflictvars );
4816 && varconflicts[leader].ncliques > 0 )
4823 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4824 assert( varconflicts !=
NULL );
4825 assert( leader >= 0 && leader < nconflictvars );
4827 assert( orbitvarinconflict !=
NULL );
4829 for (i = 0; i < orbitsize; ++i)
4832 if ( i == *leaderidx )
4836 varmapid = orbits[orbitbegins[*orbitidx] + i];
4839 if ( ! varconflicts[varmapid].
active )
4844 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4845 varconflicts[varmapid].ncliques, sortByPointerValue) )
4848 orbitvarinconflict[i] =
TRUE;
4849 ++(*norbitvarinconflict);
4861 assert( varconflicts !=
NULL );
4866 for (i = 0; i < nconflictvars; ++i)
4874 if ( varconflicts[i].orbitidx == -1 )
4877 curcriterion = varconflicts[i].nconflictinorbit;
4879 if ( curcriterion > orbitcriterion )
4881 orbitcriterion = curcriterion;
4882 *orbitidx = varconflicts[i].orbitidx;
4883 *leaderidx = varconflicts[i].posinorbit;
4889 leader = orbits[orbitbegins[*orbitidx] + *leaderidx];
4890 assert( leader < nconflictvars );
4891 assert( norbitvarinconflict !=
NULL );
4893 if ( *success && varconflicts[leader].ncliques > 0 )
4898 orbitsize = orbitbegins[*orbitidx + 1] - orbitbegins[*orbitidx];
4899 assert( varconflicts !=
NULL );
4900 assert( leader >= 0 && leader < nconflictvars );
4902 assert( orbitvarinconflict !=
NULL );
4904 for (i = 0; i < orbitsize; ++i)
4907 if ( i == *leaderidx )
4911 varmapid = orbits[orbitbegins[*orbitidx] + i];
4913 if ( ! varconflicts[varmapid].
active )
4918 varconflicts[leader].ncliques, (
void**)varconflicts[varmapid].cliques,
4919 varconflicts[varmapid].ncliques, sortByPointerValue) )
4922 orbitvarinconflict[i] =
TRUE;
4923 ++(*norbitvarinconflict);
4943 SCIP_CONFLICTDATA* varconflicts =
NULL;
4949 int nmovedbinpermvars;
4950 int nmovedintpermvars;
4951 int nmovedimplintpermvars;
4952 int nmovedcontpermvars;
4959 int* componentbegins;
4960 int* vartocomponent;
4962 unsigned* componentblocked;
4967 int norbitvarinconflict;
4975 int nvarsselectedtype;
4978 int norbitleadercomponent;
4987 assert( scip !=
NULL );
4988 assert( propdata !=
NULL );
4989 assert( propdata->computedsymmetry );
4991 permvars = propdata->permvars;
4992 npermvars = propdata->npermvars;
4993 nperms = propdata->nperms;
4994 assert( permvars !=
NULL );
4995 assert( npermvars > 0 );
4996 assert( nperms > 0 );
4999 permvarmap = propdata->permvarmap;
5000 assert( permvarmap !=
NULL );
5003 permstrans = propdata->permstrans;
5004 assert( permstrans !=
NULL );
5007 componentbegins = propdata->componentbegins;
5008 componentblocked = propdata->componentblocked;
5009 vartocomponent = propdata->vartocomponent;
5010 ncomponents = propdata->ncomponents;
5013 assert( componentbegins !=
NULL );
5014 assert( vartocomponent !=
NULL );
5015 assert( componentblocked !=
NULL );
5016 assert( ncomponents > 0 );
5017 assert( 0 <= cidx && cidx < ncomponents );
5020 if ( componentblocked[cidx] )
5024 if ( propdata->componenthassignedperm[cidx] )
5027 leaderrule = propdata->sstleaderrule;
5028 tiebreakrule = propdata->ssttiebreakrule;
5029 leadervartype = propdata->sstleadervartype;
5030 mixedcomponents = propdata->sstmixedcomponents;
5034 nmovedpermvars = propdata->nmovedpermvars;
5035 nmovedbinpermvars = propdata->nmovedbinpermvars;
5036 nmovedintpermvars = propdata->nmovedintpermvars;
5037 nmovedimplintpermvars = propdata->nmovedimplintpermvars;
5038 nmovedcontpermvars = propdata->nmovedcontpermvars;
5039 assert( nmovedpermvars > 0 );
5042 nvarsselectedtype = 0;
5043 if (
ISSSTBINACTIVE(leadervartype) && nmovedbinpermvars > nvarsselectedtype )
5046 nvarsselectedtype = nmovedbinpermvars;
5049 if (
ISSSTINTACTIVE(leadervartype) && nmovedintpermvars > nvarsselectedtype )
5052 nvarsselectedtype = nmovedintpermvars;
5055 if (
ISSSTIMPLINTACTIVE(leadervartype) && nmovedimplintpermvars > nvarsselectedtype )
5058 nvarsselectedtype = nmovedimplintpermvars;
5061 if (
ISSSTCONTACTIVE(leadervartype) && nmovedcontpermvars > nvarsselectedtype )
5064 nvarsselectedtype = nmovedcontpermvars;
5068 if ( nvarsselectedtype == 0 )
5072 if ( onlywithcontvars )
5074 for (p = componentbegins[cidx]; p < componentbegins[cidx + 1]; ++p)
5076 perm = propdata->perms[p];
5077 for (i = 0; i < propdata->npermvars; ++i)
5099 conflictgraphcreated = varconflicts !=
NULL;
5107 if ( conflictgraphcreated )
5112 SCIPdebugMsg(scip,
"Start selection of orbits and leaders for Schreier Sims constraints.\n");
5113 SCIPdebugMsg(scip,
"orbitidx\tleaderidx\torbitsize\n");
5115 if ( nchgbds !=
NULL )
5119 for (c = 0; c < ncomponents; ++c)
5121 for (p = componentbegins[c]; p < componentbegins[c + 1]; ++p)
5126 inactiveperms[components[p]] =
TRUE;
5129 ninactiveperms = nperms - componentbegins[cidx + 1] + componentbegins[cidx];
5132 norbitleadercomponent = 0;
5133 while ( ninactiveperms < nperms )
5139 orbits, orbitbegins, &norbits,
components, componentbegins, vartocomponent,
5140 componentblocked, ncomponents, nmovedpermvars) );
5143 if ( ! mixedcomponents )
5145 for (p = 0; p < norbits; ++p)
5148 if (
SCIPvarGetType(permvars[orbits[orbitbegins[p]]]) != selectedtype )
5160 if ( conflictgraphcreated )
5178 norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype, &orbitidx, &orbitleaderidx,
5179 orbitvarinconflict, &norbitvarinconflict, &success) );
5184 assert( 0 <= orbitidx && orbitidx < norbits );
5185 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5186 SCIPdebugMsg(scip,
"%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5190 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5192 ++norbitleadercomponent;
5194 if ( nchgbds !=
NULL )
5195 *nchgbds += nchanges;
5198 posleader = orbits[orbitbegins[orbitidx] + orbitleaderidx];
5199 for (p = 0; p < nperms; ++p)
5201 if ( inactiveperms[p] )
5204 if ( permstrans[posleader][p] != posleader )
5206 inactiveperms[p] =
TRUE;
5213 if ( norbitleadercomponent > 0 )
5216 if ( conflictgraphcreated )
5222 if ( varconflicts !=
NULL )
5255 assert( scip !=
NULL );
5256 assert( propdata !=
NULL );
5257 assert( propdata->usedynamicprop );
5258 assert( varidxmatrix !=
NULL );
5259 assert( nrows > 0 );
5260 assert( ncols > 0 );
5261 assert( success !=
NULL );
5275 &propdata->genlinconsssize, propdata->ngenlinconss + ncols - 1) );
5276 for (i = 0; i < ncols - 1; ++i)
5280 consvars[0] = propdata->permvars[varidxmatrix[0][i]];
5281 consvars[1] = propdata->permvars[varidxmatrix[0][i + 1]];
5288 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5296 if ( ncols == 2 && propdata->lexreddata !=
NULL )
5301 orbisackperm = propdata->perms[propdata->components[propdata->componentbegins[id]]];
5304 propdata->permvars, propdata->npermvars, orbisackperm, (
SYM_SYMTYPE) propdata->symtype,
5305 propdata->permvardomaincenter,
TRUE, success) );
5312 for (i = 0; i < nrows; ++i)
5315 for (j = 0; j < ncols; ++j)
5316 varmatrix[i][j] = propdata->permvars[varidxmatrix[i][j]];
5323 ispporbitope = npprows >= 3;
5332 assert( pprows !=
NULL );
5337 for (i = 0; i < nrows; ++i)
5341 assert( r < npprows );
5342 ppvarsarrayonlypprows[r++] = varmatrix[i];
5345 assert( r == npprows );
5356 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5360 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5374 nelem = nrows * ncols;
5376 for (i = 0; i < nrows; ++i)
5378 for (j = 0; j < ncols; ++j)
5379 orbitopevarmatrix[pos++] = varmatrix[i][j];
5388 orbitopevarmatrix, nrows, ncols, success) );
5396 for (i = nrows - 1; i >= 0; --i)
5411 int** componentperms,
5430 int** pporbisackperms;
5431 int npporbisackperms;
5435 int* npermvarssetppcconss;
5436 int* maxnpermvarssetppcconss;
5440 assert( scip !=
NULL );
5441 assert( propdata !=
NULL );
5442 assert( componentperms !=
NULL );
5443 assert( componentsize > 0 );
5444 assert( success !=
NULL );
5450 if ( hassignedperm )
5454 if ( setppcconshdlr ==
NULL )
5458 if ( nsetppcconss == 0 )
5462 assert( setppcconss !=
NULL );
5469 for (c = 0; c < nsetppcconss; ++c)
5471 cons = setppcconss[c];
5477 setppconsssort[nsetppconss++] = cons;
5479 SCIPsortPtr((
void**) setppconsssort, sortByPointerValue, nsetppcconss);
5487 for (c = 0; c < nsetppconss; ++c)
5490 assert( c < nsetppconss );
5491 cons = setppconsssort[c];
5492 assert( cons !=
NULL );
5497 for (i = 0; i < nsetppcvars; ++i)
5499 var = setppcvars[i];
5500 assert( var !=
NULL );
5502 assert( varid == INT_MAX || varid < propdata->npermvars );
5503 assert( varid >= 0 );
5504 if ( varid < propdata->npermvars )
5507 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5508 assert( npermvarssetppcconss[varid] < maxnpermvarssetppcconss[varid] );
5509 permvarssetppcconss[varid][npermvarssetppcconss[varid]++] = cons;
5517 npporbisackperms = 0;
5518 for (p = 0; p < componentsize; ++p)
5520 perm = componentperms[p];
5524 for (i = 0; i < propdata->npermvars; ++i)
5543 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) )
5552 if ( ntwocycles > 0 )
5554 pporbisackperms[npporbisackperms++] = perm;
5555 if ( ntwocycles > maxntwocycles )
5556 maxntwocycles = ntwocycles;
5564 if ( npporbisackperms * 2 >= componentsize )
5572 assert( npporbisackperms > 0 );
5573 assert( maxntwocycles > 0 );
5578 for (i = 0; i < maxntwocycles; ++i)
5579 ppvarsmatrix[i] = &(ppvarsblock[2 * i]);
5582 for (p = 0; p < npporbisackperms; ++p)
5584 perm = pporbisackperms[p];
5588 for (i = 0; i < propdata->npermvars; ++i)
5599 assert( perm[j] == i );
5601 (
void**) permvarssetppcconss[j], npermvarssetppcconss[j], sortByPointerValue) );
5603 assert( nrows < maxntwocycles );
5604 row = ppvarsmatrix[nrows++];
5605 row[0] = propdata->permvars[i];
5606 row[1] = propdata->permvars[j];
5607 assert( row[0] != row[1] );
5609 assert( nrows > 0 );
5618 &propdata->genlinconsssize, propdata->ngenlinconss + 1) );
5622 propdata->genlinconss[propdata->ngenlinconss++] = cons;
5636 for (varid = 0; varid < propdata->npermvars; ++varid)
5638 assert( (permvarssetppcconss[varid] ==
NULL) == (maxnpermvarssetppcconss[varid] == 0) );
5639 assert( npermvarssetppcconss[varid] >= 0 );
5640 assert( maxnpermvarssetppcconss[varid] >= 0 );
5641 assert( npermvarssetppcconss[varid] <= maxnpermvarssetppcconss[varid] );
5642 if ( npermvarssetppcconss[varid] == 0 )
5645 permvarssetppcconss[varid] =
NULL;
5646 npermvarssetppcconss[varid] = 0;
5647 maxnpermvarssetppcconss[varid] = 0;
5667 int** componentperms;
5675 assert( scip !=
NULL );
5676 assert( propdata !=
NULL );
5680 && propdata->usedynamicprop
5681 && propdata->addsymresacks
5683 assert( propdata->nperms > 0 );
5684 assert( 0 <= cidx && cidx < propdata->ncomponents );
5685 assert( propdata->componentblocked !=
NULL );
5688 if ( propdata->componentblocked[cidx] )
5693 checklexred =
ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5694 assert( checkorbired || checklexred );
5697 assert( propdata->nmovedpermvars );
5700 componentsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
5702 for (p = 0; p < componentsize; ++p)
5703 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
5712 checkpporbisack =
SCIPgetParam(scip,
"constraints/orbisack/checkpporbisack");
5716 componentperms, componentsize, propdata->componenthassignedperm[cidx], &success) );
5721 goto FINISHCOMPONENT;
5726 if ( checkorbired && !propdata->componenthassignedperm[cidx] )
5729 propdata->permvars, propdata->npermvars, componentperms, componentsize, &success) );
5738 for (p = 0; p < componentsize; ++p)
5740 assert( componentperms[p] !=
NULL );
5742 propdata->permvars, propdata->npermvars, componentperms[p],
5743 (
SYM_SYMTYPE) propdata->symtype, propdata->permvardomaincenter,
TRUE, &success) );
5751 if ( propdata->componentblocked[cidx] )
5752 ++propdata->ncompblocked;
5767 int ncomponentshandled;
5770 assert( scip !=
NULL );
5771 assert( propdata !=
NULL );
5774 if ( propdata->orbitopalreddata )
5778 if ( propdata->orbitalreddata )
5782 if ( propdata->lexreddata )
5786 if ( propdata->ncomponents >= 0 )
5793 ncomponentshandled = 0;
5794 for (i = 0; i < propdata->ncomponents; ++i)
5796 if ( propdata->componentblocked[i] )
5797 ++ncomponentshandled;
5799 assert( propdata->ncompblocked <= ncomponentshandled );
5800 assert( ncomponentshandled <= propdata->ncomponents );
5802 ncomponentshandled, propdata->ncomponents);
5820 assert( scip !=
NULL );
5821 assert( propdata !=
NULL );
5822 assert( varidxmatrix !=
NULL );
5823 assert( nrows > 0 );
5824 assert( ncols > 0 );
5825 assert( success !=
NULL );
5830 if ( propdata->usedynamicprop )
5835 else if ( propdata->binvaraffected )
5847 for (i = 0; i < nrows; ++i)
5854 for (j = 0; j < ncols; ++j)
5857 orbitopematrix[nbinrows][j] = propdata->permvars[varidxmatrix[i][j]];
5872 &propdata->genorbconsssize, propdata->ngenorbconss + 1) );
5873 propdata->genorbconss[propdata->ngenorbconss++] = cons;
5874 ++propdata->norbitopes;
5879 for (i = nbinrows - 1; i >= 0; --i)
5918 assert( scip !=
NULL );
5919 assert( propdata !=
NULL );
5920 assert( varidxmatrix !=
NULL );
5921 assert( nrows > 0 );
5922 assert( ncols > 0 );
5923 assert( rowsbegin !=
NULL );
5924 assert( colsbegin !=
NULL );
5925 assert( nrowblocks > 0 );
5926 assert( ncolblocks > 0 );
5927 assert( success !=
NULL );
5931 &propdata->genorbconsssize, propdata->ngenorbconss + nrowblocks + ncolblocks) );
5933 maxdim =
MAX(nrows, ncols);
5935 for (i = 0; i < maxdim; ++i)
5941 for (p = 0; p < ncolblocks; ++p)
5944 for (i = 0; i < nrows; ++i)
5947 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[i][colsbegin[p]]]) )
5950 for (col = 0, j = colsbegin[p]; j < colsbegin[p + 1]; ++j, ++col)
5953 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[i][j]];
5965 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
5971 for (p = 0; p < nrowblocks; ++p)
5974 for (i = 0; i < ncols; ++i)
5977 if ( !
SCIPvarIsBinary(propdata->permvars[varidxmatrix[rowsbegin[p]][i]]) )
5980 for (col = 0, j = rowsbegin[p]; j < rowsbegin[p + 1]; ++j, ++col)
5983 orbitopematrix[nbinrows][col] = propdata->permvars[varidxmatrix[j][i]];
5995 propdata->genorbconss[(propdata->ngenorbconss)++] = cons;
6000 for (i = maxdim - 1; i >= 0; --i)
6018 int** lexmatrix =
NULL;
6019 int* lexrowsbegin =
NULL;
6020 int* lexcolsbegin =
NULL;
6032 assert( scip !=
NULL );
6033 assert( propdata !=
NULL );
6034 assert( 0 <= cidx && cidx < propdata->ncomponents );
6037 if ( propdata->componentblocked[cidx] )
6041 if ( propdata->componenthassignedperm[cidx] )
6049 compsize = propdata->componentbegins[cidx + 1] - propdata->componentbegins[cidx];
6051 for (p = 0, i = propdata->componentbegins[cidx]; i < propdata->componentbegins[cidx + 1]; ++i)
6052 perms[p++] = propdata->perms[propdata->components[i]];
6055 &success, &isorbitope, &lexmatrix, &nrows, &ncols,
6056 &lexrowsbegin, &lexcolsbegin, &nrowmatrices, &ncolmatrices) );
6063 assert( lexmatrix !=
NULL );
6064 assert( nrows > 0 );
6065 assert( ncols > 0 );
6076 for (i = 0; i < nrows && !hasbinaryvar; ++i)
6078 for (p = 0; p < ncols; ++p)
6082 hasbinaryvar =
TRUE;
6091 lexrowsbegin, lexcolsbegin, nrowmatrices, ncolmatrices, &success) );