70 assert( permvars !=
NULL );
71 assert( perms !=
NULL );
73 assert( npermvars > 0 );
74 assert( orbits !=
NULL );
75 assert( orbitbegins !=
NULL );
76 assert( norbits !=
NULL );
86 for (i = 0; i < permlen; ++i)
91 for (i = 0; i < permlen; ++i)
101 beginorbitidx = orbitidx;
102 orbits[orbitidx++] = i;
107 while ( j < orbitidx )
115 for (p = 0; p < nperms; ++p)
117 image = perms[p][curelem];
120 if ( ! varadded[image] )
122 orbits[orbitidx++] = image;
123 assert( orbitidx <= permlen );
124 varadded[image] =
TRUE;
131 if ( orbitidx <= beginorbitidx + 1 )
132 orbitidx = beginorbitidx;
134 orbitbegins[(*norbits)++] = beginorbitidx;
138 assert( *norbits < permlen );
139 orbitbegins[*norbits] = orbitidx;
142 printf(
"Orbits (total number: %d):\n", *norbits);
143 for (i = 0; i < *norbits; ++i)
148 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
149 printf(
"%d ", orbits[j]);
183 int* componentbegins,
187 unsigned* componentblocked,
200 assert( permstrans !=
NULL );
201 assert( nperms > 0 );
202 assert( npermvars > 0 );
203 assert( inactiveperms !=
NULL );
204 assert( orbits !=
NULL );
205 assert( orbitbegins !=
NULL );
206 assert( norbits !=
NULL );
207 assert( components !=
NULL );
208 assert( componentbegins !=
NULL );
209 assert( vartocomponent !=
NULL );
210 assert( ncomponents > 0 );
211 assert( nmovedpermvars > 0 );
217 for (i = 0; i < npermvars; ++i)
222 for (i = 0; i < npermvars; ++i)
229 componentidx = vartocomponent[i];
230 if ( componentidx < 0 || componentblocked[componentidx] )
238 beginorbitidx = orbitidx;
239 orbits[orbitidx++] = i;
245 while ( j < orbitidx )
254 pt = permstrans[curelem];
255 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
259 perm = components[p];
261 if ( ! inactiveperms[perm] )
264 assert( vartocomponent[image] == componentidx );
267 if ( ! varadded[image] )
269 orbits[orbitidx++] = image;
270 assert( orbitidx <= npermvars );
271 varadded[image] =
TRUE;
280 if ( orbitidx <= beginorbitidx + 1 )
281 orbitidx = beginorbitidx;
283 orbitbegins[(*norbits)++] = beginorbitidx;
286 if ( nvaradded >= nmovedpermvars )
291 assert( *norbits < npermvars );
292 orbitbegins[*norbits] = orbitidx;
295 printf(
"Orbits (total number: %d):\n", *norbits);
296 for (i = 0; i < *norbits; ++i)
301 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
302 printf(
"%d ", orbits[j]);
326 int* componentbegins,
342 assert( perms !=
NULL || permstrans !=
NULL );
343 assert( components !=
NULL );
344 assert( componentbegins !=
NULL );
345 assert( ignoredvars !=
NULL );
346 assert( orbit !=
NULL );
347 assert( orbitsize !=
NULL );
348 assert( 0 <= varidx && varidx < npermvars );
349 assert( component >= 0 );
350 assert( npermvars > 0 );
358 varstotest[0] = varidx;
361 varadded[varidx] =
TRUE;
363 if ( varfound !=
NULL )
364 varfound[varidx] =
TRUE;
368 while ( j < nvarstotest )
372 currvar = varstotest[j++];
374 for (p = componentbegins[component]; p < componentbegins[component+1]; ++p)
379 comp = components[p];
382 image = perms[comp][currvar];
384 image = permstrans[currvar][comp];
387 if ( ! varadded[image] )
389 varstotest[nvarstotest++] = image;
390 varadded[image] =
TRUE;
392 if ( ! ignoredvars[image] )
394 orbit[(*orbitsize)++] = image;
396 if ( varfound !=
NULL )
397 varfound[image] =
TRUE;
426 int* componentbegins,
441 assert( permstrans !=
NULL );
442 assert( nperms > 0 );
443 assert( npermvars > 0 );
444 assert( components !=
NULL );
445 assert( componentbegins !=
NULL );
446 assert( vartocomponent !=
NULL );
447 assert( ncomponents > 0 );
448 assert( orbits !=
NULL );
449 assert( orbitbegins !=
NULL );
450 assert( norbits !=
NULL );
451 assert( varorbitmap !=
NULL );
457 for (i = 0; i < npermvars; ++i)
465 for (i = 0; i < npermvars; ++i)
472 componentidx = vartocomponent[i];
473 if ( componentidx < 0 )
481 beginorbitidx = orbitidx;
482 orbits[orbitidx++] = i;
484 varorbitmap[i] = *norbits;
488 while ( j < orbitidx )
497 pt = permstrans[curelem];
498 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
502 perm = components[p];
504 assert( vartocomponent[image] == componentidx );
507 if ( ! varadded[image] )
509 orbits[orbitidx++] = image;
510 assert( orbitidx <= npermvars );
511 varadded[image] =
TRUE;
512 varorbitmap[image] = *norbits;
519 if ( orbitidx <= beginorbitidx + 1 )
521 orbitidx = beginorbitidx;
525 orbitbegins[(*norbits)++] = beginorbitidx;
529 assert( *norbits < npermvars );
530 orbitbegins[*norbits] = orbitidx;
554 assert( perm !=
NULL );
555 assert( vars !=
NULL );
556 assert( ntwocyclesperm !=
NULL );
557 assert( nbincyclesperm !=
NULL );
561 for (i = 0; i < nvars; ++i)
563 assert( 0 <= perm[i] && perm[i] < nvars );
569 if ( perm[perm[i]] == i )
573 else if ( earlytermination )
586 *ntwocyclesperm = ntwocycles;
607 assert( perms !=
NULL );
608 assert( nperms > 0 );
609 assert( permvars !=
NULL );
610 assert( npermvars > 0 );
611 assert( nvarsaffected !=
NULL );
618 for (p = 0; p < nperms; ++p)
620 for (i = 0; i < npermvars; ++i)
625 if ( perms[p][i] != i )
659 int nintersections = 0;
664 assert( suborbitope !=
NULL );
666 assert( nfilledcols > 0 );
667 assert( coltoextend >= 0 );
668 assert( perm !=
NULL );
669 assert( nusedelems !=
NULL );
670 assert( permvars !=
NULL );
671 assert( success !=
NULL );
672 assert( infeasible !=
NULL );
679 if ( nfilledcols == 2 )
682 for (row = 0; row < nrows; ++row)
684 idx1 = suborbitope[row][0];
685 idx2 = suborbitope[row][1];
688 if ( idx1 != perm[idx1] )
691 if ( ! leftextension )
693 suborbitope[row][0] = idx2;
694 suborbitope[row][1] = idx1;
696 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
698 suborbitope[row][2] = perm[idx1];
701 ++(*nusedelems)[idx1];
702 ++(*nusedelems)[perm[idx1]];
705 if ( (*nusedelems)[idx1] + (*nusedelems)[perm[idx1]] > 3 )
711 else if ( idx2 != perm[idx2] )
716 suborbitope[row][0] = idx2;
717 suborbitope[row][1] = idx1;
719 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
721 suborbitope[row][2] = perm[idx2];
724 ++(*nusedelems)[idx2];
725 ++(*nusedelems)[perm[idx2]];
728 if ( (*nusedelems)[idx2] + (*nusedelems)[perm[idx2]] > 3 )
739 for (row = 0; row < nrows; ++row)
741 idx1 = suborbitope[row][coltoextend];
744 if ( idx1 != perm[idx1] )
746 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
748 suborbitope[row][nfilledcols] = perm[idx1];
751 ++(*nusedelems)[idx1];
752 ++(*nusedelems)[perm[idx1]];
755 if ( (*nusedelems)[idx1] + (*nusedelems)[perm[idx1]] > 3 )
765 if ( nintersections > 0 && nintersections < nrows )
767 else if ( nintersections == nrows )
785 int** componentbegins,
787 int** vartocomponent,
789 unsigned** componentblocked,
796 int* permtocomponent;
802 assert( permvars !=
NULL );
803 assert( npermvars > 0 );
804 assert( perms !=
NULL );
805 assert( components !=
NULL );
806 assert( componentbegins !=
NULL );
807 assert( vartocomponent !=
NULL );
808 assert( componentblocked !=
NULL );
809 assert( ncomponents !=
NULL );
815 *ncomponents = npermvars;
819 for (p = 0; p < nperms; ++p)
820 permtovarcomp[p] = -1;
824 for (i = 0; i < npermvars; ++i)
826 (*vartocomponent)[i] = -1;
828 for (p = 0; p < nperms; ++p)
832 img = transposed ? perms[i][p] : perms[p][i];
841 if ( img >= npermvars )
845 assert( 0 <= img && img < npermvars );
850 (*vartocomponent)[i] = p;
851 (*vartocomponent)[img] = p;
854 if ( component2 < component1 )
859 component1 = component2;
864 if ( permtovarcomp[p] == -1 )
866 permtovarcomp[p] = component1;
867 representative = component1;
872 representative = permtovarcomp[p];
876 if ( component1 != component2 )
884 if ( representative != component1 && representative != component2 )
886 if ( representative > component1 )
889 permtovarcomp[p] = component1;
895 else if ( representative > component1 )
897 assert( representative == component2 );
898 permtovarcomp[p] = component1;
904 if ( (*vartocomponent)[i] == -1 )
907 assert( *ncomponents > 0 );
910 for (p = 0; p < nperms; ++p)
915 for (p = 0; p < nperms; ++p)
916 (*components)[p] = p;
925 (*componentbegins)[0] = 0;
926 permtocomponent[(*components)[0]] = 0;
929 for (p = 1; p < nperms; ++p)
931 if ( permtovarcomp[p] > permtovarcomp[p - 1] )
932 (*componentbegins)[++idx] = p;
934 assert( (*components)[p] >= 0 );
935 assert( (*components)[p] < nperms );
936 permtocomponent[(*components)[p]] = idx;
938 assert( *ncomponents == idx + 1 );
939 (*componentbegins)[++idx] = nperms;
942 for (i = 0; i < npermvars; ++i)
945 permidx = (*vartocomponent)[i];
946 assert( -1 <= permidx && permidx < nperms );
950 assert( 0 <= permtocomponent[permidx] );
951 assert( permtocomponent[permidx] < *ncomponents );
953 (*vartocomponent)[i] = permtocomponent[permidx];
959 for (i = 0; i < *ncomponents; ++i)
960 (*componentblocked)[i] = 0;
967 printf(
"number of components: %d\n", *ncomponents);
968 for (i = 0; i < *ncomponents; ++i)
970 printf(
"Component %d contains the following permutations:\n\t", i);
971 for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
973 printf(
"%d, ", (*components)[p]);
994 int** orbitopevaridx,
1005 int nfilledcols = 0;
1009 int nvarsorderold = 0;
1011 assert( vars !=
NULL );
1012 assert( nrows > 0 );
1013 assert( ncols > 0 );
1014 assert( permvars !=
NULL );
1015 assert( npermvars > 0 );
1016 assert( orbitopevaridx !=
NULL );
1017 assert( columnorder !=
NULL );
1018 assert( nusedelems !=
NULL );
1019 assert( infeasible !=
NULL );
1020 assert( ! storelexorder || lexorder !=
NULL );
1021 assert( ! storelexorder || nvarsorder !=
NULL );
1022 assert( ! storelexorder || maxnvarsorder !=
NULL );
1028 if ( storelexorder )
1030 assert( *nvarsorder == *maxnvarsorder );
1031 assert( lexorder !=
NULL );
1033 *maxnvarsorder += nrows * ncols;
1034 nvarsorderold = *nvarsorder;
1036 if ( *lexorder ==
NULL )
1046 curcolumn = ncols - 1;
1049 while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 && ! *infeasible )
1052 for (i = 0; i < nrows; ++i)
1055 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1058 assert( 0 <= orbitopevaridx[i][curcolumn] && orbitopevaridx[i][curcolumn] < npermvars );
1062 if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1065 assert( ! storelexorder );
1069 if ( storelexorder )
1071 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1074 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1086 assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
1088 if ( curcolumn > 1 && ! *infeasible )
1092 for (i = 0; i < nrows; ++i)
1095 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1098 assert( orbitopevaridx[i][1] < npermvars );
1101 if ( storelexorder )
1103 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][1];
1106 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][1]];
1112 for (i = 0; i < nrows; ++i)
1115 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1118 assert( orbitopevaridx[i][0] < npermvars );
1121 if ( storelexorder )
1123 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][0];
1126 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][0]];
1131 if ( nfilledcols < ncols )
1133 assert( ncols > 2 );
1136 while ( nfilledcols < ncols && ! *infeasible )
1138 assert( columnorder[curcolumn] < 0 );
1141 for (i = 0; i < nrows; ++i)
1144 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1147 assert( orbitopevaridx[i][curcolumn] < npermvars );
1151 if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1154 assert( ! storelexorder );
1158 if ( storelexorder )
1160 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1163 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1196 int* rowcoveragesetppc;
1205 assert( vars !=
NULL );
1206 assert( vars !=
NULL );
1207 assert( nrows > 0 );
1208 assert( ncols > 0 );
1209 assert( type !=
NULL );
1212 if ( npprows !=
NULL )
1216 if ( setppcconshdlr ==
NULL )
1226 if ( nsetppcconss == 0 || (nsetppcconss < nrows && npprows ==
NULL ))
1228 assert( setppcconss !=
NULL );
1240 for (i = 0; i < nprobvars; ++i)
1243 for (i = 0; i < nrows; ++i)
1245 for (j = 0; j < ncols; ++j)
1264 for (c = 0; c < nsetppcconss && ncoveredpart < ncols; ++c)
1268 int nrowintersect = 0;
1269 int nvarsinorbitope;
1279 if ( nsetppcvars < ncols )
1283 assert( setppcvars !=
NULL );
1286 nvarsinorbitope = nsetppcvars;
1292 for (i = 0; i < nsetppcvars && nvarsinorbitope >= ncols; ++i)
1298 var = setppcvars[i];
1301 assert( 0 <= idx && idx < nprobvars );
1303 rowidx = rowidxvar[idx];
1313 if ( covered[rowidx] == 2 || (covered[rowidx] == 1 && (nsetppcvars > ncols || nrowintersect > 1)) )
1320 if ( rowcoveragesetppc[rowidx] == 0 )
1321 rowsinsetppc[nrowintersect++] = rowidx;
1322 ++(rowcoveragesetppc[rowidx]);
1327 if ( nsetppcvars - nrowintersect < ncols - 1 )
1335 && nrowintersect == 1 && rowcoveragesetppc[rowsinsetppc[0]] == ncols && nsetppcvars == ncols )
1337 if ( covered[rowsinsetppc[0]] == 1 )
1339 covered[rowsinsetppc[0]] = 2;
1345 for (i = 0; i < nrowintersect; ++i)
1347 if ( covered[rowsinsetppc[i]] == 0 && rowcoveragesetppc[rowsinsetppc[i]] >= ncols )
1349 covered[rowsinsetppc[i]] = 1;
1356 for (i = 0; i < nrowintersect; ++i)
1357 rowcoveragesetppc[rowsinsetppc[i]] = 0;
1361 if ( ncovered == nrows )
1363 if ( ncoveredpart == nrows )
1369 if ( npprows !=
NULL )
1370 *npprows = ncovered;
1372 if ( pprows !=
NULL )
1375 for (i = 0; i < nrows; ++i)
1376 (*pprows)[i] = covered[i] > 0 ? 1 : 0;
1398 assert( perm !=
NULL );
1399 assert( permlen > 0 );
1400 assert( isinvolution !=
NULL );
1401 assert( ntwocycles !=
NULL );
1404 *isinvolution =
TRUE;
1405 for (v = 0; v < permlen && *isinvolution; ++v)
1412 if ( perm[perm[v]] == v )
1415 *isinvolution =
FALSE;
1439 int* permstoconsider;
1447 int npermstoconsider;
1448 int colorrepresentative1 = -1;
1449 int colorrepresentative2 = -1;
1466 assert( perms !=
NULL );
1467 assert( selectedperms !=
NULL );
1468 assert( nselectedperms >= 0 );
1469 assert( permlen > 0 );
1470 assert( nrows > 0 || nselectedperms == 0 );
1471 assert( success !=
NULL );
1472 assert( matrices !=
NULL );
1473 assert( ncols !=
NULL );
1474 assert( nmatrices !=
NULL );
1483 if ( nselectedperms == 0 )
1500 for (v = 0; v < permlen; ++v)
1501 complastperm[v] = -1;
1504 for (p = 0; p < nselectedperms; ++p)
1506 perm = perms[selectedperms[p]];
1511 for (v = 0; v < permlen; ++v)
1522 if ( curcomp1 == curcomp2 )
1526 if ( complastperm[curcomp1] == p || complastperm[curcomp2] == p )
1534 if ( curcolor1 == curcolor2 )
1537 if ( curdeg1 == -1 )
1539 assert( curdeg2 == -1 );
1541 curdeg1 = degrees[v];
1542 curdeg2 = degrees[
w];
1543 colorrepresentative1 = curcolor1;
1544 colorrepresentative2 = curcolor2;
1547 if ( curdeg1 == 2 || curdeg2 == 2 )
1553 if ( ! ((curdeg1 == degrees[v] && curdeg2 == degrees[
w])
1554 || (curdeg1 == degrees[
w] && curdeg2 == degrees[v])) )
1556 assert( colorrepresentative1 >= 0 );
1557 assert( colorrepresentative2 >= 0 || curdeg2 == -1 );
1560 if ( curdeg1 > 0 && curcolor1 != colorrepresentative1 && curcolor2 != colorrepresentative1 )
1562 if ( curdeg2 > 0 && curcolor1 != colorrepresentative2 && curcolor2 != colorrepresentative2 )
1567 complastperm[curcomp1] = p;
1568 complastperm[curcomp2] = p;
1577 assert( curdeg1 >= 0 && curdeg2 >= 0 );
1580 for (v = 0; v < permlen; ++v)
1590 assert( curcomp1 != curcomp2 );
1602 if ( curcolor1 != curcolor2 )
1612 for (v = 0; v < permlen; ++v)
1614 if ( degrees[v] > 0 )
1622 for (v = 0,
w = 0; v < permlen; ++v)
1624 if ( degrees[v] > 0 )
1629 if (
w > 0 && compidx[
w] == compidx[
w-1] )
1630 assert( colidx[
w] == colidx[
w-1]);
1635 assert(
w == nposdegree );
1644 for (v = 1; v < nposdegree; ++v)
1646 if ( colidx[v] != colidx[
w] )
1649 colorbegins[++ncolors] = v;
1654 colorbegins[++ncolors] = nposdegree;
1661 *nmatrices = ncolors;
1663 for (c = 0; c < ncolors; ++c)
1666 for (v = colorbegins[c]; compidx[v] == compidx[colorbegins[c]]; ++v)
1668 assert( v < nposdegree );
1670 if ( degrees[varidx[v]] == 1 )
1673 assert( compidx[v] == compidx[colorbegins[c]] );
1674 elemtomove = varidx[v];
1677 npermstoconsider = 0;
1678 for (p = 0; p < nselectedperms; ++p)
1680 perm = perms[selectedperms[p]];
1681 for (v = colorbegins[c]; v < nposdegree && compidx[v] == compidx[colorbegins[c]]; ++v)
1683 if ( perm[varidx[v]] != varidx[v] )
1685 permstoconsider[npermstoconsider++] = selectedperms[p];
1693 (*ncols)[c] = npermstoconsider + 1;
1694 for (p = 0; p < nrows; ++p)
1700 assert( degrees[elemtomove] == 1 );
1703 for (p = 0; p < npermstoconsider; ++p)
1705 perm = perms[permstoconsider[p]];
1706 if ( perm[elemtomove] != elemtomove )
1709 assert( p < npermstoconsider );
1712 for (v = 0, cnt = 0; v < permlen; ++v)
1716 if ( degrees[v] == 1 )
1718 (*matrices)[c][cnt][0] = v;
1719 (*matrices)[c][cnt++][1] = perm[v];
1723 (*matrices)[c][cnt][0] = perm[v];
1724 (*matrices)[c][cnt++][1] = v;
1733 for (p = nrows - 1; p >= 0; --p)
1742 goto FREEMOREMEMORY;
1744 assert( cnt == nrows );
1747 permstoconsider[p] = permstoconsider[--npermstoconsider];
1750 while ( npermstoconsider > 0 )
1752 elemtomove = (*matrices)[c][0][ncurcols];
1755 for (p = 0; p < npermstoconsider; ++p)
1757 perm = perms[permstoconsider[p]];
1758 if ( perm[elemtomove] != elemtomove )
1761 assert( p < npermstoconsider );
1764 for (v = 0; v < nrows; ++v)
1766 assert( perm[(*matrices)[c][v][ncurcols]] != (*matrices)[c][v][ncurcols] );
1767 (*matrices)[c][v][ncurcols + 1] = perm[(*matrices)[c][v][ncurcols]];
1770 permstoconsider[p] = permstoconsider[--npermstoconsider];
1807 int*** doublelexmatrix,
1834 assert( nsymvars >= 0 );
1835 assert( matrices1 !=
NULL );
1836 assert( nrows1 > 0 );
1837 assert( ncols1 !=
NULL );
1838 assert( nmatrices1 > 0 );
1839 assert( matrices2 !=
NULL );
1840 assert( nrows2 > 0 || nmatrices2 == 0 );
1841 assert( ncols2 !=
NULL );
1842 assert( nmatrices2 >= 0 );
1843 assert( doublelexmatrix !=
NULL );
1844 assert( nrows !=
NULL );
1845 assert( ncols !=
NULL );
1846 assert( rowsbegin !=
NULL );
1847 assert( colsbegin !=
NULL );
1848 assert( success !=
NULL );
1856 for (j = 0, cnt = 0; j < nmatrices1; ++j)
1858 if ( cnt != *ncols )
1864 for (i = 0, cnt = 0; i < nmatrices2; ++i)
1866 if ( cnt != *nrows )
1881 for (i = 0; i < nsymvars; ++i)
1882 idxtomatrix1[i] = -1;
1883 for (i = 0; i < nsymvars; ++i)
1884 idxtomatrix2[i] = -1;
1885 for (i = 0; i < nsymvars; ++i)
1887 for (i = 0; i < nsymvars; ++i)
1889 for (i = 0; i < nsymvars; ++i)
1891 for (i = 0; i < nsymvars; ++i)
1894 for (c = 0; c < nmatrices1; ++c)
1896 for (i = 0; i < nrows1; ++i)
1898 for (j = 0; j < ncols1[c]; ++j)
1900 idxtomatrix1[matrices1[c][i][j]] = c;
1901 idxtorow1[matrices1[c][i][j]] = i;
1902 idxtocol1[matrices1[c][i][j]] = j;
1906 for (c = 0; c < nmatrices2; ++c)
1908 for (i = 0; i < nrows2; ++i)
1910 for (j = 0; j < ncols2[c]; ++j)
1912 idxtomatrix2[matrices2[c][i][j]] = c;
1913 idxtorow2[matrices2[c][i][j]] = i;
1914 idxtocol2[matrices2[c][i][j]] = j;
1920 for (i = 0; i < nsymvars; ++i)
1922 if ( (idxtomatrix1[i] == -1) != (idxtomatrix2[i] == -1) )
1925 goto FREEINITMEMORY;
1943 for (i = 0; i < *nrows; ++i)
1946 (*doublelexmatrix)[i][0] = matrices1[0][i][0];
1947 sortvals[i] = idxtomatrix2[matrices1[0][i][0]];
1952 mat = idxtomatrix2[(*doublelexmatrix)[0][0]];
1953 col = idxtocol2[(*doublelexmatrix)[0][0]];
1955 for (j = 0; j < *ncols; ++j)
1958 if ( matrices2[mat][j][col] == (*doublelexmatrix)[0][0] )
1961 sortvals[cnt++] = idxtomatrix1[matrices2[mat][j][col]];
1962 (*doublelexmatrix)[0][cnt] = matrices2[mat][j][col];
1964 assert( cnt == nrows2 - 1);
1968 for (i = 1; i < *nrows; ++i)
1970 for (j = 1; j < *ncols; ++j)
1973 mat = idxtomatrix1[(*doublelexmatrix)[0][j]];
1974 mat2 = idxtomatrix2[(*doublelexmatrix)[i][0]];
1975 col = idxtocol1[(*doublelexmatrix)[0][j]];
1976 col2 = idxtocol2[(*doublelexmatrix)[i][0]];
1982 for (c = 0; c < *nrows; ++c)
1984 for (d = 0; d < *ncols; ++d)
1986 if ( matrices1[mat][c][col] == matrices2[mat2][d][col2] )
1989 elem = matrices1[mat][c][col];
2001 (*doublelexmatrix)[i][j] = elem;
2008 assert( nmatrices2 > 0 );
2011 (*rowsbegin)[0] = 0;
2012 (*colsbegin)[0] = 0;
2013 for (j = 0; j < nmatrices2; ++j)
2014 (*rowsbegin)[j + 1] = (*rowsbegin)[j] + ncols2[j];
2015 for (j = 0; j < nmatrices1; ++j)
2016 (*colsbegin)[j + 1] = (*colsbegin)[j] + ncols1[j];
2024 for (i = *nrows - 1; i >= 0; --i)
2029 *doublelexmatrix =
NULL;
2068 int*** matricestype1 =
NULL;
2069 int*** matricestype2 =
NULL;
2070 int* ncolstype1 =
NULL;
2071 int* ncolstype2 =
NULL;
2072 int nmatricestype1 = 0;
2073 int nmatricestype2 = 0;
2076 int npermstype1 = 0;
2077 int npermstype2 = 0;
2086 assert( perms !=
NULL );
2087 assert( nperms > 0 );
2088 assert( permlen > 0 );
2089 assert( success !=
NULL );
2090 assert( lexmatrix !=
NULL );
2091 assert( nrows !=
NULL );
2092 assert( ncols !=
NULL );
2093 assert( lexrowsbegin !=
NULL );
2094 assert( lexcolsbegin !=
NULL );
2095 assert( nrowmatrices !=
NULL );
2096 assert( ncolmatrices !=
NULL );
2099 *isorbitope =
FALSE;
2108 for (p = 0; p < nperms; ++p)
2113 if ( ! isinvolution )
2120 if ( ncycs1 == -1 || ncycs1 == tmpncycs )
2123 permstype1[npermstype1++] = p;
2125 else if ( ncycs2 == -1 || ncycs2 == tmpncycs )
2128 permstype2[npermstype2++] = p;
2139 &matricestype1, &ncolstype1, &nmatricestype1) );
2144 &matricestype2, &ncolstype2, &nmatricestype2) );
2150 if ( !detectsinglelex && ncycs2 != -1 )
2152 assert( ncycs1 > 0 );
2155 matricestype2, ncycs2, ncolstype2, nmatricestype2,
2156 lexmatrix, nrows, ncols, lexrowsbegin, lexcolsbegin, success) );
2160 *nrowmatrices = nmatricestype2;
2161 *ncolmatrices = nmatricestype1;
2166 if ( !(*success) && ncycs2 == -1 && nmatricestype1 == 1 )
2169 for (i = 0; i < ncycs1; ++i)
2172 for (p = 0; p < ncolstype1[0]; ++p)
2173 (*lexmatrix)[i][p] = matricestype1[0][i][p];
2176 *ncols = ncolstype1[0];
2182 for (p = nmatricestype2 - 1; p >= 0; --p)
2184 for (i = ncycs2 - 1; i >= 0; --i)
2192 for (p = nmatricestype1 - 1; p >= 0; --p)
2194 for (i = ncycs1 - 1; i >= 0; --i)
2233 if ( minf1 && minf2 )
2235 if ( minf1 != minf2 )
2260 if ( !inf1 && inf2 )
2262 if ( inf1 && !inf2 )
2269 if ( minf1 && minf2 )
2271 if ( !minf1 && minf2 )
2273 if ( minf1 && !minf2 )
2298 if ( !inf1 && inf2 )
2300 if ( inf1 && !inf2 )
2307 if ( minf1 && minf2 )
2309 if ( !minf1 && minf2 )
2311 if ( minf1 && !minf2 )
2336 if ( !inf1 && inf2 )
2338 if ( inf1 && !inf2 )
2345 if ( minf1 && minf2 )
2347 if ( !minf1 && minf2 )
2349 if ( minf1 && !minf2 )
2374 if ( !inf1 && inf2 )
2376 if ( inf1 && !inf2 )
2383 if ( minf1 && minf2 )
2385 if ( !minf1 && minf2 )
2387 if ( minf1 && !minf2 )
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
Constraint handler for the set partitioning / packing / covering constraints .
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
@ SCIP_SETPPCTYPE_PARTITIONING
@ SCIP_SETPPCTYPE_COVERING
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
int SCIPgetNTotalVars(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
SCIP_RETCODE SCIPcomputeOrbitVar(SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(SCIP *scip, int npermvars, int **permstrans, int nperms, int *components, int *componentbegins, int *vartocomponent, int ncomponents, int *orbits, int *orbitbegins, int *norbits, int *varorbitmap)
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_Bool issigned, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
internal miscellaneous methods
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
structs for symmetry computations
static SCIP_RETCODE detectOrbitopalSymmetries(SCIP *scip, int **perms, int *selectedperms, int nselectedperms, int permlen, int nrows, SCIP_Bool *success, int ****matrices, int **ncols, int *nmatrices)
static SCIP_RETCODE isPermInvolution(int *perm, int permlen, SCIP_Bool *isinvolution, int *ntwocycles)
static SCIP_RETCODE isDoublelLexSym(SCIP *scip, int nsymvars, int ***matrices1, int nrows1, int *ncols1, int nmatrices1, int ***matrices2, int nrows2, int *ncols2, int nmatrices2, int ***doublelexmatrix, int *nrows, int *ncols, int **rowsbegin, int **colsbegin, SCIP_Bool *success)
methods for handling symmetries
enum SCIP_Retcode SCIP_RETCODE
type definitions for symmetry computations
@ SCIP_ORBITOPETYPE_PACKING
@ SCIP_ORBITOPETYPE_PARTITIONING
enum SYM_Symtype SYM_SYMTYPE
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE