prop_symmetry.c
Go to the documentation of this file.
34 * - It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry
47 * - We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently
48 * no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt
49 * our code more than continuous/real variables (we basically do not handle integral variables at all).
50 * - We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
51 * symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
58 * - The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly
61 * - We try to compute symmetry as late as possible and then add constraints based on this information.
62 * - Currently, we only allocate memory for pointers to symresack constraints for group generators. If further
71 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
72 * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other
73 * variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering
76 * @pre All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to
77 * a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.@n
78 * F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.
81 * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the
82 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
83 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
84 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
85 * values). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we
86 * can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to
87 * consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have
90 * @pre All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.
92 * @pre No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to
93 * wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing
94 * \f$x_2 = 0\f$ and is interrupted afterwards, orbital fixing detects that the orbit \f$\{x_1, x_2\}\f$ contains
95 * one variable that is fixed to 0, and thus, it fixes \f$x_1\f$ to 0 as well. Thus, after these reductions, every
96 * feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is
97 * complete, because then \f$x_1\f$ is globally fixed to 1, and thus, is stabilized in orbital fixing.
99 * Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path
100 * from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the
101 * initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot
104 * @note If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied
111 * D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.
113 * These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained.
114 * Initially the set of leaders is empty. In a first step, select a variable \f$x_i\f$ and compute its orbit w.r.t.
115 * the symmetry group of the mixed-integer program. For each variable \f$x_j\f$ in the orbit of \f$x_i\f$, the
116 * inequality \f$x_i \geq x_j\f$ is a valid symmetry handling inequality, which can be added to the mixed-integer
117 * program. We call \f$x_i\f$ the leader of this inequality. Add the leader \f$x_i\f$ to the set of leaders and
118 * compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit
119 * w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader
120 * to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become
131 * @todo Order rows of orbitopes (in particular packing/partitioning) w.r.t. cliques in conflict graph.
136 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
167 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
169 #define PROP_PRESOL_PRIORITY -10000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
170 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
171 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
175 #define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
176 #define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
177 #define DEFAULT_DISPLAYNORBITVARS FALSE /**< Should the number of variables affected by some symmetry be displayed? */
178 #define DEFAULT_USECOLUMNSPARSITY FALSE /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
180 #define DEFAULT_COMPRESSSYMMETRIES TRUE /**< Should non-affected variables be removed from permutation to save memory? */
181 #define DEFAULT_COMPRESSTHRESHOLD 0.5 /**< Compression is used if percentage of moved vars is at most the threshold. */
182 #define DEFAULT_SYMFIXNONBINARYVARS FALSE /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
186 #define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
188 #define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
189 #define DEFAULT_DETECTSUBGROUPS TRUE /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
190 #define DEFAULT_ADDWEAKSBCS TRUE /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
191 #define DEFAULT_ADDSTRONGSBCS FALSE /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
192 #define DEFAULT_ADDCONSSTIMING 2 /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
193 #define DEFAULT_MAXNCONSSSUBGROUP 500000 /**< Maximum number of constraints up to which subgroup structures are detected */
194 #define DEFAULT_USEDYNAMICPROP TRUE /**< whether dynamic propagation should be used for full orbitopes */
195 #define DEFAULT_PREFERLESSROWS TRUE /**< Shall orbitopes with less rows be preferred in detection? */
198 #define DEFAULT_OFSYMCOMPTIMING 2 /**< timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
200 #define DEFAULT_RECOMPUTERESTART 0 /**< Recompute symmetries after a restart has occurred? (0 = never) */
203 #define DEFAULT_SSTTIEBREAKRULE 1 /**< index of tie break rule for selecting orbit for Schreier Sims constraints? */
204 #define DEFAULT_SSTLEADERRULE 0 /**< index of rule for selecting leader variables for Schreier Sims constraints? */
205 #define DEFAULT_SSTLEADERVARTYPE 14 /**< bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);
207 #define DEFAULT_ADDCONFLICTCUTS TRUE /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
209 #define DEFAULT_SSTMIXEDCOMPONENTS TRUE /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
213 #define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"
219 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
223 #define MAXGENNUMERATOR 64000000 /**< determine maximal number of generators by dividing this number by the number of variables */
224 #define SCIP_SPECIALVAL 1.12345678912345e+19 /**< special floating point value for handling zeros in bound disjunctions */
225 #define COMPRESSNVARSLB 25000 /**< lower bound on the number of variables above which compression could be performed */
251 int** permstrans; /**< pointer to store transposed permutation generators as (npermvars x nperms) matrix */
256 int nmovedimplintpermvars; /**< number of implicitly integer variables moved by any permutation */
258 SCIP_Shortbool* nonbinpermvarcaptured; /**< array to store which non-binary variables have been captured
269 unsigned* componentblocked; /**< array to store which symmetry methods have been applied to a component using
278 int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
280 SCIP_Bool displaynorbitvars; /**< Whether the number of variables in non-trivial orbits shall be computed */
281 SCIP_Bool compresssymmetries; /**< Should non-affected variables be removed from permutation to save memory? */
282 SCIP_Real compressthreshold; /**< Compression is used if percentage of moved vars is at most the threshold. */
286 SCIP_Bool usecolumnsparsity; /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
288 SCIP_Bool symfixnonbinaryvars; /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
296 int addconsstiming; /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
303 SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
304 SCIP_Bool detectsubgroups; /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
305 SCIP_Bool addweaksbcs; /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
306 SCIP_Bool addstrongsbcs; /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
310 int maxnconsssubgroup; /**< maximum number of constraints up to which subgroup structures are detected */
326 int recomputerestart; /**< Recompute symmetries after a restart has occured? (0 = never, 1 = always, 2 = if OF found reduction) */
327 int ofsymcomptiming; /**< timing of orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
332 SCIP_Bool offoundreduction; /**< whether orbital fixing has found a reduction since the last time computing symmetries */
346 SCIP_Bool addconflictcuts; /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
348 SCIP_Bool sstmixedcomponents; /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
369 /** exec the event handler for handling global variable bound changes (necessary for orbital fixing)
371 * Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain
372 * preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be
373 * caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of
374 * orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when
379 {
455 {
468 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
469 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
479 {
504 * Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.
508 {
548 return SCIPhashFour(SCIPrealHashCode(k->obj), SCIPrealHashCode(k->lb), SCIPrealHashCode((double) k->nconss), SCIPrealHashCode(k->ub));
553 {
557 };
562 {
565 };
579 {
613 {
640 {
797 /* If symmetry is computed before presolving, it might happen that some variables are turned into binary
798 * variables, for which no event has been catched. Since there currently is no way of checking whether a var
802 SCIP_CALL( SCIPdropVarEvent(scip, propdata->permvars[i], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
828 SCIPfreeBlockMemoryArray(scip, &propdata->nonbinpermvarcaptured, propdata->npermvars - propdata->nbinpermvars);
960 /* if orbital fixing runs exclusively, propdata->perms was already freed in determineSymmetry() */
1013 (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) )
1019 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
1027 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
1046 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
1053 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
1074 SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */
1137 /* check whether we have to resize; note that we have to add 2 * nvars since two inequalities may be added */
1144 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matidx), matrixdata->nmaxmatcoef, newsize) );
1145 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matrhsidx), matrixdata->nmaxmatcoef, newsize) );
1146 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matvaridx), matrixdata->nmaxmatcoef, newsize) );
1147 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matcoef), matrixdata->nmaxmatcoef, newsize) );
1148 SCIPdebugMsg(scip, "Resized matrix coefficients from %d to %d.\n", matrixdata->nmaxmatcoef, newsize);
1180 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1193 /* add negative of equation; increases chance to detect symmetry, but might increase time to compute symmetry. */
1199 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1241 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1270 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1293 * We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed
1332 /* create hashmaps for variable permutation and constraints in non-linear part array for occuring variables */
1412 if ( matrixdata->rhssense[r1] == matrixdata->rhssense[r2] && SCIPisEQ(scip, matrixdata->rhscoef[r1], matrixdata->rhscoef[r2]) )
1420 while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r2 && SCIPisEQ(scip, permrow[matrixdata->matvaridx[j]], matrixdata->matcoef[j] ) )
1508 SCIP_CALL( SCIPsimplifyExpr(scip, permutedexpr, &permutedexpr, &success, &infeasible, NULL, NULL) );
1599 return propdata->conshdlr_nonlinear != NULL && SCIPconshdlrGetNActiveConss(propdata->conshdlr_nonlinear) > 0;
1614 int* nmovedvars, /**< pointer to store number of vars affected by symmetry (if usecompression) or NULL */
1615 SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
1617 SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1714 /* detect whether binary variable is affected by symmetry and count number of binary permvars */
1738 SCIP_Bool compresssymmetries, /**< Should non-affected variables be removed from permutation to save memory? */
1739 SCIP_Real compressthreshold, /**< Compression is used if percentage of moved vars is at most the threshold. */
1744 SCIP_Bool usecolumnsparsity, /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
1750 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1755 SCIP_Bool* binvaraffected, /**< pointer to store wether a binary variable is affected by symmetry */
1852 SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
1855 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
1860 /* use a staggered scheme for allocating space for non-zeros of constraint matrix since it can become large */
1947 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
1960 /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
1970 /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
1987 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata, nconssforvar) );
1990 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1993 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2026 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
2027 (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata, nconssforvar) );
2081 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
2082 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2096 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
2097 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2107 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
2108 SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2122 * is of type 1. If the bound disjunction has length two and both disjunctions contain the same variable,
2123 * we say the bound disjunction is of type 2. Further bound disjunctions are possible, but can currently
2134 * Note that problems arise if \fb'_i = 0\f for some variable \fx_i\f, because its coefficient in the
2172 /* stop, we cannot handle bounddisjunctions with more than two variables that contain a variable twice */
2178 " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
2203 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nbounddisjvars, 0.0, 0.0,
2233 for (expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
2237 /* for variables, we check whether they appear nonlinearly and store the result in the resp. array */
2241 (*isnonlinvar)[SCIPvarGetProbindex(SCIPgetVarExprVar(expr))] = (SCIPexpriterGetParentDFS(it) != rootexpr || !SCIPisExprSum(scip, rootexpr));
2268 SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
2311 SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
2331 if ( SymmetryFixVar(fixedtype, var) || (nnlconss > 0 && SCIPhashsetExists(auxvars, (void*) var)) )
2335 SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
2366 SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
2367 SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
2430 SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
2464 SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
2479 SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
2480 SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
2481 SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
2483 /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
2484 if ( matrixdata.nuniquevars < nvars && (matrixdata.nuniquemat == 0 || matrixdata.nuniquemat < matrixdata.nmatcoef) )
2487 SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, &exprdata, nperms, nmaxperms,
2492 if ( checksymmetries && SCIPgetStage(scip) > SCIP_STAGE_INITPRESOLVE && ! SCIPisStopped(scip) )
2499 SCIP_CALL( setSymmetryData(scip, vars, nvars, nbinvars, permvars, npermvars, nbinpermvars, *perms, *nperms,
2553 SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2554 SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2605 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2631 /* do not compute symmetry if there are no binary variables and non-binary variables cannot be handled, but only binary variables would be used */
2654 /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2662 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2688 " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2709 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2727 SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2728 maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity, propdata->conshdlr_nonlinear,
2729 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2743 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2756 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
2766 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2776 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2782 SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2785 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2789 /* exit if no binary variables are affected by symmetry and we cannot handle non-binary symmetries */
2792 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2798 ! ( ISSSTINTACTIVE(propdata->sstleadervartype) || ISSSTIMPLINTACTIVE(propdata->sstleadervartype)
2803 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) -> no handable symmetry found, free symmetry data.\n",
2822 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2825 /* we only need the components for orbital fixing, orbitope and subgroup detection, and Schreier Sims constraints */
2829 SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2835 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
2901 /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
2906 SCIP_CALL( SCIPcatchVarEvent(scip, propdata->permvars[v], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
2977 /* if Schreier-Sims constraints are enabled, also capture symmetric variables and forbid multi aggregation of handable vars */
3032 /** Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
3034 * If @p activevars == NULL, then the function assumes all permutations of the component are active and therefore all
3037 * We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes.
3038 * For example (1,2), (2,3), (3,4), (3,5) defines the symmetric group on {1,2,3,4,5}, but the generators we expect
3133 /* in the subgroup case it might happen that a generator has less than ntwocycles many 2-cyles */
3176 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3213 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3236 int* ntwocycleperms /**< pointer to store the number of 2-cycle permutations in component compidx */
3278 SCIP_CALL( SCIPisInvolutionPerm(perm, propdata->permvars, npermvars, &(ntwocycles[i]), &nbincycles, FALSE) );
3304 * After execution, @p graphcomponents contains all permvars sorted by their color and component,
3305 * @p graphcompbegins points to the indices where new components in @p graphcomponents start and
3315 int** graphcomponents, /**< buffer to store the components of the graph (ordered var indices) */
3388 /* iteratively handle each swap of perm until an invalid one is found or all edges have been added */
3408 /* another permutation has already merged these variables into one component; store its color */
3427 /* a generator is not allowed to connect two components of the same color, since they depend on each other */
3495 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, k)) == firstcolor );
3496 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, img)) == firstcolor );
3506 * disjoint sets to the arrays graphcomponents, graphcompbegins, and compcolorbegins (see above).
3592 SCIP_Bool mayinteract, /**< whether orbitope's symmetries might interact with other symmetries */
3685 /* it might happen that we cannot detect the orbitope if it is generated by permutations with different
3725 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3737 /* iterate over all columns (elements in orbit), because we cannot see from ngencols which columns
3767 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "suborbitope_%d_%d", graphcoloridx, propdata->norbitopes);
3770 SCIP_ORBITOPETYPE_FULL, nrows, ngencols, FALSE, mayinteract, FALSE, FALSE, propdata->conssaddlp,
3801 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3854 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "strong_sbcs_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3875 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
3900 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3956 assert( ! SCIPhashmapExists(varsinlexorder, (void*) (long) (*lexorder)[k]) ); /* Use int as pointer */
3961 /* We will store the newest and the largest orbit and activeorb will be used to mark at which entry of the array
3979 /* if the first variable was already contained in another orbit or if there are no variables left anyway, skip the
4028 SCIPdebugMsg(scip, " adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
4040 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "weak_sbcs_%d_%s_%s", symgrpcompidx, SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
4061 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4092 /* the leader of the weak inequalities has to be the first element in the lexicographic order */
4140 SCIP_VAR** modifiedpermvars, /**< memory for array of permutation vars w.r.t. new variable ordering */
4176 /* Iterate over leaders and put the l-th leader to the l-th position of the lexicographic order.
4177 * We do this by swapping the l-th leader with the element at position l of the current permvars array. */
4339 /* create arrays for modified permutations in case we adapt the lexicographic order because of suborbitopes */
4354 SCIPdebugMsg(scip, "starting subgroup detection routine for %d components\n", propdata->ncomponents);
4390 /* set the first npermsincomp entries of genorder; the others are not used for this component */
4399 SCIPdebugMsg(scip, "component %d has %d permutations consisting of 2-cycles\n", i, ntwocycleperms);
4427 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%s,", SCIPvarGetName(propdata->permvars[k]));
4431 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s,", SCIPvarGetName(propdata->permvars[j]));
4458 SCIPdebugMsg(scip, " created subgroup detection graph using %d of the permutations\n", nusedperms);
4499 norbitopesincomp = getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
4502 /* if there is just one orbitope satisfying the requirements, handle the full component by symresacks */
4514 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, propdata->perms[propdata->components[propdata->componentbegins[i] + k]],
4560 SCIPdebugMsg(scip, " color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4612 SCIPdebugMsg(scip, " affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4625 SCIPdebugMsg(scip, " detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4632 * It might happen that we cannot generate the orbitope matrix if the orbitope is not generated by permutations
4633 * all having the same number of 2-cycles, e.g., the orbitope generated by (1,2)(4,5), (2,3), (5,6).
4646 /* adapt the first variable per color to be compatible with the created orbiope (upper left variable) */
4686 SCIP_CALL( addStrongSBCsSubgroup(scip, propdata, graphcompbegins, graphcomponents, largestcolorcomp,
4690 if ( ! SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4737 SCIPdebugMsg(scip, " don't add weak sbcs because all generators were used or the settings forbid it\n");
4739 /* if suborbitopes or strong group actions have been found, potentially add symresacks adapted to
4760 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[propdata->components[propdata->componentbegins[i] + k]],
4775 SCIPdebugMsg(scip, " add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, i);
4816 /** sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row;
4906 int* componentbegins, /**< array containing begin positions of components in components array */
4995 /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
5016 SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
5055 SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(scip, &vars, ntwocyclescomp, npermsincomponent + 1, permvars,
5056 npermvars, orbitopevaridx, columnorder, nusedelems, rowisbinary, &infeasibleorbitope, FALSE, NULL, NULL, NULL) );
5062 SCIPdebugMsg(scip, "found an orbitope of size %d x %d in component %d\n", ntwocyclescomp, npermsincomponent + 1, i);
5067 SCIP_CALL( SCIPsortOrbitope(scip, orbitopevaridx, vars, nbincyclescomp, npermsincomponent + 1) );
5110 SCIP_VAR** graphvars, /**< variables encoded in conflict graph (either all vars or permvars) */
5259 SCIP_Bool* success /**< pointer to store whether conflict graph could be created successfully */
5287 SCIPdebugMsg(scip, "Could not find setppc conshdlr --> construction of conflict graph aborted.\n");
5296 SCIPdebugMsg(scip, "No setppc constraints present --> construction of conflict graph aborted.\n");
5368 SCIPdebugMsg(scip, "Construction of conflict graph terminated; %d conflicts detected.\n", nedges);
5417 int* componentbegins, /**< array containing begin positions of components in components array */
5458 /* adapt natural variable order to a variable order that is compatible with Schreier Sims constraints */
5471 SCIP_CALL( adaptSymmetryDataSST(scip, perms, modifiedperms, nperms, permvars, modifiedpermvars, npermvars,
5537 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[permidx], modifiedpermvars, npermvars, FALSE,
5542 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
5586 SCIP_Shortbool* orbitvarinconflict, /**< indicator whether orbitvar is in conflict with orbit leader */
5620 /* variables in conflict with leader are fixed and not treated by a cut; trailing -1 to not count the leader */
5742 SCIP_HASHMAP* varmap, /**< map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE */
5753 SCIP_Shortbool* orbitvarinconflict, /**< array to store whether a var in the orbit is conflicting with leader */
5754 int* norbitvarinconflict, /**< pointer to store number of vars in the orbit in conflict with leader */
5799 if ( leaderrule == (int) SCIP_LEADERRULE_FIRSTINORBIT || leaderrule == (int) SCIP_LEADERRULE_LASTINORBIT )
5867 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
5873 if ( *success && tiebreakrule == (int) SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && nconflictvars > 0 )