53 assert( scip !=
NULL );
54 assert( permvars !=
NULL );
55 assert( perms !=
NULL );
57 assert( npermvars > 0 );
58 assert( orbits !=
NULL );
59 assert( orbitbegins !=
NULL );
60 assert( norbits !=
NULL );
66 for (i = 0; i < npermvars; ++i)
71 for (i = 0; i < npermvars; ++i)
81 beginorbitidx = orbitidx;
82 orbits[orbitidx++] = i;
87 while ( j < orbitidx )
95 for (p = 0; p < nperms; ++p)
97 image = perms[p][curelem];
100 if ( ! varadded[image] )
102 orbits[orbitidx++] = image;
103 assert( orbitidx <= npermvars );
104 varadded[image] =
TRUE;
111 if ( orbitidx <= beginorbitidx + 1 )
112 orbitidx = beginorbitidx;
114 orbitbegins[(*norbits)++] = beginorbitidx;
118 assert( *norbits < npermvars );
119 orbitbegins[*norbits] = orbitidx;
122 printf(
"Orbits (total number: %d):\n", *norbits);
123 for (i = 0; i < *norbits; ++i)
128 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
129 printf(
"%d ", orbits[j]);
163 int* componentbegins,
179 assert( scip !=
NULL );
180 assert( permstrans !=
NULL );
181 assert( nperms > 0 );
182 assert( npermvars > 0 );
183 assert( inactiveperms !=
NULL );
184 assert( orbits !=
NULL );
185 assert( orbitbegins !=
NULL );
186 assert( norbits !=
NULL );
187 assert( components !=
NULL );
188 assert( componentbegins !=
NULL );
189 assert( vartocomponent !=
NULL );
190 assert( ncomponents > 0 );
191 assert( nmovedpermvars > 0 );
197 for (i = 0; i < npermvars; ++i)
202 for (i = 0; i < npermvars; ++i)
209 componentidx = vartocomponent[i];
210 if ( componentidx < 0 || componentblocked[componentidx] )
218 beginorbitidx = orbitidx;
219 orbits[orbitidx++] = i;
225 while ( j < orbitidx )
234 pt = permstrans[curelem];
235 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
239 perm = components[p];
241 if ( ! inactiveperms[perm] )
244 assert( vartocomponent[image] == componentidx );
247 if ( ! varadded[image] )
249 orbits[orbitidx++] = image;
250 assert( orbitidx <= npermvars );
251 varadded[image] =
TRUE;
260 if ( orbitidx <= beginorbitidx + 1 )
261 orbitidx = beginorbitidx;
263 orbitbegins[(*norbits)++] = beginorbitidx;
266 if ( nvaradded >= nmovedpermvars )
271 assert( *norbits < npermvars );
272 orbitbegins[*norbits] = orbitidx;
275 printf(
"Orbits (total number: %d):\n", *norbits);
276 for (i = 0; i < *norbits; ++i)
281 for (j = orbitbegins[i]; j < orbitbegins[i+1]; ++j)
282 printf(
"%d ", orbits[j]);
310 int* componentbegins,
324 assert( scip !=
NULL );
325 assert( permstrans !=
NULL );
326 assert( nperms > 0 );
327 assert( npermvars > 0 );
328 assert( components !=
NULL );
329 assert( componentbegins !=
NULL );
330 assert( vartocomponent !=
NULL );
331 assert( ncomponents > 0 );
332 assert( orbits !=
NULL );
333 assert( orbitbegins !=
NULL );
334 assert( norbits !=
NULL );
335 assert( varorbitmap !=
NULL );
341 for (i = 0; i < npermvars; ++i)
349 for (i = 0; i < npermvars; ++i)
356 componentidx = vartocomponent[i];
357 if ( componentidx < 0 )
365 beginorbitidx = orbitidx;
366 orbits[orbitidx++] = i;
368 varorbitmap[i] = *norbits;
372 while ( j < orbitidx )
381 pt = permstrans[curelem];
382 for (p = componentbegins[componentidx]; p < componentbegins[componentidx + 1]; ++p)
386 perm = components[p];
388 assert( vartocomponent[image] == componentidx );
391 if ( ! varadded[image] )
393 orbits[orbitidx++] = image;
394 assert( orbitidx <= npermvars );
395 varadded[image] =
TRUE;
396 varorbitmap[image] = *norbits;
403 if ( orbitidx <= beginorbitidx + 1 )
405 orbitidx = beginorbitidx;
409 orbitbegins[(*norbits)++] = beginorbitidx;
413 assert( *norbits < npermvars );
414 orbitbegins[*norbits] = orbitidx;
436 assert( perm !=
NULL );
437 assert( vars !=
NULL );
438 assert( iscompoftwocycles !=
NULL );
439 assert( ntwocyclesperm !=
NULL );
440 assert( allvarsbinary !=
NULL );
442 *iscompoftwocycles =
FALSE;
444 *allvarsbinary =
TRUE;
445 for (i = 0; i < nvars; ++i)
451 if ( perm[perm[i]] == i )
458 *allvarsbinary =
FALSE;
470 *iscompoftwocycles =
TRUE;
471 *ntwocyclesperm = ntwocycles;
491 assert( scip !=
NULL );
492 assert( perms !=
NULL );
493 assert( nperms > 0 );
494 assert( permvars !=
NULL );
495 assert( npermvars > 0 );
496 assert( nvarsaffected !=
NULL );
503 for (p = 0; p < nperms; ++p)
505 for (i = 0; i < npermvars; ++i)
510 if ( perms[p][i] != i )
542 int nintersections = 0;
547 assert( suborbitope !=
NULL );
549 assert( nfilledcols > 0 );
550 assert( coltoextend >= 0 );
551 assert( perm !=
NULL );
552 assert( nusedelems !=
NULL );
553 assert( success !=
NULL );
554 assert( infeasible !=
NULL );
561 if ( nfilledcols == 2 )
564 for (row = 0; row < nrows; ++row)
566 idx1 = suborbitope[row][0];
567 idx2 = suborbitope[row][1];
570 if ( idx1 != perm[idx1] )
573 if ( ! leftextension )
575 suborbitope[row][0] = idx2;
576 suborbitope[row][1] = idx1;
578 suborbitope[row][2] = perm[idx1];
581 (*nusedelems)[idx1] += 1;
582 (*nusedelems)[perm[idx1]] += 1;
585 if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
591 else if ( idx2 != perm[idx2] )
596 suborbitope[row][0] = idx2;
597 suborbitope[row][1] = idx1;
599 suborbitope[row][2] = perm[idx2];
602 (*nusedelems)[idx2] += 1;
603 (*nusedelems)[perm[idx2]] += 1;
606 if ( (*nusedelems)[idx2] > 2 || (*nusedelems)[perm[idx2]] > 2 )
617 for (row = 0; row < nrows; ++row)
619 idx1 = suborbitope[row][coltoextend];
622 if ( idx1 != perm[idx1] )
624 suborbitope[row][nfilledcols] = perm[idx1];
627 (*nusedelems)[idx1] += 1;
628 (*nusedelems)[perm[idx1]] += 1;
631 if ( (*nusedelems)[idx1] > 2 || (*nusedelems)[perm[idx1]] > 2 )
641 if ( nintersections > 0 && nintersections < nrows )
643 else if ( nintersections == nrows )
660 int** componentbegins,
662 int** vartocomponent,
671 int* permtocomponent;
676 assert( scip !=
NULL );
677 assert( permvars !=
NULL );
678 assert( npermvars > 0 );
679 assert( perms !=
NULL );
680 assert( components !=
NULL );
681 assert( componentbegins !=
NULL );
682 assert( vartocomponent !=
NULL );
683 assert( componentblocked !=
NULL );
684 assert( ncomponents !=
NULL );
690 *ncomponents = npermvars;
694 for (p = 0; p < nperms; ++p)
695 permtovarcomp[p] = -1;
699 for (i = 0; i < npermvars; ++i)
701 (*vartocomponent)[i] = -1;
703 for (p = 0; p < nperms; ++p)
707 img = transposed ? perms[i][p] : perms[p][i];
718 (*vartocomponent)[i] = p;
719 (*vartocomponent)[img] = p;
722 if ( component2 < component1 )
727 component1 = component2;
732 if ( permtovarcomp[p] == -1 )
734 permtovarcomp[p] = component1;
735 representative = component1;
740 representative = permtovarcomp[p];
744 if ( component1 != component2 )
752 if ( representative != component1 && representative != component2 )
754 if ( representative > component1 )
757 permtovarcomp[p] = component1;
763 else if ( representative > component1 )
765 assert( representative == component2 );
766 permtovarcomp[p] = component1;
772 if ( (*vartocomponent)[i] == -1 )
775 assert( *ncomponents > 0 );
778 for (p = 0; p < nperms; ++p)
783 for (p = 0; p < nperms; ++p)
784 (*components)[p] = p;
793 (*componentbegins)[0] = 0;
794 permtocomponent[(*components)[0]] = 0;
797 for (p = 1; p < nperms; ++p)
799 if ( permtovarcomp[p] > permtovarcomp[p - 1] )
800 (*componentbegins)[++idx] = p;
802 assert( (*components)[p] >= 0 );
803 assert( (*components)[p] < nperms );
804 permtocomponent[(*components)[p]] = idx;
806 assert( *ncomponents == idx + 1 );
807 (*componentbegins)[++idx] = nperms;
810 for (i = 0; i < npermvars; ++i)
813 permidx = (*vartocomponent)[i];
814 assert( -1 <= permidx && permidx < nperms );
818 assert( 0 <= permtocomponent[permidx] );
819 assert( permtocomponent[permidx] < *ncomponents );
821 (*vartocomponent)[i] = permtocomponent[permidx];
827 for (i = 0; i < *ncomponents; ++i)
828 (*componentblocked)[i] =
FALSE;
835 printf(
"number of components: %d\n", propdata->ncomponents);
836 for (i = 0; i < *ncomponents; ++i)
838 printf(
"Component %d contains the following permutations:\n\t", i);
839 for (p = (*componentbegins)[i]; p < (*componentbegins)[i + 1]; ++p)
841 printf(
"%d, ", (*components)[p]);
858 int** orbitopevaridx,
868 assert( vars !=
NULL );
871 assert( permvars !=
NULL );
872 assert( npermvars > 0 );
873 assert( orbitopevaridx !=
NULL );
874 assert( columnorder !=
NULL );
875 assert( nusedelems !=
NULL );
876 assert( infeasible !=
NULL );
878 curcolumn = ncols - 1;
881 while ( curcolumn >= 0 && columnorder[curcolumn] >= 0 )
883 for (i = 0; i < nrows; ++i)
885 assert( orbitopevaridx[i][curcolumn] < npermvars );
889 if ( nfilledcols == 0 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
895 (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
907 assert( curcolumn > 1 || (curcolumn < 0 && nfilledcols == ncols) );
912 for (i = 0; i < nrows; ++i)
914 assert( orbitopevaridx[i][1] < npermvars );
917 (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][1]];
922 for (i = 0; i < nrows; ++i)
924 assert( orbitopevaridx[i][0] < npermvars );
927 (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][0]];
932 if ( nfilledcols < ncols )
937 while ( nfilledcols < ncols )
939 assert( columnorder[curcolumn] < 0 );
941 for (i = 0; i < nrows; ++i)
943 assert( orbitopevaridx[i][curcolumn] < npermvars );
947 if ( nfilledcols == ncols - 1 && nusedelems[orbitopevaridx[i][curcolumn]] > 1 )
953 (*vars)[i][nfilledcols] = permvars[orbitopevaridx[i][curcolumn]];
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
#define SCIPfreeBufferArray(scip, ptr)
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, SCIP_Shortbool *componentblocked, int ncomponents, int nmovedpermvars)
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPgetPropertiesPerm(int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
internal miscellaneous methods
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
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)
methods for handling symmetries
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, SCIP_Shortbool **componentblocked, int *ncomponents)
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)