102 orbits[orbitidx++] =
i;
107 while (
j < orbitidx )
115 for (
p = 0;
p < nperms; ++
p)
122 orbits[orbitidx++] = image;
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)
183 int* componentbegins,
187 unsigned* componentblocked,
210 assert( ncomponents > 0 );
211 assert( nmovedpermvars > 0 );
217 for (
i = 0;
i < npermvars; ++
i)
222 for (
i = 0;
i < npermvars; ++
i)
239 orbits[orbitidx++] =
i;
245 while (
j < orbitidx )
259 perm = components[
p];
269 orbits[orbitidx++] = image;
270 assert( orbitidx <= npermvars );
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)
326 int* componentbegins,
379 comp = components[
p];
394 orbit[(*orbitsize)++] = image;
426 int* componentbegins,
447 assert( ncomponents > 0 );
457 for (
i = 0;
i < npermvars; ++
i)
465 for (
i = 0;
i < npermvars; ++
i)
482 orbits[orbitidx++] =
i;
484 varorbitmap[
i] = *norbits;
488 while (
j < orbitidx )
502 perm = components[
p];
509 orbits[orbitidx++] = image;
510 assert( orbitidx <= npermvars );
512 varorbitmap[image] = *norbits;
529 assert( *norbits < npermvars );
530 orbitbegins[*norbits] = orbitidx;
569 if ( perm[perm[
i]] ==
i )
618 for (
p = 0;
p < nperms; ++
p)
620 for (
i = 0;
i < npermvars; ++
i)
625 if ( perms[
p][
i] !=
i )
656 SCIP_Bool* infeasible
682 for (row = 0; row < nrows; ++row)
701 ++(*nusedelems)[
idx1];
702 ++(*nusedelems)[perm[
idx1]];
724 ++(*nusedelems)[
idx2];
725 ++(*nusedelems)[perm[
idx2]];
739 for (row = 0; row < nrows; ++row)
751 ++(*nusedelems)[
idx1];
752 ++(*nusedelems)[perm[
idx1]];
785 int** componentbegins,
787 int** vartocomponent,
789 unsigned** componentblocked,
815 *ncomponents = npermvars;
819 for (
p = 0;
p < nperms; ++
p)
824 for (
i = 0;
i < npermvars; ++
i)
826 (*vartocomponent)[
i] = -1;
828 for (
p = 0;
p < nperms; ++
p)
841 if (
img >= npermvars )
850 (*vartocomponent)[
i] =
p;
851 (*vartocomponent)[
img] =
p;
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;
929 for (
p = 1;
p < nperms; ++
p)
932 (*componentbegins)[++idx] =
p;
934 assert( (*components)[
p] >= 0 );
935 assert( (*components)[
p] < nperms );
938 assert( *ncomponents == idx + 1 );
939 (*componentbegins)[++idx] = nperms;
942 for (
i = 0;
i < npermvars; ++
i)
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]);
998 SCIP_Bool* infeasible,
1052 for (
i = 0;
i < nrows; ++
i)
1092 for (
i = 0;
i < nrows; ++
i)
1112 for (
i = 0;
i < nrows; ++
i)
1141 for (
i = 0;
i < nrows; ++
i)
1243 for (
i = 0;
i < nrows; ++
i)
1245 for (
j = 0;
j < ncols; ++
j)
1375 for (
i = 0;
i < nrows; ++
i)
1412 if ( perm[perm[v]] == v )
1614 if ( degrees[v] > 0 )
1622 for (v = 0,
w = 0; v <
permlen; ++v)
1624 if ( degrees[v] > 0 )
1670 if ( degrees[
varidx[v]] == 1 )
1694 for (
p = 0;
p < nrows; ++
p)
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)
1764 for (v = 0; v < nrows; ++v)
1857 if ( cnt != *ncols )
1865 if ( cnt != *nrows )
1919 for (
i = 0;
i < *nrows; ++
i)
1929 col =
idxtocol2[(*doublelexmatrix)[0][0]];
1931 for (
j = 0;
j < *ncols; ++
j)
1944 for (
i = 1;
i < *nrows; ++
i)
1946 for (
j = 1;
j < *ncols; ++
j)
1958 for (
c = 0;
c < *nrows; ++
c)
1960 for (
d = 0;
d < *ncols; ++
d)
1977 (*doublelexmatrix)[
i][
j] =
elem;
1984 (*rowsbegin)[0] = 0;
1985 (*colsbegin)[0] = 0;
2003 for (
i = *nrows - 1;
i >= 0; --
i)
2081 for (
p = 0;
p < nperms; ++
p)
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)
assert(minobj< SCIPgetCutoffbound(scip))
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 ***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