64 assert( scip !=
NULL );
65 assert( permvars !=
NULL );
66 assert( perms !=
NULL );
68 assert( npermvars > 0 );
69 assert( orbits !=
NULL );
70 assert( orbitbegins !=
NULL );
71 assert( norbits !=
NULL );
77 for (i = 0; i < npermvars; ++i)
82 for (i = 0; i < npermvars; ++i)
92 beginorbitidx = orbitidx;
93 orbits[orbitidx++] = i;
98 while ( j < orbitidx )
106 for (p = 0; p < nperms; ++p)
108 image = perms[p][curelem];
111 if ( ! varadded[image] )
113 orbits[orbitidx++] = image;
114 assert( orbitidx <= npermvars );
115 varadded[image] =
TRUE;
122 if ( orbitidx <= beginorbitidx + 1 )
123 orbitidx = beginorbitidx;
125 orbitbegins[(*norbits)++] = beginorbitidx;
129 assert( *norbits < npermvars );
130 orbitbegins[*norbits] = orbitidx;
133 printf(
"Orbits (total number: %d):\n", *norbits);
134 for (i = 0; i < *norbits; ++i)
139 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
140 printf(
"%d ", orbits[j]);
174 int* componentbegins,
178 unsigned* componentblocked,
190 assert( scip !=
NULL );
191 assert( permstrans !=
NULL );
192 assert( nperms > 0 );
193 assert( npermvars > 0 );
194 assert( inactiveperms !=
NULL );
195 assert( orbits !=
NULL );
196 assert( orbitbegins !=
NULL );
197 assert( norbits !=
NULL );
198 assert( components !=
NULL );
199 assert( componentbegins !=
NULL );
200 assert( vartocomponent !=
NULL );
201 assert( ncomponents > 0 );
202 assert( nmovedpermvars > 0 );
208 for (i = 0; i < npermvars; ++i)
213 for (i = 0; i < npermvars; ++i)
220 componentidx = vartocomponent[i];
221 if ( componentidx < 0 || componentblocked[componentidx] )
229 beginorbitidx = orbitidx;
230 orbits[orbitidx++] = i;
236 while ( j < orbitidx )
245 pt = permstrans[curelem];
246 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
250 perm = components[p];
252 if ( ! inactiveperms[perm] )
255 assert( vartocomponent[image] == componentidx );
258 if ( ! varadded[image] )
260 orbits[orbitidx++] = image;
261 assert( orbitidx <= npermvars );
262 varadded[image] =
TRUE;
271 if ( orbitidx <= beginorbitidx + 1 )
272 orbitidx = beginorbitidx;
274 orbitbegins[(*norbits)++] = beginorbitidx;
277 if ( nvaradded >= nmovedpermvars )
282 assert( *norbits < npermvars );
283 orbitbegins[*norbits] = orbitidx;
286 printf(
"Orbits (total number: %d):\n", *norbits);
287 for (i = 0; i < *norbits; ++i)
292 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
293 printf(
"%d ", orbits[j]);
317 int* componentbegins,
332 assert( scip !=
NULL );
333 assert( perms !=
NULL || permstrans !=
NULL );
334 assert( components !=
NULL );
335 assert( componentbegins !=
NULL );
336 assert( ignoredvars !=
NULL );
337 assert( orbit !=
NULL );
338 assert( orbitsize !=
NULL );
339 assert( 0 <= varidx && varidx < npermvars );
340 assert( component >= 0 );
341 assert( npermvars > 0 );
349 varstotest[0] = varidx;
352 varadded[varidx] =
TRUE;
354 if ( varfound !=
NULL )
355 varfound[varidx] =
TRUE;
359 while ( j < nvarstotest )
363 currvar = varstotest[j++];
365 for (p = componentbegins[component]; p < componentbegins[component+1]; ++p)
370 comp = components[p];
373 image = perms[comp][currvar];
375 image = permstrans[currvar][comp];
378 if ( ! varadded[image] )
380 varstotest[nvarstotest++] = image;
381 varadded[image] =
TRUE;
383 if ( ! ignoredvars[image] )
385 orbit[(*orbitsize)++] = image;
387 if ( varfound !=
NULL )
388 varfound[image] =
TRUE;
417 int* componentbegins,
431 assert( scip !=
NULL );
432 assert( permstrans !=
NULL );
433 assert( nperms > 0 );
434 assert( npermvars > 0 );
435 assert( components !=
NULL );
436 assert( componentbegins !=
NULL );
437 assert( vartocomponent !=
NULL );
438 assert( ncomponents > 0 );
439 assert( orbits !=
NULL );
440 assert( orbitbegins !=
NULL );
441 assert( norbits !=
NULL );
442 assert( varorbitmap !=
NULL );
448 for (i = 0; i < npermvars; ++i)
456 for (i = 0; i < npermvars; ++i)
463 componentidx = vartocomponent[i];
464 if ( componentidx < 0 )
472 beginorbitidx = orbitidx;
473 orbits[orbitidx++] = i;
475 varorbitmap[i] = *norbits;
479 while ( j < orbitidx )
488 pt = permstrans[curelem];
489 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
493 perm = components[p];
495 assert( vartocomponent[image] == componentidx );
498 if ( ! varadded[image] )
500 orbits[orbitidx++] = image;
501 assert( orbitidx <= npermvars );
502 varadded[image] =
TRUE;
503 varorbitmap[image] = *norbits;
510 if ( orbitidx <= beginorbitidx + 1 )
512 orbitidx = beginorbitidx;
516 orbitbegins[(*norbits)++] = beginorbitidx;
520 assert( *norbits < npermvars );
521 orbitbegins[*norbits] = orbitidx;
545 assert( perm !=
NULL );
546 assert( vars !=
NULL );
547 assert( ntwocyclesperm !=
NULL );
548 assert( nbincyclesperm !=
NULL );
552 for (i = 0; i < nvars; ++i)
554 assert( 0 <= perm[i] && perm[i] < nvars );
560 if ( perm[perm[i]] == i )
564 else if ( earlytermination )
577 *ntwocyclesperm = ntwocycles;
597 assert( scip !=
NULL );
598 assert( perms !=
NULL );
599 assert( nperms > 0 );
600 assert( permvars !=
NULL );
601 assert( npermvars > 0 );
602 assert( nvarsaffected !=
NULL );
609 for (p = 0; p < nperms; ++p)
611 for (i = 0; i < npermvars; ++i)
616 if ( perms[p][i] != i )
650 int nintersections = 0;
655 assert( suborbitope !=
NULL );
657 assert( nfilledcols > 0 );
658 assert( coltoextend >= 0 );
659 assert( perm !=
NULL );
660 assert( nusedelems !=
NULL );
661 assert( permvars !=
NULL );
662 assert( success !=
NULL );
663 assert( infeasible !=
NULL );
670 if ( nfilledcols == 2 )
673 for (row = 0; row < nrows; ++row)
675 idx1 = suborbitope[row][0];
676 idx2 = suborbitope[row][1];
679 if ( idx1 != perm[idx1] )
682 if ( ! leftextension )
684 suborbitope[row][0] = idx2;
685 suborbitope[row][1] = idx1;
687 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
689 suborbitope[row][2] = perm[idx1];
692 ++(*nusedelems)[idx1];
693 ++(*nusedelems)[perm[idx1]];
696 if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
702 else if ( idx2 != perm[idx2] )
707 suborbitope[row][0] = idx2;
708 suborbitope[row][1] = idx1;
710 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
712 suborbitope[row][2] = perm[idx2];
715 ++(*nusedelems)[idx2];
716 ++(*nusedelems)[perm[idx2]];
719 if ( (*nusedelems)[idx2] > 2 || (*nusedelems)[perm[idx2]] > 2 )
730 for (row = 0; row < nrows; ++row)
732 idx1 = suborbitope[row][coltoextend];
735 if ( idx1 != perm[idx1] )
737 assert( rowisbinary ==
NULL || rowisbinary[row] ==
SCIPvarIsBinary(permvars[perm[idx1]]) );
739 suborbitope[row][nfilledcols] = perm[idx1];
742 ++(*nusedelems)[idx1];
743 ++(*nusedelems)[perm[idx1]];
746 if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
756 if ( nintersections > 0 && nintersections < nrows )
758 else if ( nintersections == nrows )
775 int** componentbegins,
777 int** vartocomponent,
779 unsigned** componentblocked,
786 int* permtocomponent;
791 assert( scip !=
NULL );
792 assert( permvars !=
NULL );
793 assert( npermvars > 0 );
794 assert( perms !=
NULL );
795 assert( components !=
NULL );
796 assert( componentbegins !=
NULL );
797 assert( vartocomponent !=
NULL );
798 assert( componentblocked !=
NULL );
799 assert( ncomponents !=
NULL );
805 *ncomponents = npermvars;
809 for (p = 0; p < nperms; ++p)
810 permtovarcomp[p] = -1;
814 for (i = 0; i < npermvars; ++i)
816 (*vartocomponent)[i] = -1;
818 for (p = 0; p < nperms; ++p)
822 img = transposed ? perms[i][p] : perms[p][i];
833 (*vartocomponent)[i] = p;
834 (*vartocomponent)[img] = p;
837 if ( component2 < component1 )
842 component1 = component2;
847 if ( permtovarcomp[p] == -1 )
849 permtovarcomp[p] = component1;
850 representative = component1;
855 representative = permtovarcomp[p];
859 if ( component1 != component2 )
867 if ( representative != component1 && representative != component2 )
869 if ( representative > component1 )
872 permtovarcomp[p] = component1;
878 else if ( representative > component1 )
880 assert( representative == component2 );
881 permtovarcomp[p] = component1;
887 if ( (*vartocomponent)[i] == -1 )
890 assert( *ncomponents > 0 );
893 for (p = 0; p < nperms; ++p)
898 for (p = 0; p < nperms; ++p)
899 (*components)[p] = p;
908 (*componentbegins)[0] = 0;
909 permtocomponent[(*components)[0]] = 0;
912 for (p = 1; p < nperms; ++p)
914 if ( permtovarcomp[p] > permtovarcomp[p - 1] )
915 (*componentbegins)[++idx] = p;
917 assert( (*components)[p] >= 0 );
918 assert( (*components)[p] < nperms );
919 permtocomponent[(*components)[p]] = idx;
921 assert( *ncomponents == idx + 1 );
922 (*componentbegins)[++idx] = nperms;
925 for (i = 0; i < npermvars; ++i)
928 permidx = (*vartocomponent)[i];
929 assert( -1 <= permidx && permidx < nperms );
933 assert( 0 <= permtocomponent[permidx] );
934 assert( permtocomponent[permidx] < *ncomponents );
936 (*vartocomponent)[i] = permtocomponent[permidx];
942 for (i = 0; i < *ncomponents; ++i)
943 (*componentblocked)[i] = 0;
950 printf(
"number of components: %d\n", propdata->ncomponents);
951 for (i = 0; i < *ncomponents; ++i)
953 printf(
"Component %d contains the following permutations:\n\t", i);
954 for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
956 printf(
"%d, ", (*components)[p]);
977 int** orbitopevaridx,
992 int nvarsorderold = 0;
994 assert( vars !=
NULL );
997 assert( permvars !=
NULL );
998 assert( npermvars > 0 );
999 assert( orbitopevaridx !=
NULL );
1000 assert( columnorder !=
NULL );
1001 assert( nusedelems !=
NULL );
1002 assert( infeasible !=
NULL );
1003 assert( ! storelexorder || lexorder !=
NULL );
1004 assert( ! storelexorder || nvarsorder !=
NULL );
1005 assert( ! storelexorder || maxnvarsorder !=
NULL );
1011 if ( storelexorder )
1013 assert( *nvarsorder == *maxnvarsorder );
1014 assert( lexorder !=
NULL );
1016 *maxnvarsorder += nrows * ncols;
1017 nvarsorderold = *nvarsorder;
1019 if ( *lexorder ==
NULL )
1029 curcolumn = ncols - 1;
1032 while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 && ! *infeasible )
1035 for (i = 0; i < nrows; ++i)
1038 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1041 assert( 0 <= orbitopevaridx[i][curcolumn] && orbitopevaridx[i][curcolumn] < npermvars );
1045 if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1048 assert( ! storelexorder );
1052 if ( storelexorder )
1054 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1057 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1069 assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
1071 if ( curcolumn > 1 && ! *infeasible )
1075 for (i = 0; i < nrows; ++i)
1078 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1081 assert( orbitopevaridx[i][1] < npermvars );
1084 if ( storelexorder )
1086 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][1];
1089 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][1]];
1095 for (i = 0; i < nrows; ++i)
1098 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1101 assert( orbitopevaridx[i][0] < npermvars );
1104 if ( storelexorder )
1106 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][0];
1109 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][0]];
1114 if ( nfilledcols < ncols )
1116 assert( ncols > 2 );
1119 while ( nfilledcols < ncols && ! *infeasible )
1121 assert( columnorder[curcolumn] < 0 );
1124 for (i = 0; i < nrows; ++i)
1127 if ( rowisbinary !=
NULL && ! rowisbinary[i] )
1130 assert( orbitopevaridx[i][curcolumn] < npermvars );
1134 if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
1137 assert( ! storelexorder );
1141 if ( storelexorder )
1143 (*lexorder)[nvarsorderold + nrows * nfilledcols + cnt] = orbitopevaridx[i][curcolumn];
1146 (*vars)[cnt++][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
1179 int* rowcoveragesetppc;
1187 assert( scip !=
NULL );
1188 assert( vars !=
NULL );
1189 assert( vars !=
NULL );
1190 assert( nrows > 0 );
1191 assert( ncols > 0 );
1192 assert( type !=
NULL );
1195 if ( npprows !=
NULL )
1199 if ( setppcconshdlr ==
NULL )
1209 if ( nsetppcconss == 0 || (nsetppcconss < nrows && npprows ==
NULL ))
1211 assert( setppcconss !=
NULL );
1223 for (i = 0; i < nprobvars; ++i)
1226 for (i = 0; i < nrows; ++i)
1228 for (j = 0; j < ncols; ++j)
1247 for (c = 0; c < nsetppcconss && ncoveredpart < ncols; ++c)
1251 int nrowintersect = 0;
1252 int nvarsinorbitope;
1262 if ( nsetppcvars < ncols )
1266 assert( setppcvars !=
NULL );
1269 nvarsinorbitope = nsetppcvars;
1275 for (i = 0; i < nsetppcvars && nvarsinorbitope >= ncols; ++i)
1281 var = setppcvars[i];
1284 assert( 0 <= idx && idx < nprobvars );
1286 rowidx = rowidxvar[idx];
1296 if ( covered[rowidx] == 2 || (covered[rowidx] == 1 && (nsetppcvars > ncols || nrowintersect > 1)) )
1303 if ( rowcoveragesetppc[rowidx] == 0 )
1304 rowsinsetppc[nrowintersect++] = rowidx;
1305 ++(rowcoveragesetppc[rowidx]);
1310 if ( nsetppcvars - nrowintersect < ncols - 1 )
1318 && nrowintersect == 1 && rowcoveragesetppc[rowsinsetppc[0]] == ncols && nsetppcvars == ncols )
1320 if ( covered[rowsinsetppc[0]] == 1 )
1322 covered[rowsinsetppc[0]] = 2;
1328 for (i = 0; i < nrowintersect; ++i)
1330 if ( covered[rowsinsetppc[i]] == 0 && rowcoveragesetppc[rowsinsetppc[i]] >= ncols )
1332 covered[rowsinsetppc[i]] = 1;
1339 for (i = 0; i < nrowintersect; ++i)
1340 rowcoveragesetppc[rowsinsetppc[i]] = 0;
1344 if ( ncovered == nrows )
1346 if ( ncoveredpart == nrows )
1352 if ( npprows !=
NULL )
1353 *npprows = ncovered;
1355 if ( pprows !=
NULL )
1358 for (i = 0; i < nrows; ++i)
1359 (*pprows)[i] = covered[i] > 0 ? 1 : 0;
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
#define SCIPallocClearBufferArray(scip, ptr, num)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
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_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
enum SCIP_Retcode SCIP_RETCODE
#define SCIPfreeBufferArray(scip, ptr)
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocCleanBufferArray(scip, ptr, num)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
internal miscellaneous methods
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
int SCIPgetNTotalVars(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
SCIP_RETCODE 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_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
type definitions for symmetry computations
methods for handling symmetries
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 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)
#define SCIPfreeCleanBufferArray(scip, ptr)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)