77 for (
i = 0;
i < npermvars; ++
i)
82 for (
i = 0;
i < npermvars; ++
i)
93 orbits[orbitidx++] =
i;
98 while (
j < orbitidx )
106 for (
p = 0;
p < nperms; ++
p)
113 orbits[orbitidx++] = image;
114 assert( orbitidx <= npermvars );
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)
174 int* componentbegins,
178 unsigned* componentblocked,
201 assert( ncomponents > 0 );
202 assert( nmovedpermvars > 0 );
208 for (
i = 0;
i < npermvars; ++
i)
213 for (
i = 0;
i < npermvars; ++
i)
230 orbits[orbitidx++] =
i;
236 while (
j < orbitidx )
250 perm = components[
p];
252 if ( ! inactiveperms[perm] )
260 orbits[orbitidx++] = image;
261 assert( orbitidx <= npermvars );
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)
317 int* componentbegins,
370 comp = components[
p];
385 orbit[(*orbitsize)++] = image;
417 int* componentbegins,
438 assert( ncomponents > 0 );
448 for (
i = 0;
i < npermvars; ++
i)
456 for (
i = 0;
i < npermvars; ++
i)
473 orbits[orbitidx++] =
i;
475 varorbitmap[
i] = *norbits;
479 while (
j < orbitidx )
493 perm = components[
p];
500 orbits[orbitidx++] = image;
501 assert( orbitidx <= npermvars );
503 varorbitmap[image] = *norbits;
520 assert( *norbits < npermvars );
521 orbitbegins[*norbits] = orbitidx;
560 if ( perm[perm[
i]] ==
i )
609 for (
p = 0;
p < nperms; ++
p)
611 for (
i = 0;
i < npermvars; ++
i)
616 if ( perms[
p][
i] !=
i )
647 SCIP_Bool* infeasible
673 for (row = 0; row < nrows; ++row)
692 ++(*nusedelems)[
idx1];
693 ++(*nusedelems)[perm[
idx1]];
715 ++(*nusedelems)[
idx2];
716 ++(*nusedelems)[perm[
idx2]];
730 for (row = 0; row < nrows; ++row)
742 ++(*nusedelems)[
idx1];
743 ++(*nusedelems)[perm[
idx1]];
775 int** componentbegins,
777 int** vartocomponent,
779 unsigned** componentblocked,
805 *ncomponents = npermvars;
809 for (
p = 0;
p < nperms; ++
p)
814 for (
i = 0;
i < npermvars; ++
i)
816 (*vartocomponent)[
i] = -1;
818 for (
p = 0;
p < nperms; ++
p)
833 (*vartocomponent)[
i] =
p;
834 (*vartocomponent)[
img] =
p;
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;
912 for (
p = 1;
p < nperms; ++
p)
915 (*componentbegins)[++idx] =
p;
917 assert( (*components)[
p] >= 0 );
918 assert( (*components)[
p] < nperms );
921 assert( *ncomponents == idx + 1 );
922 (*componentbegins)[++idx] = nperms;
925 for (
i = 0;
i < npermvars; ++
i)
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]);
981 SCIP_Bool* infeasible,
1035 for (
i = 0;
i < nrows; ++
i)
1075 for (
i = 0;
i < nrows; ++
i)
1095 for (
i = 0;
i < nrows; ++
i)
1124 for (
i = 0;
i < nrows; ++
i)
1226 for (
i = 0;
i < nrows; ++
i)
1228 for (
j = 0;
j < ncols; ++
j)
1358 for (
i = 0;
i < nrows; ++
i)
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
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
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 SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
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)
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_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
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_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 SCIPvarIsBinary(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
void SCIPsortIntInt(int *intarray1, int *intarray2, 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)
methods for handling symmetries
enum SCIP_Retcode SCIP_RETCODE
type definitions for symmetry computations
@ SCIP_ORBITOPETYPE_PACKING
@ SCIP_ORBITOPETYPE_PARTITIONING
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE