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 */
1855 SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
1858 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
1863 /* use a staggered scheme for allocating space for non-zeros of constraint matrix since it can become large */
1950 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
1963 /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
1973 /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
1990 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata, nconssforvar) );
1993 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
1996 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2029 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
2030 (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata, nconssforvar) );
2084 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
2085 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2099 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
2100 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2110 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
2111 SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2125 * is of type 1. If the bound disjunction has length two and both disjunctions contain the same variable,
2126 * we say the bound disjunction is of type 2. Further bound disjunctions are possible, but can currently
2137 * Note that problems arise if \fb'_i = 0\f for some variable \fx_i\f, because its coefficient in the
2175 /* stop, we cannot handle bounddisjunctions with more than two variables that contain a variable twice */
2181 " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
2206 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nbounddisjvars, 0.0, 0.0,
2236 for (expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
2240 /* for variables, we check whether they appear nonlinearly and store the result in the resp. array */
2244 (*isnonlinvar)[SCIPvarGetProbindex(SCIPgetVarExprVar(expr))] = (SCIPexpriterGetParentDFS(it) != rootexpr || !SCIPisExprSum(scip, rootexpr));
2271 SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
2314 SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
2334 if ( SymmetryFixVar(fixedtype, var) || (nnlconss > 0 && SCIPhashsetExists(auxvars, (void*) var)) )
2338 SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
2369 SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
2370 SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
2433 SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
2467 SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
2482 SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
2483 SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
2484 SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
2486 /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
2487 if ( matrixdata.nuniquevars < nvars && (matrixdata.nuniquemat == 0 || matrixdata.nuniquemat < matrixdata.nmatcoef) )
2490 SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, &exprdata, nperms, nmaxperms,
2495 if ( checksymmetries && SCIPgetStage(scip) > SCIP_STAGE_INITPRESOLVE && ! SCIPisStopped(scip) )
2502 SCIP_CALL( setSymmetryData(scip, vars, nvars, nbinvars, permvars, npermvars, nbinpermvars, *perms, *nperms,
2556 SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2557 SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2609 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2635 /* do not compute symmetry if there are no binary variables and non-binary variables cannot be handled, but only binary variables would be used */
2658 /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2666 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2692 " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2713 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2731 SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2732 maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity, propdata->conshdlr_nonlinear,
2733 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2747 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2760 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present (symcode time: %.2f)\n", SCIPgetSolvingTime(scip), symcodetime);
2770 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2780 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2786 SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2789 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2793 /* exit if no binary variables are affected by symmetry and we cannot handle non-binary symmetries */
2796 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2802 ! ( ISSSTINTACTIVE(propdata->sstleadervartype) || ISSSTIMPLINTACTIVE(propdata->sstleadervartype)
2807 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) -> no handable symmetry found, free symmetry data.\n",
2826 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2829 /* we only need the components for orbital fixing, orbitope and subgroup detection, and Schreier Sims constraints */
2833 SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2839 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
2905 /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
2910 SCIP_CALL( SCIPcatchVarEvent(scip, propdata->permvars[v], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
2981 /* if Schreier-Sims constraints are enabled, also capture symmetric variables and forbid multi aggregation of handable vars */
3036 /** Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
3038 * If @p activevars == NULL, then the function assumes all permutations of the component are active and therefore all
3041 * We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes.
3042 * 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
3137 /* in the subgroup case it might happen that a generator has less than ntwocycles many 2-cyles */
3180 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3217 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3240 int* ntwocycleperms /**< pointer to store the number of 2-cycle permutations in component compidx */
3282 SCIP_CALL( SCIPisInvolutionPerm(perm, propdata->permvars, npermvars, &(ntwocycles[i]), &nbincycles, FALSE) );
3308 * After execution, @p graphcomponents contains all permvars sorted by their color and component,
3309 * @p graphcompbegins points to the indices where new components in @p graphcomponents start and
3319 int** graphcomponents, /**< buffer to store the components of the graph (ordered var indices) */
3392 /* iteratively handle each swap of perm until an invalid one is found or all edges have been added */
3412 /* another permutation has already merged these variables into one component; store its color */
3431 /* a generator is not allowed to connect two components of the same color, since they depend on each other */
3499 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, k)) == firstcolor );
3500 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, img)) == firstcolor );
3510 * disjoint sets to the arrays graphcomponents, graphcompbegins, and compcolorbegins (see above).
3596 SCIP_Bool mayinteract, /**< whether orbitope's symmetries might interact with other symmetries */
3689 /* it might happen that we cannot detect the orbitope if it is generated by permutations with different
3729 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3741 /* iterate over all columns (elements in orbit), because we cannot see from ngencols which columns
3771 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "suborbitope_%d_%d", graphcoloridx, propdata->norbitopes);
3774 SCIP_ORBITOPETYPE_FULL, nrows, ngencols, FALSE, mayinteract, FALSE, FALSE, propdata->conssaddlp,
3805 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3858 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "strong_sbcs_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3879 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
3904 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3961 assert( ! SCIPhashmapExists(varsinlexorder, (void*) (size_t) (*lexorder)[k]) ); /* Use int as pointer */
3966 /* We will store the newest and the largest orbit and activeorb will be used to mark at which entry of the array
3985 /* if the first variable was already contained in another orbit or if there are no variables left anyway, skip the
4034 SCIPdebugMsg(scip, " adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
4046 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "weak_sbcs_%d_%s_%s", symgrpcompidx, SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
4067 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4099 /* the leader of the weak inequalities has to be the first element in the lexicographic order */
4147 SCIP_VAR** modifiedpermvars, /**< memory for array of permutation vars w.r.t. new variable ordering */
4183 /* Iterate over leaders and put the l-th leader to the l-th position of the lexicographic order.
4184 * We do this by swapping the l-th leader with the element at position l of the current permvars array. */
4346 /* create arrays for modified permutations in case we adapt the lexicographic order because of suborbitopes */
4361 SCIPdebugMsg(scip, "starting subgroup detection routine for %d components\n", propdata->ncomponents);
4397 /* set the first npermsincomp entries of genorder; the others are not used for this component */
4406 SCIPdebugMsg(scip, "component %d has %d permutations consisting of 2-cycles\n", i, ntwocycleperms);
4434 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%s,", SCIPvarGetName(propdata->permvars[k]));
4438 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s,", SCIPvarGetName(propdata->permvars[j]));
4465 SCIPdebugMsg(scip, " created subgroup detection graph using %d of the permutations\n", nusedperms);
4506 norbitopesincomp = getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
4509 /* if there is just one orbitope satisfying the requirements, handle the full component by symresacks */
4521 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, propdata->perms[propdata->components[propdata->componentbegins[i] + k]],
4567 SCIPdebugMsg(scip, " color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4619 SCIPdebugMsg(scip, " affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4632 SCIPdebugMsg(scip, " detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4639 * It might happen that we cannot generate the orbitope matrix if the orbitope is not generated by permutations
4640 * all having the same number of 2-cycles, e.g., the orbitope generated by (1,2)(4,5), (2,3), (5,6).
4653 /* adapt the first variable per color to be compatible with the created orbiope (upper left variable) */
4693 SCIP_CALL( addStrongSBCsSubgroup(scip, propdata, graphcompbegins, graphcomponents, largestcolorcomp,
4697 if ( ! SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4744 SCIPdebugMsg(scip, " don't add weak sbcs because all generators were used or the settings forbid it\n");
4746 /* if suborbitopes or strong group actions have been found, potentially add symresacks adapted to
4767 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[propdata->components[propdata->componentbegins[i] + k]],
4782 SCIPdebugMsg(scip, " add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, i);
4823 /** sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row;
4913 int* componentbegins, /**< array containing begin positions of components in components array */
5002 /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
5023 SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
5062 SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(scip, &vars, ntwocyclescomp, npermsincomponent + 1, permvars,
5063 npermvars, orbitopevaridx, columnorder, nusedelems, rowisbinary, &infeasibleorbitope, FALSE, NULL, NULL, NULL) );
5069 SCIPdebugMsg(scip, "found an orbitope of size %d x %d in component %d\n", ntwocyclescomp, npermsincomponent + 1, i);
5074 SCIP_CALL( SCIPsortOrbitope(scip, orbitopevaridx, vars, nbincyclescomp, npermsincomponent + 1) );
5117 SCIP_VAR** graphvars, /**< variables encoded in conflict graph (either all vars or permvars) */
5266 SCIP_Bool* success /**< pointer to store whether conflict graph could be created successfully */
5294 SCIPdebugMsg(scip, "Could not find setppc conshdlr --> construction of conflict graph aborted.\n");
5303 SCIPdebugMsg(scip, "No setppc constraints present --> construction of conflict graph aborted.\n");
5375 SCIPdebugMsg(scip, "Construction of conflict graph terminated; %d conflicts detected.\n", nedges);
5424 int* componentbegins, /**< array containing begin positions of components in components array */
5465 /* adapt natural variable order to a variable order that is compatible with Schreier Sims constraints */
5478 SCIP_CALL( adaptSymmetryDataSST(scip, perms, modifiedperms, nperms, permvars, modifiedpermvars, npermvars,
5544 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[permidx], modifiedpermvars, npermvars, FALSE,
5549 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
5593 SCIP_Shortbool* orbitvarinconflict, /**< indicator whether orbitvar is in conflict with orbit leader */
5627 /* variables in conflict with leader are fixed and not treated by a cut; trailing -1 to not count the leader */
5749 SCIP_HASHMAP* varmap, /**< map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE */
5760 SCIP_Shortbool* orbitvarinconflict, /**< array to store whether a var in the orbit is conflicting with leader */
5761 int* norbitvarinconflict, /**< pointer to store number of vars in the orbit in conflict with leader */
5806 if ( leaderrule == (int) SCIP_LEADERRULE_FIRSTINORBIT || leaderrule == (int) SCIP_LEADERRULE_LASTINORBIT )
5874 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
5880 if ( *success && tiebreakrule == (int) SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && nconflictvars > 0 )
5948 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
6181 /* initialize array indicating whether permutations shall not be considered for orbit permutations */
6232 SCIP_CALL( updateSymInfoConflictGraphSST(scip, conflictgraph, vars, nvars, permvars, npermvars, FALSE,
6237 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6240 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6245 if ( tiebreakrule == SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && selectedtype != SCIP_VARTYPE_BINARY )
6250 permvars, npermvars, orbits, orbitbegins, norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype,
6251 &orbitidx, &orbitleaderidx, orbitvarinconflict, &norbitvarinconflict, conflictgraphcreated, &success) );
6257 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
6258 SCIPdebugMsg(scip, "%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
6262 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges, conflictgraphcreated) );
6264 ++norbitleadercomponent[propdata->vartocomponent[orbits[orbitbegins[orbitidx] + orbitleaderidx]]];
6288 /* if Schreier Sims constraints have been added, store that Schreier Sims has been used for this component */
6355 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6359 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6362 /* if there is no symmetry compatible with OF, check whether there are more general symmetries */
6370 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6375 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6384 SCIPdebugMsg(scip, "Symmetry propagator: problem is linear and no symmetry on binary variables has been found, turning symretope constraints off.\n");
6388 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || propdata->sstenabled );
6398 SCIP_CALL( detectOrbitopes(scip, propdata, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6416 if ( propdata->ncompblocked < propdata->ncomponents && propdata->detectsubgroups && propdata->symconsenabled )
6420 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize) );
6443 SCIP_CALL( addSymresackConss(scip, prop, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6446 /* free symmetry conss if no orbitope/symresack constraints have been found (may happen if Schreier-Sims constraints are active) */
6463 * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
6464 * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
6465 * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
6604 * The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
6644 /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
6743 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6747 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6749 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || ! propdata->ofenabled );
6787 SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, bg1, bg1list, &nbg1) );
6842 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
6845 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
6848 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
6901 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
6904 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
6907 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
6924 * Note that variables globally fixed to 1 are not resetted, since the loop starts at propdata->nbg1. */
6936 orbits, orbitbegins, &norbits, components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
6943 SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits (%d active perms).\n", norbits, nactiveperms);
6944 SCIP_CALL( performOrbitalFixing(scip, permvars, nbinpermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
6965 /** presolving initialization method of propagator (called when presolving is about to begin) */
6998 /* otherwise compute symmetry if timing requests it; fix non-binary potential branching variables */
7001 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7005 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7014 /** presolving deinitialization method of propagator (called after presolving has been finished) */
7030 /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
7032 if ( (propdata->symconsenabled || propdata->sstenabled) && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7037 /* if timing requests it, guarantee that symmetries are computed even if presolving is disabled */
7038 if ( propdata->ofenabled && propdata->ofsymcomptiming <= 1 && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7043 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7047 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7082 assert( 0 <= propdata->addconsstiming && propdata->addconsstiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7083 if ( propdata->addconsstiming > SYM_COMPUTETIMING_DURINGPRESOL && ! SCIPisPresolveFinished(scip) )
7115 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
7121 SCIP_CALL( SCIPpresolCons(scip, propdata->genorbconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7122 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7123 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7128 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genorbconss[i]));
7135 SCIP_CALL( SCIPpresolCons(scip, propdata->genlinconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7136 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7137 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7142 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genlinconss[i]));
7151 SCIP_CALL( SCIPpresolCons(scip, propdata->sstconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7152 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7153 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7158 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->sstconss[i]));
7162 SCIPdebugMsg(scip, "Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
7168 assert( 0 <= propdata->ofsymcomptiming && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7169 if ( propdata->ofenabled && propdata->performpresolving && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_DURINGPRESOL )
7196 /* otherwise compute symmetry early if timing requests it; fix non-binary potential branching variables */
7199 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7203 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7288 {
7324 * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
7325 * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
7444 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(propdata->eventhdlr), EVENTHDLR_SYMMETRY_NAME, EVENTHDLR_SYMMETRY_DESC,
7458 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSymmetry, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
7470 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
7516 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
7522 "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
7562 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
7567 "rule to select the orbit in Schreier Sims inequalities (variable in 0: minimum size orbit; 1: maximum size orbit; 2: orbit with most variables in conflict with leader)",
7572 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit; 3: var having most conflicting vars in problem)",
7577 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
7593 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
7614 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetName(), SYMsymmetryGetDesc()) );
7617 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetAddName(), SYMsymmetryGetAddDesc()) );
7632 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
7633 int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
7635 SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected (or NULL) */
7637 int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
7638 int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
7650 assert( ncomponents != NULL || (components == NULL && componentbegins == NULL && vartocomponent == NULL) );
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)
Definition: symmetry.c:766
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
Definition: type_symmetry.h:63
static SCIP_RETCODE addSSTConssOrbitAndUpdateSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds, SCIP_Bool useconflictgraph)
Definition: prop_symmetry.c:5585
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
Definition: type_result.h:42
void SCIPsortIntIntPtr(int *intarray1, int *intarray2, void **ptrarray, int len)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:500
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
Definition: prop_symmetry.c:6700
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPsimplifyExpr(SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1763
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:56
Definition: type_symmetry.h:56
Definition: type_symmetry.h:87
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11208
Definition: struct_scip.h:68
Constraint handler for variable bound constraints .
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents)
Definition: prop_symmetry.c:5421
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2497
static SCIP_RETCODE updateSymInfoConflictGraphSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_VAR **permvars, int npermvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *varmap, int *orbits, int *orbitbegins, int norbits)
Definition: prop_symmetry.c:5115
static SCIP_Bool isLeadervartypeCompatible(SCIP_VAR *var, int leadervartype)
Definition: prop_symmetry.c:717
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
Definition: prop_symmetry.c:479
Definition: type_symmetry.h:57
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:739
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3366
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5407
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5424
Definition: struct_var.h:160
SCIP_RETCODE SCIPgetSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents)
Definition: prop_symmetry.c:7627
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_symresack.c:1733
Definition: type_symmetry.h:115
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
Definition: type_result.h:58
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds)
Definition: prop_symmetry.c:5994
Definition: cons_setppc.h:89
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3387
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7731
Definition: type_result.h:47
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3429
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:773
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
Definition: compute_symmetry_bliss.cpp:1025
Definition: type_symmetry.h:62
Definition: struct_misc.h:149
Definition: struct_var.h:207
Definition: struct_var.h:91
static SCIP_DECL_PROPRESPROP(propRespropSymmetry)
Definition: prop_symmetry.c:7330
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
Definition: prop_symmetry.c:4910
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)
Definition: symmetry.c:163
Definition: type_message.h:54
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4554
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes)
Definition: prop_symmetry.c:5384
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
Definition: type_symmetry.h:89
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3709
Definition: type_var.h:62
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3142
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3767
int SCIPgetSymmetryNGenerators(SCIP *scip)
Definition: prop_symmetry.c:7727
Definition: cons_setppc.h:88
static SCIP_RETCODE SCIPsortOrbitope(SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols)
Definition: prop_symmetry.c:4828
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13765
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, SCIP_CONSHDLR *conshdlr_nonlinear, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool **isnonlinvar, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *symcodetime, SCIP_Bool *success)
Definition: prop_symmetry.c:1736
Definition: type_symmetry.h:61
Constraint handler for AND constraints, .
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:4307
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5453
Constraint handler for the set partitioning / packing / covering constraints .
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)
Definition: prop_symmetry.c:2554
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
Definition: prop_symmetry.c:1298
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18475
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:682
static SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
Definition: prop_symmetry.c:6968
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
Definition: prop_symmetry.c:1025
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
Definition: struct_tree.h:141
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:617
Definition: type_symmetry.h:86
Definition: prop_symmetry.c:553
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2246
static SCIP_RETCODE addWeakSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int ncompcolors, int *chosencomppercolor, int *firstvaridxpercolor, int symgrpcompidx, int *naddedconss, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: prop_symmetry.c:3894
public functions to work with algebraic expressions
Definition: struct_symmetry.h:44
interface for symmetry computations
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1724
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3373
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
constraint handler for symresack constraints
static SCIP_RETCODE checkTwoCyclePermsAreOrbitope(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int *activeperms, int ntwocycles, int nactiveperms, int **orbitopevaridx, int *columnorder, int *nusedelems, int *nusedcols, SCIP_Shortbool *rowisbinary, SCIP_Bool *isorbitope, SCIP_Shortbool *activevars)
Definition: prop_symmetry.c:3051
Constraint handler for "or" constraints, .
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
static int getNSymhandableConss(SCIP *scip, SCIP_CONSHDLR *conshdlr_nonlinear)
Definition: prop_symmetry.c:1556
Definition: type_symmetry.h:58
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
Definition: struct_misc.h:137
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:263
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
Definition: prop_symmetry.c:3236
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5430
const char * SYMsymmetryGetAddName(void)
Definition: compute_symmetry_bliss.cpp:1013
Definition: type_result.h:44
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3738
Definition: struct_cons.h:46
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2567
SCIP_Bool SCIPisOrbitalfixingEnabled(SCIP *scip)
Definition: prop_symmetry.c:7707
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5176
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *bg1, int *bg1list, int *nbg1)
Definition: prop_symmetry.c:6608
Definition: struct_cons.h:126
static SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
Definition: prop_symmetry.c:455
Definition: type_expr.h:700
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7668
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Definition: type_lp.h:56
SCIP_RETCODE SCIPpresolCons(SCIP *scip, SCIP_CONS *cons, int nrounds, SCIP_PRESOLTIMING presoltiming, int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, int *nfixedvars, int *naggrvars, int *nchgvartypes, int *nchgbds, int *naddholes, int *ndelconss, int *naddconss, int *nupgdconss, int *nchgcoefs, int *nchgsides, SCIP_RESULT *result)
Definition: scip_cons.c:2352
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3740
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7684
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
Definition: prop_symmetry.c:7366
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5447
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
Definition: prop_symmetry.c:498
static SCIP_RETCODE addOrbitopeSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *usedperms, int nusedperms, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int graphcoloridx, int nrows, int ncols, int *firstvaridx, int *compidxfirstrow, int **lexorder, int *nvarslexorder, int *maxnvarslexorder, SCIP_Bool mayinteract, SCIP_Bool *success)
Definition: prop_symmetry.c:3581
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12268
internal miscellaneous methods
Definition: prop_symmetry.c:562
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11181
Definition: type_retcode.h:42
Definition: cons_setppc.h:87
Definition: type_stat.h:42
static SCIP_RETCODE addStrongSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: prop_symmetry.c:3800
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1738
propagator for symmetry handling
Definition: type_result.h:51
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
Definition: struct_expr.h:202
static SCIP_RETCODE selectOrbitLeaderSSTConss(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_HASHMAP *varmap, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool useconflictgraph, SCIP_Bool *success)
Definition: prop_symmetry.c:5745
static SCIP_RETCODE createConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *permvarmap, SCIP_Bool *success)
Definition: prop_symmetry.c:5260
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
Definition: scip_datastructures.c:654
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11278
static int getNOrbitopesInComp(SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
Definition: prop_symmetry.c:4224
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2523
Definition: struct_prop.h:46
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2296
Definition: type_retcode.h:43
const char * SYMsymmetryGetAddDesc(void)
Definition: compute_symmetry_bliss.cpp:1019
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13685
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1591
Definition: struct_expr.h:104
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5476
constraint handler for linking binary variables to a linking (continuous or integer) variable ...
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7605
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7716
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:584
static SCIP_RETCODE setSymmetryData(SCIP *scip, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
Definition: prop_symmetry.c:1605
Definition: type_var.h:64
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17159
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9461
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_var.h:63
Definition: type_message.h:52
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:668
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:533
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2482
SCIP_Bool SYMcanComputeSymmetry(void)
Definition: compute_symmetry_bliss.cpp:979
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17197
Definition: type_set.h:49
static SCIP_RETCODE adaptSymmetryDataSST(SCIP *scip, int **origperms, int **modifiedperms, int nperms, SCIP_VAR **origpermvars, SCIP_VAR **modifiedpermvars, int npermvars, int *leaders, int nleaders)
Definition: prop_symmetry.c:4142
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:857
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5499
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2558
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12764
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)
Definition: symmetry.c:970
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4631
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)
Definition: symmetry.c:636
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9438
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:663
Definition: type_set.h:48
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17865
Constraint handler for XOR constraints, .
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:529
Definition: struct_misc.h:89
Definition: type_symmetry.h:104
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5450
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18562
methods for handling symmetries
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
Definition: cons_linking.c:3669
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)
Definition: symmetry.c:311
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2255
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:695
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3408
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3646
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3750
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13742
public methods for data structures
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
Definition: type_retcode.h:54
Definition: type_set.h:53
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2609
Definition: struct_symmetry.h:78
static SCIP_RETCODE performOrbitalFixing(SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone)
Definition: prop_symmetry.c:6470
static SCIP_RETCODE collectCoefficients(SCIP *scip, SCIP_Bool doubleequations, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata, int *nconssforvar)
Definition: prop_symmetry.c:1071
static SCIP_Bool hasNonlinearConstraints(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1594
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:713
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool mayinteract, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_orbitope.c:3676
Definition: struct_misc.h:277
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18586
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
static SCIP_RETCODE setSymmetryMethodEnabledValues(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:746
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12796
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3106
Definition: type_retcode.h:52
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3231
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
constraint handler for bound disjunction constraints
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
Definition: scip_datastructures.c:669
Definition: objbenders.h:43
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
Definition: prop_symmetry.c:1004
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13788
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
Definition: struct_misc.h:219
static SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
Definition: prop_symmetry.c:7017
Definition: struct_symmetry.h:101
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18538
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
Definition: prop_symmetry.c:543
static SCIP_RETCODE tryAddSymmetryHandlingConss(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
Definition: prop_symmetry.c:6317
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18451
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
static SCIP_RETCODE buildSubgroupGraph(SCIP *scip, SCIP_PROPDATA *propdata, int *genorder, int ntwocycleperms, int compidx, int **graphcomponents, int **graphcompbegins, int **compcolorbegins, int *ngraphcomponents, int *ncompcolors, int **usedperms, int *nusedperms, int usedpermssize, SCIP_Shortbool *permused)
Definition: prop_symmetry.c:3314
Definition: type_result.h:48
Definition: struct_event.h:204
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
Definition: type_var.h:87
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
Definition: type_symmetry.h:59
Definition: type_var.h:71
Definition: type_symmetry.h:60